组合数学 (Fall 2016)/Problem Set 4: Difference between revisions
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 |
||
| 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 <math>|S|\ge \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 <math>|S|\ge \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 with Cauchy-Schwartz theorem, without using the Turan theorem. | #Prove the theorem directly for the independent sets by the probabilistic method with Cauchy-Schwartz theorem, without using the Turan theorem. | ||
Revision as of 05:39, 21 November 2016
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].
- Show that this theorem is a corollary to the Turan theorem for cliques.
- Prove the theorem directly for the independent sets by the probabilistic method with Cauchy-Schwartz theorem, without using the Turan theorem.