Combinatorics (Fall 2010)/Extremal set theory II

From TCS Wiki
Revision as of 06:11, 18 October 2010 by imported>WikiSysop
Jump to navigation Jump to search

Blocking sets

Duality

Block sensitivity and certificates

The switching lemma

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.

Lovász local lemma

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.