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

Problem 1

Recall that [math]\displaystyle{ \chi(G) }[/math] is the chromatic number of graph [math]\displaystyle{ G }[/math].

Prove:

• Any graph [math]\displaystyle{ G }[/math] must have at least [math]\displaystyle{ {\chi(G)\choose 2} }[/math] edges.
• For any two graphs [math]\displaystyle{ G(V,E) }[/math] and [math]\displaystyle{ H(V,F) }[/math]. Prove that [math]\displaystyle{ \chi(G\cup H)\le\chi(G)\chi(H) }[/math].

Problem 2

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