30 Three famous theorems on finite sets

Theorem 30.1

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

Proof ▶

Lemma 30.2

Let $n \geq 2 k$ , 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 \leq k$ .

Proof ▶

Theorem 30.3

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

Proof ▶

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 \leq m \leq n$ .

Proof ▶