组合数学 (Fall 2015)/Problem Set 4
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 .
- 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.
(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.)
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.
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.
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.)