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.
| Identifer | oai:union.ndltd.org:ADTP/253757 |
| Creators | Ramsay, Colin |
| Source Sets | Australiasian Digital Theses Program |
| Detected Language | English |
Page generated in 0.002 seconds