Skip to main content Skip to navigation

Abstracts

Omer Angel (UBC)
A dichotomy for unimodular maps

We show that for a unimodular random planar map, many geometric and probabilistic properties are equivalent. These include local and global properties: Negative mean curvature, invariant non-amenability, gap between the critical and uniqueness parameters for percolation, distinction between free and wired uniform spanning forests, and more.
With Tom Hutchcroft, Asaf Nachmias and Gourab Ray

Márton Balázs (Bristol)
Electric network for non-reversible Markov chains (Joint work with Áron Folly)

There is a well-known analogy between reversible Markov chains and electric networks: the probability of reaching one state before another agrees with voltages in a corresponding network of resistances, and the electric current also has a probabilistic interpretation. Such analogies can be used to prove a variety of theorems regarding transience-recurrence, commute times, cover times. The electric counterpart is very simple, consists of resistors only.
These simple components behave in a symmetric fashion, that's why the analogy only works for reversible chains.
We found the electric component that allows to extend the above analogy from reversible Markov chains to irreversible ones. I will describe this new component, show how the analogy works, demonstrate some arguments that can be saved from the reversible case. I will also show how Rayleigh's monotonicity principle fails in our case, and interpret a recent non-reversible result of Gaudillière and Landim on the Dirichlet and Thomson variational principles in the electrical language.

Johannes Carmesin (Hamburg/Cambridge)
Every planar graph with the Liouville property is amenable

We introduce a strengthening of the notion of transience for plane graphs in order to relax the standard condition of bounded degree appearing in various results, in particular, the existence of Dirichlet harmonic functions proved by Benjamini & Schramm. As a corollary we obtain that every planar non-amenable graph admits Dirichlet harmonic functions.
This is joint work with Agelos Georgakopoulos.

Ronen Eldan (Washington)
Braess's paradox for the spectral gap in random graphs and delocalization of Eigenvectors

We study how the spectral gap of the normalized Laplacian of a random graph changes when an edge is added to or removed from the graph. There are known examples of graphs where, perhaps counterintuitively, adding an edge can decrease the spectral gap, a phenomenon that is analogous to Braess's paradox in traffic networks. We will see that this is often the case in Erdös-Rényi random graphs, in the sense that with a strictly positive probability, the addition of a random edge will decrease the spectral gap. To do this, we introduce a new de-localization result for eigenvectors of the Laplacian, which might be of independent interest. Joint work with Miklos Racz and Tselil Schramm.

Antoine Gournay (Neuchatel)
The reduced $\ell^p$-cohomology in degree 1 and harmonic functions

Reduced $\ell^p$-cohomology in degree 1 (for short "LpR1") is a useful quasi-isometry invariant of graphs [of bounded valency] whose definition is relatively simple. On a graph, there is a natural gradient operator from functions to vertices to functions on edges defined by looking at the difference of the value on the extremities of the edge. Simply put, this cohomology is the quotient of functions with gradient in $\ell^p$ (of the edges) by functions who are themselves in $\ell^p$ (of the vertices).
"LpR1" is a space of function on some ideal boundary. For example, for $p=1$ it can be seen as a space of functions on the ends. In the case of hyperbolic graphs it can be seen as a space of Besov functions on the usual boundary (a result of Bourdon & Pajot).
In this talk, I will explain how, under some assumptions on the isoperimetric profile one can identify "LpR1" with a subspace of the space of bounded harmonic functions and yields some interesting corollaries on this space (for example, on lamplighter graphs). The transport cost comes up naturally as a key ingredient in the proof.

Ori Gurel-Gurevich (Hebrew University, Jerusalem)
Boundaries of planar graphs

We discuss the relation between properties of the simple random walk on a bounded degree, planar graph and the geometric properties of a nice embedding of the graph in the plane (e.g. a circle packing of the graph). Specifically, we show two results:
1) The graph is recurrent if and only if the boundary of the embedding is a polar set (that is, Brownian motion misses it almost surely).
2) If the graph is one ended and transient, and it is embedded nicely in the unit disk then the boundary of the disk, i.e. the unit circle is a representation of the Poisson and Martin boundaries, via the natural extension of the embedding.
Based of joint works with Omer Angel, Martin Barlow, Asaf Nachmias and Juan Souto.

Ben Hambly (Oxford)
Asymptotics for spectra and heat kernels for some random fractals

I will look at diffusions on some random fractal structures and discuss the behaviour of the associated on-diagonal heat kernel and spectral counting function. The aim is to get sharper information about theshort time and high frequency asymptotics of these quantities. We will consider examples such as the continuum random tree, the scaling limit of the Erdos-Renyi random graph and percolation clusters on the diamond hierarchical lattice.

Vadim Kaimanovich (Ottawa)
Stopping times and Poisson boundaries

The Poisson boundary of a random walk on a group is defined as the space of ergodic components of the time shift in its path space. In this talk I will discuss how Markov stopping times applied to the path space (in a way similar to time changes in the classical dynamical setup) give rise to new random walks with the same Poisson boundary.

Konrad Kolesko (Wroclaw)
Almost sure pointwise fluctuations of critical Mandelbrot cascades

A lognormal multiplicative chaos was introduced by Mandelbrot to model turbulences. Its ''toy model'', so-called Mandelbrot cascades, is a measures valued stochastic process. An appropriately normalized sequence of multiplicative cascades converges weakly in probability to a nontrivial limit measure $\mu$. In the simplest example, given $\beta>0$ (inverse temperature parameter), $\mu$ is a finite random measure on the unit interval $I=[0,1)$ satisfying the self-similarity property $$\mu(B)\stackrel{d}{=}\frac{e^{\beta \xi_1-\beta^2/2}}2\mu_{1}\Big(2\big(B\cap [0,1/2)\big)\Big)+\frac{e^{\beta+\xi_2-\beta^2/2}}2\mu_{2}\Big(2\big(B\cap[1/2,1)\big)-1\Big),$$where $\mu_1,\mu_2$ have the same law as $\mu$, $\xi_1,\xi_2$ are standard normal variables and all random variables $\mu_1,\mu_2,\xi_1,\xi_2$ are independent.
It is known that there is a critical value $\beta_c=\sqrt{2\log2}$ (freezing temperature) where there is a phase transition. For $\beta\le\beta_c$ (high temperature) the measure $\mu$ is continuous, although singular with respect to the Lebesgue measure, whereas for $\beta>\beta_c$ (low temperature) it is purely atomic. In the continuous case one may asked about the Hausdorff dimension of $\mu$. Closely related problem, by Frostman's lemma, is the question how $\mu$ fluctuates. We are looking for deterministic functions $\phi$ and $\psi$ such that for almost all realizations of $\mu$, for $\mu$-almost all $x\in I$ and for sufficiently large $n$ we have $$\phi(n)\le\mu(B_n(x))\le\psi(n),$$ where $B_n(x)$ is a dyadic set of length $2^{-n}$ containing $x$.
The question above has been answered in the subcritical case $\beta<\beta_c$ by Liu. For the critical case $\beta=\beta_c$ some partial results were obtained by Barral, Kupiainen, Nikula, Saksman and Webb. In the talk we will present sharper results.
Bibliography
Q. Liu On generalized multiplicative cascades. Stoch. Proc. Appl. 86, 263–286 (2000).
J. Barral, A. Kupiainen, M. Nikula, E. Saksman & C. Webb Critical Mandelbrot Cascades. Commun. Math. Phys. 325, 685–711 (2014).

Daniel Lenz (Jena)
Uniformly transient graphs

We study a special class of graphs with a strong transience feature called uniform transience. We characterize uniform transience via a Feller-type property, via validity of an isoperimetric inequality and via equality of the Royden boundary and the harmonic boundary and show that the Dirichlet problem has a unique solution for such graphs. The Markov semigroups and resolvents (with Dirichlet boundary conditions) on these graphs are shown to be ultracontractive. Moreover, if the underlying measure is finite, the semigroups and resolvents are trace class and their generators have $\ell^p$ independent pure point spectra. Examples of uniformly transient graphs include Cayley graphs of hyperbolic groups as well as trees and Euclidean lattices of dimension at least three. This is joint work with Matthias Keller, Marcel Schmidt and Radoslaw Wojciechowski.

Peter Morters (Bath)
Robustness of spatial preferential attachment networks

A growing family of random graphs is called robust if it retains a giant component after percolation with arbitrarily small positive retention probability. We study robustness for graphs, in which new vertices are given a spatial position on the unit circle and are connected to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering we can independently tune the power law exponent τ of the degree distribution and the rate −δ at which the connection probability decreases with the distance of two vertices. We show that the network is robust if τ < 2 + 1/δ , but fails to be robust if τ > 2 + 1/(δ−1) . This seems to be the first instance of a scale-free network where robustness depends not only on its degree distribution but also on its clustering features. This is joint work with Emmanuel Jacob (ENS Lyon).

Thomas Sauerwald (Cambridge)
Multiple Random Walks: Cover Times, Hitting Times and Applications

In this talk we will consider multiple random walks that are run independently and in parallel on a finite, undirected and connected graph. Following Alon, Avin, Koucký, Kozma, Lotker and Tuttle (2008), we will study the speed-up defined as the ratio of the cover time (hitting time) of a single random walk to the cover time (hitting time) of k independent random walks, where all k walks start from a single vertex that maximises their cover time (hitting time). We will exhibit general connections between the speed-up and other parameters like the mixing time or diameter of the underlying graph, and apply these results to specific networks including d-dimensional grids, hypercubes and expanders. Finally, we will outline how multiple random walks can be applied to the design and analysis of efficient load balancing algorithms.

Alessandro Sisto (ETH)
Central limit theorem for acylindrically hyperbolic groups

Acylindrically hyperbolic groups form a large class of groups including non-elementary (relatively) hyperbolic groups, mapping class groups, Out(F_n), many CAT(0) groups, etc.
Random walks (generated by measures with exponential tail) on such groups tend to stay close to geodesics in Cayley graphs.
This property has several applications, including a central limit theorem for the distance from the identity of the endpoint of the random walk.
Joint work with Pierre Mathieu.

Perla Sousi (Cambridge)
Mixing, hitting and intersection times for Markov chains

These three notions have been studied extensively in the literature. I will present new connections between them for arbitrary reversible Markov chains. In particular, the mixing time is comparable to the maximal hitting time of large sets, and is a lower bound for the expected time it takes two copies of the chain, started at random sites, to have their paths intersect. I will also show an application to robustness of mixing time.
Based on joint works with Yuval Peres, Thomas Sauerwald and Alexandre Stauffer.

John Sylvester (Warwick)
Hitting times and effective resistances in sparsely connected Erdős–Rényi random graphs

We outline a modified breadth-first search algorithm which allows us to show w.h.p. there are many edge independent paths in an Erdős–Rényi random graph G(n,p) with edge probability $p=c\log(n)/n$. This is then used to give expectation and concentration results for the effective resistance between two vertices u and v and the random walk hitting time from u to v.

Vladislav Vysotskiy (Imperial College London/Arizona State University/St. Petersburg Division of Steklov Institute)
On hitting times of bounded sets by random walks

Consider a centred one-dimensional random walk with a finite variance. We study the tail behavior of the hitting time $\tau_B$ of a bounded set $B$ and prove that $P_x(\tau_B > n) ~ V_B(x) n^{-1/2}$. Here the asymptotic in n is the same as for hitting times of positive and negative half-lines, and $V_B$ represents dependence on the starting point $x$. The function $V_B(x)$ is harmonic for the random walk killed as it hits $B$ and hence is the potential due to a certain charge on $B$. This is gives an intuitive but a very implicit way to think of $V_B(x)$. Our proof is based on probabilistic ideas that allow to construct an explicit representation for the limit function $V_B$. If time allows, we show applications of our result to the largest gap (maximal spacing) between the first $n$ steps of the random walk.

Stephan Wagner (Stellenbosch)
Loop models on a fractal
joint work with Elmar Teufl (Tübingen)

We consider two types of loop models on self-similar, fractal-like graphs, the Sierpiński gasket and its finite approximations being a classical example. In one model, a 2-factor (spanning subgraph whose components are cycles) is chosen uniformly at random. In the other, the edge set is partitioned into cycles, again uniformly at random. The presence of "holes" in the graph turns out to have interesting consequences.
While the latter model mostly yields rather short cycles, long cycles surrounding the holes appear with high probability in random 2-factors, and those long loops feature interesting geometric properties reminiscent of random walks and their loop-erased variant.

Anita Winter (Duisberg-Essen)
Invariance principle for variable speed random walks on trees

We consider stochastic processes $X$ on complete, locally compact tree-like metric spaces on their ''natural scale'' with a boundedly finite speed measure. If the tree is discrete, $X$ is a continuous time nearest neighbor random walk which jumps from $v$ to $v'\sim v$ at rate $\tfrac{1}{2}\cdot\(\nu(\{v\})\cdot r(v,v')\)^{-1}$. If the tree is path-connected, $X$ has continuous paths. In this talk we show that a family of such processes converge weakly in path space provided that the underlying metric measure spaces converge in the Gromov-Hausdorff-vague topology.

Wolfgang Woess (TU Graz)
Quasi-isometries of graphs and groups, random walks, and harmonic functions

In this talk, I will review the story of the construction of transitive graphs that are not quasi-isometric with Cayley graphs, its relation with lamplighter groups, associated random walks and harmonic functions.
This will lead to extended construcions and questions for future work, regarding both graph & group theoretical and random walk issues.

Alex Zhai (Stanford)
Exponential concentration of cover times

For random walk on a graph, the cover time is the time it takes for all the vertices to be visited at least once. Ding, Lee, and Peres (2010) proved a connection between the cover time and the Gaussian free eld. The connection is obtained via a miraculous formula known as the generalized second Ray-Knight theorem, which remains somewhat mysterious despite many years of study.
We will prove a stochastic domination in the generalized second RayKnight theorem, which was observed by Ding (2011) to imply that the cover time is exponentially concentrated around its expectation. It was later pointed out to us that this stochastic domination result appeared earlier in a preprint of Lupu, but the connection to cover times was not mentioned. We do not assume familiarity with Gaussian free elds and Ray-Knight theorems.