Homework 3

Deadline: Oct. 21, 22:00:00
  1. Given two graphs and , where and , suppose that does not contain as a subgraph. Show that for , there is an edge-coloring for such that contains no monochromatic .

  2. Prove that every -uniform hypergraph with vertices and edges contains an independent set (i.e., a set of vertices containing no edges) of size at least .

  3. [Spencer 1990] Let be a -uniform hypergraph. Suppose that, in average, each vertex belongs to edges. Show that there exists an independent set of size at least .

    Remark: Note that . When , this result is exactly the same as Problem .

  4. [Alon 1986] An edge clique covering of a graph is a family of complete subgraphs of such that every edge in belongs to at least one subgraph in the family. The minimum size of such a family is called the edge clique covering number, denoted by . Let be a graph on vertices such that every vertex has degree at least . Show that .

    Hint: (probably will be given next week)

  5. Let be a bipartite graph with vertices on each side. Suppose that the minimum degree of vertices is . Show that the edges of can be covered by at most complete bipartite subgraphs.

  6. [Zarankiewicz’s problem; Erdős--Spencer 1974] At most how many ’s can a - matrix contain if it has no submatrix whose entries are all ’s? Let denote the maximum number of 's in such a matrix. Show that for every there exists such that .

    (Bonus) Show that .