Combinatorics (Fall 2010)/Extremal set theory II: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop No edit summary |
||
Line 1: | Line 1: | ||
== Blocking sets == | |||
=== Duality === | |||
=== Block sensitivity and certificates === | |||
== The switching lemma == | |||
== Hypergraph coloring == | == Hypergraph coloring == | ||
Revision as of 06:11, 18 October 2010
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.