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

## Contents |

## Problem 1

Prove the following independent set version of the Turan theorem:

- Let
*G*(*V*,*E*) be a graph of*n*= |*V*| vertices and*m*= |*E*| edges.*G*must have an independent set*S*of size .

- 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 *G*(*V*,*E*), a *matching* is a subset of edges such that there are no two edges in *M* sharing a vertex, and a *star* is a subset of edges such that every pair of distinct edges in *S* share the same vertex *v*.

Prove that any graph *G* containing more than 2(*k* − 1)^{2} edges either contains a matching of size *k* or a star of size *k*.

(Hint: Learn from the proof of Erdos-Rado's sunflower lemma.)

## Problem 3

An *n*-player tournament (竞赛图) *T*([*n*],*E*) is said to be **transitive**, if there exists a permutation π of [*n*] such that π_{i} < π_{j} for every .

Show that for any , there exists a finite *N*(*k*) such that every tournament of players contains a transitive sub-tournament of *k* players. Express *N*(*k*) in terms of Ramsey number.

## Problem 4

Let *G*(*U*,*V*,*E*) be a bipartite graph. Let δ_{U} be the **minimum** degree of vertices in *U*, and Δ_{V} be the maximum degree of vertices in *V*.

Show that if , then there must be a matching in *G* such that all vertices in *U* are matched.

## Problem 5

Prove the following statement:

- For any
*n*distinct finite sets , there always is a collection such that and for any different we have .

(Hint: use Dilworth theorem.)