1. The problem of coloring a given graph with at most three colors is NP-complete. Formulate a linear programming relaxation of this problem. 2. Consider a random walk on a complete graph with n vertices. The graph has no self-loops, so the walk must move to a different vertex at each step. (a) For what values of n does this process generate an aperiodic and irreducible Markov chain? (b) Suppose we start the walk at some particular vertex v_0, deterministically, and then perform the random walk as above. Let P_i denote the probability distribution on the vertices of the graph after i steps of the walk. What is the total variation distance between P_1 and the uniform distribution, as a function of n? (c) Suppose that you wish to generate approximately-uniform random samples of a set of n elements. Would constructing a complete graph on this set and performing a random walk for enough steps to make the variation distance small be a good way of doing so? Why or why not? 3. (M-U 7.19). Suppose we perform a simple random walk (starting from zero and with equal probability adding either +1 or -1 to our current position at each step), stopping when we reach either the negative number L or the positive number R. Prove that the expected number of steps until stopping is exactly LR. 4. (M-U 11.2). Consider the following Markov chain on a deck of cards: at each step choose one card uniformly at random and move it to the top of the deck. Stop shuffling when every card has been moved to the top at least once. (a) Use coupling to show that, no matter what state the deck starts in, at the point that we stop the algorithm, the deck is random (every permutation is equally likely). (b) Use the coupon collector's problem to give a bound (in O-notation, as a function of the number n of cards) on the number of steps performed by this algorithm.