组合数学 (Spring 2014)/Problem Set 3

Problem 1

(Erdős-Lovász 1975)

Let [math]\displaystyle{ \mathcal{H}\subseteq{V\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform [math]\displaystyle{ k }[/math]-regular hypergraph, so that for each [math]\displaystyle{ v\in V }[/math] there are exact [math]\displaystyle{ k }[/math] many [math]\displaystyle{ S\in\mathcal{H} }[/math] having [math]\displaystyle{ v\in S }[/math].

Use the probabilistic method to prove: For [math]\displaystyle{ k\ge 10 }[/math], there is a two coloring [math]\displaystyle{ f:V\rightarrow\{0,1\} }[/math] such that [math]\displaystyle{ \mathcal{H} }[/math] does not contain any monochromatic hyperedge [math]\displaystyle{ S\in\mathcal{H} }[/math].