8 Extremal Set theory 8.1 Chains and Antichains in Set systems 8.3 Fisher’s inequality

8.2 Intersecting and non-intersecting sets

Theorem 8.6 (Erdős-Ko-Rado (1961)).

Let ${\mathcal{A}}=\{A_{1},\ldots,A_{n}\}$ be a collection of $k$ -subsets in $2^{[n]}$ such that $A_{i}\cap A_{j}\neq\emptyset$ for all $i, j$ . Then $m\leq\binom{n-1}{k-1}$

Proof.

Put $1,\ldots,n$ on a circle and consider the set of ${\mathcal{F}}=\{F_{1},\ldots,F_{n}\}$ of all consecutive $k$ -tuples on circle. Say $F_{i}=\{i,\ldots,i+k-1\}$ with $i=i(\text{mod}\,n)$ . If $F_{i}=A_{j}$ then since all other $A_{i}$ ’s intersect $A_{j}$ , then any other $F\in{\mathcal{A}}$ has to be either $F=\{l,\ldots,l+k-1\}$ or $F=\{l-k,\ldots,l-1\}$ but not both and this for $i<l<i+k$ . We can define ${\mathcal{F}}^{\pi}$ similar to ${\mathcal{F}}$ by applying permutation $\pi$ to $[n]$ . So

\Sigma=\sum_{\pi}|A\cap{\mathcal{F}}^{\pi}|\leq kn!.

Now for an exact computation of $\Sigma$ . For a fixed $A_{j}$ and $F_{i}$ , there are $k!(n-k)!$ permutations $\pi$ such that $F_{i}^{\pi}=A_{j}$ . Thus $\Sigma=mnk!(n-k)!$ and so we have that

mnk!(n-k)!\leq kn!,

and so proves the theorem. ∎

We prove a generalization of the theorem using Hall’s theorem for SDR.

Theorem 8.7.

Let ${\mathcal{A}}=\{A_{1},\ldots,A_{n}\}$ be an anti-chain in $2^{[n]}$ and $A_{i}\cap A_{j}\neq\emptyset$ for all $i, j$ . Further, let $|A_{i}|\leq k\leq n/2$ for all $i$ . Then $m\leq\binom{n-1}{k-1}$

Proof.

If all subsets have size $k$ , the theorem is proven.

The proof is now via reduction. Let $A_{1},\ldots,A_{s}$ be subsets of the smallest cardinality $l\leq n/2-1$ . Consider all the $(l+1)$ -subsets $B_{j}$ of $[n]$ that contain at least one of the $A_{i},1\leq i\leq s$ . Clearly none of these is in ${\mathcal{A}}$ as ${\mathcal{A}}$ is an anti-chain. For each $A_{i}$ , there are $n-l$ $B_{j}$ ’s containing it. Each $B_{j}$ can contain at most $l+1$ $A_{i}$ ’s. Define a bi-partite graph between $A_{i}$ ’s and $B_{j}$ ’s using the inclusion and observe that degree of $B_{j}$ ’s are at most $l+1\leq n-l$ , the degree of $A_{i}$ ’s. Thus there is a complete matching on $A_{i}$ ’s i.e., there exist distinct $B_{1},\ldots,B_{s}$ such that $A_{i}\subset B_{i}$ for all $i$ . Now replace $A_{1},\ldots,A_{s}$ in ${\mathcal{A}}$ by $B_{1},\ldots,B_{s}$ and clearly the new collection is an anti-chain and satisfies the assumptions of the theorem and now the subset of smallest cardinality is $>l$ . Recursively, we can make all subsets have cardinality $k$ and $m$ remains unchanged. Then we use the previous theorem. ∎

Exercise(A) 8.8.

Let ${\mathcal{A}}=\{A_{1},\ldots,A_{n}\}$ be an anti-chain of $[n]$ such that $A_{i}\cap A_{j}\neq\emptyset$ for all $i, j$ and $|A_{i}|\leq n/2$ for all $i$ . Then show that

\sum_{i=1}^{m}\binom{n-1}{|A_{i}|-1}^{-1}\leq 1.

Theorem 8.9 (Bollobas (1965)).

Let $A_{1},\ldots,A_{m}$ and $B_{1},\ldots,B_{m}$ be two sequences of subsets of $[n]$ such that $A_{i}\cap B_{j}=\emptyset$ iff $i=j$ . Then setting $a_{i}=|A_{i}|,b_{i}=|B_{i}|$ , we have that

\sum_{i}\binom{a_{i}+b_{i}}{a_{i}}^{-1}\leq 1.

A special case when $a_{i}\equiv a,b_{i}\equiv b$ is that $m\leq\binom{a+b}{a}$ .

Exercise(A) 8.10.

Prove the inequality in Exercise 8.4 using the above theorem.

Exercise(A) 8.11.

Show that the bound in Theorem 8.9 is tight.

Proof of Theorem 8.9.

The proof is a variant of Lubell’s proof for Sperner’s theorem. A permutation $\sigma=(\sigma_{1},\ldots,\sigma_{n})$ separates a pair $(A,B)$ if $\sigma_{k}\in A,\sigma_{l}\in B$ implies that $k<l$ i.e., elements of $\sigma\in A$ occur before elements of $\sigma\in B$ .

Let $D$ be the number of pairs $\sigma,(A_{i},B_{i})$ such that $\sigma$ separates $(A_{i},B_{i})$ . Each $\sigma$ can seperate at most one pair. Suppose $\sigma$ seperates $(A_{i},B_{i})$ and $(A_{j},B_{j})$ . WLOG $k_{i}\leq k_{j}$ be the maximal indices in $A_{i},A_{j}$ and $l_{j}$ be the minimal index in $B_{j}$ . Then we have that $k_{i}\leq k_{j}<l_{j}$ which implies that $A_{i}\cap B_{j}=\emptyset$ , thus a contradiction. So $D\leq n!$ .

Fix $(A_{i},B_{i})$ . The number of permutations $\sigma$ that seperate $A_{i},B_{i}$ are $\binom{n}{a_{i}+b+i}(n-a_{i}-b_{i})!a_{i}!b_{i}!$ . This is argued as follows : $\binom{n}{a_{i}+b+i}$ counts the number of ways to place $A_{i}\cup B_{i}$ in $n$ places and then the rest of the factors account for permutations of the elements in those places. Thus

D=\sum_{i=1}^{m}n!\binom{a_{i}+b_{i}}{a_{i}}^{-1},

and combining with the bound $D\leq n!$ gives the result. ∎