# 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

Graham Brightwell | London School of Economics |

Elisabeta Candellero | University of Warwick |

Mia Deijfen | Stockholm University, Abstract |

Charilaos Efthymiou | Goethe Universitat |

Nikolaos Fountoulakis | University of Birmingham, Abstract |

David Gamarnik | MIT |

Alexandre Gaudilliere | CNRS, Abstract |

Christina Goldschmidt | University of Oxford |

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

Ross Kang | Radboud University Nijmegen |

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

Jason Miller | University of Cambridge |

Tobias Muller | Utrecht University |

Guillem Perarnau | University of Birmingham |

Will Perkins | University of Birmingham, Abstract |

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

Sanchayan Sen | McGill University, Abstract |

Perla Sousi | University of Cambridge |

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

Alexandre Stauffer | University of Bath |

Daniel Valesin | University of Groningen, Abstract |

Lutz Warnke | Georgia Tech |

#### Programme

To be announced soon

#### Abstracts

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

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

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

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

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

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

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

**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.”

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

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

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