组合数学 (Fall 2015)/Problem Set 4: Difference between revisions
Jump to navigation
Jump to search
imported>Etone No edit summary |
imported>Etone |
||
| Line 1: | Line 1: | ||
==Problem 1== | ==Problem 1== | ||
Prove the following independent set version of the Turan theorem: | 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. <math>G</math> must have an independent set <math>S</math> of size | *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, without using the Turan theorem. | #Prove the theorem directly by the probabilistic method, without using the Turan theorem. | ||
Revision as of 11:51, 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 [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 by the probabilistic method, without using the Turan theorem.