Combinatorics Seminar

When: Sunday, November 13, 10am Where: Schreiber 309 Speaker: Yuval Peres, Microsoft Research Redmond Title: Two Erdos problems on lacunary sequences: chromatic number and Diophantine approximation

Abstract:

Let {n_k} be a lacunary sequence, i.e., the ratio of successive elements of the sequence is at least some q>1. In 1987, Erdos asked for the chromatic number of a graph G on the integers, where two integers are connected by an edge iff their difference is in the sequence {n_k}. Y. Katznelson found a connection to a Diophantine approximation problem: finding irrationals x such that n_k times x is at least r>0 away from the integers for all k. In joint work with W. Schlag, we improve Katznelson's bounds for both problems using the Lovasz local lemma. It is still an unsolved problem to obtain matching upper and lower bounds.