8 Extremal Set theory 8 Extremal Set theory 8.2 Intersecting and non-intersecting sets

8.1 Chains and Antichains in Set systems

A common example of poset is the power-set $2^{S}$ (subsets of a set $S$ ) ordered by inclusion. We now prove some results about this poset in the spirit of Dilworth’s theorem and Mirsky’s lemma. We can also say more about the decomposition of the chains. A chain here is sets $A_{1},\ldots,A_{k}$ such that $A_{1}\subset\ldots A_{k}$ . Let $|S|=n$ . The chain is symmetric (i.e., about $n/2$ ) if $|A_{1}|+|A_{k}|=n$ and $|A_{i+1}|=|A_{i}|+1$ for all $i=1,\ldots,k-1$ . Symmetric chains are maximal if $k=n$ . Maximal chains can be given a bijection with permutations. Given a permutation $x_{1},\ldots,x_{n}$ , we have a maximal chain $A_{i}=\{x_{1},\ldots,x_{i}\},i=1,\ldots,n$ and vice-versa. On the other hand sets of cardinality $k$ form an anti-chain. The cardinality of the anti-chain is $\binom{n}{k}$ . The maximal cardinality anti-chain among these is the middle-level one i.e., sets of cardinality $k=\lfloor n/2\rfloor$ . This anti-chain has cardinality $\binom{n}{\lfloor n/2\rfloor}$ and as will see indicates a lot about the structure of the power-set. We now prove that the middle-level anti-chain is the largest possible.

Theorem 8.3 (Sperner (1928)).

If $A_{1},\ldots,A_{m}$ forms an anti-chain in $2^{[n]}$ then $m\leq\binom{n}{\lfloor n/2\rfloor}$ .

Proof.

(Lubell, 1966) By the bijection with permutations, there are $n!$ maximal chains. Refining the same argument, given a $k$ -set $A$ , there are $k!(n-k)!$ maximal chains that contain $A$ . We will now prove the result via a double-counting argument.

Count the ordered pairs $(A,{\mathcal{C}})$ such that $A=A_{i}$ for some $i$ and ${\mathcal{C}}$ is a maximal chain with $A\in{\mathcal{C}}$ . Since each maximal chain contains at most one element of an antichain, the number of pairs is at most the number of maximal chains which is $n!$ . Let $\alpha_{k}$ be the number of sets $A_{i}$ with cardinality $k$ . Since each $k$ -set is in $k!(n-k)!$ maximal chains, the number of pairs is $\sum_{k}\alpha_{k}k!(n-k)!$ Thus we have that

\sum_{k}\alpha_{k}k!(n-k)!\leq n!

or equivalently,

\sum_{k}\alpha_{k}\binom{n}{k}^{-1}\leq 1

. Since $\binom{n}{k}$ is maximized for $k=\lfloor n/2\rfloor$ and $\sum\alpha_{k}=m$ , we have that

m\binom{n}{\lfloor n/2\rfloor}^{-1}\leq 1.

∎

Lubell used his proof to derive a general theorem which was also discovered independently by Meshalkin (1963) and Yamamoto (1954).

Exercise(A) 8.4.

If ${\mathcal{F}}$ is an anti-chain, then

\sum_{A\in{\mathcal{F}}}\binom{n}{|A|}^{-1}\leq 1.

More can be said about the partition into chains.

Proposition 8.5 (De Bruijn, Tengbergen and Kruyswijk (1952)).

$2^{[n]}$ can be partitioned into $\binom{n}{\lfloor n/2\rfloor}$ mutually disjoint symmetric chains

Proof.

Let $P=2^{[n]}$ be the poset. Consider the middle level sets in $P$ i.e., sets of cardinality $\lfloor n/2\rfloor$ . Since these form an anti-chain, there must be at least $\binom{n}{\lfloor n/2\rfloor}$ chains partitioning $P$ . We will now show existence of one such chain.

The proof of existence if by induction. Suppose $C_{1},\ldots,C_{r}$ is a symmetric partition of $2^{[n-1]}$ then we shall produce a symmetric partition of $2^{[n]}$ into $2r$ sets. Since $r=\binom{n-1}{\lfloor(n-1)/2\rfloor}$ , we can check that for $n$ even,

2r=\frac{\lfloor n/2\rfloor}{n}\binom{n}{\lfloor n/2\rfloor}=\binom{n}{\lfloor n% /2\rfloor},

and hence the proof is complete for $n$ even. Proof for $n$ odd to be completed.

Suppose $C_{i}$ is $A_{1}\subset A_{2}\ldots A_{k}$ then define

C^{\prime}_{i}:A_{1}\subset A_{2}\ldots A_{k}\subset A_{k}\cup\{n\}

and

C^{\prime\prime}_{i}:A_{1}\cup\{n\}\subset A_{2}\cup\{n\}\ldots A_{k-1}\cup\{n\}

It is easy to check that $C^{\prime}_{i}$ and $C_{i}$ preserve the symmetry of $C_{i}$ ’s but now w.r.t $n$ . Suppose $A\in 2^{[n]}$ . If $n\notin A$ , then $A$ belongs to at most one $C^{\prime}_{i}$ . Suppose $A=B\cup\{n\}$ . If $B$ is a maximal element in a chain $C_{i}$ of $Y$ , then $B\in C^{\prime}_{i}$ alone and if not $B\in C^{\prime\prime}_{i}$ alone. Thus $C^{\prime}_{i},C^{\prime\prime}_{i},1\leq i\leq r$ form a partition of $2^{[n]}$ into symmetric chains. ∎