组合数学 (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 at least [math]\displaystyle{ \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.