Lesson 3

Optional Problems.

1. (20 points) Let \(D = (V,E)\) be a directed graph with minimum outdegree \(\delta\) and maximum indegree \(\Delta\). Show that for any \(k \in \mathbb{N}\) such that \[k \le \frac{\delta}{1 + \log (1 + \delta \Delta)},\] \(D\) contains a directed cycle of length divisible by \(k\).
2. (20 points) Let \(c\colon \mathbb{R}\to [k]\) be a coloring of the real numbers. A set \(T \subset \mathbb{R}\) is called colorful if \(c(T) = [k]\).

   Prove that for any \(k\) there is \(m\) such that for any \(m\)-point set \(S \subset \mathbb{R}\), the real numbers can be colored with \(k\) colors so that any translation of \(S\) is colorful.

3. (15 points) We call a formula in CNF \(3\)-satisfiable if every subset of at most three of its clauses is satisfiable. In this problem you need to prove that for any 3-satisfiable formula, at least a fraction of \(2/3\) of its clauses can be satisfied (no matter how many clauses it has).
   • (2 points) Consider a random assignment \(\alpha \in \{0,1\}^{n}\) where \(\Pr[\alpha_{i}=1]\) is \(2/3\) if \((x_{i}) \in F\), \(1/3\) if \((\overline{x_i}) \in F\), and \(1/2\) otherwise. Explain why this distribution is well-defined.
   
   
   • (3 points) Show that under this distribution, any literal \(z_{i} \in \{x_{i}, \overline{x_i}\}\) is falsified with probability at most \(2/3\).
   
   
   • (4 points) Prove that any clause of length \(1\) or length at least \(3\) is satisfied with probability at least \(2/3\).
   
   
   • (5 points) Prove that any clause of length \(2\) is also satisfied with probability at least \(2/3\).
   
   
   • (1 point) Conclude the proof using the expected number of satisfied clauses.