Search

Here R(n, k) denotes the minimum possible size of a completely separating system C on [n] with |A| = k for each A ∈ C. Values of R(n, k) are determined for k−1 2 ≤ n < k 2 or 11 ≤ n ≤ 12. Using the dual interpretation of completely separating systems as antichains, this paper provides corresponding results for dual k-regular antichains.

Let n⩾4 be a natural number, and let K be a set K⊆[n]:={1,2,…,n} . We study the problem of finding the smallest possible size of a maximal family A of subsets of [n] such that A contains only sets whose size is in K , and A⊈B for all {A,B}⊆A , i.e. A is an antichain. We present a general construction of such antichains for sets K containing 2, but not 1. If 3∈K our construction asymptotically yields the smallest possible size of such a family, up to an o(n 2 ) error. We conjecture our construction to be asymptotically optimal also for 3∉K , and we prove a weaker bound for the case K={2,4} . Our asymptotic results are straightforward applications of the graph removal lemma to an equivalent reformulation of the problem in extremal graph theory, which is interesting in its own right.

It is proved that, for any positive integer m, the weight of the union-closure of any m distinct 2-sets is at least as large as the weight of the union-closure of the first m 2-sets in squashed (antilexicographic) order, where all i-sets have the same non-negative weight wi with wi ≤ wi+1 for all i, and the weight of a family of sets is the sum of the weights of its members. As special cases, solutions are obtained for the problems of minimising size and volume of the union-closure of a given number of distinct 2-sets.

An (n)completely separating system C ((n)CSS) is a collection of blocks of [n] = {1,..., n} such that for all distinct a, b ∈ [n] there are blocks A, B ∈C with a ∈ A \ B and b ∈ B \ A. An (n)CSS is minimal if it contains the minimum possible number of blocks for a CSS on [n]. The number of non-isomorphic minimal (n)CSSs is determined for 11 ≤ n ≤ 35. This also provides an enumeration of a natural class of antichains.

A collection A of finite sets is closed under union if A, B ∈ A implies that A ∪ B ∈ A. The Union-Closed Sets Conjecture states that if A is a union-closed collection of sets, containing at least one non-empty set, then there is an element which belongs to at least half of the sets in A. We show that if q is the minimum cardinality of ∪A taken over allcounterexamples A, then any counterexample A has cardinality at least 4q − 1.

A Covering Separating System on a set X is a collection of blocks in which each element of X appears at least once, and for each pair of distinct points a, b ∈ X, there is a block containing a and not b, or vice versa.An introduction to Covering Separating Systems is given, constructions are described for a class of minimal Covering Separating Systems and an application to Search Theory is presented.

The minimum number of blocks having maximum size precisely four that are required to cover, exactly times, all pairs of elements from a set of cardinality v is denoted by g(4) (v) (or g(4)(v) when = 1). All values of g(4) (v) are known except for = 1 and v = 17 or 18. It is known that 30 g(4)(17) 31 and 32 g(4)(18) 33. In this paper we show that g(4)(17) 6= 30 and g(4)(18) 6= 32, thus finalising the determination of g(4) (v) for all and v.

An (n)Completely Separating System C is a collection of subsets of n] = {l, , n} such that for all distinct a, b E n] there are subsets A, B E C with a  E A - B and b E B - A R(n, k) denotes the minimum possible size of a completely separating system C on n] with /A/ = k for each A E C Exact values of R(n, k) are known for k ::: 6 and  for some other values of n and k Upper and lower bounds are known in all other cases R(n, k) is  fully determined here for 7 ::: k ::: l0 and general results are provided to aid in determining  R(n, k) for larger k in certain cases.

This paper includes a short survey of extremal results and open problems on various types of separating systems and Sperner families, along with a brief introduction to Search Theory. Some questions on applications of separating systems and Sperner families to Search Theory are stated.

This thesis considers three related structures on finite sets and outstanding conjectures on two of them. Several new problems and conjectures are stated.A union-closed collection of sets is a collection of sets which contains the union of each pair of sets in the collection. A completely separating system of sets is a collection of sets in which for each pair of elements of the universal set, there exists a set in the collection which contains the first element but not the second, and another set which contains the second element but not the first. An antichain (Sperner Family) is a collection of distinct sets in which no set is a subset of another set in the collection. The size of an antichain is the number of sets in the collection. The volume of an antichain is the sum of the cardinalities of the sets in the collection. A flat antichain is an antichain in which the difference in cardinality between any two sets in the antichain is at most one.The two outstanding conjectures considered are:The union-closed sets conjecture - In any union-closed collection of non-empty sets there is an element of the universal set in at least half of the sets in the collection;The flat antichain conjecture - Given an antichain with size s and volume V, there is a flat antichain with the same size and volume.Union-closed collections are considered in two ways. Improvements are made to the previously known bounds concerning the minimum size of a counterexample to the union-closed sets conjecture. Results are derived on the minimum size of a union-closed collection generated by a given number of k-sets. An ordering on sets is described, called order R and it is conjectured that choosing a collection of m k-sets in order R will always minimise the size of the union-closed collection generated by m k-sets.Several variants on completely separating systems of sets are considered. A determination is made of the minimum size of such collections, subject to various constraints on the collec