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

From EtoneWiki
Jump to: navigation, search

Problem 1

Prove the following independent set version of the Turan theorem:

  • Let be a graph of vertices and edges. must have an independent set of size .
  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 , a matching is a subset of edges such that there are no two edges in sharing a vertex, and a star is a subset of edges such that every pair of distinct edges in share the same vertex .

Prove that any graph containing more than edges either contains a matching of size or a star of size .

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

Problem 3

An -player tournament (竞赛图) is said to be transitive, if there exists a permutation of such that for every .

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

Problem 4

Let be a bipartite graph. Let be the minimum degree of vertices in , and be the maximum degree of vertices in .

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

Problem 5

Prove the following statement:

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

(Hint: use Dilworth theorem.)