Date of Award

1-1-2013

Document Type

Open Access Dissertation

Department

Mathematics

First Advisor

Jerrold Griggs

Abstract

Sperner's Theorem is a well known theorem in extremal set theory that gives the size of the largest antichain in the poset that is the Boolean lattice. This is equivalent to finding the largest family of subsets of an $n$-set, $[n]:=\{1,2,\dots,n\}$, such that the family is constructed from pairwise unrelated copies of the single element poset. For a poset $P$, we are interested in maximizing the size of a family $\mathcal{F}$ of subsets of $[n]$, where each maximally connected component of $\mathcal{F}$ is a copy of $P$, and finding the extreme configurations that achieve this value. For instance, Sperner showed that when $P$ is one element, $\dbinom{n}{\lfloor \frac{n}{2}\rfloor}$ is the maximum number of copies of $P$ and that this is only achieved by taking subsets of a middle size. Griggs, Stahl, and Trotter have shown that when $P$ is a chain on $k$ elements, $\dfrac{1}{2^{k-1}}\dbinom{n}{\lfloor \frac{n}{2}\rfloor}$ is asymptotically the maximum number of copies of $P$. We find the extreme families for a packing of chains, answering a conjecture of Griggs, Stahl, and Trotter, as well as finding the extreme packings of certain other posets. For the general poset $P$, we prove that the maximum number of unrelated copies of $P$ is asymptotic to a constant times $\dbinom{n}{\lfloor \frac{n}{2}\rfloor}$. Moreover, the constant has the form $\dfrac{1}{c(P)}$, where $c(P)$ is the size of the smallest convex closure over all embeddings of $P$ into the Boolean lattice. Sperner's Theorem has been generalized by looking for $\operatorname{La}(n,P)$, the size of a largest family of subsets of an $n$-set that does not contain a general poset $P$ in the family. We look at this generalization, exploring different techniques for finding an upper bound on $\operatorname{La}(n,P)$, where $P$ is the diamond. We also find all the families that achieve $\operatorname{La}(n,\{\mathcal{V},\Lambda\})$, the size of the largest family of subsets that do not contain either of the posets $\mathcal{V}$ or $\Lambda$. We also consider another generalization of Sperner's theorem, supersaturation, where we find how many copies of $P$ are in a family of a fixed size larger than $\operatorname{La}(n,P)$. We seek families of subsets of an $n$-set of given size that contain the fewest $k$-chains. Erd\H{o}s showed that a largest $k$-chain-free family in the Boolean lattice is formed by taking all subsets of the $(k-1)$ middle sizes. Our result implies that by taking this family together with $x$ subsets of the $k$-th middle size, we obtain a family with the minimum number of $k$-chains, over all families of this size. We prove our result using the symmetric chain decomposition method of de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk (1951).

Rights

© 2013, Andrew Philip Dove

Download

Included in

Mathematics Commons

Share

COinS