组合数学 (Fall 2016)/Problem Set 4: Difference between revisions
imported>Etone |
imported>Etone No edit summary |
||
| 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 for the independent sets by the probabilistic method along with the Cauchy-Schwartz theorem, without using the Turan theorem. | #Prove the theorem directly for the independent sets by the probabilistic method along with the Cauchy-Schwartz theorem, without using the Turan theorem. | ||
== Problem 2 == | |||
(Matching vs. Star) | |||
Given a graph <math>G(V,E)</math>, a ''matching'' is a subset <math>M\subseteq E</math> of edges such that there are no two edges in <math>M</math> sharing a vertex, and a ''star'' is a subset <math>S\subseteq E</math> of edges such that every pair <math>e_1,e_2\in S</math> of distinct edges in <math>S</math> share the same vertex <math>v</math>. | |||
Prove that any graph <math>G</math> containing more than <math>2(k-1)^2</math> edges either contains a matching of size <math>k</math> or a star of size <math>k</math>. | |||
(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.) | |||
Revision as of 05:41, 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 along with the Cauchy-Schwartz theorem, without using the Turan theorem.
Problem 2
(Matching vs. Star)
Given a graph [math]\displaystyle{ G(V,E) }[/math], a matching is a subset [math]\displaystyle{ M\subseteq E }[/math] of edges such that there are no two edges in [math]\displaystyle{ M }[/math] sharing a vertex, and a star is a subset [math]\displaystyle{ S\subseteq E }[/math] of edges such that every pair [math]\displaystyle{ e_1,e_2\in S }[/math] of distinct edges in [math]\displaystyle{ S }[/math] share the same vertex [math]\displaystyle{ v }[/math].
Prove that any graph [math]\displaystyle{ G }[/math] containing more than [math]\displaystyle{ 2(k-1)^2 }[/math] edges either contains a matching of size [math]\displaystyle{ k }[/math] or a star of size [math]\displaystyle{ k }[/math].
(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)