Homework 4

Deadline: Oct. 28, 22:00:00
  1. Derandomize balancing vectors. Namely, given vectors of unit length in , find an polynomial-time deterministic algorithm to output numbers such that .

  2. 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.

  3. 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 .

  4. 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.