组合数学 (Fall 2015)/Problem Set 4

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 an [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.

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.)