组合数学 (Fall 2015)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "=Problem 1= Prove the following independent set version of the Turan theorem: *Let <math>G(V,E)</math> be a graph of <math>n=|V|</math> vertices and <math>m=|E|</math> edges. ..."
 
imported>Etone
No edit summary
Line 3: Line 3:
*Let <math>G(V,E)</math> be a graph of <math>n=|V|</math> vertices and <math>m=|E|</math> edges. <math>G</math> must have an independent set <math>S</math> of size at least <math>\frac{n^2}{2m+n}</math>.
*Let <math>G(V,E)</math> be a graph of <math>n=|V|</math> vertices and <math>m=|E|</math> edges. <math>G</math> must have an independent set <math>S</math> of size at least <math>\frac{n^2}{2m+n}</math>.
#Show that this theorem is a corollary to the Turan theorem for cliques.
#Show that this theorem is a corollary to the Turan theorem for cliques.
#Prove the theorem directly by the probabilistic method, without using the Turan theorem.
#Prove the theorem directly by using the probabilistic method, without using the Turan theorem.

Revision as of 11:43, 15 December 2015

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 using the probabilistic method, without using the Turan theorem.