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