Hint for Problem 4

Here's a handy hint for problem 4 on the most recent problem set:

Suppose L_t and R_t are the partition your algorithm has selected at time t. Define some integer valued potential function f(L_t, R_t) such that f is always in some bounded range [o, R].

Show that:

1) If we ever have f(L_t, R_t) = R, then L_t, R_t is a triangle free partition

2) Pr[f(L_t+1,R_t+1) = f(L_t, R_t) + 1 ] = Pr[f(L_t+1,R_t+1) = f(L_t, R_t) - 1 ]

Then all you have to do is analyze the evolution of the potential function: and this is just a random walk on a line graph of length R.