- This event has passed.

# Randomness and Graphs : Processes and Structures

## Sep 11 - Sep 15

Sponsored by:

In the most general formulation, a random geometric graph is what you get if you take a random set of points in some metric space and you join pairs of points depending on some rule (which may include additional randomness). A special case is the Gilbert model where we take n points uniformly at random in the square (or d-dimensional hypercube) and connect two points if the distance is less than r. The model is named after E.N. Gilbert who defined a very similar model in 1961.

Image and caption by Tobias Müller (http://www.staff.science.uu.nl/~muell001/).

#### Summary

The aim of this workshop is to bring together researchers to discuss the latest developments in various topics at the interface of probability, combinatorics, and algorithms including amongst others:

– Random graphs and matrices

– Threshold phenomena

– Discrete random processes and algorithms on graphs

#### Organizers

Luca Avena | Leiden University |

Jop Briët | CWI |

Remco van der Hofstad | TU Eindhoven |

Tim Hulshof | TU Eindhoven |

Júlia Komjáthy | TU Eindhoven |

Viresh Patel | University of Amsterdam |

Guus Regts | University of Amsterdam |

#### Speakers

Peter Allen | London School of Economics, Abstract |

Graham Brightwell | London School of Economics |

Elisabetta Candellero | University of Warwick, Abstract |

Mia Deijfen | Stockholm University, Abstract |

Charilaos Efthymiou | Goethe Universitat, Abstract |

Nikolaos Fountoulakis | University of Birmingham, Abstract |

David Gamarnik | MIT, Abstract |

Alexandre Gaudilliere | CNRS, Abstract |

Christina Goldschmidt | University of Oxford, Abstract |

Mark Jerrum | Queen Mary, University of London, Abstract |

Ross Kang | Radboud University Nijmegen, Abstract |

Malwina Luczak | Queen Mary, University of London, Abstract |

Jason Miller | University of Cambridge, Abstract |

Tobias Muller | Utrecht University, Abstract |

Guillem Perarnau | University of Birmingham, Abstract |

Will Perkins | University of Birmingham, Abstract |

Balázs Ráth | Budapest University of Technology and Economics, Abstract |

Sanchayan Sen | McGill University, Abstract |

Perla Sousi | University of Cambridge, Abstract |

Joel Spencer | Courant Institute (New York), Abstract |

Alexandre Stauffer | University of Bath, Abstract |

Daniel Valesin | University of Groningen, Abstract |

Lutz Warnke | Georgia Institute of Technology, Abstract |

#### Programme

(preliminary)

#### Abstracts

**Peter Allen**

**A simple proof of Shamir’s conjecture
**I will present a simplified proof of Shamir’s conjecture, using some ideas from Johannson, Kahn and Vu and some new ideas.

(joint work with Julia Boettcher, Ewan Davies, Matthew Jenssen, Yoshiharu Kohayakawa and Barnaby Roberts)

**Elisabetta Candellero**

**Percolation and isoperimetric inequalities
**In this talk we will discuss some relations between percolation on a given graph G and its geometry. There are several interesting questions relating various properties of G such as growth (or dimension) and the process of percolation on it. In particular we will look for conditions under which its critical percolation threshold is non-trivial, that is: p_c(G) is strictly between zero and one. In a very influential paper on this subject, Benjamini and Schramm asked whether it was true that for every graph satisfying dim(G) > 1, one has p_c(G) < 1. We will explain this question in detail and present some recent results that have been obtained in this direction. This talk is based on a joint work with Augusto Teixeira (IMPA, Rio de Janeiro, Brazil).

**Mia Deijfen**

**Cows on the move
**Consider an epidemic that spread in a population of moving particles on Z^d. The particles may infect each other upon direct contact, but may also be infected via contaminated locations. We formulate a simple model incorporating this phenomenon and demonstrate that the presence of site contamination may have an impact on the epidemic spread. Specifically, site contamination can cause a subcritical model to become supercritical, and measures aimed at controlling site contamination thereby has the potential to suppress large outbreaks. We also discuss a number of open problems for the model, and other versions of it.

**David Gamarnik**

**(Arguably) Hard on Average Constraint Satisfaction Problems
**Many randomly generated constraint satisfaction problems exhibit an apparent gap between the optimal value, which can be estimated by non-constructive means, and the best values achievable by fast (polynomial time) algorithms. Through a combined efforts of mathematicians, computer scientists and statistical physicists, it became apparent that a potential and in some cases a provable obstruction for designing algorithms bridging this gap is an intricate geometry of nearly optimal solutions, in particular the presence of a certain Overlap Gap Property (OGP). In this talk we demonstrate how for many such problems, the onset of the OGP phase transition indeed nearly coincides with algorithmically hard regimes. Our examples will include the problem of finding a largest independent set of a graph, finding a largest cut in a random hypergrah, random NAE-K-SAT problem, the problem of finding a largest submatrix of a random matrix, and high-dimensional sparse linear regression problem in statistics.

(joint work with Wei-Kuo Chen, Quan Li, Dmitry Panchenko, Mustazee Rahman, Madhu Sudan and Ilias Zadik)

**Alexandre Gaudilleire**

**Intertwining wavelets
**We use random spanning forests on arbitrary finite graphs to build approximate solutions of Markov process intertwining equations, with localized linking measures, that allow for defining a coarse grained version of the original network together with some “wavelet basis”. The associated multiresolution scheme leads to a numerically stable algorithm for compression and analysis of signals that are defined on the given graph.

(joint work with L. Avena, F. Castel and C. Mélot)

**Charis Efthymiou**

**Improved bounds for sampling colorings of sparse random graphs
**We study the mixing properties of the single-site Markov chain known as the Glauber dynamics for sampling k-colorings of a sparse random graph G(n,d/n) for constant d. The best known rapid mixing results for general graphs are in terms of the maximum degree \Delta of the input graph G and hold when k>11\Delta/6 for all G. Improved results hold when k>\alpha\Delta for graphs with girth =>5 and \Delta sufficiently large where \alpha\approx 1.7632… is the root of \alpha=\exp(1/\alpha); further improvements on the constant \alpha hold with stronger girth and maximum degree assumptions.

For sparse random graphs the maximum degree is a function of n and the goal is to obtain results in terms of the expected degree d. The following rapid mixing results for G(n,d/n) hold with high probability over the choice of the random graph for sufficiently large constant d. Mossel and Sly (2009) proved rapid mixing for constant k, and Efthymiou (2014) improved this to k linear in~d. The condition was improved to k>3d by Yin and Zhang (2016) using non-MCMC methods.

Here we prove rapid mixing when k>\alpha d where $\alpha\approx 1.7632… is the same constant as above. Moreover we obtain O(n^{3}) mixing time of the Glauber dynamics, while in previous rapid mixing results the exponent was an increasing function in d. As in previous results for random graphs our proof analyzes an appropriately defined block dynamics to “hide” high-degree vertices. One new aspect in our improved approach is utilizing so-called local uniformity properties for the analysis of block dynamics. To analyze the “burn-in” phase we prove a concentration inequality for the number of disagreements propagating in large blocks.

(joint work with Tom Hayes, Daniel Stefankovic and Eric Vigoda)

**Nikolaos Fountoulakis**

**Percolation on random graphs with given degrees revisited
**We consider the standard bond percolation process on a random graph with given degrees. We would like to sample a random graph uniformly at random from the set of all simple graphs with a given degree sequence. Thereafter, its edges are deleted randomly and independently with probability 1−p. The question we consider is whether there a critical value p_c for the probability p, such that when p crosses p_c a giant component emerges. We will give a rough characterisation of which degree sequences have such a critical value that is bounded away from 0, as the order of the random graph grows. To this end, we will avoid the use of the classic configuration model (and the restrictions it incurs), but make use of a recent approach developed by Joos, Perarnau, Rautenbach and Reed (Probability Theory and Related Fields, to appear – also in proceedings of FOCS ’16). In particular, this allows us to deal with degree sequences that have very heavy tails. (This is joint work with F. Joos and G. Perarnau.)

**Christina Goldschmidt**

**Voronoi cells in the Brownian continuum random tree
(and other unicellular continuum random maps)
**Take a uniform random tree with n vertices and select k of those vertices independently and uniformly at random; call them sites. (We assume that n is large and k is fixed, so that with high probability the sites are distinct.) Find the associated Voronoi cells: for each vertex in the tree, assign it to the cell of the site (or sites) which is closest in the graph distance. Now consider the vector of the proportions of the vertices lying in each of the k cells. We prove that this vector converges in distribution to the Dirichlet(1,1,…,1) distribution (that is, it is asymptotically uniform on the (k-1)-dimensional simplex). In fact, this is most easily formulated as a result about the scaling limit of the uniform random tree, namely the Brownian continuum random tree: if we pick k independent sites from the mass measure of the tree, their Voronoi cells have masses which are jointly Dirichlet(1,1,…,1) distributed. An analogue of this result also holds for (the scaling limit of) uniform unicellular random maps on surfaces of arbitrary genus.

(joint work (in progress) with Louigi Addario-Berry, Omer Angel, Guillaume Chapuy and Éric Fusy)

**Mark Jerrum**

**Random cluster dynamics for the Ising model is rapidly mixing
**We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at

*q=2*is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.

**Ross Kang**

**Guarantees of sparse or dense subgraphs
**Ramsey showed that any large enough graph contains a set of k vertices that forms a clique or a stable set. Quantitative estimates of “large enough” have underpinned the entire field of probabilistic/extremal graph theory. We consider a natural generalisation where we are happy with subsets that are dense (clique-like) or sparse (stable set-like) enough. More precisely, how large must a graph be for it to always contain a set of k vertices that induces a subgraph either of minimum degree at least c(k-1) or of maximum degree at most (1-c)(k-1)? Something remarkable happens at c=1/2 and we investigate this phenomenon thoroughly, partially answering a question of Erdos and Pach.

(joint works with Eoin Long, Janos Pach, Viresh Patel and Guus Regts)

**Malwina Luczak**

**Extinction time for the weaker of two competing stochastic SIS logistic epidemics
**We consider a simple stochastic model for the spread of a disease caused by two virus strains in a closed homogeneously mixing population of size N. In our model, the spread of each strain is described by the stochastic logistic SIS epidemic process in the absence of the other strain, and we assume that there is perfect cross-immunity between the two virus strains, that is, individuals infected by one strain are temporarily immune to re-infections and infections by the other strain. For the case where one strain has a strictly larger basic reproductive ratio than the other, and the stronger strain on its own is supercritical (that is, its basic reproductive ratio is larger than 1), we derive precise asymptotic results for the distribution of the time when the weaker strain disappears from the population, that is, its extinction time. We further consider what happens when the difference between the two reproductive ratios may tend to 0.

(joint work with Fabio Lopes)

**Jason Miller**

**Convergence of percolation on uniform quadrangulations
**Let Q be a uniformly random quadrangulation with simple boundary decorated by a critical (p=3/4) face percolation configuration. We prove that the chordal percolation exploration path on Q between two marked boundary edges converges in the scaling limit to SLE(6) on the Brownian disk (equivalently, a Liouville quantum gravity surface). The topology of convergence is the Gromov-Hausdorff-Prokhorov-uniform topology, the natural analog of the Gromov-Hausdorff topology for curve-decorated metric measure spaces. Our method of proof is robust and, up to certain technical steps, extends to any percolation model on a random planar map which can be explored via peeling. (joint work with E. Gwynne)

**Tobias Muller**

**Logic and random graphs
**We say that a graph property is expressible in the “first order language of graphs” if it can be written as a logic sentence using the universal and existential quantifiers with variables ranging over the nodes of the graph, the usual connectives AND, OR, NOT, parentheses and the relations = and ~, where x ~ y means that x and y share an edge. For example, the property that G contains a triangle can be written as exists x,y,z : (x ~ y) AND (x ~ z) AND (y ~ z). A classical result of Glebskii et al. 1969 and indepently Fagin 1976 states that if one samples a graph on n vertices uniformly at random from all such graphs then every first order expressible graph property holds with probability tending to either zero or one (as n tends to infinity). Since then, first order expressible properties have been studied extensively on the most commonly studied model of random graphs, the Erdos-Renyi model. A number of very attractive and surprising results have been obtained, and by now

we have a fairly full description of the behaviour of first order expressible properties on this model. After describing some of these results, time permitting, I will discuss some recent and ongoing work where we try to see what happens both in other models of random graphs (such as random planar graphs, random perfect graphs, random geometric graphs, …) and when one considers other (i.e. “higher order”) logics.

(joint works with S. Haber, P. Heinig, T. Luczak, M. Noy, A. Taraz)

**Guillem Perarnau**

**Manifolds are rare
**Consider a random triangulation obtained by randomly gluing all the facets of n tetrahedra by pairs. Gromov asked for the probability that the resulting triangulated topological space is homeomorphic to a 3-sphere. This question is motivated by the connections between general triangulations and quantum gravity theory. We show that the probability that a random coloured triangulation is homeomorphic to a 3-manifold is n−5n/6, up to an exponential factor. Our result improves the previous bounds on the number of triangulated 3-spheres. It also generalises to manifolds of any dimension d ≥ 3, unveiling some topological properties of the configuration model.

(joint work with Guillaume Chapuy)

**Will Perkins**

**Phase transitions and the cavity method**

Originally developed by statistical physicists to understand the behavior of glassy materials, the powerful but non-rigorous cavity method has subsequently been used to describe in great detail phase transitions in random graphs and random computational problems. Using random graph coloring and the stochastic block model as running examples, I will describe how the cavity method pinpoints the condensation and information theoretic thresholds respectively, and present some of the mathematical tools we can use to make the method rigorous in these cases.

(joint work with Amin Coja-Oghlan, Florent Krzakala, and Lenka Zdeborova)

**Balázs Ráth**

**A moment-generating formula for Erdős-Rényi component sizes**

The central result of the talk is a new simple formula characterizing the distribution of the size of the connected component of a fixed vertex in the Erdős-Rényi random graph which allows one to give elementary proofs of some results of

(a) Federico, van der Hofstad, den Hollander and Hulshof as well as Janson and Luczak about the susceptibility in the subcritical graph and

(b) the central limit theorem of Barraez, Boucheron and De La Vega for the size of the giant component in the supercritical graph.

**Sanchayan Sen**

**Geometry of probabilistic structures constructed on random regular graphs
**The intrinsic geometry of several probabilistic structures constructed on different underlying discrete systems are believed to be universal. But mathematical results making this rigorous have been proven only very recently. We discuss two such recent results.

(a) The minimal spanning tree (MST) constructed by assigning exchangeable weights to the edges of a random -regular graph: We prove scaling of distance which supports a prediction for the strong disorder regime. We further show that its scaling limit exists and has the same law as the scaling limit of the MST of the complete graph up to a scaling factor of , and in particular, is compact and has Minkowski dimension almost surely. Joint work with Louigi Addario-Berry.

(b) The vacant set left by a random walk run on a random -regular graph when : We show that around the point of phase transition, the components of the vacant set asymptotically behave like components of the complete graph under critical percolation, i.e., the critical Erdos-Renyi random graph. This answers a question posed by Cerny and Teixeira.

Our approach forms the main technical bedrock for the broader program of developing general universality theorems for such structures. We also discuss related open problems.

(joint work with Shankar Bhamidi)

**Perla Sousi**

**Random walks on dynamical percolation
**We study the behaviour of random walk on dynamical percolation. In this model, the edges of a graph are either open or closed and refresh their status at rate μ, while at the same time a random walker moves on G at rate 1, but only along edges which are open. On the d-dimensional torus with side length n, when the bond parameter is subcritical, the mixing times for both the full system and random walker were determined by Peres, Stauffer and Steif. I will talk about the supercritical case, which was left open, but can be analysed using evolving sets.

(joint work with Y. Peres and J. Steif)

**Joel Spencer**

**Erdos-Renyi Revisited
**The “double jump” at

*np=1*shown by Paul Erdos and Alfred Renyi nearly sixty years ago remains a bedrock of our studies of threshold phenomenon. The perspectives on their discovery, however, have changed over the decades.

In this semi-expository talk the speaker will discuss the various approaches to understanding of this “mother of all phase transitions.”

**Alexandre Stauffer**

**Multi-particle diffusion limited aggregation
**We consider a stochastic aggregation model on Z^d. Start with an infinite collection of particles located at the vertices of the lattice, with at most one particle per vertex, and initially distributed according to the product Bernoulli measure with parameter $\mu\in(0,1)$. In addition, there is an aggregate, which initially consists of only one particle placed at the origin. Non-aggregated particles move as continuous time simple symmetric random walks obeying the exclusion rule, whereas aggregated particles do not move. The aggregate grows indefinitely by attaching particles to its surface whenever a particle attempts to jump onto it. Our main result states that if on Z^d, d at least 2, the initial density of particles \mu is large enough, then with positive probability the aggregate grows with positive speed.

(joint work with Vladas Sidoravicius)

**Daniel Valesin**

**Percolation on the stationary distribution of the voter model on Z^d
**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 the model is considered in dimension 3 or higher, its set of (extremal) stationary distributions is equal to a family of measures $\mu_\alpha$, for $\alpha$ between 0 and 1. A configuration sampled from $\mu_alpha$ is a field of 0’s and 1’s on $\Z^d$ in which the density of 1’s is $\alpha$. We consider such a configuration from the point of view of site percolation on $\Z^d$. We prove that in dimensions 5 and higher, the probability of existence of an infinite percolation cluster exhibits a phase transition in $\alpha$. If the voter model is allowed to have long range, we prove the same result for dimensions 3 and higher; we also prove that, if the range is taken to infinity, then the critical percolation parameter converges to that of Bernoulli site percolation.

(joint work with Balázs Ráth)

**Lutz Warnke**

**The phase transition in the random d-process
**One of the most interesting features of Erdös-Rényi random graphs is the `percolation phase transition’, where the global structure intuitively changes from only small components to a single giant component plus small ones.

In this talk we discuss the percolation phase transition in the random d-process, which corresponds to a natural algorithmic model for generating random regular graphs that differs from the usual configuration model (starting with an empty graph on n vertices, the random d-process evolves by sequentially adding new random edges so that the maximum degree remains at most d).

Our results on the phase transition solve a problem of Wormald from 1997, and verify a conjecture of Balinska and Quintas from 1990.

(joint work with Nick Wormald)

#### Registration

Registration for the workshop is free, but compulsory: **REGISTRATION FORM**

#### Practical Information

● Venue

Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

De Groene Loper 5, 5612 AE EINDHOVEN, The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the MetaForum building, 4th floor (more about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).

Accessibility TU/e campus and map.

● Accommodation

For speakers, we will take care of accommodation. Other attendees must make their own arrangements.

Our preferred hotel is The Student Hotel Eindhoven. They offer 10% discount if you book with promocode, please follow the link TSHE .

For hotels around the university, please see: Hotels (please note: prices listed are “best available”).

More hotel options can be found on Tourist Information Eindhoven.

● Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult Public Transport.

The University can be reached easily by car from the highways leading to Eindhoven. For details: Route and map TU/e campus.

● Conference facilities

Conference room, MetaForum Building “MF11 & 12”.

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants giving an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

● Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

● Cancellation

Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.

● Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl