## Select Seminar Series

All seminars- Home
- ›
- Studying at the Faculty
- ›
- Seminars ›
- Geometric Functional Analysis and Probability Seminar

# Geometric Functional Analysis and Probability Seminar

We will show that there exists a metric space that does not admit a coarse embedding into any Alexandrov space of global nonpositive curvature, thus answering a question of Gromov (1993). In contrast, any metric space embeds coarsely into an Alexandorv space of nonnegative curvature. Based on joint works with Andoni and Neiman, and Eskenazis and Mendel.

Let F be a fixed infinite, vertex-transitive graph. We say a graph G is `r-locally F' if for every vertex v of G, the ball of radius r and centre v in G is isometric to the ball of radius r in F. For each positive integer n, let G_n be a graph chosen uniformly at random from the set of all unlabelled, n-vertex graphs that are r-locally F. We investigate the properties that the random graph G_n has with high probability --- i.e., how these properties depend on the fixed graph F.

We show that if F is a Cayley graph of a torsion-free group of polynomial growth, then there exists a positive integer r_0 such that for every integer r at least r_0, with high probability the random graph G_n = G_n(F,r) defined above has largest component of size between n^{c_1} and n^{c_2}, where 0 < c_1 < c_2 < 1 are constants depending upon F alone, and moreover that G_n has a rather large automorphism group. This contrasts sharply with the random d-regular graph G_n(d) (which corresponds to the case where F is replaced by the infinite d-regular tree).

Our proofs use a mixture of results and techniques from group theory, geometry and combinatorics.

We obtain somewhat more precise results in the case where F is L^d (the standard Cayley graph of Z^d): for example, we obtain quite precise estimates on the number of n-vertex graphs that are r-locally L^d, for r at least linear in d.

Many intriguing open problems remain: concerning groups with torsion, groups with faster than polynomial growth, and what happens for more general structures than graphs.

This is joint work with Itai Benjamini (WIS).

I will describe a new approach to the study of spherical spin glass models via free energy landscapes, defined by associating to interior points of the sphere the free energy computed only over the spherical band around them.

They are closely related to several fundamental objects from spin glass theory: the TAP free energy, pure states decomposition, overlap distribution, and temperature chaos. I will explain some of of those connections.

The classical Gaussian isoperimetric inequality, established in the 70's independently by Sudakov-Tsirelson and Borell, states that the optimal way to decompose $\mathbb{R}^n$ into two sets of prescribed Gaussian measure, so that the (Gaussian) area of their interface is minimal, is by using two complementing half-planes. This is the Gaussian analogue of the classical Euclidean isoperimetric inequality, and is therefore referred to as the "single-bubble" case.

A natural generalization is to decompose $\mathbb{R}^n$ into $q \geq 3$ sets of prescribed Gaussian measure. It is conjectured that when $q \leq n+1$, the configuration whose interface has minimal (Gaussian) area is given by the Voronoi cells of $q$ equidistant points. For example, for $q=3$ (the "double-bubble"conjecture) in the plane ($n=2$), the interface is conjectured to be a "tripod" or "Y" - three rays meeting at a single point in 120 degree angles. For $q=4$ (the "triple-bubble" conjecture) in $\mathbb{R}^3$, the interface is conjectured to be a tetrahedral cone.

We confirm the Gaussian double-bubble and, more generally, multi-bubble conjectures for all $3 \leq q \leq n+1$. The double-bubble case $q=3$ is simpler, and we will explain why.

None of the numerous methods discovered over the years for establishing the classical $q=2$ case seem amenable to the $q \geq 3$ cases, and our method consists of establishing a Partial Differential Inequality satisfied by the isoperimetric profile. To treat $q > 3$, we first prove that locally minimimal configurations must have flat interfaces, and thus convex polyhedral cells. Uniqueness of minimizers up to null-sets is also established.

This is joint work with Joe Neeman (UT Austin).

**Ohad Feldheim: Convergence of a quantile admission processes**

**Abstract**: Consider the following stochastic model for a growing set. At time 0 the model consists of the singleton S = {-infty}. At every subsequent time, two i.i.d. samples, distributed according to some distribution D on R, are suggested as candidates for S. If the smaller among the two is closer to at least a fraction of r of the current elements of S (in comparison with the larger one), then it is admitted into S.

How will the distribution of the members of S evolve over time as a function of r and D?

This model was suggested by Alon, Feldman, Mansour, Oren and Tennenholtz as a model for the evolution of an exclusive social group. We'll show that the empirical distribution of the elements of S converges to a (not-necessarily deterministic) limit distribution for any r and D.

This we do by relating the process to a random walk in changing environment. The analysis of this random walk involves various classical exponential concentration inequalities as well as a new general inequality concerning mean and minimum of independent random variables.

Joint work with Naomi Feldheim

**Eviatar Procaccia:** **Stabilization of Diffusion Limited Aggregation in a Wedge**

**Abstract**: We prove a discrete Beurling estimate for the harmonic measure in a wedge in $\mathbf{Z}^2$, and use it to show that Diffusion Limited Aggregation (DLA) in a wedge of angle smaller than $\pi/4$ stabilizes. This allows to consider the infinite DLA and questions about the number of arms, growth and dimension. I will present some conjectures and open problems.

**Bhaswar Bhattacharya**: Large Deviation Variational Problems in Random Combinatorial Structures

The upper tail problem in the Erdos-Renyi random graph $G\sim\mathcal{G}_{n,p}$, where every edge is included independently with probability $p$, is to estimate the probability that the number of copies of a graph $H$ in $G$ exceeds its expectation by a factor of $1+\delta$. The arithmetic analog of this problem counts the number of $k$-term arithmetic progressions in a random subset of $\{1, 2, \ldots, N\}$, where every element is included independently with probability $p$. The recently developed framework of non-linear large deviations (Chatterjee and Dembo (2016) and Eldan (2017)) shows that the logarithm of these tail probabilities can be reduced to a natural variational problem on the space of weighted graphs/functions. In this talk we will discuss methods for solving these variational problems in the sparse regime ($p \rightarrow 0$), and show how the solutions are often related to extremal problems in combinatorics. (This is based on joint work with Shirshendu Ganguly, Eyal Lubetzky, Xuancheng Shao, and Yufei Zhao.)

**Elliot Paquette**: Random matrix point processes via stochastic processes

In 2007, Virag and Valko introduced the Brownian carousel, a dynamical system that describes the eigenvalues of a canonical class of random matrices. This dynamical system can be reduced to a diffusion, the stochastic sine equation, a beautiful probabilistic object requiring no random matrix theory to understand. Many features of the limiting eigenvalue point process, the Sine--beta process, can then be studied via this stochastic process. We will sketch how this stochastic process is connected to eigenvalues of a random matrix and sketch an approach to two questions about the stochastic sine equation: deviations for the counting Sine--beta counting function and a functional central limit theorem.

Random surfaces in statistical physics are commonly modeled by a real-valued function phi on a lattice, whose probability density penalizes nearest-neighbor fluctuations. Precisely, given an even function V, termed the potential, the energy H(phi) is computed as the sum of V over the nearest-neighbor gradients of phi, and the probability density of phi is set proportional to exp(-H(phi)). The most-studied case is when V is quadratic, resulting in the so-called Gaussian free field. Brascamp, Lieb and Lebowitz initiated in 1975 the study of the global fluctuations of random surfaces for other potential functions and noted that understanding is lacking even in the case of the quartic potential, V(x)=x^4. We will review the state of the art for this problem and present recent work with Alexander Magazinov which finally settles the question of obtaining upper bounds for the fluctuations for the quartic and many other potential functions.

**David Jerison:** Localization of eigenfunctions via an effective potential

We discuss joint work with Douglas Arnold, Guy David, Marcel Filoche and Svitlana Mayboroda. Consider the Neumann boundary value problem for the operator $L u = - \mbox{div} (A \nabla u) + Vu$ on a Lipschitz domain $\Omega$ and, more generally, on a manifold with or without boundary. The eigenfunctions of $L$ are often localized, as a result of disorder of the potential $V$, the matrix of coefficients $A$, irregularities of the boundary, or all of the above. In earlier work, Filoche and Mayboroda introduced the function $u$ solving $Lu = 1$, and showed numerically that it strongly reflects this localization. Here, we deepen the connection between the eigenfunctions and this {\em landscape} function $u$ by proving that its reciprocal $1/u$ acts as an {\em effective potential}. The effective potential governs the exponential decay of the eigenfunctions of the system and delivers information on the distribution of eigenvalues near the bottom of the spectrum.

**Ron Rosenthal:** Eigenvector correlation in the complex Ginibre ensemble

The complex Ginibre ensemble is a non-Hermitian random matrix on C^N with i.i.d. complex Gaussian entries normalized to have mean zero and variance 1=N. Unlike the Gaussian unitary ensemble, for which the eigenvectors are orthogonal, the geometry of the eigenbases of the Ginibre ensemble are not particularly well understood. We will discuss a some results regarding the analytic and algebraic structure of eigenvector correlations in this matrix ensemble. In particular, we uncover an extended algebraic structure which describes the asymptotic behavior (as N goes to infinity) of these correlations. Our work extends previous results of Chalker and Mehlig [CM98], in which the correlation for pairs of eigenvectors was computed. Based on a joint work with Nick Crawford.

Consider a sequence of growing graphs converging locally weakly to an infinite (possibly random) tree. As there are uncountably many Ising and Potts Gibbs measures on the limiting tree in the low-temperature regime it is not apriori clear whether the local weak limit of such measures exists and if so, identifying the limit remains a challenge. In this talk, I will describe these limits. The talk is based on joint works with Amir Dembo and Allan Sly.

Talk 1: David Ellis (Queen Mary U)

**Title: The edge-isoperimetric problem for antipodally symmetric subsets of the discrete cube.**

Abstract: A major open problem in geometry is to solve the isoperimetric problem for n-dimensional real projective space, i.e. to determine, for each real number V, the minimum possible size of the boundary of a (well-behaved) set of volume V, in n-dimensional real projective space. We study a discrete analogue of this question: namely, among all antipodally symmetric subsets of {0,1}^n of fixed size, which sets have minimal edge-boundary? We obtain a complete answer to the second question. This is joint work with Imre Leader (Cambridge)

Talk 2: Benjamin Fehrman (Max Planck Institute)

**Title: Well-posedness of stochastic porous media equations with nonlinear, conservative noise.**

Abstract: In this talk, which is based on joint work with Benjamin Gess, I will describe a pathwise well-posedness theory for stochastic porous media equations driven by nonlinear, conservative noise. Such equations arise in the theory of mean field games, as an approximation to the Dean-Kawasaki equation in fluctuating hydrodynamics, to describe the fluctuating hydrodynamics of a zero range process, and as a model for the evolution of a thin film in the regime of negligible surface tension. Our methods are loosely based on the theory of stochastic viscosity solutions, where the noise is removed by considering a class of test functions transported along underlying stochastic characteristics. We apply these ideas after passing to the equation's kinetic formulation, for which the noise enters linearly and can be inverted using the theory of rough paths.

**Mark Rudelson (UMich)**

**Title**: Invertibility of the adjacency matrices of random graphs.

**Abstract**: Consider an adjacency matrix of a bipartite, directed, or undirected Erdos-Renyi random graph. If the average degree of a vertex is large enough, then such matrix is invertible with high probability. As the average degree decreases, the probability of the matrix being singular increases, and for a sufficiently small average degree, it becomes singular with probability close to 1. We will discuss when this transition occurs, and what the main reason for the singularity of the adjacency matrix is.

This is a joint work with Anirban Basak.

**Yinon Spinka (TAU)**

**Title**: Finitary codings of Markov random fields

**Abstract**: Let X be a stationary Z^d-process. We say that X can be coded by an i.i.d. process if there is a(deterministic and translation-invariant) way to construct a realization of X from i.i.d. variables associated to the sites of Z^d. That is, if there is an i.i.d. process Y and a measurable map F from the underlying space of Y to that of X, which commutes with translations of Z^d and satisfies that F(Y)=X in distribution. Such a coding is called finitary if, in order to determine the value of X at a given site, one only needs to look at a finite (but random) region of Y.

It is known that a phase transition (existence of multiple Gibbs states) is an obstruction for the existence of such a finitary coding. On the other hand, we show that when X is a Markov random field satisfying certain spatial mixing conditions, then X can be coded by an i.i.d. process in a finitary manner. Moreover, the coding radius has exponential tails, so that typically the value of X at a given site is determined by a small region of Y.

We give applications to models such as the Potts model, proper colorings and the hard-core model.

Points of infinite multiplicity are particular points which the Brownian motion visits infinitely often. Following a work of Bass, Burdzy and Khoshnevisan, we construct and study a measure carried by these points. Joint work with Yueyun Hu and Zhan Shi.

We present a new way to derive the replica symmetric solution for the free energy in mean-field spin glasses. Only the Sherrington-Kirpatrick case has been worked out in details, but the method also works in other cases, for instance for the perceptron (work in progress), and probably also for the Hopfield net. The method is closely related to the TAP equations (for Thouless-Anderson-Palmer). It does not give any new results, presently, but it gives a new viewpoint, and it looks to be quite promising. As the TAP equations are widely discussed in the physics literature, also at low temperature, it is hoped that the method could be extended to this case, too. But this is open, and probably very difficult.

Oren Louidor (Technion)

**Title: Dynamical freezing in a spin-glass with logarithmic correlations**.

Abstract: We consider a continuous time random walk on the 2D torus, governed by the exponential of the discrete Gaussian free field acting as potential. This process can be viewed as Glauber dynamics for a spin-glass system with logarithmic correlations. Taking temperature to be below the freezing point, we then study this process both at pre-equilibrium and in-equilibrium time scales. In the former case, we show that the system exhibits aging and recover the arcsine law as asymptotics for a natural two point temporal correlation function. In the latter case, we show that the dynamics admits a functional scaling limit, with the limit given by a variant of Kolmogorov's K-process, driven by the limiting extremal process of the field, or alternatively, by a super-critical Liouville Brownian motion. Joint work with A. Cortines, J. Gold and A. Svejda.

Alexander Glazman (Tel Aviv)

**Title: Level lines of a random Lipschitz function**

Abstract: We consider the uniform distribution on Lipschitz functions on the triangular lattice, i.e. all integer-valued functions which differ by 0 or 1 on any two adjacent vertices. We show that with a positive probability such a function exhibits macroscopic level lines. Instead of working directly with Lipschitz functions we map this model to the loop $O(2)$ model with parameter $x=1$. The loop $O(n)$ model is a model for a random collection of non-intersecting loops on the hexagonal lattice, which is believed to be in the same universality class as the spin $O(n)$ model.

A main tool in the proof is a positive association (FKG) property that was recently shown to hold when $n \ge 1$ and $0<x\le\frac{1}{\sqrt{n}}$. Though the case $n=2$, $x=1$ is not in the FKG regime, it turns out that when loops are assigned one of two colours independently the marginal on loops of either of the colours does satisfy the FKG property. The colouring of loops allows to view the loop $O(2)$ model with $x=1$ as coupling of two percolation configurations. Studying each of them independently and using the XOR operation we establish existence of macroscopic loops, i.e. level lines in the original setting.

(Based on a joint work with H. Duminil-Copin, and I. Manolescu)

Sebastien Bubeck (Microsoft Research)

**Title: k-server via multiscale entropic regularization**

Abstract: I will start by describing how mirror descent is a natural strategy for online decision making, specifically in online learning and metrical task systems. To motivate the k-server problem I will also briefly recall what we know and what we don't know for structured state/action spaces in these models. Using the basic mirror descent calculations I will show how to easily obtain a log(k)-competitive algorithm for k-paging. I will then introduce our new parametrization of fractional k-server on a tree, and explain how to analyze the movement cost of entropy-regularized mirror descent on this parametrization. This leads to a depth*log(k)-competitive (fractional) algorithm for general trees, and log^2(k) for HSTs. I will also briefly mention dynamic embeddings to go beyond the standard log(n) loss in the reduction from general metrics to HSTs.

Joint work with Michael B. Cohen, James R. Lee, Yin Tat Lee, and Aleksander Madry.

Percy Deift (Courant Institute )

**Title: Universality in numerical analysis with some examples of cryptographic algorithms.**

Abstract: We show that a wide variety of numerical algorithms with random data exhibit universality. Most of the results are computational, but in some important cases universality is established rigorously. We also discuss universality for some cryptographic algorithms.

Joint work with C. Pfrany, G. Menon, S. Olver, T. Trogdan and S. Miller.

Talk 1: Amir Dembo (Stanford)

**Title: Large deviations theory for chemical reaction networks.**

The microscopic dynamics of well-stirred networks of chemical reactions are modeled as jump Markov processes. At large volume, one may expect in this framework to have a straightforward application of large deviation theory. This is not at all true, for the jump rates are typically neither globally Lipschitz, nor bounded away from zero, with both blowup and absorption as quite possible scenarios. In joint work with Andrea Agazzi and Jean-Pierre Eckman, we utilize Lyapunov stability theory to bypass this challenge and to characterize a large class of network topologies that satisfy the full Wentzell-Freidlin theory of asymptotic rates of exit from domains of attraction.

Talk 2: Yuval Peres (Microsoft)

Title: **Trace reconstruction for the deletion channel**

Abstract: In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability q, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability?

The best lower bound known is linear in $n$. Until 2016, the best upper bound was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some inequalities for Littlewood polynomials on the unit circle. This bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De O'Donnell and Servedio). If the string $x$ is random, we can show a subpolynomial number of traces suffices by comparison to a random walk. (Joint works with Fedor Nazarov, STOC 2017, with Alex Zhai, FOCS 2017 and with Nina Holden & Robin Pemantle, preprint (2017).)

In this talk we discuss the fine scale $L^2$-mass distribution of toral Laplace eigenfunctions with respect to random position. For the 2-dimensional torus, under certain flatness assumptions on the Fourier coefficients of the eigenfunctions and generic restrictions on energy levels, both the asymptotic shape of the variance and the limiting Gaussian law are established, in the optimal Planck-scale regime. We also discuss the 3-dimensional case, where the asymptotic behaviour of the variance is analysed in a more restrictive scenario. This is joint work with Igor Wigman.

The random-cluster model is a dependent percolation model where the weight of a configuration is proportional to q to the power of the number of connected components. It is highly related to the ferromagnetic q-Potts model, where every vertex is assigned one of q colors, and monochromatic neighbors are encouraged. Through non-rigorous means, Baxter showed that the phase transition is first-order whenever $q > 4$ - i.e. there are multiple Gibbs measures at criticality. We provide a rigorous proof of this claim. Like Baxter, our proof uses the correspondence between the above models and the six-vertex model, which we analyze using the Bethe ansatz and transfer matrix techniques. We also prove Baxter's formula for the correlation length of the models at criticality.

This is joint work with Hugo Duminil-Copin, Maxime Gangebin, Ioan Manolescu, and Vincent Tassion.

In this talk, I will try to present some techniques to handle the problem of large deviations of the spectrum of random matrices. I will focus on the case of macroscopic statistics of the spectrum of Hermitian matrices - in particular Wigner matrices - as the empirical distribution of the eigenvalues, the largest eigenvalue or the traces of powers.

In a first part, I will be concerned with the so-called "objective method''. Coined by David Aldous, this method consists in introducing, given a sequence of random objects, like random finite graphs, a new infinite random object from which one can deduce asymptotic properties of the original sequence. In the context of random matrices, this method has been mainly advertised by Balint Virag, and proven effective in showing universality results for the so-called beta-ensembles. Regarding large deviations of random matrices, this "objective method'' amounts to embed our sequence of matrices with growing size into an appropriate space on which one is able to understand the large deviations, and carry out a contraction principle. I will review several large deviations principles obtained by this method, given by interpretations of random matrices as either dense or sparse graphs, and point out the limits of this strategy.

Consider a real Gaussian stationary process, either on Z or on R.

What is the probability that it remains positive on [0,N] for large N?

The relation between this probability, known as the persistence probability, and the covariance kernel of the process has been investigated since the 1950s with motivations stemming from probability, engineering and mathematical physics. Nonetheless, until recently, good estimates were known only for particular cases, or when the covariance kernel is either non-negative or summable.

In the first hour of the talk we will discuss new spectral methods which greatly simplify the analysis of persistence. We will then describe its qualitative behavior in a very general setting.

In the second hour, we will describe (very) recent progress. In particular we will show the proof of the "spectral gap conjecture'', which states: if the spectral measure vanishes on an interval containing 0 then the persistence is less then e^{-cN^2}, and this bound is tight if the measure is non-singular and compactly supported.

Time permitting, we will also discuss "tiny persistence'' phenomena (of the order of e^{-e^{cN}}).

Based on joint works with Ohad Feldheim, Benjamin Jaye, Fedor Nazarov and Shahaf Nitzan.

A determinantal point process governed by a locally trace class Hermitian contraction kernel on a measure space $E$ remains determinantal when conditioned on its configuration on an arbitrary measurable subset $B \subset E$. Moreover, the conditional kernel can be chosen canonically in a way that is "local" in a non-commutative sense, i.e. invariant under "restriction" to closed subspaces $L^2(B) \subset P \subset L^2(E)$.

Using the properties of the canonical conditional kernel we establish a conjecture of Lyons and Peres: if $K$ is a projection then almost surely all functions in its image can be recovered by sampling at the points of the process.

Given a quadratic form Q in d variables over the integers, e.g. Q(x,y,z) = xy - z^2, and a set of positive density E in Z^d, we investigate what kind of structure can be found in the set Q(E-E).

We will see that if d >= 3, and Q is indefinite, then the measure rigidity, due to Bourgain-Furman-Lindenstrauss-Mozes or Benoist-Quint, of the action of the group of the symmetries of Q implies that there exists k >=1 such that k^2*Q(Z^d) is a subset of Q(E-E).

We will give an alternative proof of the theorem for the case Q(x,y,z) = xy - z^2 that uses more classical equidistribution results of Vinogradov, and Weyl, as well as a more recent result by Frantzikinakis-Kra. The latter proof extends the theorem to other polynomials having a much smaller group of symmetries. Based on joint works with M. Bjorklund (Chalmers), and K. Bulinski (Sydney).

Let M be a smooth, compact, connected two-dimensional, Riemannian manifold without boundary, and let C_epsilon be the amount of time needed for the Brownian motion to come within (Riemannian) distance epsilon of all points in M. The first order asymptotics of C_epsilon as epsilon goes to 0 are known. We show that for the two dimensional sphere

\sqrt{C_epsilon}-2\sqrt{2}\( \log \epsilon^{-1}- \frac{1}{4}\log\log \epsilon^{-1}\) is tight.

Joint work with David Belius and Ofer Zeitouni.

**First Speaker: Ran Tessler (ETH)**

Time: 11:00

Title: A sharp threshold for Hamiltonian spheres in a random 2-complex.

Abstract: We define the notion of Hamiltonian sphere - a 2-complex homeomorphic to a sphere which uses all vertices. We prove an explicit sharp threshold for the appearance of Hamiltonian spheres in the Linial-Meshulam model for random 2-complexes. The proof combines combinatorial, probabilistic and geometric arguments. Based on a joint work with Zur Luria.

**Second Speaker: Assaf Naor (Princeton)**

Time: 12:00

Title: A new vertical-versus-horizontal isoperimetric inequality on the Heisenberg group, with applications to metric geometry and approximation algorithms

Abstract: In this talk we will show that for every measurable subset of the Heisenberg group of dimension at least 5, an appropriately defined notion of its "vertical perimeter" is at most a constant multiple of its horizontal (Heisenberg) perimeter. We will explain how this new isoperimetric-type inequality solves open questions in analysis (an endpoint estimate for a certain singular integral on W^{1,1}), metric geometry (sharp nonembeddability into L_1) and approximation algorithms (asymptotic evaluation of the performance of the Goemans-Linial algorithm for the Sparsest Cut problem). Joint work with Robert Young.

Consider the Gaussian Entire Function (GEF) whose Taylor coefficients are independent complex-valued Gaussian variables, and the variance of the k-th coefficient is 1/k!. This random Taylor series is distinguished by the invariance of its zero set with respect to the isometries of the complex plane.

I will show that the law of the zero set, conditioned on the GEF having no zeros in a disk of radius r, and properly normalized, converges to an explicit limiting Radon measure in the plane, as r goes to infinity. A remarkable feature of this limiting measure is the existence of a large 'forbidden region' between a singular part supported on the boundary of the (scaled) hole and the equilibrium measure far from the hole. This answers a question posed by Nazarov and Sodin, and is in stark contrast to the corresponding result known to hold in the random matrix setting, where such a gap does not appear.

The talk is based on a joint work with S. Ghosh.

Given a dynamical system, a partition of the space induces a mapping to the space of sequences of the partition elements (a point is mapped to the partition elements containing its orbit terms). Such a duality is called Symbolic Dynamics, Markov partitions are an important tool, as the symbolic dynamics they induce enfold many of the important dynamical properties of the original system, and they allow an easier studying of them.

We show that general non uniformly hyperbolic C^{1+epsilon} diffeomorphism on compact manifolds of any dimension admit countable Markov partitions. Previously this was only known in dimension 2.

If $X$ is a finite set, the $p$-biased measure on the power-set of $X$ is defined as follows: choose a subset $S$ of $X$ at random by including each element of $X$ independently with probability $p$. If $\mathcal{F}$ is a family of subsets of $X$, one can consider the {\em $p$-biased measure} of $\mathcal{F}$, denoted by $\mu_p(\mathcal{F})$, as a function of $p$; if $\mathcal{F}$ is closed under taking supersets, then this function is an increasing function of $p$. Seminal results of Friedgut and Friedgut-Kalai give criteria for this function to have a 'sharp threshold'. A careful analysis of the behaviour of this function also yields some rather strong results in extremal combinatorics which do not explicitly mention the $p$-biased measure - in particular, in the field of {\em Erd\H{o}s-Ko-Rado type problems}, which concern the sizes of families of objects in which any two (or three...) of the objects 'agree' or 'intersect' in some way. We will discuss some of these, including a recent proof of an old conjecture of Frankl that a symmetric three-wise intersecting family of subsets of $\{1,2,\ldots,n\}$ has size $o(2^n)$, and some 'stability' results characterizing the structure of 'large' $t$-intersecting families of $k$-element subsets of $\{1,2,\ldots,n\}$. Based on joint work with (subsets of) Nathan Keller, Noam Lifshitz and Bhargav Narayanan.

There are numerous essentially equivalent characterizations of mixing in $L_1$ of a finite Markov chain. Some of these characterizations involve natural probabilistic concepts such as couplings, stopping times and hitting times. In contrast, while there are several analytic and geometric tools for bounding the $L_2$ mixing time, none of them are tight and they do not have a probabilistic interpretation.

We provide tight probabilistic characterizations in terms of hitting times distributions for mixing in $L_2$ (for normal chains) and (under reversibility) in relative entropy. This is done by assigning appropriate penalty (depending on the size of the set) to the case that the chain did not escape from a certain set.

We also prove a new extremal characterization of the log-sobolev constant in terms of a weighted version of the spectral gap (where the weight depends on the size of the support of the function).

Projection inequalities bound the volume of a body in terms of a product of the volumes of lower-dimensional projections of the body. Two well-known examples are the Loomis-Whitney inequality and the more general Uniform Cover inequality. We will see how to use information theory to prove stability versions of these inequalities, showing that when they are close to being tight, the body in question is close to being a box (which is the unique case of equality). We will also see how to obtain a stability result for the edge-isoperimetric inequality in the infinite d-dimensional lattice. Namely, that a subset of Z^d with small edge-boundary must be close in symmetric difference to a d-dimensional cube.

Based on work with David Ellis, Ehud Friedgut and Guy Kindler.

We show that a version of the classical Iterated Log Law of Khinchin, and independently of Kolmogorov from the 1920's, holds for various parameters in the binomial random graph model and in a random 0/1 Bernoulli matrix. In particular, for a constant p, we show that such a law holds for the number of copies of a fixed graph H in G(n,p), we show a similar statement for the number of Hamilton cycles in a random k-uniform hypergraph, provided that k\geq 4. In the graph case (that is, k=2), since the number of Hamilton cycles in G(n,p), denoted by X_n, does not converge to a normal distribution but rather tends to a log-normal distribution (as has been first proved by Janson), we show that a version of the Iterated Log Law holds for \log X_n. We also obtain similar result for the permanent of a 0/1 bernouli random matrix.

No prior knowledge is required.

Joint with Daniel Motealegre and Van Vu.

Heuristically, delocalization for a random matrix means that its normalized eigenvectors look like the vectors uniformly distributed over the unit sphere. This can be made precise in a number of different ways. We show that with high probability, any sufficiently large set of coordinates of an eigenvector carries a non-negligible portion of its Euclidean norm. Our results pertain to a large class of random matrices including matrices with independent entries, symmetric, skew-symmetric matrices, as well as more general ensembles.

Joint work with Roman Vershynin.

Erdös-Ko-Rado (EKR) type theorems yield upper bounds on the size of set families under various intersection requirements on the elements. Stability versions of such theorems assert that if the size of a family is close to the maximum possible then the family itself must be close (in appropriate sense) to a maximum family. In this talk we present an approach to stability versions of EKR-type theorems through isoperimetric inequalities for subsets of the hypercube. We use this approach to obtain tight stability versions of the EKR theorem itself and of the Ahlswede-Khachatrian theorem on t-intersecting families (for k < n/(t+1)), and to show that, somewhat surprisingly, both theorems hold when the "intersection" requirement is replaced by a much weaker requirement. Furthermore, we obtain stability versions of several recent EKR-type results, including Frankl's proof of the Erdös matching conjecture for n>(2s+1)k-s.

Joint work with David Ellis and Noam Lifshitz.

Many questions about properties of a finite group such as random walks, spectrum of Cayley graphs, distribution of word maps etc., can be approached by using “generalized Fourier sum” formulas involving characters of the group. Numerical data show that characters of low dimensional representations of the group contribute the largest terms to these sums. However, relatively little seems to be known about these small representations so a systematic knowledge of them could lead to proofs of some of the properties. The talk will demonstrates, through concrete examples, and numerical simulations, a new method to construct and analyze those small representations, and hence hopefully to solve some of the aforementioned questions.

The talk is intended for non-experts.

This is part from a joint project with Roger Howe (Yale).

Recently, the "information percolation" framework was introduced as a way to obtain sharp estimates on mixing for spin systems at high temperatures, and in particular, to establish cutoff for the Ising model in three dimensions up to criticality from a worst starting state. I will describe how this method can be used to understand the effect of different initial states on the mixing time, both random (''warm start'') and deterministic.

Joint work with Allan Sly.

By a Theorem of Aaronson, normalized Birkhoff sums of positive integrable functions in infinite, ergodic systems either tend to 0 almost surely or there is a subsequence along which every further subsequence tends to infinity. This is not true for normalized symmetric Birkhoff sums where the summation is along a symmetric time interval as there are examples of infinite, ergodic systems for which the absolutely normalized symmetric Birkhoff sums of positive integrable functions may be almost surely bounded away from zero and infinity. In this talk I will start by explaining a variety of transformations (of different nature) satisfying this phenomena, discuss the case main result that the absolutely normalized, symmetric Birkhoff sums of positive integrable functions in infinite, ergodic systems never converge point-wise and there even exists a universal divergence statement. Time permits I will show some examples of actions of other groups which converge and some recent (yet unwritten) results on actions by commuting skew products which are related to self intersection local times.

The contents of this talk are a combination of 3 papers, one of which is a joint work with Benjamin Weiss and Jon Aaronson and another one is work in progress with Jon Aaronson.

The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless *P=NP*), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi graph of *M=Nd/2* edges, the leading correction to *M/2 *(the typical cut size), is *P∗sqrt(NM/2)*. Here *P∗* is the ground state energy of the Sherrington-Kirkpatrick model, expressed analytically via Parisi's formula.

This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.

We consider random polynomials of degree n whose coefficients are i.i.d. distributed over a finite set of integers, with probability at most 1/2 to take any particular value. We show that the probability that such a polynomial of degree n has a double root is dominated by the probability that 0,1 or -1 are double roots up to an error of o(n^{−2}). Our result generalizes a similar result of Peled, Sen and Zeitouni for Littlewood polynomials.

Joint work with Ron Peled and Arnab Sen.

The voter model on $\Z^d$ is a particle system that serves as a rough model for changes of opinions among social agents or, alternatively, competition between biological species occupying space. When $d \geq 3$, the set of (extremal) stationary distributions is a family of measures $\mu_\alpha$, for $\alpha$ between 0 and 1. A configuration sampled from $\mu_\alpha$ is a strongly correlated field of 0's and 1's on $\Z^d$ in which the density of 1's is $\alpha$.

We consider such a configuration as a site percolation model on $\Z^d$. We prove that if $d \geq 5$, the probability of existence of an infinite percolation cluster of 1's exhibits a phase transition in $\alpha$. If the voter model is allowed to have sufficiently spread-out interactions, we prove the same result for $d \geq 3$.

These results partially settle a conjecture of Bricmont, Lebowitz and Maes (1987).

Joint work with Daniel Valesin (University of Groningen)

We consider two stationary versions of the Eden model, on the upper half planar lattice, resulting in an infinite forest covering the half plane. Under weak assumptions on the weight distribution and by relying on ergodic theorems, we prove that almost surely all trees are finite. Using the mass transport principle, we generalize the result to Eden model in graphs of the form $G \times Z$, where G is a Cayley graph. This generalizes certain known results on the two-type Richardson model, in particular of Deijfen and Häggström in 2007.

We will talk on the validity of the mean ergodic theorem along left Følner sequences in a countable amenable group G. Although the weak ergodic theorem always holds along any left Følner sequence in G, we will provide examples where the mean ergodic theorem fails in quite dramatic ways. On the other hand, if G does not admit any ICC quotients, e.g. if G is virtually nilpotent, then we will prove that the mean ergodic theorem does indeed hold along any left Følner sequence. Based on the joint work with M. Björklund (Chalmers).

Consider a random coloring of a bounded domain in *Z ^{d}* with the probability of each coloring

*F*proportional to

*exp(−β∗N(F))*, where

*β>0*is a parameter (representing the inverse temperature) and

*N(F)*is the number of nearest neighboring pairs colored by the same color. This is the anti-ferromagnetic 3-state Potts model of statistical physics, used to describe magnetic interactions in a spin system. The Kotecký conjecture is that in such a model, for

*d≥3*and high enough

*β*, a sampled coloring will typically exhibit long-range order, placing the same color at most of either the even or odd vertices of the domain. We give the first rigorous proof of this fact for large

*d*. This extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the case

*β=∞*.

The main ingredient in our proof is a new structure theorem for 3-colorings which characterizes the ways in which different "phases" may interact, putting special emphasis on the role of edges connecting vertices of the same color. We also discuss several related conjectures. No background in statistical physics will be assumed and all terms will be explained thoroughly.

Joint work with Ohad Feldheim.

Consider a one-dimensional semi-infinite system of Brownian particles, starting at Poisson (L) point process on the positive half-line, with the left-most (Atlas) particle endowed a unit drift to the right. We show that for the equilibrium density (L=2), the asymptotic Gaussian space-time particle fluctuations are governed by the stochastic heat equation with Neumann boundary condition at zero. As a by product we resolve a conjecture of Pal and Pitman (2008) about the asympotic (random) fBM trajectory of the Atlas particle.

In a complementary work, we derive and explicitly solve the Stefan (free-boundary) equations for the limiting particle-profile when starting at out of equilibrium density (L other than 2). We thus determine the corresponding (non-random) asymptotic trajectory of the Atlas particle.

This talk is based on joint works with Li-Cheng Tsai, Manuel Cabezas, Andrey Sarantsev and Vladas Sidoravicius.

Consider a random finite metric space X given by sampling n points in the unit interval uniformly, and a deterministic finite metric space U given by placing n points in the unit interval at uniform distance. With high probability, X will contain some pairs of points at distance roughly 1/n^2, so any bijection from X to U must distort distances by a factor of roughly n. However, with high probability, two of these random spaces, X_1 and X_2, have a bijection which distorts distances by a factor of only about n^2/3. The exponent of 2/3 is optimal.

In the famous KKL (Kahn-Kalai-Linial) paper of 1988 the authors "imported" to combinatorics and theoretical computer science a hypercontractive inequality known as Beckner's ineqaulity (proven first, independently, by Gross and Bonami). This inequality has since become an extremely useful and influential tool, used in tens of papers, in a wide variety of settings. In many cases there are no proofs known that do not use the inequality.

In this talk I'll try to illuminate the information theoretic nature of both the inequality and its dual, touch upon a proof of the dual version from about a decade ago, (joint with V. Rodl), and a fresh (and unrelated) information theoretic proof of the primal version.

No prior knowledge will be assumed regarding discrete Fourier analysis, Entropy, and hypercontractivity.

Branching processes have been subject of intense and fascinating studies for a long time. In my talk I will present two problems in order to highlight their rich structure and various technical approaches in the intersection of probability and analysis.

Firstly, I will present results concerning a branching random walk with the time-inhomogeneous branching law. We consider a system of particles, which at the end of each time unit produce offspring randomly and independently. The branching law, determining the number and locations of the offspring is the same for all particles in a given generation. Until recently, a common assumption was that the branching law does not change over time. In a pioneering work, Fang and Zeitouni (2010) considered a process with two macroscopic time intervals with different branching laws. In my talk I will present the results when the branching law varies at mesoscopic and microscopic scales. In arguably the most interesting case, when the branching law is sampled randomly for every step, I will present a quenched result with detailed asymptotics of the maximal particle. Interestingly, the disorder has a slowing-down effect manifesting itself on the log level.

Secondly, I will turn to the classical branching Brownian motion. Let us assume that particles move according to a Brownian motion with drift μ and split with intensity 1. It is well-know that for μ≥2√ the system escapes to infinity, thus the overall minimum is well-defined. In order to understand it better, we modify the process such that the particles are absorbed at position 0. I will present the results concerning the law of the number of absorbed particles N. In particular I will concentrate on P(N=0) and the maximal exponential moment of N. This reveals new deep connections with the FKPP equation. Finally, I will also consider −2√<μ<2√ and Nxt the number of particles absorbed until the time t when the system starts from x. In this case I will show the convergence to the traveling wave solution of the FKPP equation for an appropriate choice of x,t−>∞.

The results were obtained jointly with B. Mallein and with J. Berestycki, E. Brunet and S. Harris respectively.

Imagine that every vertex of a graph contains a sleeping frog. At time 0, the frog at some designated vertex wakes up and begins a simple random walk. When it lands on a vertex, the sleeping frog there wakes up and begins its own simple random walk, which in turn wakes up any sleeping frogs it lands on, and so on. This process is called the frog model.

I'll talk about a question posed by Serguei Popov in 2003: On an infinite d-ary tree, is the frog model recurrent or transient? That is, is each vertex visited infinitely or finitely often by frogs? The answer is that it depends on d: there's a phase transition between recurrence and transience as d grows. Furthermore, if the system starts with Poi(m) sleeping frogs on each vertex independently, there's a phase transition as m grows. This is joint work with Christopher Hoffman and Matthew Junge.

Examine random walk in a stationary, ergodic, random environment which is bistochastic i.e. the sum of probabilities to enter any fixed vertex is 1. Consider the drift as a function on the probability space on the environments, and assume it belongs to domain of definition of where D is the symmetrized generator of the walk (this is the famous condition). We show that under these conditions the walk satisfies a central limit theorem. The proof uses the "relaxed sector condition" which shows an unexpected connection to the spectral theory of unbounded operators.

All terms will be explained in the talk. This is joint work with Balint Toth.