David Aldous (Berkeley)
Energy of cutoff functions and heat kernel upper bounds
It is well known that electrical resistance arguments provide (usually) the best method for determining whether a graph is transient or recurrent. In this talk I will discuss a similar characterization of 'sub-diffusive behaviour' - this occurs in spaces with many obstacles or traps.
The characterization is in terms of the energy of functions in annuli. (Joint work with S. Andres.)
Localization and delocalization of eigenvectors for heavy-tailed random matrices
This is based on a joint work with Alice Guionnet. Consider an n x n Hermitian random matrix with, above the diagonal, independent entries with α-stable symmetric distribution and 0<α< 2. The spectrum of this random matrix differs significantly from the spectrum of Wigner matrices with finite variance. It can be seen as an instance of a sparse random matrix : only O(1) entries in each row have a significant impact on the behavior of the matrix. We will indeed see that this model of random matrix is closely related to a random operator defined on Aldous' Poisson weighted infinite tree. When 1<α< 2 and p >2, we will see that the Lp-norm of the eigenvectors normalized to have unit L2-norm goes to 0. On the contrary, when 0<α< 2/3, we will see that these eigenvectors are localized. These localization/delocalization results only partially recover some predictions due to Bouchaud and Cizeau in 1994.
Catching the k-NAESAT threshold
The best current estimates of the thresholds for the existence of solutions in random CSPs mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. Here we present an enhanced second moment method that allows us to narrow the gap to an additive 2-(1-o_k(1))k in the random k-NAESAT problem, one of the standard benchmarks in the theory or random CSPs. The talk is based on joint work with Konstantinos Panagiotou and Lenka Zdeborova.
In this talk, I will discuss two problems that are motivated by understanding how biased random walks behave on large critical
percolation clusters. Firstly, I consider the biased random walk on the range of a random walk. In this setting, I indicate how a localisation result can be proved by adapting techniques originally developed for one-dimensional random walks in random environments in Sinai's regime. Secondly, I will describe how introducing a bias slows down random walks on critical Galton-Watson branching process trees (this is joint work with Alexander Fribergh, New York University, and Takashi Kumagai, Kyoto University). In both settings, it is possible to make a precise statement about how the increasing the strength of the bias affects the long-time behaviour of the associated random walk.
The stable trees are nested
We show that we can construct simultaneously all the stable trees as a nested family. More precisely if 1 <β< β' ≤2 we prove that hidden inside any β-stable we can find a version of a β'-stable tree rescaled by an independent Mittag-Leffler type distribution. This tree can be explicitly constructed by a pruning procedure of the underlying stable tree or by a modification of the fragmentation associated with it. Our proofs are based on a recursive construction due to Marchal which is proved to converge almost surely towards a stable tree.
Joint work with Bénédicte Haas.
Universality and isoradiality
We present recent work with Ioan Manolescu on the universality of bond percolation on isoradial graphs. Isoradial graphs are planar graphs satisfying a geometric condition on their faces. They are harmonious environments for discretely analytic functions and the star-triangle transformation.
Spectral properties of the scaling limits of some random graphs
We consider the Laplace operator and the distance operator on the scaling limits of some random graphs. We determine the spectral asymptotics for these operators in the continuum random tree, the critical random graph scaling limit and some more general random fractals. We also discuss the spectral gap for the Laplace operator for these examples.
Google maps and improper Poisson line processes
I will report on join work in progress with David Aldous, concerning a curious random metric space on the plane which can be constructed with the help of an improper Poisson line process.
The Brownian map
Consider a triangulation of the sphere chosen uniformly at random among all triangulations with a fixed number of faces (two triangulations are identified if they correspond via an orientation-preserving homeomorphism of the sphere). We equip the vertex set of this triangulation with the usual graph distance. When the number of faces tends to infinity, the (suitably rescaled) resulting metric space converges in distribution, in the sense of the Gromov-Hausdorff distance, towards a random compact metric space called the Brownian map. This result, which confirms a conjecture of Schramm in 2006, holds with the same limit for much more general random graphs drawn on the sphere. The Brownian map thus appears as a universal model of a random surface, which is homeomorphic to the sphere but has Hausdorff dimension 4.
Comb percolation and stochastic domination
For p in (0,1), consider a percolation model on Zd under which each site is open with probability p and closed with probability 1-p. Given a graph G and an integer m, one can ask: is there an injective map from G to Zd such that (i) the image of every point in G is an open site; (ii) the images of any two neighbours in G are at distance at most m?
Such "Lipschitz embeddings into percolation" have been previously considered by Grimmett, Holroyd and others. For example, it was known that for sufficiently large p, such embeddings exist with probability 1 if G is the lattice Zd-1, but do not exist if G is Zd.
I'll describe such results, and go on to consider the case where G is a d-dimensional version of a "comb graph". We show that Lipschitz embeddings do exist in this case. The proof involves some interesting new stochastic domination results.
Joint work with Alexander Holroyd and Alexandre Stauffer.
The giant component in preferential attachment networks
We study a dynamical random network model in which at every construction step a new vertex is introduced and attached to every
existing vertex independently with a probability proportional to a concave function of its current degree. We use local approximation by branching random walks to investigate the existence of a giant component, its robustness under random and targeted attack, and its size near criticality.
(Joint work with Steffen Dereich and Maren Eckhoff.)
Renyi's random parking process on a domain D in d-space is a point process with hard-core and no-empty-space properties that are desirable for modelling materials such as rubber. It is obtained as follows: particles arrive sequentially at uniform random locations in D, and are rejected if they violate the hard-core constraint, until the accepted particles saturate D.
We describe how any real-valued functional on this point process, provided it enjoys certain subadditivity properties, satisfies an averaging property in the thermodynamic limit. Consequently in this limit, one has a convergence of macoroscopically-defined energy functionals for deformations of the point process, to a
homogenized limiting energy functional. We may also apply the results to derive laws of large numbers for classical optimization problems such as travelling salesman on the parking point process.
Joint work with Antoine Gloria (INRIA, Lille)
In the classical Erdos-Renyi random graph process, a graph on n vertices grows step-by-step, by the addition of edges selected uniformly at random. Achlioptas processes are a variant in which in each step, two potential edges are selected uniformly at random, but only one is added to the graph, chosen according to some rule. Depending on the rule, the evolution of the component structure, and in particular the phase transition where a giant component emerges, may differ substantially from the Erdos-Renyi case. The talk will include a number of recent joint results with Lutz Warnke; there are also many open questions.
On Gaussian Free Fields and Random Interlacements
We describe recent results obtained jointly with Pierre-Francois Rodriguez, concerning level-set percolation of the Gaussian free field on Zd, with d at least 3, for which methods developed in the context of random interlacements have been helpful.