Derandomize balancing vectors. Namely, given vectors of unit length in , find an polynomial-time deterministic algorithm to output numbers such that .

Let be real numbers of absolute value . Consider the linear combinations , . Then the number of sums which are in any interval is at most .

*Remark: An interpretation of this result is that for any random walk on the real line, where the -th step is either or at random, the probability that after steps we end up in some fixed interval is at most .**Hint: DO NOT use the second moment method.*Show that there is a graph on vertices with minimum degree at least in which the size of every dominating set is at least .

*Hint: Pick a random graph .*Let be the property that does

*NOT*contain two*DISTINCT*(distinct, not disjoint) cycles of the same length. Show that there exists a constant such that any -vertex graph satisfying has at most edges.*Hint: Remove some edges from so that there is no cycles remaining.*