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 for the independent sets by the probabilistic method along with the Cauchy-Schwartz theorem, without using the Turan theorem.
(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.)
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 .
Let and let be a -uniform family such that for all . Show that .