Homework 6

Deadline: Nov. 18, 22:00:00

1. Let $k \geq 10$ be an integer and $H = (V, E)$ be a $k$-uniform $k$-regular graph (namely, each edge contains exactly $k$ vertices and each vertex appears in exactly $k$ edges).
   Show that there exists a proper $2$-coloring of $H$.

2. Let $G = (V, E)$ be a $k$-regular directed graph without parallel edges (namely, each vertex has exactly $k$ outgoing edges, and there is no edge $u\to v$ if $v\to u$ exists).
   Show that $G$ has a collection of $\lfloor k/(3\ln k) \rfloor$ vertex-disjoint cycles.

3. Let $G = (V, E)$ be a simple graph, and suppose each $v \in V$ is associated with a set $S(v)$ of colors of size at least $10d$, where $d \geq 1$. Suppose, in addition, that for each $v \in V$ and $c \in S(v)$ there are at most $d$ neighbors $u$ of $v$ such that $c$ lies in $S(u)$. Prove that there is a proper coloring of $G$ assigning to each vertex $v$ a color from its class $S(v)$.

   (Hint: Independent sets.)

4. The van der Waerden number $W(2, k)$ is the least number $n$ such that any $2$-coloring of $\{1, 2, \ldots , n\}$ gives a monochromatic arithmetic progression of length $k$.
   Show that $W(2, k) > 2^k/(2ek)$.

5. (Bonus) Let $\Phi = (V ,C)$ be a SAT formula, where $V$ is the set of variables and $C$ is the set of clauses.
   Assume each clause contains at least $k_1$ variables and at most $k_2$ variables, and each variable belongs to at most $d$ clauses.
   For any $s \geq k_2$, if $2^{k_1} \geq 2eds$, show that there exists a satisfying assignment for $\Phi$ and for any $v \in V$ and any $b\in \{0, 1\}$,

   $$\Pr[X(v) = b \mid \Phi \text{ is satisfied}] \leq \frac{1}{2}\cdot \exp(1/s)\,$$

   where $X: V \to \{0, 1\}$ is an assignment chosen uniformly at random from all $2^{|V|}$ possibilities.

   (Hint will be given in the next week.)