组合数学 (Spring 2014)/Problem Set 3

From EtoneWiki
Jump to: navigation, search

注意:这次作业时间只有一周。

Problem 1

(Erdős-Lovász 1975)

Let be a -uniform -regular hypergraph, so that for each there are exact many having .

Use the probabilistic method to prove: For , there is a 2-coloring such that does not contain any monochromatic hyperedge .

Problem 2

(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 3

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 .

Problem 4

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