Abstract
This thesis considers two related structures on finite sets, namely separating systems and covering separating systems. These systems are considered from the point of view of combinatorial designs. Separating systems have been considered by previous authors but this is the first time that covering separating systems have been studied in detail.A separating system on [n] = {1, ... , n} is a collection of subsets of [n], in which for each pair of elements of [n), there exists a set in the collection which contains the first element but not the second or vice versa. A covering separating system on [n] is a separating system on [n] in which each element of [n] occurs at least once. A covering separating system on [n] in which each set has cardinality k is called a (n, k) covering separating system. The size of a (covering) separating system is the number of sets in the collection. The volume of at (covering) separating system is the sum of the cardinalities of the sets in the collection. A minimal (covering) separating system on [n) is one which contains the least possible number of sets.
The size of a minimal separating system has been determined for all n by Renyi. The size of minimal covering separating systems on [n] and bounds or exact values on the size of a minimal (n, k) covering separating system is determined here for all n and k. Various results are derived on the volume of minimal separating systems and minimal covering separating systems on [n], and on the volume of minimal (n, k) covering separating systems.
A catalogue of all non-isomorphic minimal separating systems for n ≤8 and all non-isomorphic minimal covering separating systems for n ≤7 is given. Some conjectures concerning minimal (n, k) covering separating systems are made.
The thesis concludes with a brief mention of the connection between covering separating systems and finite topologies. This provides one possible avenue for applications of the theory of covering separating systems.
| Date of Award | Feb 1999 |
|---|---|
| Original language | English |
| Supervisor | Ian Roberts (Supervisor) & Paulette Lieby (Supervisor) |