Homework 4

Deadline: Oct. 28, 22:00:00

1. Derandomize balancing vectors. Namely, given $n$ vectors $v_1, v_2, \ldots, v_n$ of unit length in $\mathbb{R}^n$, find an polynomial-time deterministic algorithm to output $n$ numbers $\epsilon_1, \epsilon_2, \ldots, \epsilon_n \in \{-1, +1\}$ such that $\lVert \epsilon_1v_1 + \cdots + \epsilon_n v_n\rVert \leq \sqrt{n}$.

2. Let $a_1, a_2, \ldots , a_n$ be real numbers of absolute value $|a_i| \geq 1$. Consider the $2^n$ linear combinations $\sum_{i=1}^n \epsilon_i\cdot a_i$, $\epsilon_i \in \{−1, +1\}$. Then the number of sums which are in any interval $(x − 1, x + 1)$ is at most $\binom{n}{\lfloor n/2 \rfloor}$.

   Remark: An interpretation of this result is that for any random walk on the real line, where the $i$-th step is either $+a_i$ or $−a_i$ at random, the probability that after $n$ steps we end up in some fixed interval $(x − 1, x + 1)$ is at most $\binom{n}{\lfloor n/2 \rfloor} = O(1/\sqrt n)$.

   Hint: DO NOT use the second moment method.

3. Show that there is a graph on $n$ vertices with minimum degree at least $n∕2$ in which the size of every dominating set is at least $\Omega(\log n)$.

   Hint: Pick a random graph $G\sim \mathcal{G}(n,p)$.

4. Let $\mathcal{P}$ be the property that $G$ does NOT contain two DISTINCT (distinct, not disjoint) cycles of the same length. Show that there exists a constant $c$ such that any $n$-vertex graph $G$ satisfying $\mathcal{P}$ has at most $n + c\sqrt{n}$ edges.

   Hint: Remove some edges from $G$ so that there is no cycles remaining.