Georgia Institute of Technology College of Sciences

The Hales--Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow. A celebrated result of Shelah from 1988 gives a significantly improved bound for this theorem. A key tool used in his proof, now known as the cube lemma, has become famous in its own right. Hoping to further improve Shelah's result, more than twenty years ago, Graham, Rothschild and Spencer asked whether there exists a polynoimal bound for this lemma. In this talk, we present the answer to their question and discuss numerous connections of the cube lemma with other problems in Ramsey theory. Joint work with David Conlon (Oxford), Jacob Fox (MIT), and Benny Sudakov (ETH Zurich).

For relations {R_1,..., R_k} on a finite set D, the {R_1,...,R_k}-CSP is a computational problem specified as follows: Input: a set of constraints C_1, ..., C_m on variables x_1, ..., x_n, where each constraint C_t is of form R_{i_t}(x_{j_{t,1}}, x_{j_{t,2}}, ...) for some i_t in {1, ..., k} Output: decide whether it is possible to assign values from D to all the variables so that all the constraints are satisfied. The CSP problem is boolean when |D|=2. Schaefer gave a sufficient condition on the relations in a boolean CSP problem guaranteeing its polynomial-time solvability, and proved that all other boolean CSP problems are NP-complete. In the planar variant of the problem, we additionally restrict the inputs only to those whose incidence graph (with vertices C_1, ..., C_m, x_1, ..., x_m and edges joining the constraints with their variables) is planar. It is known that the complexities of the planar and general variants of CSP do not always coincide. For example, let NAE={(0,0,1),(0,1,0),(1,0,0),(1,1,0),(1,0,1),(0,1,1)}). Then {NAE}-CSP is NP-complete, while planar {NAE}-CSP is polynomial-time solvable. We give some partial progress towards showing a characterization of the complexity of planar boolean CSP similar to Schaefer's dichotomy theorem.Joint work with Martin Kupec.

Abstract: the theory of weak turbulence has been put forward by appliedmathematicians to describe the asymptotic behavior of NLS set on a compactdomain - as well as many other infinite dimensional Hamiltonian systems.It is believed to be valid in a statistical sense, in the weaklynonlinear, infinite volume limit. I will present how these limits can betaken rigorously, and give rise to new equations.

Experimentalists observed that microscopically disordered systems exhibit homogeneous geometry on a macroscopic scale. In the last decades elegant tools were created to mathematically assert such phenomenon. The classical geometric results, such as asymptotic graph distance and isoperimetry of large sets, are restricted to i.i.d. Bernoulli percolation. There are many interesting models in statistical physics and probability theory, that exhibit long range correlation. In this talk I will survey the theory, and discuss a new result proving, for a general class of correlated percolation models, that a random walk on almost every configuration, scales diffusively to Brownian motion with non-degenerate diffusion matrix. As a corollary we obtain new results for the Gaussian free field, Random Interlacements and the vacant set of Random Interlacements. In the heart of the proof is a new isoperimetry result for correlated models.