组合数学 (Fall 2015)/Problem Set 4: Difference between revisions
Jump to navigation
Jump to search
imported>Etone |
imported>Etone |
||
| Line 4: | Line 4: | ||
#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. | ||
# (optional) Try to explain when does the equality hold. | |||
Revision as of 11:53, 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.
- (optional) Try to explain when does the equality hold.