Homework 3

Deadline: Oct. 21, 22:00:00

1. Given two graphs $G = (V, E)$ and $H = (W, F)$, where $|V| = n > |W|$ and $|E| = m$, suppose that $G$ does not contain $H$ as a subgraph. Show that for $k > n^2 \ln n/m$, there is an edge$k$-coloring for $K_n$ such that $K_n$ contains no monochromatic $H$.

2. Prove that every $3$-uniform hypergraph with $n$ vertices and $m \ge n /3$ edges contains an independent set (i.e., a set of vertices containing no edges) of size at least $2n^{3/2}/(3\sqrt{3m})$.

3. [Spencer 1990] Let $H$ be a $r$-uniform hypergraph. Suppose that, in average, each vertex belongs to $d$ edges. Show that there exists an independent set of size at least $(1-1/r)\cdot n \cdot d^{-1/(r-1)}$.

   Remark: Note that $d=r\cdot m/n$. When $r = 2$, this result is exactly the same as Problem $2$.

4. [Alon 1986] An edge clique covering of a graph is a family of complete subgraphs of $G$ such that every edge in $G$ 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 $cc(G)$. Let $G$ be a graph on $n$ vertices such that every vertex has degree at least $n-1-d$. Show that $cc(G) = O(d^2\ln n)$.

   Hint: (probably will be given next week)

5. Let $G$ be a bipartite graph with $n$ vertices on each side. Suppose that the minimum degree of vertices is $n-d$. Show that the edges of $G$ can be covered by at most $O(d\ln n)$ complete bipartite subgraphs.

6. [Zarankiewicz’s problem; Erdős--Spencer 1974] At most how many $1$’s can a $n\times n$ $0$-$1$ matrix contain if it has no $a\times a$ submatrix whose entries are all $1$’s? Let $k_a(n)$ denote the maximum number of $1$'s in such a matrix. Show that for every $a\geq 2$ there exists $\varepsilon > 0$ such that $k_a(n) \geq \varepsilon n^{2-2/a}$.

   (Bonus) Show that $k_2(n) \geq (1-o(1))n^{3/2}$.