Combinatorics (Fall 2010)/Extremal set theory II: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with '== Hypergraph coloring == {{Theorem|Theorem (Erdős 1963)| :Let <math>\mathcal{F}</math> be a <math>k</math>-uniform. If <math>|\mathcal{F}|<2^{k-1}</math> then <math>\mathcal{F…'
 
imported>WikiSysop
(No difference)

Revision as of 06:07, 18 October 2010

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.