Combinatorics (Fall 2010)/Extremal set theory II

Kruskal–Katona theorem

Theorem (Kruskal 1963, Katona 1966)

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] with [math]\displaystyle{ |\mathcal{F}|=m }[/math], and suppose that [math]\displaystyle{ m={n_k\choose k}+{n_{k-1}\choose k-1}+\cdots+{n_t\choose t} }[/math] where [math]\displaystyle{ a_k\gt a_{k-1}\gt \cdots\gt a_t\ge t\ge 1 }[/math]. Then [math]\displaystyle{ |\Delta\mathcal{F}|\ge {n_k\choose k-1}+{n_{k-1}\choose k-2}+\cdots+{n_t\choose t-1} }[/math].

Hypergraph coloring

Theorem (Erdős 1963)

Let [math]\displaystyle{ \mathcal{F} }[/math] be a [math]\displaystyle{ k }[/math]-uniform. If [math]\displaystyle{ |\mathcal{F}|\lt 2^{k-1} }[/math] then [math]\displaystyle{ \mathcal{F} }[/math] is 2-colorable.

Colorings

Theorem (Erdős-Lovász 1975)

Let [math]\displaystyle{ \mathcal{F} }[/math] be a [math]\displaystyle{ k }[/math]-uniform. If every member of [math]\displaystyle{ \mathcal{F} }[/math] intersects at most [math]\displaystyle{ 2^{k-3} }[/math] other members, then [math]\displaystyle{ \mathcal{F} }[/math] is 2-colorable.