Trades and Defining Sets: Theoretical and Computational Results

Ramsay, Colin (1998). Trades and Defining Sets: Theoretical and Computational Results PhD Thesis, Information Technology and Electrical Engineering, University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
n01front.pdf n01front.pdf application/pdf 119.97KB 0
n02chapter1.pdf n02chapter1.pdf application/pdf 137.59KB 0
n03chapter2.pdf n03chapter2.pdf application/pdf 182.24KB 0
n04chapter3.pdf n04chapter3.pdf application/pdf 223.37KB 0
n05chapter4.pdf n05chapter4.pdf application/pdf 237.93KB 0
n06chapter5.pdf n06chapter5.pdf application/pdf 128.77KB 0
n07chapter6.pdf n07chapter6.pdf application/pdf 132.59KB 0
n08chapter7.pdf n08chapter7.pdf application/pdf 115.16KB 0
n09chapter8.pdf n09chapter8.pdf application/pdf 154.55KB 0
n10chapter9.pdf n10chapter9.pdf application/pdf 113.15KB 0
n11chapter10.pdf n11chapter10.pdf application/pdf 214.48KB 0
n12chapter11.pdf n12chapter11.pdf application/pdf 144.75KB 0
n13appendixa.pdf n13appendixa.pdf application/pdf 127.62KB 0
n14appendixb.pdf n14appendixb.pdf application/pdf 52.15KB 0
n15appendixc.pdf n15appendixc.pdf application/pdf 136.97KB 0
n16appendixd.pdf n16appendixd.pdf application/pdf 87.85KB 0
n17appendixe.pdf n17appendixe.pdf application/pdf 80.78KB 0
n18appendixf.pdf n18appendixf.pdf application/pdf 48.44KB 0
n19appendixg.pdf n19appendixg.pdf application/pdf 79.81KB 0
n20references.pdf n20references.pdf application/pdf 86.79KB 0
Author Ramsay, Colin
Thesis Title Trades and Defining Sets: Theoretical and Computational Results
School, Centre or Institute Information Technology and Electrical Engineering
Institution University of Queensland
Publication date 1998
Thesis type PhD Thesis
Supervisor George Havas and Anne P Street
Abstract/Summary Given a particular combinatorial structure, there may be many distinct objects having this structure. When investigating these, two natural questions to ask are: - Given two objects, where and how do they differ? - How much of an individual object is necessary to uniquely identify it? These two questions are obviously related, with the first leading to the concept of a trade, and the second to that of a defining set. In this thesis we study trades and defining sets, in the context of t-(v,k,lambda) designs. In our enquiries, we make use of both theoretical and computational techniques. We investigate the spectrum of trades, and prove an extant conjecture regarding this. Our results also suggest a more general version of this conjecture. A t-(v,k,lambda) design where lambda=1 is called a Steiner design, and the related trades are called Steiner trades. In the case t=2, we establish the spectrum of Steiner trades for each value of k, except for a finite number of values in each case. The connection between trades and defining sets is used to obtain some new theoretical results on defining sets of designs, and is exploited throughout the thesis. We also consider the collections of all trades and all defining sets in a design. A simple design is one which is a set, as opposed to a multiset. We present an algorithm to enumerate all the trades in simple designs. For non-simple designs we introduce the concept of a discriminating set, and present an algorithm to enumerate these. Output from these algorithms was used to investigate the trades and defining sets of a number of designs, and some new results were obtained. Given part of a design, its completions are all those designs that contain it. An existing algorithm to complete partial designs is examined, and a heuristic yielding a much improved algorithm for Steiner designs is discussed. This completion routine was used to investigate a number of designs, and new information on the size and distribution of their defining sets was obtained.
Keyword defining set

Citation counts: Google Scholar Search Google Scholar
Created: Fri, 21 Nov 2008, 17:52:01 EST