组合数学 (Fall 2015)/Problem Set 4

Problem 1

Prove the following independent set version of the Turan theorem:

• Let [math]\displaystyle{ G(V,E) }[/math] be a graph of [math]\displaystyle{ n=|V| }[/math] vertices and [math]\displaystyle{ m=|E| }[/math] edges. [math]\displaystyle{ G }[/math] must have an independent set [math]\displaystyle{ S }[/math] of size [math]\displaystyle{ |S|\ge \frac{n^2}{2m+n} }[/math].

1. Show that this theorem is a corollary to the Turan theorem for cliques.
2. Prove the theorem directly by the probabilistic method, without using the Turan theorem.
3. (optional) Try to explain when does the equality hold.

Problem 2

(Matching vs. Star)

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

(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)