Homework 5

Deadline: Nov. 4, 22:00:00

1. Show that there is a finite $n_0$ such that any directed graph on $n > n_0$ vertices in which each outdegree is at least $\log_2 n − \frac{1}{10}\log_2 \log_2 n$ contains an even simple directed cycle.

2. Show that the property "no isolated vertices" for $\mathcal{G}(n, p)$ has a sharp threshold function $p = \ln n/n$.

3. Consider a random bipartite graph $G\sim \mathcal{G}(n, n, p)$. We claim that the property "$G$ has a perfect matching" has a sharp threshold function $p = \ln n/n$. We prove this conclusion as follows.

   • Show that for any $\delta > 0$, if $p < (1-\delta) \ln n /n$ then $G$ does not have a perfect matching.

   • Show that if $G$ does not have a perfect matching, then there exists a set $S$ such that (i) $|S| = |N(S)|+1$, where $N(S)$ is the set of all neighbors of $S$; (ii) $|S| \leq \lceil n/2\rceil$; (iii) every vertex in $N(S)$ has at least two neighbors in $S$.

   • Show that if $p \geq (\ln n - \ln \ln n)/n$, $G$ does not contain such $S$ of size $s \geq 2$ asymptotically almost surely.

     (Hint: You may need the estimation $\binom{n}{m} \leq (en/m)^m$, and compute for the case $s = 2$ and $s \geq 3$ respectively.)

   • Complete the whole proof.

     (Hint: Is there any situation we're missing above?)

4. We now claim a four-point concentration for the chromatic number of sparse random graphs.

   Let $\alpha > 5/6$ be fixed, and $p < n^{-\alpha}$. We will show that for all $\varepsilon > 0$, there exists a function $u = u(n)$ such that

   $$\Pr[u\leq \chi(\mathcal{G}(n, p)\leq u+3)] \geq 1-\varepsilon -o(1)\,.$$

   Let $u$ be the smallest positive integer such that $\Pr_{G\sim \mathcal{G}(n, p)}[\chi(G) \leq u] > \varepsilon/2$, and $Y$ be the random variable that is the minimum size of $S$ where $G\setminus S$ can be properly $u$-colored. If $\chi(G)$ is already at most $u$, then $Y = 0$.

   • Upper bound the difference of $Y$ with respect to the vertex-exposure martingale and the edge-exposure martingale, respectively.

   • Use the bounded differences inequality to show that $\mathbb{E}[Y] =\lambda \sqrt{n}$ for some $\lambda = \lambda(\varepsilon)$.

   • Show that $\Pr[Y\geq 2\lambda \sqrt{n}] \leq \varepsilon /2$.

   • Show that for any subset $S$ of size at most $2\lambda \sqrt{n}$ (where $\lambda$ does not depend on $n$), the induced subgraph $G[S]$ can be properly colored with $3$ colors with probability $1-o(1)$.

     (Hint: Review the previous lecture notes.)