组合数学 (Fall 2015)/Problem Set 4: Difference between revisions
imported>Etone No edit summary |
imported>Etone |
||
| (6 intermediate revisions by the same user not shown) | |||
| 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 | #Prove the theorem directly by the probabilistic method, without using the Turan theorem. | ||
# (optional) Try to explain when does the equality hold. | |||
== 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.) | |||
==Problem 3 == | |||
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be '''transitive''', if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>. | |||
Show that for any <math>k\ge 3</math>, there exists a finite <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players. Express <math>N(k)</math> in terms of Ramsey number. | |||
== Problem 4 == | |||
Let <math>G(U,V,E)</math> be a bipartite graph. Let <math>\delta_U</math> be the '''minimum''' degree of vertices in <math>U</math>, and <math>\Delta_V</math> be the maximum degree of vertices in <math>V</math>. | |||
Show that if <math>\delta_U\ge \Delta_V</math>, then there must be a matching in <math>G</math> such that all vertices in <math>U</math> are matched. | |||
== Problem 5 == | |||
Prove the following statement: | |||
* For any <math>n</math> distinct finite sets <math>S_1,S_2,\ldots,S_n</math>, there always is a collection <math>\mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\}</math> such that <math>|\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor</math> and for any different <math>A,B,C\in\mathcal{F}</math> we have <math>A\cup B\neq C</math>. | |||
(Hint: use Dilworth theorem.) | |||
Latest revision as of 11:58, 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.
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.)
Problem 3
An [math]\displaystyle{ n }[/math]-player tournament (竞赛图) [math]\displaystyle{ T([n],E) }[/math] is said to be transitive, if there exists a permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math] such that [math]\displaystyle{ \pi_i\lt \pi_j }[/math] for every [math]\displaystyle{ (i,j)\in E }[/math].
Show that for any [math]\displaystyle{ k\ge 3 }[/math], there exists a finite [math]\displaystyle{ N(k) }[/math] such that every tournament of [math]\displaystyle{ n\ge N(k) }[/math] players contains a transitive sub-tournament of [math]\displaystyle{ k }[/math] players. Express [math]\displaystyle{ N(k) }[/math] in terms of Ramsey number.
Problem 4
Let [math]\displaystyle{ G(U,V,E) }[/math] be a bipartite graph. Let [math]\displaystyle{ \delta_U }[/math] be the minimum degree of vertices in [math]\displaystyle{ U }[/math], and [math]\displaystyle{ \Delta_V }[/math] be the maximum degree of vertices in [math]\displaystyle{ V }[/math].
Show that if [math]\displaystyle{ \delta_U\ge \Delta_V }[/math], then there must be a matching in [math]\displaystyle{ G }[/math] such that all vertices in [math]\displaystyle{ U }[/math] are matched.
Problem 5
Prove the following statement:
- For any [math]\displaystyle{ n }[/math] distinct finite sets [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math], there always is a collection [math]\displaystyle{ \mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\} }[/math] such that [math]\displaystyle{ |\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor }[/math] and for any different [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math] we have [math]\displaystyle{ A\cup B\neq C }[/math].
(Hint: use Dilworth theorem.)