Thursday 11:00-13:00, Ziskind Room 261. map, directions.

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

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

Upcoming talks

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

March 15, 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 22, 2012

Igal Sason, Technion, TBA

March 29, 2012

Ron Blei, University of Connecticut, TBA

May 3, 2012

Ran Tessler, Hebrew University, TBA

May 17, 2012

Mark Rudelson, University of Michigan, TBA

List of previous talks sorted backwards

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 http://www.wisdom.weizmann.ac.il/spd3/spd3.html

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.

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)