Consider a Markov chain on the set of n by n invertible matrices mod 2, where in each step, two distinct rows are chosen uniformly at random, and the first row is added to the second mod 2. How does the mixing time grow with n? And how does it change if only test functions that are computable in polynomial time are allowed?
Given a lacunary sequence of integers, Erdos asked for the chromatic number of the graph on the integers where two integers are linked by an edge is their difference is in the sequence. determining the optimal bound for this chromatic number is closely related to a question on Diophantine approximation considered by Khinchin, Erdos and Katznelson.
Consider random transpositions on sequences of 1, -1, with non-negative partial sums (transpositions that violate this condition are rejected.) How does the mixing time of this chain grow as a function of n ?