Geometric Functional Analysis & Probability Seminar

Thursday 11:10-13:00, Ziskind 155 map, directions.

To suggest a talk (yours or somebody else's) contact Ronen Eldan, Itai Benjamini, Gady Kozma or Gideon Schechtman.

To join the mailing list, contact Ronen Eldan. This seminar also has a google calendar entry: Weizmann - GFAP Seminar  (Geometric Functional Analysis and Probability)

Upcoming talks

June 29th

Amir Dembo (Stanford)

The criticality of a randomly-driven front

Consider independent continuous-time random walks on the integers to the right of a front R(t). Starting at R(0)=0, whenever a particle attempts to jump into the front, the latter instantaneously advances k steps to the right, absorbing all particles along its path. Sly (2016) resolves the question of Kesten and Sidoravicius (2008), by showing that for k=1 the front R(t) advances linearly once the particle density exceeds 1, but little is known about the large t asymptotic of R(t) at critical density 1. In a joint work with L-C Tsai, for the variant model with k taken as the minimal random integer such that exactly k particles are absorbed by the move of R(t), we obtain both scaling exponent and the random scaling limit for the front at the critical density 1. Our result unveils a rarely seen phenomenon where the macroscopic scaling exponent is sensitive to the initial local fluctuations (with the scaling limit oscillating between instantaneous super and sub-critical phases).

List of previous talks sorted backwards

June 15th

Pyotr Nayar (Technion)

Gaussian mixtures with applications to entropy inequalities and convex geometry

We say that a symmetric random variable X is a Gaussian mixture if X has the same distribution as YG, where G is a standard Gaussian random variable, and Y is a positive random variable independent of G. In the first part of the talk we use this simple notion to study the Shannon entropy of sums of independent random variables. In the second part we investigate, using Gaussian mixtures, certain topics related to the geometry of $B_p^n$ balls, including optimal Khinchine-type inequalities and Schur-type comparison for volumes of section and projections of these sets. In the third part we discuss extensions of Gaussian correlation inequality to the case of p-stable laws and uniform measure on the Euclidean sphere. Based on a joint work with Alexandros Eskenazis and Tomasz Tkocz.

June 8th

Nishant Chandgotia (Tel Aviv University)

Irrational rotations, random affine transformations and the central limit theorem

It is a well-known result from Hermann Weyl that if alpha is an irrational number in [0,1) then the number of visits of successive multiples of alpha modulo one in an interval contained in [0,1) is proportional to the size of the interval. In this talk we will revisit this problem, now looking at finer joint asymptotics of visits to several intervals with rational end points. We observe that the visit distribution can be modelled using random affine transformations; in the case when the irrational is quadratic we obtain a central limit theorem as well. Not much background in probability will be assumed. This is in joint work with Jon Aaronson and Michael Bromberg.

March 9th

Sasha Shamov

Conditional determinantal processes are determinantal

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.

Feb 9th

Alexander Fish (Sydney)

The values of quadratic forms on difference sets, measure rigidity and equidistribution.

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).

Jan 19th

Jay Rosen

Tightness for the Cover Time of $S^{2}$

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}\left( \log \epsilon^{-1}- \frac{1}{4}\log\log \epsilon^{-1}\right)$is tight. Joint work with David Belius and Ofer Zeitouni.

Jan 12th

Ran Tessler (ETH) + Assaf Naor (Princeton)

Ran Tessler (11:00): A sharp threshold for Hamiltonian spheres in a random 2-complex

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.

Assaf Naor (12:00): A new vertical-versus-horizontal isoperimetric inequality on the Heisenberg group, with applications to metric geometry and approximation algorithms.

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.

Jan 5th

Amir Dembo

Title: Walking within growing domains: recurrence versus transience

When is simple random walk on growing in time d-dimensional domains recurrent? For domain growth which is independent of the walk, we review recent progress and related universality conjectures about a sharp recurrence versus transience criterion in terms of the growth rate. We compare this with the question of recurrence/transience for time varying conductance models, where Gaussian heat kernel estimates and evolving sets play an important role. We also briefly contrast such expected universality with examples of the rich behavior encountered when monotone interaction enforces the growth as a result of visits by the walk to the current domain's boundary. This talk is based on joint works with Ruojun Huang, Ben Morris, Yuval Peres, Vladas Sidoravicius and Tianyi Zheng.

Dec 29th

Alon Nishry

Gaussian complex zeros on the hole event: the emergence of a forbidden region

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.

Dec 15th

Snir Ben Ovadia

Symbolic dynamics for non uniformly hyperbolic diffeomorphisms of compact smooth manifolds

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.

Nov 17th

Anirban Basak

Title: Invertibility of sparse random matrices

We consider a class of sparse random matrices of the form $A_n =(\xi_{i,j}\delta_{i,j})_{i,j=1}^n$, where $\{\xi_{i,j}\}$ are i.i.d.~centered random variables, and $\{\delta_{i,j}\}$ are i.i.d.~Bernoulli random variables taking value $1$ with probability $p_n$, and prove a quantitative estimate on the smallest singular value for $p_n = \Omega(\frac{\log n}{n})$, under a suitable assumption on the spectral norm of the matrices. This establishes the invertibility of a large class of sparse matrices. We also find quantitative estimates on the smallest singular value of the adjacency matrix of a directed Erd\H{o}s-R\'{e}yni graph whenever its edge connectivity probability is above the critical threshold $\Omega(\frac{\log n}{n})$. This is joint work with Mark Rudelson.

September 14, 14:00-16:00 (note unusual time)!

Assaf Naor (Princeton)

The Lipschitz extension problem for finite dimensional normed spaces

Nov 3rd

David Ellis (Queen Mary U)

Some applications of the $p$-biased measure to Erd\H{o}s-Ko-Rado type problems

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.

June 16, 2016

Double Feature: Eviatar Procaccia (Texas A&M) + Eliran Subag (WIS)

Eviatar Procaccia: Can one hear the shape of a random walk?

We consider a Gibbs distribution over random walk paths on the square lattice, proportional to a random weight of the path's boundary. We show that in the zero temperature limit, the paths condensate around an asymptotic shape. This limit shape is characterized as the minimizer of the functional, mapping open connected subsets of the plane to the sum of their principle eigenvalue and perimeter (with respect to the first passage percolation norm). A prime novel feature of this limit shape is that it is not in the class of Wulff shapes. Joint work with Marek Biskup.

Eliran Subag: Critical points and the Gibbs measure of pure spherical spin glasses.

Recently, several results concerning the critical points of the energy landscape of pure $p$-spin spherical spin glasses have been obtained by means of moment computations and a proof of a certain invariance property. I will describe those and explain how they can be boosted by an investigation of the behavior around the critical points to obtain a geometric description for the Gibbs measure at low enough temperature. The talk is based on joint work with Ofer Zeitouni.

June 23, 2016

Double Feature: Jonathan Hermon (Berkeley) + Shamgar Gurevitch (Madison)

Jonathan Hermon: $L_2$ Mixing and hypercontractivity via maximal inequalities and hitting-times

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).

Shamgar Gurevitch: Small Representations of Finite Classical Groups.

Many properties of a finite group G can be approached using formulas involving sums over its characters. A serious obstacle in applying these formulas seemed to be lack of knowledge over the low dimensional representations of G. In fact, the "small" representations tend to contribute the largest terms to these sums, so a systematic knowledge of them might lead to proofs of some conjectures which are currently out of reach.

May 5, 2016

Double Feature: Tal Orenshtein (Lyon) + Ilya Goldsheid (Queen Mary, London) TBA

Tal Orenshtein: One-dependent walks in hypergeometric-Dirichlet environments

Dirichlet environments are one of the few examples in Random Walk in Random Environment in which some non-trivial random walk properties are fully and explicitly characterized in terms of the parameters. A key feature of the model is the so-called 'time reversal property', saying that inverting the time is resulting in the same class of models, with an explicit change of parameters. In this talk, which is based on a joint work in process with Christophe Sabot, I'll present a generalization of random walks in Dirichlet environments using hypergeometric functions having that nice feature, and discuss the question of existence of an invariant probability measure for the process on the environments from the point of view of the walker which is absolutely continuous with respect to the initial measure.

Ilya Goldsheid: Recurrent Random Walks on a Strip: conditions for the CLT.

This is joint work with Dima Dolgopyat. We prove that a recurrent random walk (RW) in i.i.d. random environment (RE) on a strip which does not obey the Sinai law exhibits the Central Limit asymptotic behaviour. Moreover, there exists a collection of proper subvarieties in the space of transition probabilities such that: (a) If the RE is stationary and ergodic and the transition probabilities are concentrated on one of sub-varieties from our collection then the CLT holds; (b) If the environment is i.i.d then the above condition is also necessary for the CLT to hold. In particular, the CLT holds for the quasiperiodic environments with Diophantine frequencies in the recurrent case and complement this result by proving that in the transient case the CLT holds for all strictly ergodic environments.

April 21st, 2016

Atilla Yilmaz, Istanbul, Large deviations for random walk in space-time random environment: averaged vs. quenched

I will present recent joint work with F. Rassoul-Agha (Utah) and T. Seppalainen (Madison) where we consider random walk on a hypercubic lattice of arbitrary dimension in a space-time random environment that is assumed to be temporally independent and spatially translation invariant. The large deviation principle (LDP) for the empirical velocity of the averaged walk (i.e., level-1) is simply Cramer’s theorem. We take the point of view of the particle and establish the process-level (i.e., level-3) averaged LDP for the environment Markov chain. The rate function $I_{3,a}$ is a specific relative entropy which reproduces Cramer’s rate function via the so-called contraction principle. We identify the unique minimizer of this contraction at any velocity and analyse its structure. When the environment is spatially ergodic, the level-3 quenched LDP follows from our previous work which gives a variational formula for the rate function $I_{3,q}$ involving a Donsker-Varadhan-type relative entropy $H_q$. We derive a decomposition formula for $I_{3,a}$ that expresses it as a sum of contributions from the walk (via $H_q$) and the environment. We use this formula to characterize the equality of the level-1 averaged and quenched rate functions, and conclude with several related results and open problems.

March 31, 2016

Amir Yehudayoff, Technion, Geometric stability using information theory

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.

March 17, 2016

Asaf Ferber, Yale, Iterated Log Law for various graph parameters

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 $G(n,p)$ 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.

March 10, 2016.

Mark Rudelson, University of Michigan, No-gaps delocalization for general random matrices

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.

March 3, 2016. Joint with the Geometry and Topology seminar.

Alexei V. Penskoi, Moscow State University, Recent advances in geometric optimization of eigenvalues of the Laplace-Beltrami operator on closed surfaces

Since a metric defines the Laplace-Beltrami operator on a closed surface, the eigenvalues of the Laplace-Beltrami operator are functionals on the space of Riemannian metrics on the surface. A metric is called maximal for i-th eigenvalue if the i-th eigenvalue attends its maximum on this metric. It turns out that the question about finding maximal metrics is very deep and related to analysis, topology, algebraic and differential geometry. In this talk several recent advances in this question will be exposed.

February 18, 2016

Evgeny Strahov, Hebrew University, Determinantal processes related to products of random matrices

I will talk about determinantal processes formed by eigenvalues and singular values of products of complex Gaussian matrices. Such determinantal processes can be understood as natural generalizations of the classical Ginibre and Laguerre ensembles of Random Matrix Theory, and the correlation kernels of these processes can be expressed in terms of special functions/double contour integrals. This enables to investigate determinantal processes for products of random matrices in different asymptotic regimes, and to compute different probabilistic quantities of interest. In particular, I will present the asymptotics for the hole probabilities, i.e. for probabilities of the events that there are no particles in a disc of radius r with its center at 0, as r goes to infinity. In addition, I will explain how the gap probabilities for squared singular values of products of random complex matrices can be described in terms of completely integrable Hamiltonian differential equations, and how to interpret these Hamiltonian differential equations as the monodromy preserving deformation equations of the Jimbo, Miwa, Mori, Ueno and Sato theory. Finally, I will discuss certain time-dependent determinantal processes related to products of random matrices.

February 4, 2016

Gaultier Lambert, KTH Stockholm, Fluctuations of linear statistics of determinantal processes

Determinantal point processes arise in the description of eigenvalues of unitary invariant Hermitian random matrices, as well as in many statistical mechanics models such as random tilings, non-intersecting paths, etc. I will explain a cumulant method developed by A. Soshnikov to analyze the asymptotics distributions of linear statistics of determinantal processes and certain combinatorial identities associated with the sine process. I will present some applications to orthogonal ensembles and, if time permits, to certain biorthogonal ensembles and discuss some models which exhibit a transition from Poisson to GUE.

January 28, 2016

Nathan Keller, Bar Ilan, Stability Versions of Erdős-Ko-Rado Type Theorems via Isoperimetry

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.

January 7, 2016

Shamgar Gurevich, Madison, Low Dimensional Representations of Finite Classical Groups

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).

January 6, 2016 Note special day: Wednesday

Eyal Lubetzky, Courant, Effect of initial conditions on mixing for spin systems

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.

December 31, 2015

Zemer Kosloff, Warwick, Symmetric Birkhoff sums in infinite ergodic theory

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 $Z^2$ 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.

December 17, 2015

Amir Dembo, Stanford, Extremal Cuts of Sparse Random Graphs

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 Erdős-Renyi graph of $M=N d/2$ edges, the leading correction to M/2 (the typical cut size), is $P_* sqrt(N M/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.

December 10, 2015

Ohad Feldheim, University of Minnesota, Double Roots of Random Polynomials

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.

December 3, 2015

Ron Rosenthal, ETH, Eigenvalue confinement and spectral gap for random simplicial complexes

We consider the adjacency operator of the Linial-Meshulam model for random simplicial complexes on $n$ vertices, where each $d$-cell is added independently with probability $p$ to the complete $(d-1)$-skeleton. From the point of view of random matrix theory, the adjacency matrix is a sparse, self adjoint random matrix with dependent entries. Under the assumption $np(1-p)>> log^4 n$, we prove that the spectral gap between the $\binom{n-1}{d}$ smallest eigenvalues and the remaining $\binom{n-1}{d-1}$ eigenvalues is $np-2\sqrt{dnp(1-p)}(1+o(1))$ with high probability. This estimate follows from a more general result on eigenvalue confinement. In addition, we prove that the global distribution of the eigenvalues is asymptotically given by the semicircle law. Based on a joint work with Antti Knowles.

November 26, 2015

Yaar Solomon, Stony Brook University, The Danzer problem and a solution to a problem of Gowers

Is there a point set $Y$ in $R^d$, and $C>0$, such that every convex set of volume 1 contains at least one point of $Y$ and at most $C$? This discrete geometry problem was posed by Gowers in 2000, and it is a special case of an open problem posed by Danzer in 1965. I will present two proofs that answers Gowers' question with a NO. The first approach is dynamical; we introduce a dynamical system and classify its minimal subsystems. This classification in particular yields the negative answer to Gowers' question. The second proof is direct and it has nice applications in combinatorics. The talk will be accessible to a general audience. [This is a joint work with Omri Solan and Barak Weiss].

November 12, 2015

Christopher Joyner, Bristol, Random Walk approach to spectral statistics in random Bernoulli matrices

Random Bernoulli matrices (in which the matrix elements are chosen independently from plus or minus 1 with equal probability) are intimately connected to the adjacency matrices of random graphs and share many spectral properties. In the limit of large matrix dimension the distribution of eigenvalues from such matrices resembles that from matrices in which the elements are chosen randomly from a Gaussian distribution - the question is why? We take a dynamical approach to this problem, which is achieved by initiating a discrete random walk process over the space of matrices. Previously we have used this idea to analyse the corresponding eigenvalue motion but I will discuss some recent developments which involve the adaptation of Stein’s method to this context.

August 6, 2015 Note special place: de Picciotto 208

Balázs Ráth, Budapest University of Technology, Voter model percolation

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)

July 30, 2015

Eviatar Procaccia, UCLA, Stationary Eden model on groups

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.

July 16, 2015. Note special place: Ziskind 1

Alexander Fish, University of Syndney, Ergodic theorems for amenable groups

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).

July 9, 2015

Dan Florentin, Weizmann, Stability and Rate of Convergence of the Steiner Symmetrization.

We present a direct analytic method towards an estimate for the rate of convergence (to the Euclidean Ball) of Steiner symmetrizations. To this end we present a modified version of a known stability property of Steiner symmetrization.

June 25, 2015

Yinon Spinka, Tel Aviv, Long-range order in random 3-colorings of $Z^d$

Consider a random coloring of a bounded domain in $Z^d$ with the probability of each coloring F proportional to $\exp(-\beta*N(F))$, where $\beta>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\ge 3$ and high enough $\beta$, 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 $\beta=\infty$.

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.

June 18, 2015

Amir Dembo, Stanford, The Atlas model, in and out of equilibrium.

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.

June 11, 2015

Anton Malyshev, Weizmann, Metric distortion between random finite subsets of the interval

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.

June 4, 2015

Mark Rudelson, University of Michigen, Approximation complexity of convex bodies.

Consider the approximation of an n-dimensional convex body by a projection of a section of an N-dimensional simplex, and call the minimal N for which such approximation exists the approximation complexity of the body. The reason for such strange definition lies in computer science. A projection of a section of a simplex is the feasible set of a linear programming problem, and so it can be efficiently generated. We will discuss how large the approximation complexity of different classes of convex bodies can be.

May 28, 2015

Gerard Ben Arous, Courant, The ant in the labyrinth: recent progress

May 21, 2015

Lenya Ryzhik, Standford, The weakly random Schroedinger equation: a consumer report

Consider a Schroedinger equation with a weakly random time-independent potential. When the correlation function of the potential is, roughly speaking, of the Schwartz class, it has been shown by Spohn (1977), and Erdős and Yau (2001) that the kinetic limit holds -- the expectation of the phase space energy density of the solution converges weakly (after integration against a test function, not in the probabilistic sense) to the solution of a kinetic equation. We "extend" this result to potentials whose correlation functions satisfy (in some sense) "sharp" conditions, and also prove a parallel homogenization result for slowly varying initial conditions. I will explain the quotation marks above and make some speculations on the genuinely sharp conditions on the random potential that separate various regimes. This talk is a joint work with T. Chen and T. Komorowski

May 20, 2015 Note special day: Wednesday

Kate Juschenko, Northwestern University, Amenability of subgroups of interval exchange transformation group

May 14, 2015

Students probability day V, in memory of Oded Schramm. See here.

May 7, 2015

Ehud Friedgut, Weizmann, An information theoretic proof of a hypercontractive inequality.

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.

April 16, 2015

Piotr Miłoś, University of Warsaw, Extremal individuals in branching systems.

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 $\mu$ and split with intensity 1. It is well-know that for $\mu\geq \sqrt{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 $-\sqrt{2}<\mu<\sqrt{2}$ and $N_t^x$ 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->\infty$.

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

March 26, 2015

Tom Hutchcroft, University of British Columbia, Hyperbolic and Parabolic Random Maps

We establish a sharp division of infinite random planar graphs into two types, hyperbolic and parabolic, showing that many probabilistic and geometric properties of such a graph are determined by the graph's average curvature, a local quantity which is often easy to compute.

Work in progress with Omer Angel, Asaf Nachmias and Gourab Ray.

March 12, 2015

Toby Johnson, University of South California, The frog model on trees

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.

February 12, 2015

Chaim Even Zohar, Hebrew University, Invariants of Random Knots and Links

We study random knots and links in $R^3$ using the Petaluma model, which is based on the petal projections developed by Adams et al. (2012).

In this model we obtain a formula for the distribution of the linking number of a random two-component link. We also obtain formulas for the expectations and the higher moments of the Casson invariant and the order-three knot invariant v3. These are the first precise formulas given for the distributions of invariants in any model for random knots or links.

All terms above will be defined and explained.

Joint work with Joel Hass, Nati Linial, and Tahl Nowik.

February 5, 2015

Yuval Peled, Hebrew University, On the phase transition in random simplicial complexes

It is well-known that the $G(n,p)$ model of random graphs undergoes a dramatic change around $p=1/n$. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant connected component. Several years ago, Linial and Meshulam have introduced the $X_d(n,p)$ model, a probability space of $n$-vertex $d$-dimensional simplicial complexes, where $X_1(n,p)$ coincides with $G(n,p)$. Within this model we prove a natural $d$-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real $d$-th homology of complexes from $X_d(n,p)$, and show that it is strictly greater than the threshold of $d$-collapsibility. In addition, we compute the real Betti numbers, i.e. the dimension of the homology groups, of $X_d(n,p)$ for $p=c/n$. Finally, we establish the emergence of giant shadow at this threshold. (For $d=1$ a giant shadow and a giant component are equivalent). Unlike the case for graphs, for $d > 1$ the emergence of the giant shadow is a first order phase transition. The talk will contain the necessary toplogical backgorund on simplicial complexes, and will focus on the main idea of the proof: the local weak limit of random simplicial complexes and its role in the analysis of phase transitions.

Joint work with Nati Linial.

January 29, 2015

Gady Kozma, Weizmann, Random walk in random environment: the operator theory approach

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 $D^{-1/2}$ where $D$ is the symmetrized generator of the walk (this is the famous $H_{-1}$ 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 Bálint Tóth.

January 22, 2015

Thomas Leblé, Paris, Large deviations for the empirical field of Coulomb and Riesz systems

We study a system of N particles with Coulomb/Riesz pairwise interactions under a confining potential. After rescaling we deal with a microscopic quantity, the associated empirical point process, for which we give a large deviation principle whose rate function is the sum of a relative entropy and of the "renormalized energy" defined by Sandier-Serfaty. We also present applications to point processes emerging from random matrix theory. This is joint work with S. Serfaty.

January 15, 2015

Naomi Feldheim, University of Minnesota, Persistence Probability for Stationary Gaussian processes

The $N$ persistence probability of a stationary process is the probability that it is positive on a time interval of length $N$. On the integers, the independent sequence has persistence probability $2^{-N}$. It is therefore natural to conjecture that in general, given sufficient independence, the persistence probability of stationary Gaussian processes will decay exponentially.

In the talk we formulate in spectral language simple broad sufficient conditions for upper and lower exponential bounds on the persistence probability. The results hold also for Gaussian processes on the real line, and generalize bounds given by Newell and Rosenblatt in the 1960's, and by Antezana, Buckley, Marzo and Olsen in 2012.

Joint work with Ohad Feldheim.

January 14, 2015 Note special day and time: Wednesday, 16:00

Aglaia Myropolska, Geneva, On Nielsen equivalence in finitely generated groups

Various problems from group theory, geometry and combinatorics motivate the study of the natural action of the group $Aut(F_n)$ on the set $Epi(F_n, G)$ of generating $n$-tuples in a group $G$ generated by at least $n$ elements. This action was mainly studied in the case when $G$ is finite. We shall consider the situation when $G$ is infinite and after an introduction into the subject we will discuss some new results on transitivity and non-amenability of this action.

January 8, 2015

Ron Rosenthal, ETH Zürich, Simplicial branching random walks.

We will discuss a new stochastic process on general simplicial complexes which allows to study their spectral and homological properties. Some results for random walks on graphs will be shown to hold in this general setting. As an application we will show how to use the process to construct solutions to the high-dimensional Dirichlet problem for forms and to calculate the spectral measures of high-dimensional analogues of regular-trees.

January 1, 2015

Ohad Feldheim, University of Minnesota, Avoidance Coupling

A simple avoidance coupling on a graph, is a coupling of discrete time simple random walks, which take turns moving on the graph without colliding. O. Angel, A. E. Holroyd, J. Martin, D. B. Wilson and P. Winkler showed that on the complete graph on n vertices there is a simple avoidance coupling of $C(n/log n)$ random walks. We improve this result, getting a linear lower bound of $n/4$ on the number of walks that can be thus coupled. To do this we introduce a new generalization of simple avoidance coupling which we call partially-ordered simple avoidance coupling, and explore its properties.

December 25, 2014

Scott Armstrong, Université Paris-Dauphine, Regularity theory for random elliptic equations

The talk will concern elliptic equation with random coefficients (the equivalent probability model is a random walk in a random environment or the random conductance model). Recently, there has been a lot of progress made in the understanding the quantitative behavior of solutions of these equations, and it turns out that at the heart of this new theory is the fact that solutions of random equations are more regularity than solutions of a general equation (i.e., they are essentially Lipschitz continuous rather than just $C^\alpha$, according to De Giorgi-Nash-Moser theory). I will give a new method for obtaining such results which turn out to be optimal in stochastic integrability.

December 18, 2014 Note unusual time: 10:30

Alexander Fish, University of Syndney, Plunnecke inequalities in countable abelian groups — general case.

Plunnecke inequalities for sumsets of finite sets in abelian groups are extended to measure-preserving systems (mps). For a set A in a group, and a set B of positive measure in mps, we estimate the measure of the union of translations along the set A of B. To prove the new inequalities we extend the graph-theoretic method recently developed by Petridis to "measure graphs". As an application, through Furstenberg's correspondence principle, we obtain the new Plunnecke type inequalities for lower and upper Banach density in countable abelian groups. Based on joint works with M. Bjorklund, Chalmers, and with Kamil Bulinski, Sydney.

December 11, 2014

Daniel Ueltschi, Warwick, On the random interchange model and quantum spin systems

The random interchange model gives a faithful representation of quantum spin systems such as the Heisenberg ferromagnet. Quantum correlations are given in terms of cycle correlations. I will review the precise correspondence and describe rigorous results and open conjectures.

December 4, 2014

Karim Adiprasito, Hebrew University, Whitney numbers of matroids via measure concentration in configuration varieties

We provide a simple proof of the Rota-Heron-Welsh conjecture for matroids realizable as c-arrangements in the sense of Goresky-MacPherson: we prove that the coefficients of the characteristic polynomial of the associated matroids form log-concave sequences, proving the conjecture for a family of matroids out of reach for all previous methods. To this end, we study the Lévy--Milman measure concentration phenomenon on natural pushforwards of uniform measures on the Grassmannian to realization spaces of arrangements under a certain extension procedure on matroids.

November 20, 2014

Yan Dolinsky, Hebrew University, Martingale Inequalities and Model Independent Arbitrage Theory

The topic of Model Independent Arbitrage leads to non trivial and open questions in Martingale theory. In this talk I will discuss the connection between the fields and some of the recent results in Martingale theory, which were motivated by the topic of Model Independent Arbitrage.

November 6, 2014

Victor Kleptsyn, Rennes, TBA

October 30, 2014

Moon Duchin, Tuft, Statistical hyperbolicity

One way to loosen up the condition that a space be hyperbolic is to sample points at random and see whether distance measurements tend to look as they would in a hyperbolic space. For instance, sample random points from the ball of radius $R$ and see whether their distance is asymptotic to $2R$ as $R$ goes to infinity. I will discuss this problem in various settings, including nilpotent groups (where the answer is no) and Teichmüller space (where the answer is yes).

August 28, 2014

Laurie Field, Chicago, Two-sided radial SLE and length-biased chordal SLE

Models in statistical physics often give measures on self-avoiding paths. We can restrict such a measure to the paths that pass through a marked point, obtaining a "pinned measure". The aggregate of the pinned measures over all possible marked points is just the original measure biased by the path's length. Does the analogous result hold for SLE curves, which appear in the scaling limits of many such models at criticality? We show that it does: the aggregate of two-sided radial SLE is length-biased chordal SLE, where the path's length is measured in the natural parametrisation.

July 24, 2014

Eviatar Procaccia, UCLA, Quenched invariance principle for simple random walk on clusters in correlated percolation models.

Quenched invariance principle and heat kernel bounds for random walks on in finite percolation clusters and among i.i.d. random conductances in $Z^d$ were proved during the last two decades. The proofs of these results strongly rely on the i.i.d structure of the models and some stochastic domination with respect to super-critical Bernoulli percolation. Many important models in probability theory and in statistical mechanics, in particular, models which come from real world phenomena, exhibit long range correlations. In this talk I will present a new quenched invariance principle, for simple random walk on the unique infinite percolation cluster for a general class of percolation models on $Z^d$, $d\geq2$, with long-range correlations. This gives new results for random interlacements in dimension $d\geq3$ at every level, as well as for the vacant set of random interlacements and the level sets of the Gaussian free field in the regime of the so-called local uniqueness (which is believed to coincide with the whole supercritical regime). An essential ingredient of the proof is a new isoperimetric inequality for correlated percolation models.

Joint work with Ron Rosenthal and Artem Sapozhnikov.

June 26, 2014

David Ellis, Weizmann, The structure of graphs which are locally lattice-like

There is a large body of results on random n-vertex, d-regular graphs, for d fixed and n large. Asymptotic formulae for the number of labelled and unlabelled d-regular graphs on n vertices were determined by Bender-Canfield and Bollobas, respectively. Amongst many other facts, it is now known that a random d-regular graph almost surely has trivial automorphism group, is almost surely Hamiltonian, is almost surely an expander and is almost surely d-connected. (These theorems were proved by Bollobas in the 1980's, the last also independently by Wormald.)

It is natural to ask what happens when we impose a local condition which is stronger than being regular. If G is a graph, and (F,w) is a rooted graph, we say that G is r-locally-F if for any vertex v of G, the subgraph of G induced by the ball of radius r around v is isomorphic to the subgraph of F induced by the ball of radius r around w. As an example we ask for a determination of the typical properties of an n-vertex graph which is r-locally-$Z^2$, for fixed r. We give an explicit description of the n-vertex graphs which are 2-locally-$Z^2$, and of the n-vertex graphs which are 3-locally-$Z^d$, for $d >=3$. We also study some of their typical properties, e.g. the size of the largest component. The proofs use methods and results from algebraic topology and number theory, as well as from combinatorics.

Joint work with Itai Benjamini.

June 19, 2014

Alain-Sol Sznitman, ETH Zurich, On random interlacements and the Gaussian free field

Random interlacements offer a model for the microscopic structure left by random walks on large recurrent graphs, which are locally transient. They have been the object of intensive research over the recent years, with a special focus on their percolative properties. Deep links of the model with the Gaussian free field, and with Poisson clouds of Markovian loops have also emerged. We will discuss some of these developments in this talk.

June 12, 2014

Ivan Corwin, Clay Mathematics Institute, Columbia University, Institute Henri Poincare, MIT, Macdonald processes, quantum integrable systems and the Kardar-Parisi-Zhang universality class

Methods originating in representation theory and integrable systems have led to detailed descriptions of new non-Gaussian statistical universality classes. This talk will focus on some of the probabilistic systems (ASEP, q-TASEP, the O'Connell-Yor polymer, and the KPZ equation) and methods (Schur / Macdonald processes and quantum integrable systems) which have played a prominent role in this story.

June 5, 2014

Adela Svejda, Technion, Clock processes on infinite graphs and aging in Bouchaud's asymmetric trap model

A clock process is the total time that elapses along a given length of the trajectory of a random motion. It is the key object in connection with aging - a phenomenon of random dynamics in random environments whose convergence towards equilibrium becomes slower as time elapses. Based on a method for proving convergence of partial sum processes due to Durrett and Resnick, convergence criteria for clock processes were established for dynamics on finite graphs by Bovier and Gayrard. In this talk, we study dynamics that are defined on infinite graphs and present general convergence criteria for their clock processes. As an application we prove the existence of a normal aging regime in Bouchaud's asymmetric trap model on $Z^2$, for $d \ge 2$.

This talk is based on joint work with V. Gayrard.

May 29, 2014

Clara Shikhelman, Thresholds of monotone properties with small minterms

Let $X$ be an upward-closed family of subsets of $[n]$, and let $n_p$ be a binomial random subset of $[n]$. We would like to ask how quick does the probability of $n_p$ to be in $X$ change when we increase $p$? The interval of the change from probability almost 0 to probability almost 1 is called the threshold interval, and one often asks how small (sharp threshold) or large (coarse threshold) it is, asymptotically, for a series of $X$'s with $n$ tending to infinity. In this talk we will focus on upwards closed families whose minimal members are of bounded size. This setting is very well understood in the case of the random graph $G(n,p)$, where it corresponds to the appearance of a fixed subgraph. We will: 1) See how much of the conventional wisdom regarding graphs (and expectations of their subgraphs) applies to this general setting, proving a structure theorem regarding such families. 2) Present a simple argument of Riordan implying a uniform bound on the coarseness of thresholds of such families. 3) Use a combination of LP duality and a weighted second moment argument to relate the threshold and the expectation threshold of such families - yielding a (weak) special case of the Kahn-Kalai expectation-threshold conjecture. The talk will be self contained. Joint work with Ehud Friedgut, Jeff Kahn.

May 22, 2014

Jonathan Hermon, University of California, Berkeley, A characterization of mixing and cutoff for reversible Markov chains in terms of hitting times via a new ergodic theory approach and applications

A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. We consider reversible chains whose absolute spectral gap equals to their spectral gap or reversible chains averaged on two consecutive times. We introduce several new cutoff notions and show that they are all equivalent in this setup. One of which is that the hitting time of a "worst" (in some sense) set of stationary measure at least $\alpha$ is concentrated, for some $\alpha \in (0,1)$ (where there is a more general relation even when there is no cutoff). Another two equivalent cutoff notions are weak-separation cutoff and weak-$L^{\infty}$-cutoff (which are some relaxations of the corresponding non-weak form of cutoff).

As an application of our techniques we show that a sequence of Markov chains on trees (with one of the conditions in the second sentence of the abstract) exhibits a cutoff iff the ratio of their relaxation times and their lazy mixing times tends to 0. We show that under a certain mild condition, the same holds also for modifications of birth and death chains in which the chain is allowed to have increments of bounded size.

Joint work with Riddhi Basu and Yuval Peres.

May 15, 2014

Omer Angel, University of British Columbia, Random walks on hyperbolic planar maps

I will describe work with Gourab Ray on hyperbolic planar maps, subsequent work with Nachmias and Ray on random walks in those maps. No knowledge of planer maps will be assumed.

May 8, 2014

Oren Louidor, Technion, Extremes of the discrete Gaussian free field the Z-measure

It was shown recently that the (space-height) extremal process associated with the discrete Gaussian free field converges weakly after thinning, scaling and centering to a Poisson point process whose intensity measure is random. The spacial component of this random intensity - known as the Z-measure, is an analog of the derivative martingale in the (closely related) branching Brownian motion model and exhibits an intricate structure. Further interest in this object stems from its conjectured equivalence (up to a constant scaling) with the critical Gaussian multiplicative chaos of Kahane for the continuous Gaussian free field, recently constructed by Duplantier, Rhodes, Sheffield and Vargas.

In this talk I will discuss various (recently made rigorous) properties of the collection of Z-measures for different domains, such as conformal covariance and the Gibbs-Markov decomposition relation. I will also give more evidence for why the conjectured equivalence with GMC should hold.

Joint work with M. Biskup.

May 1, 2014

Elliot Paquette, Choices and Intervals

Consider the following point process on the unit circle. Finitely many distinct points are placed on the circle in any arbitrary configuration. This configuration of points subdivides the circle into a finite number of intervals. At each time step, two points are sampled uniformly from the circle. Each of these points lands within some pair of intervals formed by the previous configuration. Add the point that falls in the larger interval to the existing configuration of points, discard the other, and then repeat this process. We study the behavior of a typical interval, and we show that as the number of points tends to infinity, this has an almost sure limit, which we characterize.

This joint work with the most excellent Pascal Maillard.

April 3, 2014

Aryeh Kontorovich, Ben Gurion University, Consistency of weighted majority votes

We revisit the classical decision-theoretic problem of weighted expert voting from a statistical learning perspective. In particular, we examine the consistency (both asymptotic and finitary) of the optimal Nitzan-Paroush weighted majority and related rules. In the case of known expert competence levels, we give sharp error estimates for the optimal rule. When the competence levels are unknown, they must be empirically estimated. We provide frequentist and Bayesian analyses for this situation. Some of our proof techniques are non-standard and may be of independent interest. The bounds we derive are nearly optimal, and several challenging open problems are posed. Experimental results are provided to illustrate the theory.

March 27, 2014

Nick Travers, Technion, Inversion statistics and longest increasing subsequence for k-card-minimum random permutations

The $k$-card-minimum procedure for generating a random permutation of $[n] = \{1,...,n \}$ is defined as follows. Begin with a deck of $n$ cards labeled $1,...,n$ and $n$ initially empty positions on a table labeled $1,...,n$ from left to right. Then, at each time $t = 1,...,n$ choose independently and uniformly at random $k$ cards from the remaining $n - t + 1$ cards in the deck, remove the lowest numbered (minimum) of these $k$ cards, and place it on the table in position $t$. The independent sampling is done with replacement, so that the $k$ cards chosen at each time $t$ are not necessarily all distinct.

We prove a weak law of large numbers and central limit theorem for the number of inversions in a random permutation generated according to this procedure, both with fixed $k$ and when $k$ grows sublinearly in $n$. We also establish the rate of growth of the longest increasing subsequence in a random permutation generated according to this procedure when $k$ grows as a sublinear power of $n$ ($k_n \sim n^{\beta}$, for some $0 < \beta < 1$).

March 6, 2014

Ariel Yadin, Ben Gurion University, An inverse Kleiner theorem for linear groups

Geometric group theory starts with the famous theorem by Gromov: A finitely generated group is of polynomial volume growth if and only if it is almost nilpotent.

In 2007 Kleiner gave a new proof of Gromov's theorem, later made elementary by Shalom and Tao. The main part of Kleiner's proof is constructing a finite dimensional representation of a polynomial growth group, using the natural action of the group on the spaces of Lipschitz harmonic functions. Specifically, Kleiner's theorem states that for a polynomial growth group $G$, the space of Lipschitz harmonic functions on $G$ is finite dimensional.

In joint work with Tom Meyerovitch we study the inverse statement: If a finitely generated group $G$ admits a finite dimensional space of Lipschitz harmonic functions, is it true that $G$ must be of polynomial growth (or, equivalently by Gromov, almost nilpotent). Indeed we prove that this is the case when $G$ is a subgroup of $GL(n,C)$. Also, we provide some structure theorems for general groups with finite dimensional Lipschitz harmonic function spaces.

Our proofs are probabilistic, and for the talk I will only assume very basic knowledge of random walks, and the definition of a group.

February 27, 2014

Idan Perl, Ben Gurion University, Extinction window of mean-field branching annihilating random walk

We study a model of growing population that competes for resources. At each time step, all existing particles reproduce and the offspring randomly move to neighboring sites. Then at any site with more than one offspring the particles are annihilated. This is a non-monotone model, which makes the analysis more difficult. We consider the extinction window of this model in the finite mean-field case, where there are $n$ sites but movement is allowed to any site (the complete graph). We show that although the system survives for exponential time, the extinction window is logarithmic.

February 26, 2014 Note unusual day and place: Wednesday, Ziskind 1

Balazs Szegedy, University of Toronto, Random $d$-regular graphs and ergodic theory on the tree

A sizable part of random graph theory deals with the properties of random $d$-regular graphs. Major breakthroughs in the subject include Friedman's solution of Alon's second eigenvalue conjecture and the result by Bayati, Gamarnik and Tetali on the convergence of the independence ratio. We give an approach to the subject using Benjamini-Schramm convergence and ergodic theory that shows great promise in understanding the structure of these graphs.

Part of the talk is joint work with Agnes Backhausz and Balint Virag.

February 20, 2014

Jesse Goodman, Technion, The gaps left by a Brownian motion

Run a Brownian motion in a compact domain for a long time. What are the shapes of the large gaps remaining? This question, while simple to state, has surprising connections to harmonic analysis, potential theory, and complex geometry.

The answer depends strongly on the dimension, and in three or more dimensions the shapes of gaps can be characterized in a largely deterministic way. I will also discuss the conjectured picture in two dimensions, where long range correlations bring the problem into the realm of multiscale, hierarchical models.

February 13, 2014

Etienne Le Masson, Hebrew University of Jerusalem, Quantum ergodicity on large regular graphs

I will present a quantum ergodicity theorem on large regular graphs. This is a result of spatial equidistribution of most eigenfunctions of the discrete Laplacian in the limit of large regular graphs. The proof uses the ergodicity of a natural evolution on the graphs in an analogous way to the quantum ergodicity theorem on compact Riemannian manifolds, which is concerned with the eigenfunctions of the Laplace-Beltrami operator in the large eigenvalue limit. The main tool constructed for the proof of the theorem is a discrete pseudo-differential calculus. It allows to connect the spectral and dynamical properties of the graphs by lifting the eigenfunctions to phase space and showing that they satisfy an invariance property with respect to the evolution. This is a joint work with Nalini Anantharaman.

February 6, 2014

Alexander Fish, University of Sydney, Ergodic Plunnecke inequalities with applications to additive combinatorics

By use of recent ideas of Petridis, we extend Plunnecke inequalities for sumsets of finite sets in abelian groups to the setting of measure-preserving systems. The main difference in the new setting is that instead of a finite set of translates we have an analogous inequality for a countable set of translates. As an application, by use of Furstenberg correspondence principle, we obtain new Plunnecke type inequalities for lower and upper Banach density in countable abelian groups.

Joint work with Michael Bjorklund, Chalmers.

January 30, 2014

Erwin Bolthausen, University of Zurich, On the localization-delocalization critical line for the random copolymer

January 23, 2014

Jay Rosen, CUNY, Loop measures and loop soups

January 16, 2014

Eyal Lubetzky, Microsoft, Harmonic pinnacles in the Discrete Gaussian model

The 2D Discrete Gaussian model gives each height function $\eta: Z^2 \to Z$ a probability proportional to $\exp[-\beta H(\eta)]$, where $\beta$ is the inverse-temperature and $H(\eta) = \sum (\eta_x-\eta_y)^2$ sums over nearest-neighbor bonds $(x,y)$. We consider the model at large fixed $\beta$, where it is flat unlike its continuous analog (the Gaussian Free Field).

We first establish that the maximum height in an $L\times L$ box with 0 boundary conditions concentrates on two integers $M,M+1$ where $M\sim [(2/\pi\beta)\log L\log\log L]^{1/2}$. The key is a large deviation estimate for the height at the origin in $Z^2$, dominated by ``harmonic pinnacles'', integer approximations of a harmonic variational problem. Second, in this model conditioned on $\eta\geq 0$ (a floor), the average height rises, and in fact the height of almost sites concentrates on levels $H,H+1$ where $H\sim M/\sqrt{2}$. This in particular pins down the asymptotics, and corrects the order, in results of Bricmont, El-Mellouki and Fröhlich (1986). Finally, our methods extend to other classical surface models (e.g., restricted SOS), featuring connections to $p$-harmonic analysis and alternating sign matrices.

January 2, 2014

Omer Bobrowski, Duke University, Phase Transitions in Random Cech Complexes

In manifold learning, one often wishes to infer geometric and topological features of an unknown manifold, embedded in a d-dimensional Euclidean space, from a finite (random) point cloud. One topological invariant of a considerable interest is the homology (connected components and holes) of the underlying space.

A common method for recovering the homology of a manifold from a set of random samples, is to cover each point with a d-dimensional ball, and study the union of these balls. By the Nerve Lemma, This method is equivalent to study the homology of the Cech complex generated from the random point cloud.

In this talk we discuss the limiting behavior of random Cech complexes, as the sample size goes to infinity, and the radius of the balls goes to zero. We show that the limiting behavior exhibits multiple phase transitions at different levels, depending on the rate at which the radius of the balls goes to zero. We present the different regimes and phase transitions discovered so far, and observe the nicely ordered fashion in which homology groups of different dimensions appear and vanish.

One interesting consequence of this analysis, is a sufficient condition for the random Cech complex to successfully recover the homology of the original manifold.

December 26, 2013

Michael Aizenman, Princeton University On the ubiquity of the Cauchy distribution in spectral problems

The resolvents of random matrices and of self-adjoint operator are examples of random functions in the Herglotz-Nevanlinna class (H-N). The scaling limit, in which the function is resolved at the scale of eigenvalue spacing, yields random H-N functions $F(x,\omega)$ with discrete spectral measures. We show that for stationary processes the distribution of the individual values of such functions is in the class of Cauchy random variables. This holds rather generally and regardless of higher correlations, such as the presence / absence of level repulsion. In particular the statement applies to both random matrix and Poisson type spectra. The phenomenon will be discussed in the context of random H-N functions and of the scaling limits of spectra of random operators.

(Joint work with Simone Warzel.)

December 25, 2013 Note unusual day: Wednesday

Yuval Peres, Microsoft, Random walks on groups and the Kaimanovich-Vershik 1983 conjecture for lamplighter groups

Let $G$ be an infinite group with a finite symmetric generating set $S$. The corresponding Cayley graph on $G$ has an edge between $x$,$y$ in $G$ if their ratio $xy^{-1}$ is in $S$.

Kaimanovich-Vershik (1983), building on fundamental results of Furstenberg, Derrienic and Avez, showed that $G$ admits non-constant bounded harmonic functions iff the entropy of simple random walk on $G$ grows linearly in time; Varopoulos (1985) showed that this is equivalent to the random walk escaping with a positive asymptotic speed. Kaimanovich and Vershik (1983) also described the lamplighter groups (groups of exponential growth consisting of finite lattice configurations) where (in dimension at least 3) the simple random walk has positive speed, yet the probability of returning to the starting point does not decay exponentially. They conjectured a complete description of the bounded harmonic functions on these groups; In dimension 5 and above, their conjecture was proved by Anna Erschler (2011).

In the talk, I will discuss the background and present a proof of the Kaimanovich-Vershik conjecture for all dimensions, obtained in joint work with Russ Lyons; the case of dimension 3 is the most delicate.

December 19, 2013

Pascal Maillard, Weizmann, Self-similar trees

Take a random rooted tree and contract each edge with probability $p$, where contracting an edge means removing it from the tree and identifying its head and tail. Which random trees are invariant (in law) under this transformation? I will present recent results (joint with Olivier Hénard) which characterize all one-ended trees invariant under this operation, and under the more general operation where edges on the infinite ray are contracted with probability $q \le p$. I will also describe the relationship with (real-valued) self-similar processes and quasi-stationary distributions of linear pure death processes, as well as the common aspects and differences with other renormalization procedures of trees or graphs.

December 12, 2013

Remi Rhodes, University of Paris Dauphine and Vincent Vargas, Ecole Normale Superieure Lyon, Critical Gaussian multiplicative chaos

This talk will be devoted to the theory of Gaussian multiplicative chaos at criticality. Gaussian multiplicative chaos is the study of random measures having formally as density with respect to the Lebesgue measure the exponential of a Gaussian field with logarithmic correlations, up to a multiplicative factor called the intermittency parameter. Depending on the values of the intermittency parameter, the behaviour of these measures presents a phase transition. We will first introduce the basic background of the theory, mainly Kahane's results of the eighties concerning the subcritical phase below the phase transition. Then the main part of our talk will be devoted to the study of the phase transition, which differs from Kahane's theory and is called critical Gaussian multiplicative chaos. We will discuss the convergence of the so-called derivative martingale and its main properties: support, uniqueness in law, modulus of continuity. When the Gaussian field is a two dimensional GFF, we will explain the applications in Liouville field theory: the conformal invariance property of the resulting measure, its fractal properties (KPZ formula) as well as the construction of the so-called tachyon fields. Time permitting, we will also discuss the construction of the geometry of a scalar metric tensor, the volume form of which is the critical Gaussian multiplicative chaos, and explain how to construct a corresponding Brownian motion, semigroup and so on...

December 5, 2013

Arnab Sen, University of Minnesota, Continuous spectra for sparse random graphs

The limiting spectral distributions of many sparse random graph models are known to contain atoms. But do they also have some continuous part? In this talk, I will give affirmative answer to this question for several widely studied models of random graphs including Erdős-Renyi random graph $G(n,c/n)$ with $c > 1$, random graphs with certain degree distributions and supercritical bond percolation on $Z^2$. I will also present several open problems.

October 17, 2013

Yury Malyshkin, Moscow State University, The power of two choices and preferential attachment

Before September 2013 the seminar ran on Wednesdays.

July 31, 2013 Note unusual location: Feinberg room A

Jonathan Hermon, Berkeley, A characterization of amenability and infinite clusters in the social network model.

Joint work with Ben Morris, Allan Sly and Chuan Qin.

Given a connected infinite graph $G$, put at each vertex $v$ Poisson($\lambda \times \deg(v)$) walkers. Let all the walkers perform independent lazy simple random walks. When two walkers visit the same vertex at the same time they become acquainted. The main question studied: Is it true that a.s. any two walkers will eventually have a path of acquaintances between them? The answer provides a characterization of amenability according to whether the answer is positive for any $\lambda > 0$ or that there is some critical $\lambda_{c}$. Both upper and lower general bounds on $\lambda_{c}$ will be given. They turn out to be matching in one particularly interesting example. The proofs show connections to branching random walk and percolation. The emergence of an infinite cluster of acquainted walkers in finite time will be discussed as time permits.

July 17, 2013

Hugo Duminil-Copin, Geneva, Absence of percolation for critical Bernoulli percolation on planar slabs

We prove that the probability that there exists an infinite cluster for critical Bernoulli percolation on $\mathbb{Z}^2\times G$ for any finite graph $G$ is equal to zero. As a byproduct of the proof, we show that finite range percolation on $\mathbb{Z}^2$ does not percolate at criticality (some symmetry is required for the interactions). This talk is based on a joint work with V. Sidoravicius and V. Tassion.

July 10, 2013

Omer Tamuz, Weizmann, Majority Dynamics and the Retention of Information

We consider a group of agents connected by a social network. Each agent starts with an opinion in {-1, +1} and repeatedly updates it to match the opinion of the majority of its neighbors.

We assume that one of {-1, +1} is the “true” state of the world $S$, and consider a setting in which the initial opinions contain enough information to reconstruct $S$ with high probability. We ask whether it is still possible to reconstruct S from the agents’ opinions after many rounds of updates.

While this is not the case in general, we show that indeed, for a large family of bounded degree graphs, information on $S$ is retained by the process of majority dynamics.

Joint with Ran Tessler

July 3, 2013

Laurent Tournier, Université Paris 13, On the greedy walker problem

Consider the following problem: a tourist wishes to visit a series of landmarks (infinitely many) and decides to always go to the closest non-visited place in his list. Depending on the spatial distribution of landmarks, does this strategy succeed?, i.e. does every landmark get eventually visited? I will give several open questions and discuss a special case. This is joint work with L. Rolla and V. Sidoravicius.

June 5, 2013

Mikhail Ostrovskii, St. John's University, New York, Low-distortion embeddings of graphs with large girth.

The main result of the talk: for each $k\ge 3$ there exist a sequence $\{G_n\}_{n=1}^\infty$ of $k$-regular graphs with girth$(G_n)\to\infty$ such that $G_n$ admit embeddings into $\ell_1$ with uniformly bounded distortions. This result answers a question posed by N. Linial, A. Magen, and A. Naor (2002). It demonstrates an important distinction between metric properties of families of expanders and families of regular graphs with indefinitely growing girths.

May 29, 2013

Arkady Templeman, Pennsylvania State University, Ergodic theorems for random fields.

We consider mean, pointwise, maximal and dominated ergodic theorems for Cesaro averages and weighted averages of random fields on multi-dimensional linear spaces and groups. The main objects are homogenous as well as non-homogeneous random fields.

May 22, 2013

Percy Deift, New York University, Toeplitz matrices and determinants under the impetus of the Ising Model I

Part of a 3-lecture series, see here.

Note special day, time and place! Thursday, May 16, 2013, 14:00-16:00, Ziskind 261

Igor Kortchemski, École normale supérieure, Random stable looptrees

May 1, 2013

Joseph Lehec, Université Paris-Dauphine, A short probabilistic proof of the Brascamp-Lieb inequality.

April 3, 2013

Doron Puder, Hebrew U, Expansion of Random Graphs: New Proofs, New Results

We present a new approach to showing that random graphs are nearly optimal expanders. This approach is based on deep results from combinatorial group theory. It applies both to regular and irregular random graphs.

Let $G$ be a random $d$-regular graph on $n$ vertices. It was conjectured by Alon (86') and proved by Friedman (08') in a 100+-page-long-booklet that the highest non-trivial eigenvalue of $G$ is a.a.s. arbitrarily close to $2*\sqrt{d-1}$. We give a new, substantially simpler proof, that nearly recovers Friedman's result. This approach also has the advantage of applying to a more general model of random graphs, concerning also non-regular graphs. Friedman (03') extended Alon's conjecture to this general case, and we obtain new, nearly optimal results here too.

March 20, 2013, Note unusual location: Feinberg room 2

Omer Angel, University of British Columbia, Half planar maps.

Certain half planar random maps enjoy a "domain Markov" property. I explore this property, describing work with Gourab Ray, as well as an application of this property to study exponents for critical percolation on several models of random planarmaps (with Nicolas Curien).

February 27, 2013

Tal Orenshtein, Weizmann, Zero-one law for directional transience for one dimensional excited random walks.

We will show that for an excited random walk in one dimension, the probability for right transience is either zero or one. This solves a problem posed by Kosygina and Zerner.

Joint with Gidi Amir and Noam Berger.

February 20, 2013

Mike Hochman, The Hebrew U, Dimension of self-similar sets with overlaps

A self similar subset $X$ of the line is a set satisfying the `geometric recursion` $X$ = union of $F_i(X)$, where $F_i$ are affine contractions. It is a classical problem to calculate the dimension of such sets. When the images $F_i(X)$ are disjoint, or under some weaker assumptions, this is easy and there is a closed formula. In general all that exists is an upper bound, but there is a conjecture, which says that the upper bound is the right bound unless there are some very special combinatorial obstructions.

In the first part of the talk I will explain the conjecture, and discuss some progress on it. Specifically, it turns out that, if the dimension is smaller than the conjecture predicts, then an approximate version of the combinatorial obstructions must be present. I'll also explain how this resolves an old conjecture of Furstenberg about the dimension of sums of Cantor sets, and gives new results on the Bernoulli convolutions problem.

In the second part I will discuss the proof, which relies on a new inverse theorem describing the structure of measures $\mu$,$\nu$ on the line for which the entropy of $\mu*\nu$ at a fixed resolution $2^{-n}$ is only $cn$ times larger than the entropy of $\mu$ at the same scale, where $c>0$ is some small parameter.

February 13, 2013

Jun Chen, Weizmann, A generalized Pólya's Urn with graph based interactions

In this talk, we study a generalized Pólya's Urn with graph based interactions. Given a finite connected graph $G$, place a bin at each vertex. Two bins are called a pair if they share an edge of $G$. At discrete times, a ball is added to each pair of bins. In a pair of bins, one of the bins gets the ball with probability proportional to its current number of balls raised by some fixed power $\alpha\ge 0$. We characterize the limiting behavior of the proportion of balls in the bins when $G$ is regular and $\alpha\le 1$. For example, when $G$ is non-bipartite the proportion converges to the uniform measure almost surely. A novel part of the proof consists of analyzing the equilibrium set of a non uniformly hyperbolic dynamical system.

Joint work with Itai Benjamini and Yuri Lima.

February 6, 2013

Alon Nishry, Tel Aviv, Small ball probability for Rademacher Fourier series and an application for Random Analytic functions

(Joint with F. Nazarov & M. Sodin).

January 30, 2013

Michael Björklund, Small talk on bi-harmonic functions on groups

I will begin the talk with an attempt to motivate the study of BI-harmonic (both left- AND right-harmonic) functions of linear growth/satisfying a Lipschitz condition on countable measured groups. I will then discuss some classical and less classical constructions of such functions, and why measurable cross-ratios on the Poisson boundaries of measured groups turn out to be useful tools to understand them. The applications include central limit theorems for distance functions on hyperbolic groups and sub-direct product thereof.

January 16, 2013

Alexander Fish, University of Wisconsin, Product sets in amenable groups through a dynamical approach

We will describe a new correspondence between product sets in a countable amenable group and product sets in compact groups. This approach enables us to get quantitative results concerning product sets in amenable groups. As an example - we will outline the proof of the statement that the product set $AB$ of two "large" sets in amenable group contains locally a "large" almost periodic structure. Also we will give examples of expected quantitative phenomena about product sets in amenable groups.

(based on a joint work with M. Bjorklund)

Note special time and place! January 16, 2013, 16:00, Physics room A. Joint with the statistical physics seminar

Michael Aizenman, Princeton, Ergodicity Hypothesis' breakdown in Random Schroedinger Operators

Of current research interest in the area concerning the disorder effects on the dynamics under random Schroedinger operators is the occurrence of energy regimes (phases) in which extended states are formed from resonating local quasi-modes.

The corresponding eigenstates are "non-ergodic", in the sense that they violate a heuristic version of the equidistribution principle, yet they do not exhibit Anderson localization. Such phases were proven to occur in the the random Schroedinger operator on tree graphs (in a joint work with Simone Warzel), and are also expected to show up in many-particle systems which are the subject of ongoing work (with SW and Mira Shamis).

January 9, 2013

Omer Tamuz, Weizmann, The Furstenberg Entropy Realization Problem

Joint work with Yair Hartman

Random walks on groups and harmonic functions on groups are intimately related to a generalization of measure preserving group actions called "stationary group actions". An important invariant of stationary group actions is their Furstenberg Entropy. The Furstenberg Entropy realization problem is the question of determining the range of possible entropy values realizable for a given random walk.

The talk will include an introduction to this field, an overview of what (little) is known, and some new results.

January 2, 2013, joint with the theory seminar

Amin Coja-Oghlan, Goethe University, Chasing the k-SAT threshold

Let $F$ be a random Boolean formula in conjunctive normal form over $n$ Boolean variables with $m$ clauses of length $k$. It is known that there is a (non-uniform) sharp threshold for the existence of satisfying assignments in such formulas [Friedgut 1999]. However, the precise location of this phase transition is not known for any $k>2$. The best previous upper and lower bounds differ by about $k\ln 2/2$ [Achlioptas, Peres 2003]. In this talk I present an improved lower bound, which reduces the gap to ~0.19. The proof is inspired by the cavity method of statistical mechanics.

Double feature! December 26, 2012, 11:00-12:00

Scott N. Armstrong, University of Wisconsin, First-passage percolation, quenched large deviations for diffusions in random environments, and Hamilton-Jacobi equations

I will present recent work on the homogenization of Hamilton-Jacobi equations in random media. Important special cases of the model we consider describe (i) a "continuum" FPP model and (ii) quenched large deviations (Lyapunov exponents) for diffusions in random environments.

We formulate very general "shape theorems" and get estimates on the fluctuations which match those proved in the 1990s in context of FPP by Kesten and Alexander and for Brownian motion in a Poissonian environment by Sznitman.

Some of the work is joint with Cardaliaguet and Souganidis.

December 26, 2012, 12:00-13:00

Sylvia Serfaty, Paris 6, Coulomb gas, Renormalized energy and Abrikosov lattice

We are interested in the statistical mechanics of (classical) two-dimensional Coulomb gases and one-dimensional log gases in a confining potential. We connect the Hamiltonian to the "renormalized energy", a way to compute the total Coulomb interaction of an infinite jellium, and whose minimum is expected to be achieved by the "Abrikosov" triangular lattice in 2D, and is achieved by the lattice $\mathbb{Z}$ in 1D. We apply this to the study of the finite temperature situation. Results include computations of the next order term in the partition function, equidistribution of charges, and concentration to the minimizers of the renormalized energy as the temperature tends to zero. This is based on joint works, mostly with Etienne Sandier.

December 19, 2012

Lionel Levine, Cornell, Logarithmic fluctuations from circularity

Starting with n particles at the origin in $Z^d$, let each particle in turn perform simple random walk until reaching an unoccupied site. Lawler, Bramson and Griffeath proved that with high probability the resulting random set of $n$ occupied sites is close to a ball. We show that its fluctuations from circularity are, with high probability, at most logarithmic in the radius of the ball, answering a question posed by Lawler in 1995 and confirming a prediction made by chemists Meakin and Deutch in the 1980's. Joint work with David Jerison and Scott Sheffield.

November 7, 2012

Pascal Maillard, Weizmann, Branching Brownian motion with selection

The branching Brownian motion (BBM) can be seen as a system of diffusing and reproducing particles. It can also be regarded as a tree-indexed Brownian motion, thereby joining two fundamental concepts in probability theory: Brownian motion and random trees.

In this talk I will present some results obtained in my thesis (arXiv:1210.3500) about a model of one-dimensional BBM with selection, called the $N$-BBM. In this model, as soon as the number of particles exceeds a (large) given number $N$, only the $N$ right-most particles are kept (space is drawn horizontally), the others being removed from the system. I will expose some precise estimates on the position of the cloud of particles for large $N$. More precisely, I show that it converges in law at the time-scale $\log^3 N$ to a Lévy process, thereby justifying results obtained by the physicists Brunet, Derrida, Mueller and Munier through PDE methods. I will explain as well how this study contributes to the understanding of the so-called noisy FKPP equation.

October 31, 2012

Rani Hod, Tel Aviv University, Component Games on Regular Graphs

In this talk we study the Maker-Breaker component game, played on the edge set of a regular graph. Given a d-regular graph $G$, the $s$-component $(1:b)$ game is defined as follows. In every round Maker claims one free edge of $G$ and Breaker claims $b$ free edges. Maker wins this game if his graph contains a connected component of size at least $s$; otherwise, Breaker wins the game. For all values of Breaker's bias $b$, we determine the winner and provide an explicit winning strategy. To this end, we prove an extension of a theorem by Gallai-Hasse-Roy-Vitaver about graph orientations without long directed simple paths.

Joint work with Alon Naor.

October 24, 2012

Eviatar Procaccia, Weizmann, Asymptotic behavior of the Cheeger constant of super-critical percolation in the square lattice.

Isoperimetry is a well studied subject that has found many applications in geometric measure theory (e.g. concentration of measure, heat-kernal estimates, mixing time, etc.) Consider the super-critical bond percolation on $\mathbb{Z}^d$ (the d-dimensional square lattice), and $\phi_n$ the Cheeger constant of the super-critical percolation cluster restricted to the finite box $[-n,n]^d$. Following several papers that proved that the leading order asymptotics of $\phi_n$ is of the order $1/n$, Benjamini conjectured a limit to $n\phi_n$ exists. As a step towards this goal, Rosenthal and myself have recently shown that $Var(n\phi_n)< C n^{2-d}$. This implies concentration of $n\phi_n$ around its mean for dimensions $d>2$.

Consider the super-critical bond percolation on $\mathbb{Z}^2$ (the square lattice). We prove the Cheeger constant of the super-critical percolation cluster restricted to finite boxes scale a.s to a deterministic quantity. This quantity is given by the solution to the isoperimetric problem on $\mathbb{R}^2$ with respect to a specific norm. The unique set which gives the solution, is the normalized Wulff shape for the same norm.

Joint work with Marek Biskup, Oren Louidor and Ron Rosenthal.

Before September 2012 the seminar ran on Thursdays.

August 9, 2012

Oren Louidor, UCLA, Trapping in the random conductance model

We consider random walks on $\mathbb{Z}^d$ among nearest-neighbor random conductances which are i.i.d., positive, bounded uniformly from above but which can be arbitrarily close to zero. Our focus is on the detailed properties of the paths of the random walk conditioned to return back to the starting point after time $2n$. We show that in the situations when the heat kernel exhibits subdiffusive behavior - which is known to be possible in dimensions $d \geq 4$ - the walk gets trapped for time of order $n$ in a small spatial region. This proves that the strategy used to infer subdiffusive lower bounds on the heat kernel in earlier studies of this problem is in fact dominant. In addition, we settle a conjecture on the maximal possible subdiffusive decay in four dimensions. Joint work with Marek Biskup, Alexander Vandenberg and Alexander Rozinov.

August 2, 2012

Omer Tamuz, Weizmann, Learning and the topology of social networks: a topological approach

We study a standard model of Bayesian agents in a social network who learn a binary state of the world $S$, from initial signals, by repeatedly observing each other's best guesses. In particular, we are interested in the question of asymptotic learning: for which large networks do the agents learn $S$ with high probability? We give a geometrical condition for learning which is derived from the notion of compactness in the Benjamini-Schramm topology of rooted graphs.

Joint work with Elchanan Mossel and Allan Sly.

Note special day! Sunday, July 15, 2012, 11:00-1:00

Ori Gurel-Gurevich, UBC, Recurrence of planar graph limits.

We will show that any distributional limit of finite planar graphs in which the degree of the root decays exponentially is almost surely recurrent. As a corollary, we obtain that the uniform infinite planar triangulation/quadrangulation (UIPT/UIPQ) are almost surely recurrent, resolving conjectures of Angel, Benjamini and Schramm. Joint work with Asaf Nachmias.

July 5, 2012

Artem Zvavitch, Kent State University, Shadow System, Duality and Volume.

We will first discuss the shadow systems of convex bodies which were introduce by Rogers and Shephard. As an application we will present the result of Campi and Gronchi which connected shadow systems and the notion of duality of convex bodies. Next we will present joint work with M. Fradelizi and M. Meyer and use shadow systems technique to prove a particular case of the conjectured lower bound of the volume product of convex body $K$ and its polar (Mahler's Conjecture). We will show that if $K$ is the convex hull of two 2-dimensional convex bodies, then the volume product of $K$ is greater then the volume product of the simplex, thus confirming the 3-dimensional case of Mahler conjecture, for this class of bodies. A similar result will be provided for symmetric case.

June 14, 2012

Tal Orenshtein, Weizmann, One dimensional Excited Random Walk with a never-ending supply of cookies.

We consider one dimensional Excited Random Walk, AKA Cookie Random Walk, defined by the following. On each site in the one dimensional lattice there is a list of enumerated cookies (that is, transition probabilities). If the walker has arrived in a certain site at the i-th time, then it uses the i-th cookie to choose a neighboring site to jump to in the next step. The standard assumptions are either that the number of cookies per site is finite or that all cookies has the same drift direction. We consider the walk without these assumptions and supply a machinery to determine the asymptotic behavior of the walk. In particular, we get an explicit formula for an invariant which determines whether the walk is recurrent, right transient or left transient, for a large family of environments. The proof goes through the analysis of a related countable-state Markov chain, which looks locally like a Bessel process. We will present some of the proof highlights and, time permitted, discuss extensions and open problems.

Joint work with Gady Kozma and Igor Shinkar.

June 7, 2012

Yaar Solomon, Ben Gurion University, Separated nets in $\mathbb{R}^d$ with a bounded displacement to $\mathbb{Z}^d$.

We study the question when a uniformly discrete set $Y$ in $\mathbb{R}^d$ has bounded displacement from $\mathbb{Z}^d$. That is, if there is a constant $C$ and a bijection $F$ from $Y$ to $C \mathbb{Z}^d$ such that $\sup||y-F(y)||$ is bounded. If $Y$ is also relatively dense, $Y$ corresponds to a tiling of $\mathbb{R}^d$. We answer the above question for substitution tilings. All the relevant background and definitions will be given in the talk.

May 31, 2012

Elchanan Mossel, Berkeley, Stochastic Block Models and Reconstruction

I will sketch a proof of recent conjectures from theoretical physics regarding a variant of the Erdős-Reyni random graph G(n,p). The conjecture was made by: A. Decelle, F. Krzakala, C. Moore, L. Zdeborová (arXiv:1109.3041)

The model under consideration was studied extensively in statistics since the 1980s as a model of communities (under the name of the "block model"). Independently, since the 1980's the model was studied extensively in theoretical computer science in the context of planted graph problems under the name of the "planted bisection problem". The conjectures establish an exact threshold for tasks involving estimating the communities / finding the planted partition and other parameter of the model. A number of fascinating open problems will be presented.

Joint work with J. Neeman and A. Sly. arXiv:1202.1499

May 24, 2012

Daniel Reem, IMPA, The geometric stability of Voronoi diagrams with respect to small changes of the sites.

Voronoi diagrams (Dirichlet tessellations, fundamental domains) appear in many areas in science and mathematics and have numerous applications. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Consider the following question: does a small change of the sites, e.g., of their position or shape, yield a small change in the corresponding Voronoi cells? This question is relevant because of dynamical scenarios, random scenarios (stochastic geometry), since imprecision is inherent in the input, etc. The traditional approach to Voronoi diagrams, and, in particular, to (variants of) this question, is combinatorial. However, there has been a limited discussion in the geometric sense (the shape of the cells), mainly an intuitive one, in Euclidean spaces. We discuss this question rigorously and show that the answer is positive in a wide class of (possibly infinite dimensional) spaces, but not in general. Explicit bounds (dimensionless) are given, and we allow infinitely many sites of a general form. The proof is related to an old-new way of measuring angles and to strong versions of the triangle inequality. The relevance of the result is illustrated using numerous real-world and theoretical examples and counterexamples.

The talk is intended for a general audience and will include many (unusual) pictures.

May 17, 2012

Mark Rudelson, University of Michigan, The smallest singular value of a unitary perturbed matrix

We study the distribution of the smallest singular value of the sum of a deterministic matrix and a random unitary matrix, uniformly distributed with respect to the Haar measure. A bound for this singular value arises as a condition in the Single Ring Theorem of Guionnet, Krishnapour, and Zeitouni. Consider a family of random matrices with given distributions of singular values. The Single Ring Theorem asserts that under some conditions the the empirical distributions of eigenvalues converge do a limit density, supported in a single ring. The conditions are of two types: "scalar", which pertain to the original distribution of singular values, and "matrix", which is significantly harder to check. Our result shows that the condition of the second type is redundant.

Joint work with Roman Vershynin.

May 3, 2012

Ran Tessler, Hebrew University, Biased voter model.

We introduce the Biased Voter Model. We begin by describing the model and some easy survival results. We prove several types of convergences. We continue by sketching the different phases of the BVM model on infinite trees and lattices, starting with different initial conditions. We finish by proving strong convergence for trees. Based on a joint work with O. Louidor and A. Vandenberg-Rodes.

April 5, 2012

Michael Bromberg, Tel Aviv University, Weak invariance principle for the local times of partial sums of Markov Chains

Let $\{ X_n\} $ be an integer valued Markov Chain with finite state space. Let $S_n=\sum_{k=0}^{n}X_k$ and let $L_n(x)$ be the number of times $S_k$ hits $x\in\mathbb{Z}$ up to step $n$. Define the normalized local time process $t_n(x)$ by $t_n(x)=\frac{L_n(\lfloor \sqrt{n}x\rfloor )}{\sqrt{n}}$, $x\in\mathbb{R}$. Our goal is to prove a functional, weak invariance principle for the normalized sequence $t_n(x)$, i.e. we prove that under some assumptions about the Markov Chain, the normalized local times converge in distribution to the local time of the Brownian Motion. This is joint work with Zemer Kosloff.

March 29, 2012

Ron Blei, University of Connecticut, The Grothendieck inequality revisited

The classical Grothendieck inequality is viewed as a statement about representing functions of two variables over discrete domains by integrals of two-fold products of functions of one variable. We prove an analogous, "upgraded" statement concerning continuous functions of two variables over general topological domains. The key is a Parseval-like formula.

In the first hour I will construct a continuous map $\Phi$ from the Euclidean space $l^2(A)$ into $L^2(\Omega_A, \mathbb{P}_A)$, where $A$ is a set, $\Omega_A = \{-1,1\}^A$, and $\mathbb{P}_A$ is the uniform probability measure on $\Omega_A$, such that

$\sum_{\alpha \in A} {\bf{x}}(\alpha) \overline{{\bf{y}}(\alpha)} = \int_{\Omega_A} \Phi({\bf{x}})\Phi(\overline{{\bf{y}}})d \mathbb{P}_A, \ \ \ {\bf{x}} \in l^2(A), \ {\bf{y}} \in l^2(A),$ (1)


$\|\Phi({\bf{x}})\|_{L^{\infty}} \leq K, \ \ \ {\bf{x}} \in B_{l^2(A)},$

for an absolute constant $K > 1$. The Parseval-like formula in (1) is obtained by iterating the usual Parseval formula in a framework of harmonic analysis on dyadic groups.

In the second hour I will describe extensions and variants of (1).

Modulo some basic harmonic and functional analysis, the talk is guaranteed to be self-contained.

March 22, 2012

Igal Sason, Technion, Exponential Bounds for Discrete Time, Conditionally Symmetric Martingales with Bounded Increments

This talk will present some new exponential bounds for discrete time, real valued, conditionally symmetric martingales with bounded increments. The new bounds will be extended to conditionally symmetric sub or supermartingales, and they will be also compared to some existing bounds. The use of the bounds will be exemplified.

March 15, 2012

Agelos Georgakopoulos, Random walks, electrical networks, etc.

I will present some basic facts concerning electrical networks and their connections to random walk. Then, I will present a new result relating Dirichlet harmonic functions on an infinite graph to its Poisson boundary. The talk will be accessible to the non-expert.

February 23, 2012

Takashi Kumagai, Kyoto University, Quenched invariance principle for random walks and random divergence forms in random media on cones

We will consider the following two models and establish quenched invariance principles;

1. Simple random walks on the infinite clusters for super-critical percolations on half and quarter planes in d-dimensional Euclidean spaces.

2. Uniform elliptic divergence forms with random stationary coefficients on cones in Euclidean spaces.

Note that because of the lack of translation invariance, we cannot apply the method of the 'corrector'. Instead, we make full use of the heat kernel estimates and Dirichlet form techniques to resolve the problem. This is a on-going joint work with Z.Q. Chen (Seattle) and D.A. Croydon (Warwick).

February 16, 2012

Eviatar Procaccia, Weizmann, The need for speed: Maximizing the speed of random walk in fixed environments.

We study nearest neighbor random walks in fixed environments of $\mathbb{Z}$ composed of two point types : $(\frac{1}{2},\frac{1}{2})$ and $(p,1-p)$ for $p>\frac{1}{2}$. We show that for every environment with density of $p$ drifts bounded by $\lambda$ we have $\limsup_{n\rightarrow\infty}\frac{X_n}{n}\leq (2p-1)\lambda$, where $X_n$ is a random walk in the environment. In addition up to some integer effect the environment which gives the greatest speed is given by equally spaced drifts.

February 9, 2012

Tamar Ziegler, Technion, Linear equations in primes and nilpotent groups

A classical theorem of Dirichlet establishes the existence of infinitely many primes in arithmetic progressions, so long as there are no local obstructions. In 2006 Green and Tao set up a programme for proving a vast generalization of this theorem. They conjectured a relation between the existence of linear patterns in primes and dynamics on nilmanifolds. In recent joint work with Green and Tao we completed the final step of this programme. I will describe the conjecture and its application to solving linear equations in primes in the first hour, and give some insights to the proof in the second hour.

February 2, 2012

Subhroshekhar Ghosh, Berkeley, What does a Point Process Outside a Domain tell us about What's Inside?

In a Poisson point process we have independence between disjoint spatial domains, so the points outside a disk give us no information on the points inside. The story gets a lot more interesting for processes with stronger spatial correlation. In the case of Ginibre ensemble, a process arising from eigenvalues of random matrices, we prove that the outside points determine exactly the number of points inside, and further, we demonstrate that they determine nothing more. In the case of zero ensembles of Gaussian power series, we prove that the outside points determine exactly the number and the centre of mass of the inside points, and nothing further. These phenomena suggest a certain hierarchy of point processes according to their rigidity; Poisson, Ginibre and the Gaussian power series fit in at levels 0, 1 and 2 in this ladder.

Time permitting, we will also look at some interesting consequences of our results, with applications to continuum percolation, reconstruction of Gaussian entire functions, and others. This is based on joint work with Fedor Nazarov, Yuval Peres and Mikhail Sodin.

January 26, 2012

Zemer Kosloff, Tel Aviv University, The Zero Type Property And Mixing of Bernoulli Shifts.

An invertible transformation $T:(X,\mathcal{B},\mu)\to(X,\mathcal{B},\mu)$ is called non singular if $\mu\circ T$ is an equivalent measure to $\mu$. We will talk about mixing notions for non singular tranformations which do not posses a $\mu$-equivalent invariant measure and show that Bernoulli shifts are always "mixing" (the maximal spectral type of its the operator $Uf:=\sqrt{\frac{d\mu\circ T}{d\mu}}f\circ T$ is a Rajchman measure) and there exists a "non singular power weakly mixing" (for every $n_1,n_2,...,n_k\in\mathbb{Z}$, $T^{n_1}\times T^{n_2}\times\cdots\times T^{n_k}$ is ergodic) Bernoulli shift.

January 12, 2012

Jay Rosen, CUNY, Loop soups, additive functionals and intersection local times.

We show how loop measures and loop soups can help us understand Dynkin's isomorphism theorem and generalize it to non-symmetric Markov processes. We use this to derive new results on additive functionals and intersection local times.

Note special time! January 5, 2012, 16:00-17:00

Mrinal Kanti Roychowdhury, University of Texas-Pan American, Quantization dimension for a countable iterated function system

Quantization for a probability distribution refers to the idea of estimating a given probability on $\mathbb{R}^d$ with a discrete probability, that is, a 'quantized' version of the probability supported on a finite set. Quantization dimension gives the speed how fast the specified measure of the error goes to zero as the number of points in the supporting set goes to infinity. Quantization dimension for a continuous singular probability measure generated by an infinite iterated function system was a long time open problem. I first determined the quantization dimension function for such a system. A relationship between the quantization dimension function and the temperature function of the thermodynamic formalism arising in multifractal analysis is also established. In my talk, I will present it.

January 5, 2012

Uzy Smilansky, Weizmann, Quantum chaos for regular graphs: Combinatorics, Random Matrix Theory and Random Waves.

The spectrum and eigenvectors of the discrete Shroedinger operator on regular graphs display many features which are typical of quantum systems with a chaotic classical dynamics. In this talk I shall describe the findings, compare them to the predictions of random matrix theory and random wave models, and explain their combinatorial origin. A conjectured combinatorial result concerning the counting of cycles will be presented and motivated.

December 29, 2011

Karim Adiprasito, Freie Universität Berlin, What is the shape of a typical convex set?

The Weierstrass function is a classic example of a function that, while continuous, is nowhere differentiable. While its construction is easy, it only tells half the truth: the Weierstrass function is not just a strange and isolated example, but displays a typical property of continuous functions (Banach 1931).

"Typical" is a topological notion based on Baire Categories. We will see how it relates to measures and recall when the two notions coincide.

For convex functions and sets, the situation is quite different from the situation for continuous functions and compacta. In 1959, Victor Klee showed that the boundary of a typical convex set is at least $C^1$. In contrast, the boundary of a typical convex set is not $C^2$ (Gruber 1977, Zamfirescu 1980), but is $C^2$ almost everywhere (Alexandrov). I will talk about these results and more typical properties of convex sets, some new, some old.

If time permits, I will discuss why it is natural to think about typical properties of Alexandrov spaces of curvature bounded below.

Necessary background will be given in the talk!

December 22, 2011

Amir Dembo, Stanford, Factor models on locally tree-like graphs

Consider factor (graphical) models on sparse graph sequences that converge locally to a random tree $T$. Using a novel interpolation scheme we prove existence of limiting free energy density under uniqueness of relevant Gibbs measures for the factor model on $T$. We demonstrate this for Potts and independent sets models and further characterize this limit via large-deviations type minimization problem and provide an explicit formula for its solution, as the Bethe free energy for a suitable fixed point of the belief propagation recursions on $T$ (thereby rigorously generalize heuristic calculations by statistical physicists using "replica" or "cavity" methods).

This talk is based on joint works with Andrea Montanari, Allan Sly and Nike Sun.

December 15, 2011

Tom Ellis, Tel Aviv University, The Brownian web is a two dimensional black noise.

The Brownian web is a stochastic process constructed from Brownian motions, and was one of the first known examples of a "black noise" in the sense of Tsirelson. I will discuss what it means to be a black noise, and demonstrate how, in joint work with Ohad Feldheim, the Brownian web is in fact a two-dimensional black noise. It is only the second known example of a two-dimensional black noise after Schramm and Smirnov's result on the scaling limit of critical planar percolation.

December 8, 2011

Daniel Johannsen, Tel Aviv University, The Degree Sequence of Random Planar Maps.

In this talk we study how typical specimen of various classes of planar maps (i.e., embedded planar graphs) look like. In particular, we are interested in the degree sequence of a random map drawn from all maps of equal size. For ordinary random maps, it is known that the expected number of vertices of a fixed degree is linear in the number of edges of that map. Moreover, this number is sharply concentrated around its expectation for which an asymptotic formula (depending on the given degree) exists. We see how this result can be transferred to other classes of random maps like those that are biconnected, 3-connected, loopless, bridgeless, or simple.

This is joint work with Konstantinos Panagiotou.

December 1, 2011

Ron Peled, Tel Aviv University, Probabilistic existence of rigid combinatorial structures

We develop a new probabilistic method for proving the existence of rare objects under certain conditions. The method applies to show the existence of rigid combinatorial structures which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. This improves existing results in the theory of $t$-designs and gives the first proof of existence of non-trivial $t$-wise permutations for $t>3$. In all cases, the sizes of the objects obtained are optimal up to polynomial overhead. Our main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps. Joint work with Greg Kuperberg and Shachar Lovett.

November 24, 2011

Gideon Amir, Bar Ilan University, A continuum of exponents for the rate of escape of random walks on groups.

For every $3/4\le \beta< 1$ we construct a finitely generated group so that the expected distance of the simple random walk from its starting point after $n$ steps is $n^{\beta+o(1)}$. This answers a question of Naor and Peres. In other examples, the speed exponent can fluctuate between any two values in this interval.

Previous examples were only of exponents of the form $1-1/2^k$ or 1, and were based on lamplighter (wreath product) constructions. (Other than the standard $\beta=1/2$ and $\beta=1$ which are simply diffusive and ballistic behaviours known for a wide variety of groups). In this lecture we will describe how a variation of the lamplighter construction, namely the permutational wreath product, can be used to get precise bounds on the rate of escape in terms of return probabilities of the random walk on some Schreier graphs. We will then show how groups of automorphisms of rooted trees, related to automata groups, can then be constructed and analyzed to get the desired rate of escape. No previous knowledge of automaton groups or wreath products is assumed.

November 17, 2011

Hilary Finucane, Weizmann, Algebraic recurrence of groups

We will consider random walks on Cayley graphs, and in particular the following question: given a Cayley graph of a group $G$, does the trace of a simple random walk generate $G$ as a semi-group almost surely? If the answer is yes, we call $G$ algebraically recurrent. Initial steps towrds understanding which groups are algebraically recurrent, will be presented. This work is joint with Itai Benjamini and Romain Tessera.

November 10, 2011

Ilya Goldsheid, Queen Mary University of London, Sub-diffusive random walks in random environment on a strip.

This is a joint work with D. Dolgopyat. We consider a random walk (RW) in random environment on a strip in a sud-diffusive regime. We show that the time the walk spends in a box of length $N$ (equivalently, the hitting time for $N$) can asymptotically be presented as a linear combination of i.i.d. exponential random variables with coefficients forming a Poisson process on $ {\mathbb{R}}^+$ with intensity measure that has the density $cx^{-1-s}$. RWs with bounded jumps on a line can be viewed as a particular case of this model. The latter in turn is a natural generalisation of the classical simple RW (with jumps to nearest neighbours) and was first considered in the classical papers by Solomon and by Kesten-Kozlov-Spitzer back in 1975. In the sub-diffusive regimes, only very partial results and only in annealed models were known about the RWs with bounded jumps so far.

Note special time! July 21, 2011, 15:00-16:00

Mira Shamis, Institute for Advanced Study, Some connections between almost periodic and periodic discrete Schroedinger operators with analytic potentials

We study discrete Schroedinger operators with analytic potentials. In particular, we are interested in the connection between the absolutely continuous spectrum in the almost periodic case and the spectra in the periodic case. We prove a weak form of a precise conjecture (due to Y. Last) relating the two.

We also bound the measure of the spectrum in the periodic case in terms of the Lyapunov exponent in the almost periodic case.

In the proofs, we use a partial generalization of Chambers' formula. Time perimitting, we shall show an additional application of this generalization: a proof of Herman's lower bound for the Lyapunov exponent.

July 21, 2011

Eviatar Procaccia, Weizmann, Geometry of the random interlacement.

We consider the geometry of random interlacements on the $d$-dimensional lattice. We use ideas from stochastic dimension theory to prove the following: Given that two vertices $x,y$ belong to the interlacement set, it is possible to find a path between $x$ and $y$ contained in the trace left by at most $\lceil d/2 \rceil$ trajectories from the underlying Poisson point process. Moreover, this result is sharp in the sense that there are pairs of points in the interlacement set which cannot be connected by a path using the traces of at most $\lceil d/2 \rceil-1$ trajectories.

Joint work with Johan Tykesson.

July 14, 2011

Yair Glasner, Ben Gurion University, A probabilistic Kesten theorem and counting closed circles in graphs

This is a joint work with Miklos Abert and Balint Virag.

I will present new asymptotic estimates on the number of closed circles in large $d$-regular graphs. These improve previous estimates obtained by Serre and McKay.

Our main statement was well known for Cayley graphs, where it follows from Kesten's spectral radius theorem (this was Kesten's dissertation). While Kesten's theorem is false for general graphs, we are able to prove a probabilistic version of the theorem which is enough to deduce the aforementioned estimates.

July 7, 2011

Omri Sarig, Weizmann, Markov partitions for surface diffeomorphisms

A basic problem in ergodic theory is to explain why for a deterministic dynamical system $f:M\to M$, the time series $\{A(f^n(x)):n>1\}$ of a smooth observable $A:M\to R$ looks "random". One idea is to look for a change of coordinates which transforms the collection of orbits of $f$ into the collection of paths on a directed graph in such a way that the action of $f$ is transformed into the left translation ("walk on the graph"). This transforms the phase space of $f$ into the sample space of a Markov chain.

The technical device needed to do this is called a "Markov partition".Markov partitions were previously known to exist for "uniformly hyperbolic" diffeomorphisms (Adler & Weiss, Sinai, Bowen). For general diffeomorphisms with positive entropy, Katok constructed invariant sets E s.t. $f|E$ has a Markov partition. But his sets usually have measure zero. The result is that every smooth surface diffeomorphism with positive topological entropy has invariant sets $E$ of full measure s.t. $f|E$ has a Markov partition.

I will try to make the talk accessible to people with little or no background in dynamical systems.

June 30, 2011

Doron Puder, Hebrew Univesity, Measure Preserving Words are Primitive

Let $a$,$b$,$c$,... in $S_n$ be random permutations on $n$ elements, chosen at uniform distribution. What is the distribution of the permutation obtained by a fixed word in the letters $a$,$b$,$c$,..., such as $ab$,$a^2$, $a^2bc^2b$, or $aba^{-2}b^{-1}$? More concretely, do these new random permutations have uniform distribution? In general, a free word $w$ in $F_k$ is called measure preserving if for every finite group $G$, the word map $w: G^k \to G$ induces uniform distribution on $G$ (given uniform distribution on $G^k$). So which words are measure preserving?

This question is strongly connected to the notion of primitive words in the free group $F_k$. The word $w$ is called primitive is it belongs to some basis, i.e. a generating set of size $k$. It is an easy observation that a primitive word is measure preserving. It is conjectured that the converse is also true. We prove it for $F_2$. In a very recent joint work with O. Parzanchevski, we manage to prove the conjecture in full.

All notions will be defined and explained.

Note unusual day, time and place! Wednesday, June 22, 2011, 14:00-15:00, Ziskind 1.

Charilaos Efthymiou, Warwick, A simple algorithm for random colouring $G(n, d/n)$ using $(2+\epsilon)d$ colours.

Approximate random $k$-colouring of a graph $G=(V,E)$ is a very well studied problem in computer science and statistical physics. It amounts to constructing a $k$-colouring of $G$ which is distributed close to the Gibbs distribution, i.e. the uniform distribution over all the $k$-colourings of $G$. Here, we deal with the problem when the underlying graph is an instance of Erdős-Rényi random graph $G(n,p)$, where $p=d/n$ and $d$ is fixed.

We propose a novel efficient algorithm for approximate random $k$-colouring with the following properties: given an instance of $G(n,d/n)$ and for any $k>(2+\epsilon)d$, it returns a $k$-colouring distributed within total variation distance $n^{-\Omega(1)}$ from the Gibbs distribution, with probability $1-n^{-\Omega(1)}$.

What we propose is neither a MCMC algorithm nor some algorithm inspired by the message passing heuristics that were introduced by statistical physicists. Our algorithm is of combinatorial nature. It is based on a rather simple recursion which reduces the random $k$-colouring of $G(n,d/n)$ to random $k$-colouring simpler subgraphs first.

The lower bound on the number of colours for our algorithm to run in polynomial time is dramatically smaller than the corresponding bounds we have for any previous algorithm.

Note unusual day and place! Wednesday, June 22, 2011, 11:00-1:00, Ziskind 1

Erick Herbin, Ecole Centrale Paris, Several characterisations of the set-indexed Lévy processes

In this joint work with Ely Merzbach, the aim is to present a satisfactory definition of the class of set-indexed Lévy processes including the set-indexed Brownian motion, the spatial Poisson process, spatial compound Poisson processes and some other stable processes and to study their properties.

More precisely, the Lévy processes are indexed by a quite general class $\mathcal{A}$ of closed subsets in a measure space $(\mathcal{T} ,m)$. In the specific case where $\mathcal{T}$ is the $d$-dimensional rectangle $[0 ,1]^d$ and $m$ is the Lebesgue measure, a special kind of this definition was given and studied by Bass and Pyke ([BaPy84]) and by Adler and Feigin ([AdFe84]). However, in our framework the parameter set is more general and, it will be shown that no group structure is needed in order to define the increment stationarity property for Lévy processes (see [HeMe06] and [HeMe09]).

Thanks to this satisfactory definition, links with infinitely divisible distributions can be established and consequently the Lévy-Khintchine representation formula.

Markov properties are also considered: We proved that a set-indexed Lévy process is a Markov process characterized by the homogeneity of its transition system.

[AdFe84] R.J. Adler and P.D. Feigin, On the cadlaguity of random measures, Ann. Probab. 12, 615-630, 1984.

[BaPy84] R.F. Bass and R. Pyke, The existence of set-indexed Lévy processes, Z. Wahr. verw. Gebiete 66, 157-172, 1984.

[HeMe06] E. Herbin and E. Merzbach, A set-indexed fractional Brownian motion, J. of Theoret. Probab., Vol. 19, No. 2, pp. 337-364, 2006.

[HeMe09] E. Herbin and E. Merzbach, Stationarity and Self-similarity Characterization of the Set-indexed Fractional Brownian Motion, J. of Theoret. Probab., Vol. 22, No. 4, pp. 1010-1029, 2009.

June 9, 2011

Asaf Nachmias, MIT, The percolation phase transition in the Hamming cube

Consider percolation on the Hamming cube $\{0,1\}^n$ at the critical probability $p_c$ (at which the expected cluster size is $2^{n/3}$). It is known that if $p=p_c(1+O(2^{-n/3}))$, then the largest component is of size roughly $2^{2n/3}$ with high probability and that this quantity is non-concentrated. We show that for any sequence $\varepsilon(n)$ such that $\varepsilon(n)\gg 2^{-n/3}$ and $\varepsilon(n)=o(1)$ percolation at $p_c(1+\varepsilon(n))$ yields a largest cluster of size $(2+o(1))\varepsilon(n)2^n$.

This result settles a conjecture of Borgs, Chayes, van der Hofstad, Slade and Spencer.

Joint work with Remco van der Hofstad.

June 2, 2011

Boris Solomyak, University of Washington, Hausdorff dimension for subshifts invariant under the multiplicative integers

Consider the set $S$ of real numbers $x$ in the unit interval, such that for all $n$, the $n$'th and $(2n)$'th binary digits of $x$ are not both 1. We find explicitly the Hausdorff dimension of $S$, and show that it is strictly smaller than the Minkowski dimension. We put this in a general context of invariance under the semigroup of multiplicative integers. (Joint work with Rick Kenyon and Yuval Peres.)

Note special place and time! May 26, 2011, 16:00-17:00, Ziskind 1

Omer Angel, University of British Columbia, Random Graph Orderings

We show that there is no interesting way to order the vertices of a graph, and deduce a theorem about isometric embedding of metric spaces in $\mathbb{R}^n$. (Joint with Lyons and Kechris)

May 26, 2011

Eyal Lubetzky, Microsoft research, Critical slowdown for the Ising model on the two-dimensional lattice

Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the Glauber dynamics for the Ising model on $\mathbb{Z}^2$ everywhere except at criticality. At the static phase-transition for Ising, the dynamics is conjectured to undergo a critical slowdown: At high temperature the inverse-gap is $O(1)$, at the critical $\beta_c$ it is polynomial in the side-length and at low temperature it is exponential in it. A long series of works verified this picture on $\mathbb{Z}^2$ except at $\beta=\beta_c$ where the behavior remained unknown. In this work we establish the first rigorous polynomial upper bound for the critical mixing, thus confirming the critical slowdown for the Ising model in $\mathbb{Z}^2$. Namely, we show that on a finite box with arbitrary boundary conditions, the inverse-gap at $\beta=\beta_c$ is polynomial in the side-length. The proof harnesses recent understanding of the scaling limit of critical Fortuin-Kasteleyn representation of the Ising model together with classical tools from the analysis of Markov chains.

Based on joint work with Allan Sly.

Note special time and place! May 19, 2011, 16:00-18:00, Ziskind 1

Francis Comets, Universite Paris Diderot, Kolmogorov-Petrovski-Piscunov equation with random rate.

We discuss the KPP equation when the rate is a random process depending on both time and space; more precisely the large time asymptotics, and how the front speed is affected by the inhomogenities in the random environment. The KPP equation has a well-known representation with a Branching Brownian Motion. The mean population size of the BBM relates to the so-called Directed Polymer in Random Environment, which has been much studied recently. We show that (i) the front has a limiting speed, which can be expressed in terms of Lyapunov exponents for the DPRE; (ii) the speed has a phase transition for large space dimension. Joint work with Errico Presutti (Roma 2), in progress.

May 19, 2011

Robert Adler, Electrical Engineering, Technion, The Gaussian kinematic formula

The classic kinematic fundamental formula is a basic result of finite dimensional integral geometry, describing, on average, what happens when one fixed set intersects another, randomly placed.

The Gaussian kinematic formula is a far more recent result, which gives explicit formulae for the mean values of a number of geometric characteristics of random sets generated by Gaussian and related random processes.

The aim of this talk will be to explain both of these results, the connections between them, and a number of applications of the Gaussian kinematic formula to areas as far apart as large deviations and (random) persistent homology.

May 12, 2011

Student Probability Day III, in memory of Oded Schramm. See

May 5, 2011

Leonid Mytnik, Technion, Uniqueness and non-uniqueness for stochastic heat equations with Hölder continuous coefficients

We consider the question of uniqueness/non-uniqueness for stochastic partial differential equations (SPDEs). We focus on heat equations perturbed by a multiplicative noise, or the stochastic heat equations. Such equations with Hölder $1/2$ coefficients arise in population models. Examples include the density of super-Brownian motion, stepping stone models and limits of branching annihilating random walks. Does pathwise uniqueness hold for such equations? In 1971, the analogous question for SDE's was resolved in the affirmative by T. Yamada and S. Watanabe. As for stochastic heat equations we prove pathwise uniqueness in the case of Hölder coefficients of index $\gamma > 3/4$. We also prove that uniqueness in law, and hence pathwise uniqueness, fails in general for $\gamma < 3/4$. The proof of non-uniqueness is closely related to considering the limits of branching-annihilating random walks. We discuss a number of open questions.

These results are joint with Ed Perkins and Carl Mueller.

April 28, 2011

Matthias Keller, Hebrew University, Absolutely continuous spectrum on trees

We study discrete Schrödinger operators on a class of rooted trees with an underlying substitution type structure. The spectrum of the free Laplacian is shown to be purely absolutely continuous and to consist of finitely many intervals. We further show stability of absolutely continuous spectrum under small perturbations of the Laplacian by certain deterministic and random potentials.

April 14, 2011

Ran Tessler, Hebrew University, 2D Spin Glass in Zero and Low Temperatures

We consider the Edwards-Anderson Ising spin-glass models, and show that in a (measurable, translation invariant) ground state the (dual) unsatisfied edges do not percolate, i.e. do not form an infinite cluster. We then consider the case of low temperature, and show a similar result about configurations in the support of a translation-invariant Gibbs-Boltzmann measure.

All terms would be explained in the talk.

April 7, 2011

Cyrille Lucas, Paris, Internal Diffusion Limited Aggregation, from the symmetric to the asymmetric case.

Internal Diffusion Limited Aggregation, or iDLA, is a growth model in which random sets are constructed recursively. At each step, a random walk starts at the origin and the first point it visits outside the cluster is added to the cluster. The asymptotic behaviour of this model depends on the properties of the random walk, and one can prove that a limiting shape exists for a wide range of symmetric walks. We show the existence of an almost sure limiting shape for random walks with a drift, which leads to an interesting result in parabolic PDE theory.

March 31, 2011

Moshe Cohen, Bar Ilan Univesity, Dimer models for the Alexander and twisted Alexander polynomials of knots

A knot is a circle embedded in three-space. One can distinguish knots by means of several popular polynomial invariants. The Alexander polynomial (and its twisted version) are algebraically constructed; this talk presents combinatorial constructions.

From a knot diagram, one constructs a bipartite graph on which to consider perfect matchings. Specified weights on these edges provide the Alexander polynomial of the knot when summing over all perfect matchings and taking the product of all edges in the perfect matching.

The twisted Alexander polynomial takes the additional input of a representation on the fundamental group of the knot complement. Choosing representations coming from knot colorings give permutation matrices, and from these one gets a bipartite graph (on which to consider matchings) that turns out to be a lifting of the previous graph.

This talk is accessible to all who understand matrix determinants and are comfortable with graphs. No background in Knot Theory will be supposed.

Joint work with Oliver Dasbach and Heather Russell

March 24, 2011

Johan Tykesson, Weizmann Random interlacements and amenability

We consider the model of random interlacements on transient graphs, which was first introduced by A-S. Sznitman in arXiv:0704.2560 for the special case of $Z^d$ (with $d > 2$). There it was shown that on $Z^d$, for any intensity $u > 0$, the interlacement set is almost surely connected. The main result of this paper says that for transient, transitive graphs, the above property holds if and only if the graph is amenable. In particular, we show that in non-amenable transitive graphs, for small values of the intensity $u$, the interlacement set has infinitely many infinite clusters. We also provide examples of non-amenable transitive graphs, for which the interlacement set becomes connected for large values of $u$. Finally, we establish the monotonicity of the transition between the 'disconnected' and the 'connected' phases, providing the uniqueness of the critical value $u_c$ where this transition occurs. This is joint work with Augusto Teixeira, ENS Paris

March 17, 2011

Yan Dolinsky, Weak Approximation of $G$-Expectations.

We introduce a notion of volatility uncertainty in discrete time and define the corresponding analogue of Peng's $G$-expectation. In the continuous-time limit, the resulting sublinear expectation converges weakly to the $G$-expectation. This can be seen as a Donsker-type result for the $G$-Brownian motion.

Joint work with M. Nutz and H. M. Soner.

March 3, 2011

Wojciech Samotij, Odd cutsets and the hard-core model on $Z^d$.

The hard-core model (short for hard-core lattice gas model) was originally introduced in statistical mechanics as a simple mathematical model of a gas whose particles have non-negligible size and cannot overlap. The canonical (and the most studied) case of a hard-core model is that when the underlying graph is the nearest-neighbor graph of the integer lattice $Z^d$.

In this talk, we will first give a brief description of this model and show how the central question about its behavior, the appearance of a phase transition, can be reduced to a purely combinatorial problem of counting weighted independent sets in a finite subgraph of the integer lattice. In the second part of the talk, we will sketch the proof of our recent contribution to the study of this model, which brings us a little close to resolving this central question. The proof is based on ideas from a recent work of Peled on the typical behavior of integer-valued Lipschitz functions on high-dimensional tori. One of the main ingredients in the proof is a careful analysis of the properties of "odd cutsets" — a class of cutsets introduced in the work of Peled, which might be of independent interest.

This is joint work with Ron Peled.

February 17, 2011

Chen Meiri, Hebrew University, Sieve methods in group theory.

Sieve theory is a classical and well developed area of analytic number theory. It had been applied in an attempt to solve many classical problems. In recent years there was an attempt to use sieve theory in non-commutative setting, e.g. in group theory. Bourgain-Gamburd-Sarnak used this theory to find "almost prime" vectors on the orbit of a non-commutative group $\Gamma$ acting on $\mathbb{Z}^n$ while Rivin used it to show that a "genric" element of the mapping class group is pseudo-Anosov.

In this talk we will present another application of the sieve in group theory: If $\Gamma$ is a finitely generated non-virtually-solvable subgroup of $\mathrm{GL}_n(\mathbb{C})$ then a "genric" element of $\Gamma$ is not a power, i.e. does not belong to the set $\{g^n \mid g \in \Gamma \wedge n \ge 2\}$. This result is joint work with Alexander Lubotzky.

Note late start! February 10, 2011, 11:30

Ehud Friedgut, Hebrew University Triangle-intersecting families of graphs.

How many graphs can you choose on a fixed set of $n$ vertices such that the intersection of any two of them contains a triangle? Sós and Simonovits conjectured in 1976 that the largest such families of graphs are obtained by taking all graphs containing a fixed triangle, and that these are the only extremal constructions. This question turned out to be relatively resilient to the standard methods in extremal combinatorics, with partial progress being made in 1986 after Chung-Graham-Frankl-Shearer introduced some novel entropy arguments. Recently, with David Ellis and Yuval Filmus, we have been able to prove the conjecture, using discrete Fourier analysis and spectral methods. In this talk I'll sketch the proof.

February 3, 2011

Tom Ellis, Cambridge, From Diffusion Limited Aggregation to the Brownian Web via Conformal Mappings.

Diffusion Limited Aggregation (DLA) is a planar growth model where the rate of growth at at point on the boundary of a cluster is proportional to the harmonic measure there. I will define the Hastings-Levitov growth models which approximate DLA, and show how they use ideas of conformal invariance which are analogous to those from the celebrated area of Schramm-Loewner Evolution.

I will demonstrate how the evolution of the harmonic measure on the cluster boundary corresponds to a stochastic flow, and will explain why -- in a suitable scaling limit -- the flow converges to an independent system of coalescing Brownion motions, known as the Brownian web.

January 27, 2011

Erwin Bolthausen, Universität Zürich, A recursive scheme for the construction of solutions of the TAP equations.

January 20, 2011

Hugo Dominil-Copin, Université de Genève, Parafermions in lattice models.

In this talk, I will describe a general strategy to prove conformal invariance in the scaling limit of interfaces of a two-dimensional lattice model. The central step consists in finding a discrete observable converging in the continuum limit to a conformally invariant object. In the case of FK percolations and $O(n)$ models, I will define natural candidates, called parafermionic observables. Despite the fact that one cannot prove the convergence of these observables (and thus conformal invariance of the underlying model), we will explain how one can use them to prove non trivial facts on the models. Joint work with Stanislav Smirnov.

Note unusual day and place! Wednesday, January 12, 2011, Feinberg Graduate School room C

Ivan Corwin, Courant, New York, The KPZ universality class and equation.

The Gaussian central limit theorem says that for a wide class of stochastic systems, the bell curve (Gaussian distribution) describes the statistics for random fluctuations of important observables. In this talk I will look beyond this class of systems to a collection of probabilistic models which include random growth models, polymers, particle systems, matrices and stochastic PDEs, as well as certain asymptotic problems in combinatorics and representation theory. I will explain in what ways these different examples all fall into a single new universality class with a much richer mathematical structure than that of the Gaussian.

January 6, 2011

Amir Dembo, Stanford University, CLT for biased random walk on multi-type Galton-Watson tree.

Let $T$ be a rooted multi-type Galton-Watson (MGW) tree of finitely many types with at least one offspring at each vertex and an offspring distribution with exponential tails. The $r$-biased random walk $X(t)$ on $T$ is the nearest neighbor random walk which, when at a vertex $v$ with $d(v)$ offspring, moves closer to the root with probability $r/(r+d(v))$ and to each of the offspring with probability $1/(r+d(v))$. This walk is transient if and only if $0 < r < R$, with $R$ the Perron-Frobenius eigenvalue for the (assumed) irreducible matrix of expected offspring numbers. Following the approach of Peres and Zeitouni (2008), in a joint work with Nike Sun we show that at the critical value $r=R$, for almost every $T$, the process $|X(nt)|/\sqrt{n}$ converges in law as $n$ goes to infinity to a deterministic positive multiple of a reflected Brownian motion. Our proof is based on a new explicit description of a reversing measure for this walk from the point of view of the particle, a construction which extends to the reversing measure for a biased random walk with random environment (RWRE) on MGW trees, again at a critical value of the bias.

Note special place! December 30, 2010, Feinberg Graduate School room A

Anatoly Vershik, Steklov Institute, Scaling entropy in ergodic theory and dynamics of metrics

The traditional approach to the theory of dynamical systems is to fix some metric space (phase space) with the group of homeomorphisms or diffeomorphisms and to consider evolution of points, functions and measures. The alternative approach is to fix invariant measure and to study the evolution of metrics. It happened that such an idea gives the new invariants of dynamics which, for instance, generalized the Kolmogorov-Sinai entropy and others. In the talk I describe the first steps in this direction and also classification of the metric spaces with measure.

Note special time, day and place! Sunday, December 26, 2010, 14:00-16:00, Feinberg graduate school, room C

Part I. Alexandre Stauffer, UC Berkeley, Mobile Geometric Graphs: Detection, Coverage and Percolation

We consider the following random graph model, which is motivated by mobile wireless networks. At time 0, take a Poisson point process over $\mathbb{R}^2$ with constant intensity to be the nodes of the graph and let each node move independently according to Brownian motion. At any time $t$, we have an edge between every pair of nodes for which their distance at time $t$ is at most $r$. We study three fundamental features in this model: detection (the time until a given target point---which may be either fixed or moving---is within distance $r$ to some node of the graph), coverage (the time until all points inside a finite box are detected by the graph), and percolation (the time until a given node belongs to the infinite connected component of the graph). We obtain precise asymptotics for these features by combining ideas from stochastic geometry, coupling, and multi-scale analysis. (Joint work with Y. Peres, A. Sinclair, P. Sousi.)

Part II. Yuval Peres, Microsoft Research, The Wiener Sausage with drift and the Pascal principle

The Wiener sausage at time $t$ is the algebraic sum of a Brownian path on $[0,t]$ and a ball. Does the expected volume of the Wiener sausage increase when we add drift? How do you compare the expected volume of the usual Wiener sausage to one defined as the algebraic sum of the Brownian path and a square (in 2D) or a cube (in higher dimensions)? We will answer these questions using their relation to the detection problem for the mobile geometric graph, and rearrangement inequalities on the sphere (based on joint works with J. Miller, P. Sousi, A. Stauffer, A. Sinclair)

December 23, 2010

Ori Gurel-Gurevich, University of British Columbia, The unlikeliness of being covered

We will show that the probability that a simple random walk will cover a finite, bounded degree graph in linear time is exponentially small.

More precisely, for every $D$ and $C$, there exists $a=a(D,C)>0$ such that for any graph $G$, with $n$ vertices and maximal degree $D$, the probability that a simple random walk, started anywhere in $G$, will visit every vertex of $G$ in its first $Cn$ steps is at most $\exp(-an)$.

Joint work with Itai Benjamini and Ben Morris.

Note special time and day! Sunday, December 19, 2010, 14:00-16:00

Asaf Nachmias, MIT, Is the critical percolation probability local?

We show that the critical probability for percolation on a $d$-regular non-amenable graph of large girth is close to the critical probability for percolation on an infinite $d$-regular tree. This is a special case of a conjecture due to O. Schramm on the locality of $p_c$. An interesting corollary is that for non-amenable graphs of high girth the critical probability is strictly smaller than the uniqueness threshold, that is, $p_c < p_u$.

Joint work with Itai Benjamini and Yuval Peres.

December 16, 2010

David Ralston, Growth rates and one-sided boundedness of a particular ergodic sum

Using nothing more sophisticated than first-return maps and elementary properties of continued fractions, we will develop a constructive approach to studying the sequence of ergodic sums of the characteristic function of the interval [0,1/2] under an irrational rotation of the circle minus the characteristic function of (1/2,1), to ensure zero mean. The principle benefit of the elementary (but somewhat tedious) approach is that statements may be derived about specific rotations, as opposed to generic ones. Our primary topics of investigation will be:

-what growth rates are allowed for such sequences?
-what is the structure of the set of positions whose ergodic sums are always nonnegative?

In both cases we will develop specific examples. Time permitting, we will then discuss applications of these techniques to informal questions of K. Park and W. Veech, as well as ongoing work regarding dynamics on a particular infinite translation surface (joint w/Barak Weiss of BGU).

December 9, 2010 (Note: talk is joint with the concurrent conference, so room remains Ziskind 261)

Amin Coja-Oghlan, Phase transitions and computational complexity

Phase transitions have long been studied in statistical mechanics in the context of disordered systems such as spin glasses. Indeed, physicists have developed ingenious, albeit non-rigorous, techniques for the study of phase transitions. In recent years it has emerged that phase transitions also play a key role in computer science. In this talk I am going to give an overview of this exciting area, and explain how ideas from statistical mechanics shed light on the mystery of computational complexity. In addition, I am going to survey the recent progress in turning the statistical mechanics work into a rigorous theory.

Note special time! November 25, 2010, 16:00-17:00

Vladas Sidoravicius, CWI and IMPA, Abundance of maximal paths in Bernoulli last-passage percolation

November 25, 2010

Ming Fang, Minnesota, On Branching Random Walks

Branching random walks are a family of random walks indexed by the tree generated by a branching process. They can be viewed as particles performing random walks while splitting. In this talk, we will first review some of the results on the maximal displacement of branching random walks in the classical settings, where the behavior for each particle is independent and identically distributed. Specifically, we will discuss the law of large numbers of the maxima, a second order correction to the LLN, exponential tails for the maximum, etc. Then, we will introduce a variant of the model in which dependence between siblings and dependence on time are allowed. For this model, we prove the tightness of the maxima using a Lyapunov function method. No prerequisites are assumed except for basic calculus.

November 18, 2010

Senya Shlosman, Centre de Physique Théorique, Marseille, Spontaneous Resonances and the Coherent States in the Queuing Networks

We study particle systems corresponding to highly connected queuing networks. We examine the validity of the so-called Poisson Hypothesis (PH), which predicts that the Markov process, describing the evolution of such particle system, started from a reasonable initial state, approaches the equilibrium in time independent of the size of the network.

This is indeed the case in many situations. However, there are networks for which the relaxation process slows down. This behavior reflects the fact that the corresponding infinite system undergoes a phase transition. It is characterized by the property that different nodes of the network start to evolve in a synchronous way.

Such transition can happen only when the load per node exceeds some critical value, while in the low load situation the PH behavior holds. The load thus plays here the same role as the inverse temperature in statistical mechanics.

We will mention a related open problem of ergodicity of an interacting particle system with unique stationary state.

November 11, 2010

Gideon Amir, Bar Ilan University, Liouville, amenability, automaton groups and random walks on discrete fractals

Many classical fractals, such as the Sierpinski gasket, and Julia sets of polynomials can be described through groups generated by finite automata. Automaton groups also provide a rich source of examples (such as Grigorchuk group of intermediate growth) and play an important role in geometric group theory. In this talk we will show a phase transition in the Liouville property of automaton groups, and deduce that all automaton groups with activity growth of degree up to 1 are amenable. A key ingredient is the analysis of random walks on the Schreier graphs of these groups.

This talk is based on joint works with O. Angel and B. Virag. No prior knowledge on automatons, the Liouville property or amenability is required

October 21, 2010

Barak Weiss, Ben Gurion University, Infinite lattice surfaces and ergodicity for $\mathbb{Z}$-valued skew products over interval exchanges

Compact lattice surfaces (also known as Veech surfaces) have been intensively studied over the last 20 years. After a quick historical introduction to the theory of compact lattice surfaces I will describe recent joint work with Pascal Hubert and Pat Hooper in which we study non-compact lattice surfaces which arise as $\mathbb{Z}$-covers of compact ones. I will discuss ergodicity results for the straightline flow in these surfaces, which give rise to new examples of ergodic $\mathbb{Z}$-valued skew products over interval exchanges.

For previous years see: 2007-2010, 2005-2007 (maintained by Boaz Tsaban) 2000-2005 (maintained by Gideon Schechtman)

Powered by MathJax