组合数学 (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].

Problem 3

Given a graph [math]\displaystyle{ G(V,E) }[/math], a matching is a subset [math]\displaystyle{ M\subseteq E }[/math] of edges such that there are no two edges in [math]\displaystyle{ M }[/math] sharing a vertex, and a star is a subset [math]\displaystyle{ S\subseteq E }[/math] of edges such that every pair [math]\displaystyle{ e_1,e_2\in S }[/math] of distinct edges in [math]\displaystyle{ S }[/math] share the same vertex [math]\displaystyle{ v }[/math].

Prove that any graph [math]\displaystyle{ G }[/math] containing more than [math]\displaystyle{ 2(k-1)^2 }[/math] edges either contains a matching of size [math]\displaystyle{ k }[/math] or a star of size [math]\displaystyle{ k }[/math].