组合数学 (Fall 2015)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
 
(4 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 at least <math>\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, 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.
== 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].
  1. Show that this theorem is a corollary to the Turan theorem for cliques.
  2. Prove the theorem directly by the probabilistic method, without using the Turan theorem.
  3. (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.)