Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Extremal problems in finite sets

Lieby, Paulette (1999). Extremal problems in finite sets. PhD Thesis, Northern Territory University.

Document type: Thesis
Citation counts: Google Scholar Search Google Scholar
Attached Files (Some files may be inaccessible until you login with your CDU eSpace credentials)
Name Description MIMEType Size Downloads
Download this reading Thesis_CDU_6305_Lieby_P.pdf PDF version generated by student application/pdf 1.20MB 198
Reading the attached file works best in Firefox, Chrome and IE 9 or later.

Author Lieby, Paulette
Title Extremal problems in finite sets
Institution Northern Territory University
Publication Date 1999
Thesis Type PhD
Subjects 0101 - Pure Mathematics
Abstract The main concern of this thesis is the study of problems involving collections of subsets of a finite set [n] = {1,2,...,n} and especially antichains on [n]. An antichain is a collection of sets in which no two sets are comparable under set inclusion. An antichain A is flat if there exists an integer k ≥ 0 such that every set in A has cardinality either k or k + 1. The size of A is |A| and the volume of A is ∑A∈A |A|. A unifying problem in the thesis is the flat antichain conjecture which states that A is an antichain on [n] if and only if there exists a flat antichain on [n] with the same size and volume as A. The truth of the conjecture would provide a simple test for the existence of antichains on [n] with a given size and volume. The flat antichain conjecture is known to hold in several special cases. This thesis shows that it holds in several further cases. Two main approaches have been taken in the investigation of the flat antichain conjecture. The first approach consists of studying the volumes of antichains. Building on earlier work of Clements we observe that for given n and s, the antichains on [n] of size s which achieve minimum (maximum) volume are flat antichains, where the minimum (maximum) is taken over all antichains on [n] of size s. Further, we show that if A is an antichain on [n] then there exists a flat antichain on [n] with the same volume as A. In proving this last result we prove that the flat antichain conjecture holds in one special case. The second approach involves counting the number of subsets and supersets of certain collections of sets as defined below. The squashed (or colex) order on sets is a set ordering with the property that the number of subsets of a collection of k-sets is minimised when the collection consists of an initial segment of k-sets in squashed order. In the universal set [n], consider the collections Lk+1(p) and Lk-1(p) consisting of the last p (k + 1)-sets in squashed order and the last p (k - 1)-sets in squashed order respectively. Let a1 be the number of supersets of size k of the sets in Lk-1(p). Let a2 be the number of subsets of size k of the sets in Lk+1(p) which are not subsets of any (k + 1)-set preceding the sets in Lk+1(p) in squashed order. We show that a1 + a2 > 2p. This result, called the 3-levels result, enables us to show that the flat antichain conjecture holds in several cases. Several conjectures and open problems which are related to the 3-levels result are stated and implications of the truth of the flat antichain conjecture are considered.


© copyright

Every reasonable effort has been made to ensure that permission has been obtained for items included in CDU eSpace. If you believe that your rights have been infringed by this repository, please contact digitisation@cdu.edu.au.

 
Versions
Version Filter Type
Access Statistics: 97 Abstract Views, 199 File Downloads  -  Detailed Statistics
Created: Thu, 18 Sep 2008, 09:44:41 CST