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