A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.[-]

In the first half of the talk, I will survey results and open problems on transience of self-interacting martingales. In particular, I will describe joint works with S. Popov, P. Sousi, R. Eldan and F. Nazarov on the tradeoff between the ambient dimension and the number of different step distributions needed to obtain a recurrent process. In the second, unrelated, half of the talk, I will present joint work with Tom Hutchcroft, showing that the component structure of the uniform spanning forest in $\mathbb{Z}^d$ changes every dimension for $d > 8$. This sharpens an earlier result of Benjamini, Kesten, Schramm and the speaker (Annals Math 2004), where we established a phase transition every four dimensions. The proofs are based on a the connection to loop-erased random walks.[-]

In this talk I will review the recent developments on weighted distances in scale free random graphs as well as highlight key techniques used in the proofs. We consider graph models where the degree distribution follows a power-law such that the empirical variance of the degrees is infinite, such as the configuration model, geometric inhomogeneous random graphs, or scale free percolation. Once the graph is created according to the model definition, we assign i.i.d. positive edge weights to existing edges, and we are interested in the proper scaling and asymptotic distribution of weighted distances.
In the infinite variance degree regime, a dichotomy can be observed in all these graph models: the edge weight distributions form two classes, explosive vs conservative weight distributions. When a distribution falls into the explosive class, typical distances converge in distribution to proper random variables. While, when a distribution falls into the conservative class, distances tend to infinity with the model size, according to a formula that captures the doubly-logarithmic graph distances as well as the precise behaviour of the distribution of edge-weights around the origin. An integrability condition decides into which class a given distribution falls.
This is joint work with Adriaans, Baroni, van der Hofstad, and Lodewijks.[-]

Graphons and graphexes are limits of graphs which allow us to model and estimate properties of large-scale networks. In this pair of talks, we review the theory of dense graph limits, and give two alterative theories for limits of sparse graphs – one leading to unbounded graphons over probability spaces, and the other leading to bounded graphons (and graphexes) over sigma-finite measure spaces. Talk I, given by Jennifer, will review the general theory, highlight the unbounded graphons, and show how they can be used to consistently estimate properties of large sparse networks. This talk will also give an application of these sparse graphons to collaborative filtering on sparse bipartite networks. Talk II, given by Christian, will recast limits of dense graphs in terms of exchangeability and the Aldous Hoover Theorem, and generalize this to obtain sparse graphons and graphexes as limits of subgraph samples from sparse graph sequences. This will provide a dual view of sparse graph limits as processes and random measures, an approach which allows a generalization of many of the well-known results and techniques for dense graph sequences.[-]

In an epidemic model, the basic reproduction number $ R_{0}$ is a function of the parameters (such as infection rate) measuring disease infectivity. In a large population, if $ R_{0}> 1$, then the disease can spread and infect much of the population (supercritical epidemic); if $ R_{0}< 1$, then the disease will die out quickly (subcritical epidemic), with only few individuals infected.
For many epidemics, the dynamics are such that $ R_{0}$ can cross the threshold from supercritical to subcritical (for instance, due to control measures such as vaccination) or from subcritical to supercritical (for instance, due to a virus mutation making it easier for it to infect hosts). Therefore, near-criticality can be thought of as a paradigm for disease emergence and eradication, and understanding near-critical phenomena is a key epidemiological challenge.
In this talk, we explore near-criticality in the context of some simple models of SIS (susceptible-infective-susceptible) epidemics in large homogeneous populations.[-]

Going back at least to the works of Witten and Kontsevich, it is known that (symplectic or Weil-Petersson) volumes of moduli spaces of Riemann surfaces share many features with the enumeration of maps. It is therefore natural to expect that the theory of random hyperbolic metrics sampled according to the Weil-Petersson measure on, say, punctured spheres is closely related to the theory of random planar maps. I will highlight some similarities and show that tree bijections, which are ubiquitous in the study of random planar maps, have analogues for hyperbolic surfaces. As an application, jointly with Nicolas Curien, we show that these random hyperbolic surfaces with properly rescaled metric admit a scaling limit towards the Brownian sphere when the number of punctures increases.[-]

Several operations of combinatorial surgery can be used to relate maps of a given genus g to maps of genus g' is smaller than g. One of them is the Tutte/Lehman-Walsh decomposition, but more advanced constructions exist in the combinatorial toolbox, based on the Marcus-Schaeffer/ Miermont or the trisection bijections.
At the asymptotic level, these constructions lead to surprising relations between the enumeration of maps of genus g, and the genus 0 Brownian map. I will talk about some fascinating identities and (open) problems resulting from these connections, related to Voronoi diagrams, 'W-functionals', and properties of the ISE measure. Although the motivation comes from 'higher genus', these questions deal with the usual Brownian map as everyone likes it.
This is not very new material, and a (mostly French) part of the audience may have heard these stories one million times. But still I hope it will be interesting to advertise them here. In particular, I do not know if recent 'Liouville-based' approaches have anything to say about all this.[-]