- This event has passed.

# YEP XIV on Networks: "Probability, Combinatorics and Algorithms"

## Sep 4, 2017 - Sep 8, 2017

Sponsored by:

- Summary
- Organizers
- Mini Course Speakers
- Invited Speakers
- Programme
- Abstracts
- Registration
- Practical Information

#### Summary

The YEP workshop series is an annually recurring workshop aimed at Young (European) Probabilists, i.e., researchers at the PhD and Postdoc level in probability and related areas. This year, the topic of YEP XIV are Networks. Since networks are naturally at the interface between various different mathematical disciplines, this YEP will focus not only on purely probabilistic aspects, but also take a more combinatorial and algorithmic perspective. The workshop consists of two parts: the first part is three mini-courses about important recent developments. The second part consist of talks by young researchers.

#### Organizers

Luca Avena | Leiden University |

Jop Briët | CWI |

Tim Hulshof | TU Eindhoven |

Julia Komjathy | TU Eindhoven |

Viresh Patel | University of Amsterdam |

Guus Regts | University of Amsterdam |

#### Mini Course Speakers

Amin Coja-Oghlan | Goethe Universität, Abstract |

Pietro Caputo | Università Roma Tre, Abstract |

Manuel Cabezas | Pontifical Catholic University of Chile, Abstract |

Alexander Fribergh | Université de Montréal, Abstract |

#### Invited Speakers

Agnes Backhausz | Eötvös Loránd University , Abstract |

Jacobien Carstens | UvA , Abstract |

Lorenzo Federico | TU Eindhoven, Abstract |

Hakan Guldas | Leiden University, Abstract |

Bruno Kimura | TU Delft, Abstract |

Léo Miolane | INRIA ENS, Abstract |

Matteo Quattropani | Roma Tre, Abstract |

Shravas Rao | New York University, Abstract |

Andrea Roccaverde | Leiden University, Abstract |

Wioletta Ruszel | TU Delft, Abstract |

Nick Simm | University of Warwick, Abstract |

Nicos Starreveld | University of Amsterdam, Abstract |

Réka Szabó | University of Groningen, Abstract |

Sam Thomas | University of Cambridge, Abstract |

Daniel Valesin | University of Groningen, Abstract |

#### Programme

#### Abstracts

**MINI COURSES**

**Manuel Cabezas and Alexander Fribergh**

**The ant in the labyrinth
**The ant in the labyrinth is a term coined in 1976 by Pierre-Gilles de Gennes to refer to the simple random walk on a critical percolation cluster of the d-dimensional integer lattice.

He proposed to study this model since it is the canonical example of diffusion in critical environments.

The goal of this mini-course is to present the history of this model and to communicate some of the recent progress towards understanding this model in the high-dimensional case. In particular, we will present a very detailed result obtained for the simple random walk on critical branching random walks on the d-dimensional integer lattice. This simplified model is strongly believed to share a common scaling limit with the critical percolation case, a behaviour that is expected to be universal in high dimension.

Presenting this topic will lead us to discuss a wide variety of subjects: random walks in random environments, critical trees, critical graphs, the super-brownian motion …

**Amin Coja-Oghlan**

**Random constraint satisfaction problems
**Random constraint satisfaction problems are of fundamental interest in probability and combinatorics and also play an important role in computer science, information theory and related areas. These lecture give an overview of the subject and highlight the connections to statistical physics that have emerged since the early 2000s. A key element of the analysis of (random) constraint satisfaction problems is the understanding of certain probability distributions that they induce, called Boltzmann distributions. We will see a mathematical framework for their study and learn how this theory mirrors the concepts of replica symmetry breaking, reconstruction and pure state decompositions that play a key role in statistical physics. Further, we will study the Belief Propagation message passing scheme, which is the fundamental tool of the modern study of random constraint satisfaction problems. Belief Propagation also plays a role as an efficient algorithm in several applications, particularly in modern coding theory. Additionally, we will learn how Belief Propagation can be used to pinpoint phase transitions and to investigate the nature of correlations under the Boltzmann distribution.

**Pietro Caputo**

**Local convergence of graphs and applications**

The mini-course is an introduction to local convergence of sparse graph sequences. Initiated by Benjamini and Schramm around 15 years ago, the theory recently advanced in several directions with many remarkable applications. We will discuss some key examples, with special emphasis on the case of sparse random graphs. The main applications we shall present are the asymptotic enumeration of spanning trees and the limiting spectral distribution in sparse random graph sequences. In both cases the theory of local convergence allows one to compute the quantities of interest directly in terms of the underlying limiting object.

**INVITED SPEAKERS**

**Agnes Backhausz**

**On the graph limit approach to eigenvectors of random regular graphs
**We are interested in the spectral properties of a randomly chosen d-regular graph on n vertices. In particular, we consider an arbitrary eigenvector of the adjacency matrix, and examine its empirical distribution, when the number of vertices tends to infinity. Starting from the theory of sparse graph limits, we could prove that the empirical distibution of any eigenvector is close to an appropriate Gaussian distribution (maybe with 0 variance) with high probability. This result will be presented in the talk, together with the main tools of the proof.

(joint work with Balazs Szegedy)

**Jacobien Carstens**

**The Curveball algorithm: A fast and flexible approach to sampling networks with fixed degree sequence
**Randomisation of binary matrices has become an important quantitative tool in modern computational biology. The equivalent problem of generating random directed networks with fixed degree sequences is used in several network analysis techniques such as community detection and motif finding. It is however challenging to generate truly unbiased random graphs with fixed degree sequence.

In this talk we focus on Markov chain approaches to network randomisation. We discuss the well-known switching model and the more recently introduced Curveball algorithm. We show that both frameworks can be used to randomise a variety of network classes and prove that both algorithms converge to the uniform distribution.

However, the main question for both theoreticians and practitioners remains unanswered: that is, in all but some special cases it is unknown how many steps the Markov chains needs to take, in order to sample from a distribution that is close to uniform. Experimental results suggest that the Curveball algorithm converges faster. We will discuss current work towards proving that the Curveball algorithm outperforms the switching model.

**Lorenzo Federico**

**Critical Percolation on the Hamming graph
**Percolation on finite graphs is known to exhibit a phase transition similar to the Erdős–Rényi Random Graph in presence of sufficiently weak geometry. This talk focuses on the Hamming graph H(d,n), the cartesian product of d complete graphs on n vertices each. We identify the critical point at which such phase transition happens and we analyse the structure of the largest connected components at criticality. We prove that the scaling limit of component sizes is identical to the one for critical Erdős–Rényi components, while the number of surplus edges is much higher. These results are obtained coupling percolation to the trace of branching random walks on the Hamming graph.

(joint work with Remco van der Hofstad, Frank den Hollander and Tim Hulshof)

**Bruno Kimura**

**Phase transition in the one-dimensional long range Ising model under the presence of decaying external fields****
**The long range Ising models differs from the classical ones by the fact that the spin-spin interaction decays spatially. Since long range models often behaves like short range models in higher dimension, we studied the phase diagram of one-dimensional Ising models in d=1 and proved that even in the presence of certain external fields there is phase transition at low temperatures. The techniques used to prove such result were based contour arguments developped by Froehlich, Spencer, Cassandro, Presutti et al.

**Léo Miolane**

**Community detection in the asymmetric stochastic block model
**The stochastic block model is a popular model of random graphs that exhibit a community structure. The graph is generated according to an underlying partition of the vertices in two communities. Then, given a realisation of this model, we would like to recover the underlying partition.

In this talk, we will focus on the information theoretic limits for this problem: is it possible to estimate the communities better than chance?

We will study two different approaches to deal with it.

The first one exploits the local convergence of the graph toward a Galton Watson branching process to study the performance of optimal tests. The second one connects the community detection problem to an equivalent matrix factorization problem which turns out to be easier to study.

**Matteo Quattropani**

**Approximating networks spectra via random spanning forests
**The work of Avena and Gaudillière on spanning forests highlighted the already know link between the spectrum of the Laplacian and the combinatorics of spanning objects. The aim of the talk is to present a recent on going project (with Avena, Gaudillière and Milanesi) focused on making useful the above mentioned link in more applied contexts. In particular, how can we obtain a (rough? fast?) approximation of the spectrum of the Laplacian of a graph by looking at the graph forest structure?

**Shravas Rao**

**Tail Bounds for the Expander Random Sampler****
**Consider an expander graph in which a mu fraction of the vertices are marked. A random walk starts at a uniform vertex and at each step continues to a random neighbor. Gillman showed in 1993 that the number of marked vertices seen in a random walk of length n is concentrated around its expectation, Phi := mu n, independent of the size of the graph. We describe further refinements on Gillman's original bound.

(joint work with Assaf Naor and Oded Regev)

**Andrea Roccaverde**

**Breaking of ensemble equivalence in complex networks**

In this talk I will speak about the phenomenon of breaking of ensembleequivalence in complex networks. For many system in statistical physics the microcanonical and canonical ensemble are equivalent in the thermodynamic limit, but not for all. The goal is to classify for which classes of complex networks with topological constraints, breaking of ensemble equivalence occurs.

We consider the simple case in which we fix the number of links and then we move to the configuration model (we fix the degree of each vertex). Then we study a more general setting with an arbitrary number of intra-connected and inter-connected layers, thus allowing modular graphs with a multi-partite, multiplex, time-varying, block-model or community structure. We give a full classication of ensemble equivalence in the sparse regime, proving that break-down occurs as soon as the number of constrained degrees is extensive in the number of nodes, irrespective of the layer structure. In addition, we derive an explicit formula for the specic relative entropy and provide an interpretation of this formula in terms of Poissonisation of the degrees.

**Wioletta Ruszel**

**Phase transition in the one-dimensional long range Ising model under the presence of decaying external fields**** II
**This talk is a continuation of the talk of Bruno Kimura where we state our results concerning phase transitions of 1d Dyson models in decaying fields. We will present general assumptions on the interaction and external field and give an idea of the proof.

(joint work with: Rodrigo Bissacot (Sao Paolo), Eric Endo (Sao Paolo), Aernout van Enter (Groningen) and Bruno Kimura (Delft))

**Nicos Starreveld**

**Breaking of Ensemble Equivalence in dense random graphs
**In this talk I will consider a random graph on which topological restrictions are imposed, such as

constraints on the total number of edges, wedges, and triangles. I will consider dense graphs, in

which the number of edges per vertex scales proportionally to the number of vertices n. My goal is

to compare the micro-canonical ensemble (in which the constraints are satisfied for every

realisation of the graph) with the canonical ensemble (in which the constraints are satisfied on

average), both subject to maximal entropy. We compute the relative entropy of the two ensembles in

the limit as n grows large, where two ensembles are said to be equivalent in the dense regime if

this relative entropy divided by

*n*

^{2}tends to zero. Our main result, whose proof relies on large deviation theory for graphons, is that breaking of ensemble equivalence occurs when the constraints satisfy a certain terseness condition. Examples are provided for three different choices

of constraints.

**Nick Simm**

**Gaussian free field and random matrices
**The Gaussian free field (GFF) is a natural generalization of Brownian motion in two dimensions; it is a fundamental object in many areas of theoretical physics and probability theory. The focus of this talk is going to be on the exponential of the GFF. This is a tricky notion because the GFF cannot be defined as a classical function; it is only a distribution, and exponentiating it is liable to raise eyebrows. Luckily a theory known as Gaussian multiplicative chaos (GMC) was invented to take care of this problem. I will discuss a little bit the main objectives of GMC. Then I will present recent results showing that certain global statistics of random matrix eigenvalues (essentially the characteristic polynomial of a big random matrix) converge in law to such GMC constructions as the size of the matrix goes to infinity. This is joint work with Gaultier Lambert (Zurich) and Dmitry Ostrovsky.

**Réka Szabó**

**From survival to extinction of the contact process by the removal of a single edge
**The contact process is one of the most well-studied stochastic models of the spread of epidemics on a graph, and can also be seen as a continuous-time version of oriented percolation. Its behavior can be affected by local modifications in the underlying graph. In this talk I will give a construction of a tree in which the contact process with any positive infection rate survives but, if a certain privileged edge is removed, one obtains two subtrees in which the contact process with infection rate smaller than 1/4 dies out.

**Sam Thomas**

**Mixing Time for Random Walk on Dynamical Erdos-Renyi
**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. In this talk I will present recent results on the mixing time in the case when G is the complete graph and the bond percolation parameter is of order 1/n, i.e. we consider random walk on dynamical Erdos-Renyi graph.

(joint work with P. Sousi)

**Daniel Valesin**

**Monotonicity for multi-range percolation on oriented trees**

Percolation theory contains a variety of monotonicity-related conjectures which are easy and natural to state but challenging to prove. In this talk, we will survey a few of these problems. We will then specialize to the setting of Bernoulli percolation on multi-range oriented trees. The trees we consider are oriented regular trees where besides the usual short bonds, all bonds of a certain length are added. Independently, short bonds are open with probability p and long bonds are open with probability q. We study properties of the critical curve which delimits the set of pairs (p,q) for which there is percolation. We also show that this curve decreases with respect to the length of the long bonds.

(joint work with Bernardo N. B. de Lima and Leonardo T. Rolla)

#### Registration

Registration is for the workshop is free, but complusory: **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).

● Accommodation

For lecturers and invited 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