Abstract
The focus of this thesis is linear orderings on collections of subsets of an n-set, and their contribution to the solutions of various minimisation problems. Three distinct areas are considered.The shadow of a collection of k-subsets of an n-set consists of all of the (k - 1)-subsets of the k-sets in the collection. Likewise, the shade of a collection of k-subsets of an n-set consists of all the (k + 1)-subsets of the k-sets in the collection. The shadow minimisation problem is the problem of finding all collections of rn k-subsets of an n-set such that the collection has a minimum sized shadow amongst all such collections. The shade minimisation counterpart to this problem is that of finding all collections of m k-subsets of an n-set such that the collection has a minimum sized shade amongst all such collections. The Kruskal-Katona Theorem is discussed as a solution to the former problem, and a corollary of the theorem provides a solution to the latter. Solutions to both problems in relation to new-shadows and new-shades are also presented, and consideration of the theory of Macaulay posets provides a context for the shadow minimisation problem in terms of other posets.
The Flat Antichain Theorem and squashed antichains are considered. The proof of the Flat Antichain Theorem for antichains containing sets of no more than three consecutive sizes emphasises the interrelationship of the theorem and squashed antichains. An associated minimisation problem is that of finding the minimum number of different sizes of sets over all of the collections of antichains of a given size and volume.
Finally, the complementary problems of union-closure and intersection-closure minimisation are discussed. These problems are concerned with minimising the union-closure and intersection-closure generated by a collection of m k-subsets of an n-set. Both problems are currently open, but new results due to Roberts have given rise to conjectured solutions to both. This part of the thesis provides a summary of some of these results, establishes a relationship between the two problems, and presents some new results relating to intersection-closed collections.
| Date of Award | Mar 2001 |
|---|---|
| Original language | English |
| Supervisor | Ian Roberts (Supervisor) |