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.
|