组合数学 (Fall 2017)/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 for the independent sets by the probabilistic method along with the Cauchy-Schwartz theorem, without using the Turan theorem.

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

(Frankl 1986)

Let be a -uniform family, and suppose that it satisfies that for any .

  • Fix any . Show that the family is an anti chain.
  • Show that .

Problem 4

Let and let be a -uniform family such that for all . Show that .

Problem 5

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.