Elegance in probability: a conference honoring Russell Lyons's 60th birthday

Elegance in probability

A conference honoring Russell Lyons's 60th birthday

Program

	Sunday 3.9	Monday 4.9	Tuesday 5.9	Wednesday 6.9	Thursday 7.9
9:00-9:30	Registration
9:30-10:15	Benjamin Weiss	Wendelin Werner	Stanislav Smirnov	Michael Aizenman	Tom Hutchcroft
10:15-10:40	Break	Break	Break	Break	Break
10:40-11:25	Robin Pemantle	Assaf Naor	James Lee	Tatiana Nagnibeda	Tianyi Zheng
11:30-12:15	Claire Mathieu	Ori Gurel-Gurevich	Hugo Duminil-Copin	Nicolas Curien	Jeff Steif
12:15-14:00	Lunch	Lunch	Free afternoon!	Lunch	Lunch
14:00-14:45	Bálint Virág	Perla Sousi		Yinon Spinka	Vincent Tassion
14:50-15:35	Miklós Ábert	Problem/Simulation session		Problem/Simulation session	Adám Timár
15:35-16:00	Break	Break		Break	Break
16:00-16:45	Itai Benjamini	Rick Kenyon		Sourav Chatterjee	Omer Angel
16:45-17:30	Poster Session
17:30-19:00	Reception

Titles and abstracts

Miklós Ábert: Cost, point processes and growth of rank of locally symmetric spaces

The cost of a vertex transitive graph is the infimum of the expected degree of an invariant random rewiring of the graph. Similarly, one can define the cost of a point process on a homogeneous space. It turns out that the cost of a Poisson process is maximal among point processes of the same density and that it is related to the growth of the minimal number of generators of lattices in Lie groups. We expect that for semisimple Lie groups, the minimal number of generators is sublinear in the volume except for SL(2,R). We outline partial results in this direction and pose some open problems. One of them is to compute the cost of the Poisson process on hyperbolic 3-space.

This is joint work with Sam Mellick.

Michael Aizenman: Phase diagrams and critical exponent bounds through probabilistic differential inequalities (PDI)

Nonlinear partial differential inequalities derived by probabilistic means yield non-perturbative information on percolation-driven first order phase transitions. Examples are found in the contact processes, random cluster models, Ising spin systems, and certain quantum spin chains. The percolation transition and the onset of long range order in these systems bear similarities with shock formation in the Burgers evolution of the velocity field in a one dimensional incompressible fluid. Curiously, Burgers equation shows up also in the evolution of the order parameter in the mean field version of some of these models. In more general cases, formulated over transitive graphs, this and a companion relation re-appear as inequalities. We shall try to convey the elegance of the method, and of the probabilistic techniques it employs, which were developed in the works of a number of different authors.

Omer Angel: Voronoi cells in random spaces.

Motivated by a conjecture from Chapuy, we consider the partition of a measured metric spaces into Voronoi cells around uniform random centres. We find that in several random spaces the cells give a uniform partition of unity. These include Brownian continuum random trees and unicellular maps. Joint with Louigi Addario-Berry, Guillaume Chapuy, Eric Fusy and Christina Goldschmidt.

Itai Benjamini: Coarse uniformization and percolation

We will present an elementary problem and a conjecture regarding percolation on planar graphs suggested by assuming quasi invariance of percolation crossing probabilities under coarse conformal uniformization.

Sourav Chatterjee: A general method for lower bounds on fluctuations of random variables

There are numerous ways of establishing upper bounds on fluctuations of random variables, but there is no systematic approach for lower bounds. As a result, lower bounds are unknown in many important problems. I will talk about a general method for lower bounds on fluctuations. The method gives new results for the stochastic traveling salesman problem, the stochastic minimal matching problem, the random assignment problem, the Sherrington--Kirkpatrick model of spin glasses, first-passage percolation and random matrices. I will discuss some of these examples.

Nicolas Curien: Geometric and spectral properties of random causal triangulations

We study the random planar maps obtained from random Galton--Watson plane trees after adding the horizontal connections between successive vertices at each level. This random graphs are closely related to the well-known causal dynamical triangulations introduced by Ambjörn and Loll and are extensively studied in physics. We prove that when the underlying Galton--Watson tree is critical and has finite variance then the horizontal distances are shrunk compared to the vertical distances, although the distance exponent remains the same. This enables us to prove that the spectral dimension of a infinite version of these graphs is almost surely equal to 2.

Based on joint work with Tom Hutchcroft and Asaf Nachmias.

Hugo Duminil-Copin: Extracting juice from weakly discrete holomorphic observables

In this talk, we will describe applications of so-called parafermionic observables. These observables pop up in several models of two-dimensional statistical physics. At criticality, they satisfy local relations which may be understood as discrete versions of Cauchy-Riemann Equations. Unfortunately, these local relations often provide partial information only on the behavior of the observables. We will explain how this partial information can still be used to prove a number of results, including the computation of the connective constant of the hexagonal lattice, and some inequalities on the critical point of the loop O(n) model.

Ori Gurel-Gurevich: The power of two choices in point allocation

Consider a set of N points chosen randomly i.i.d. uniformly from the unit interval. For each subinterval J, consider the difference between the number of points in J to the length of J times N. It is well know that the maximum of this difference over all subintervals, called the discrepancy, is roughly sqrt(N).

Suppose, instead, the set is chosen in N stages where at each stage you are given 2 i.i.d. uniform points and have to choose which to add to the set and which to discard. Can you significantly reduce the discrepancy? We show that it is possible to get a discrepancy of roughly log^3(N) and discuss generalizations to higher dimensions.

Based on joint works with Raaz Dwivedi, Ohad Feldheim and Aaditya Ramdas.

Tom Hutchcroft: Multiplicity of phase transitions and mean-field criticality for percolation on nonunimodular transitive graphs

We study Bernoulli bond percolation on nonunimodular quasi-transitive graphs, and more generally graphs whose automorphism group has a nonunimodular quasi-transitive subgroup. We prove that percolation on any such graph has a non-empty phase in which there are infinite light clusters, which implies the existence of a non-empty phase in which there are infinitely many infinite clusters. That is, we show that p_c<p_h <= p_u for any such graph. This answers a question of Haggstrom, Peres, and Schonmann (1999), and verifies the nonunimodular case of a well-known conjecture of Benjamini and Schramm (1996). We also prove that the triangle condition holds at criticality on any such graph, and that various critical exponents attain their mean-field values.

All our results apply, for example, to the product TxZ^d of a k-regular tree with Z^d for k >2 and d >= 1, for which these results were previously known only for large k.

Rick Kenyon: Determinantal spanning forests

We discuss determinantal measures on spanning forests on planar graphs generalizing the UST measure. Fixing boundary connections leads to limit shape theorems in the scaling limit.

James Lee: Uniformizing the geometry of unimodular random graphs

In analogy with classical conformal uniformization, we examine deformations of the graph metric of a unimodular random graph by attaching weights to its vertices. Endowing a graph with a nice geometry in this way yields a powerful tool for understanding the random walk and its associated spectral measure. We use discrete conformal metrics to study the spectral properties of distributional limits of graphs that can be sphere-packed in a Euclidean space. In particular, this applies to planar graphs, and these tools yield new results for extensively studied models like the uniform infinite planar triangulation (UIPT) and its relatives.

Claire Mathieu: Algorithms with noisy comparisons

Crowdsourcing and web applications have caused a resurgence of interest in algorithms that have a great degree of parallelism and are robust in the presence of random noise when items are being compared. I will discuss algorithms and lower bounds for finding the top items, and related questions.

This is joint work with Vincent Cohen-Addad, Frederik Mallmann-Trenn, and Victor Verdugo.

Tatiana Nagnibeda: Spectral computations in groups of intermediate growth

I will discuss spectra of laplacians associated with groups of intermediate growth and their actions.

Assaf Naor: A spectral gap precludes low-dimensional embeddings

We prove that if an n-vertex O(1)-expander graph embeds with average distortion D into a finite dimensional normed space X, then necessarily the dimension of X is at least n^{c/D} for some universal constant c>0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X)>c(logn)^2/D^2. The proof relies on a probabilistic argument, namely the behavior of Markov chains in spaces obtained from complex interpolation.

Robin Pemantle: Regularity of invasion measure on a Galton-Watson tree

We consider the law of the invasion ray on a Galton-Watson tree. In the case of a regular tree, where precise information is available about the rate at which the invasion cluster approximates critical percolation and the incipient infinite cluster, the law of the invasion ray is precisely uniform for obvious reasons of symmetry. On a Galton-Watson tree, the invasion law is not equal to the limit uniform measure. We show it is absolutely continuous with respect to limit uniform measure and describe joint behavior of the tree and the invasion process along the backbone of the invasion ray.

Perla Sousi: Random walks on dynamical percolation

We study the behaviour of random walk on dynamical percolation. In this model, the edges of a graph are either open or closed and refresh their status at rate μ, while at the same time a random walker moves on G at rate 1, but only along edges which are open. On the d-dimensional torus with side length n, when the bond parameter is subcritical, the mixing times for both the full system and the random walker were determined by Peres, Stauffer and Steif. I will talk about the supercritical case, which was left open, but can be analysed using evolving sets (joint work with Y. Peres and J. Steif).

Stas Smirnov: TBA

TBA

Yinon Spinka: A condition for long-range order in discrete spin systems

We present a new condition for the existence of long-range order in discrete spin systems, which emphasizes the role of entropy and high dimension. The condition applies to all symmetric nearest-neighbor discrete spin systems with an internal symmetry of `dominant phases'. Specific applications include a proof of Kotecký's conjecture (1985) on anti-ferromagnetic Potts models, a strengthening of results of Lebowitz-Gallavotti (1971) and Runnels-Lebowitz (1975) on Widom-Rowlinson models and of Burton-Steif (1994) on shifts of finite type, and a significant extension of results of Engbers-Galvin (2012) on random graph homomorphisms on the hypercube. Joint with Ron Peled.

Jeff Steif: Generalized Divide and Color Models

In this talk, we consider the following model: one starts with a finite or countable set V, a random partition of V and a parameter p in [0,1]. The corresponding Generalized Divide and Color Model is the {0,1}-valued process indexed by V obtained by independently, for each partition element in the random partition chosen, with probability p assigning all the elements of the partition element the value 1, and with probability 1−p, assigning all the elements of the partition element the value 0.

A very special interesting case of this is the ``Divide and Color Model'' (which motivates the name we use) introduced and studied by Olle Häggström. Models which fit into this context are the 0 external field Ising (and fuzzy Potts) model, the stationary distributions for the voter model and random walk in random scenery (aka the T T inverse process).

Some of the questions which we study here are the following. Under what situations can different random partitions give rise to the same color process? What can one say concerning exchangeable random partitions? What is the set of product measures that a color process stochastically dominates? For random partitions which are translation invariant, what ergodic properties do the resulting color processes have? This is joint with with Johan Tykesson.

Vincent Tassion: Sharpness of the phase transition via randomized algorithms

In this talk, we provide a new proof of exponential decay for the connection probabilities of subcritical Bernoulli percolation, based on randomized algorithms. This proof does not rely on the domain Markov property or the BK inequality. In particular, it extends to FK percolation and continuum percolation models such as Boolean and Voronoi percolation in arbitrary dimension. This provides the first proof of sharpness of the phase transition for these models.

This talk is based on a joint work with Hugo Duminil-Copin and Aran Raoufi.

Adám Timár: A nonamenable "factor" of a euclidean space

Itai Benjamini proposed the following question. Is there a way to represent a nonamenable transitive graph, say, a regular tree, in R^3, as a random invariant partition into “nice” connected pieces, so that the pieces are indistinguishable? In other words, is there a 3-dimensional isometry-invariant “map” of indistinguishable regions whose adjacency graph is the 3-regular tree? The answer was expected to be negative because of the known case of R^2, and because of the intuition that nonamenability should be an obstacle. However, such a representation is possible. The proof uses factor of iid constructions.

Bálint Virág: Random matrices for Russ

A few new short proofs for basic random matrix facts.

Benjamin Weiss: Stationary processes and harmonic analysis

I will discuss several new and old results on applications of harmonic analysis to the theory of stationary stochastic processes. For example: If the spectral measure of a finite valued stationary process has a spectral gap then the process is periodic (in part joint work with A. Borichev and M. Sodin).

Wendelin Werner: Conformal loop ensembles on Liouville quantum gravity

We will explain how explorations of conformal loop ensembles (and their loop-trunk decompositions of these explorations) on some independent random "quantum surfaces" give rise to (and can be encoded by) simple growth/fragmentation processes of the type that appear in the study of O(N) models on large planar maps. This description has implications for the study of Liouville quantum gravity in the case of general γ, and yields also some new results on SLE itself. This is based on ongoing joint work with Jason Miller and Scott Sheffield.

Tianyi Zheng: On groups slow decay of heat kernel implies Liouville property

Given a symmetric step distribution μ of finite entropy on a group G, we show that if the return probability decays slower than exp(-n^{1/2}), then all bounded μ-harmonic functions are constant. Furthermore return probability lower bounds imply upper bounds on entropy. We illustrate the sharpness of the bound on a family of examples. We will also discuss some results and questions on joint behavior of random walk parameters.