30 Three famous theorems on finite sets

Theorem 30.1

The size of a largest antichain of an \(n\)-set is \(\binom {n}{\lfloor n/2\rfloor }\).

Proof ▶

TODO

Lemma 30.2

Let \(n \ge 2k\), and suppose we are given \(t\) distinct arcs \(A_1, \dots A_t\) of length \(k\), such that any two arcs have an edge in common. Then \(t \le k\).

Proof ▶

TODO

Theorem 30.3

The largest size of an intersection \(k\)-family in an \(n\)-set is \(\binom {n - 1}{k - 1}\).

Proof ▶

TODO

Theorem 30.4 Marriage theorem

Let \(A_1, \dots A_n\) be a collection of subset of a finite set \(X\). Then there exists a system of distinct representatives if and only if the union of any \(m\) sets \(A_i\) contains at least \(m\) elements, for \(1 \le m \le n\).

Proof ▶

TODO