9. Extremal set theory

How large or how small a collection of finite objects can be, if it has to satisfy certain restrictions

Sunflower

set system $\mathcal{F}\subset 2^{[n]}$ with ground set $[n]$
a sunflower of size $r$ $r$ with center $C$ $C$
- $|\mathcal{F}|=r$
- $\forall S,T\in\mathcal{F},S\cap T=C$
Sunflower Lemma (Erdős-Rado 1960)
- $\mathcal{F}\subset{[n]\choose k},|\mathcal{F}|>k!(r-1)^k\Rightarrow\exists$ a sunflower $\mathcal{G}\subset\mathcal{F}$ such that $|\mathcal{G}|=r$
Sunflower Conjecture: $|\mathcal{F}|>c(r)^k$

Erdős-Ko-Rado Theorem: $\mathcal{F}\subset{[n]\choose k},n\geq 2k,\forall S,T\in\mathcal{F},S\cap T\neq\emptyset\Rightarrow|\mathcal{F}|\leq{n-1\choose k-1}$ $F \subset (k [ n ]), n \geq 2 k, \forall S, T \in F, S \cap T \neq = \emptyset \Rightarrow ∣ F ∣ \leq (k - 1 n - 1)$
- Katona's proof: double counting
- Erdős' proof: shifting
Shifting(Compression)
- Define a shift operator
  - perserve desired property
  - original problem is easy on shifted elements
- e.g. Isoperimetric problem: Steiner symmetrization

Antichains: $\forall A,B\in\mathcal{F},A\not\subseteq B,{[n]\choose k}$ is an antichain
Sperner's Theorem(1928): $\mathcal{F}\subseteq 2^{[n]}$ $F \subseteq 2^{[n]}$ is an antichain, $|\mathcal{F}|\leq {n\choose\lfloor n/2\rfloor}$ $∣ F ∣ \leq (⌊ n /2 ⌋ n)$
- Sperner's proof(shadows)
- LYM inequality: $\mathcal{F}\subseteq 2^{[n]}$ $F \subseteq 2^{[n]}$ is an antichain, $\sum_{S\in\mathcal{F}}\frac{1}{n\choose|S|}\leq 1$ $\sum_{S \in F} \frac{1}{( ∣ S ∣ n )} \leq 1$
  - Lubell's proof(counting)
  - Alon's proof(probabilistic)

trace: $\mathcal{F}\subseteq 2^X,R\subseteq X$ , the trace of $\mathcal{F}$ on $R$ is $\mathcal{F}|_R=\{S\cap R|S\in \mathcal{F}\}$
$\mathcal{F}$ $F$ shatters $R$ $R$ if $\mathcal{F}|_R=2^R$ $F ∣_{R} = 2^{R}$
- $\forall T\subseteq R,\exists S\in\mathcal{F},T=S\cap R$
VC-dimesion(Vapnik–Chervonenkis dimension) of a set family $\mathcal{F}\subseteq 2^{[n]}$ : $\text{VC-dim}(\mathcal{F})=\max\{|R||R\subseteq [n],\mathcal{F}|_R=2^R\}$
Sauer's Lemma: Let $\mathcal{F}\subseteq 2^X,|X|=n$ $F \subseteq 2^{X}, ∣ X ∣ = n$ . If $|\mathcal{F}|>\sum_{1\leq i<k}{n\choose i}$ $∣ F ∣ > \sum_{1 \leq i < k} (i n)$ then $\exists R\in{X\choose k}$ $\exists R \in (k X)$ , $F$ $F$ shatters $R$ $R$
- $|\mathcal{F}|>\sum_{1\leq i<k}{n\choose i}$ then $\text{VC-dim}(\mathcal{F})\geq k$
hereditary(ideal, abstract simplicial): $S\subseteq T\in\mathcal{F}\Rightarrow S\in\mathcal{F}$ $S \subseteq T \in F \Rightarrow S \in F$
- $R\in\mathcal{F},\mathcal{F}$ shatters $R$
down-shift $S_i$ : $S_i(T)=T\backslash\{i\}$ if $i\in T$ and $T\backslash\{i\}\not\in\mathcal{F}$ , $T$ otherwise