# Simons Conference on Random Graph Processes

Click the titles to show/hide the abstracts. Click here to expand all.

# Main Talks

### A Framework for Imperfectly Observed Networks

David Aldous (Berkeley, USA)

Model a network as an edge-weighted graph, where the (unknown) weight $w_e$ of edge $e$ indicates the frequency of observed interactions, that is over time $t$ we observe a Poisson($t w_e$) number of interactions across edges $e$. How should we estimate some given statistic of the underlying network? This leads to wide-ranging and challenging problems.

### First-Passage Statistics of Extreme Values

Eli Ben-Naim (Los Alamos, USA)

Theoretical concepts from nonequilibrium statistical physics such as scaling and correlations are used to analyze first-passage processes involving extreme values. The focus of this talk is statistics of the running maxima, defined as the largest variable in a sequence of random variables. In particular, the running maxima of multiple independent sequences of stochastic variables are compared. The probability that these maxima remain perfectly ordered decays algebraically with the number of random variables, and the decay exponent characterizing this decay is nontrivial. Exact solutions for the scaling exponents will be discussed for uncorrelated variables as well as Brownian trajectories which are correlated. Relevance of such statistical measures for analysis of empirical data will be discussed as well.

### Scale-Free Percolation

Remco van der Hofstad (Eindhoven, The Netherlands)

We propose and study a random graph model on the hypercubic lattice that interpolates between models of scale-free random graphs and long-range percolation. In our model, each vertex $x$ has a weight $W_x$, where the weights of different vertices are i.i.d. random variables. Given the weights, the edge between $x$ and $y$ is, independently of all other edges, occupied with probability $1-e^{-\lambda W_xW_y/|x-y|^{\alpha}}$, where

• $\lambda$ is the percolation parameter,
• $|x-y|$ is the Euclidean distance between $x$ and $y$, and
• $\alpha$ is a long-range parameter.

The most interesting behavior can be observed when the random weights have a power-law distribution, i.e., when $\mathbb P(W_x>w)$ is regularly varying with exponent $1-\tau$ for some $\tau>1$. In this case, we see that the degrees are infinite a.s. when $\gamma =\alpha(\tau-1)/d < 1$, while the degrees have a power-law distribution with exponent $\gamma$ when $\gamma>1$.

Our main results describe phase transitions in the positivity of the critical value and in the graph distances in the percolation cluster as $\gamma$ varies. Let $\lambda_c$ denote the critical value of the model. Then, we show that $\lambda_c=0$ when $\gamma < 2$, while $\lambda_c > 0$ when $\gamma > 2$. Further, conditionally on $0$ and $x$ being connected, the graph distance between $0$ and $x$ is of order $\log\log|x|$ when $\gamma < 2$ and at least of order $\log|x|$ when $\gamma > 2$. These results are similar to the ones in inhomogeneous random graphs, where a wealth of further results is known.

We also discuss many open problems, inspired both by recent work on long-range percolation (i.e., $W_x=1$ for every $x$), and on inhomogeneous random graphs (i.e., the model on the complete graph of size n and where $|x-y|=n$ for every $x\neq y$).

This is joint work with Mia Deijfen and Gerard Hooghiemstra.

### Local Graph Coloring

Alexander Holroyd (Microsoft/Seattle, USA)

How can we color the vertices of a graph by a local rule based on i.i.d. vertex labels? More precisely, suppose that the color of vertex $v$ is determined by examining the labels within a finite (but perhaps random and unbounded) distance $R$ of $v$, with the same rule applied at each vertex. (The coloring is then said to be a finitary factor of the i.i.d. labels). Focusing on $Z^d$, we investigate what can be said about the random variable $R$ if the coloring is required to be proper, i.e. if adjacent vertices must have different colors. Depending on the dimension and the number of colors, the optimal tail decay is either a power law, or a tower of exponentials. I will briefly discuss generalizations to shifts of finite type and finitely dependent processes.

Based on joint work with Oded Schramm and David B Wilson.

slides, video

### Linear Spaces of Tilings

Richard Kenyon (Brown Univ., USA)

It is a well-known theorem that given a rectangle tiling of a rectangle there is a combinatorially equivalent tiling in which the rectangles have prescribed areas. We discuss generalizations of this results to tilings with other shapes, including random tilings and their scaling limits.

### Shotgun Assembly of Graphs

Elchanan Mossel (UPenn & Berkeley, USA)

We will present some results and some open problems related to shotgun assembly of graphs for random generating models. Shotgun assembly of graphs is the problem of recovering a random graph or a randomly labelled graphs from small pieces. The question of shotgun assembly presents novel problems in random graphs, percolation, and random constraint satisfaction problems.

Based on joint works with Nathan Ross, with Nike Sun and with Charles Bordenave and Uri Feige.

slides

### Bounds on the Condensation Threshold in Stochastic Block Models

Joe Neeman (UT Austin, USA & Hausdorff Inst., Germany)

Consider a random graph model consisting of $k$ communities of equal size. Edges are added to the graph independently at random, but are somewhat more likely to connect two vertices that belong to the same community. We choose parameters so that the average degree of the graph is fixed as the number of vertices tends to infinity. This random graph model is believed to have two phase transitions as the strength of community attachment increases. At the first transition, it becomes information-theoretically possible to detect the hidden communities from the graph structure; at the second, one can find them in polynomial time. We give upper and lower bounds on this first phase transition, which is known as the "condensation threshold" in statistical physics. Our bounds are asymptotically sharp in some limits, but not in others.

This is joint work with Jess B, Cristopher Moore, and Praneeth Netrapalli.

### Erdös-Rényi Percolation

Joel Spencer (NYU, USA)

The Random Graph $G(n,p)$ undergoes a macroscopic change at $p = \frac 1 n$. Why does this occur, how does this occur, how can $p$ be parametrized to "see" this change. What are the analogies to the Galton-Watson birth process, to bond percolation in $d$-space. We give a comprehensive discription, with (mostly!) proofs, of this vital phenomenon.

### Superstar Model and Networks from Surgery on Branching Processes

Michael Steele (UPenn, USA)

If you look at the graph one obtains from twitter retweets, the largest component is almost a tree. Moreover, in many empirical cases, this tree looks like there is one vertex that has a degree that evolves linearly over time, while other vertices show "power law" behavior of a common type. This talk mainly considers a one-parameter model that exhibits such behavior. The construction of the model goes via surgery on multi-type branching processes.

Part of this work is joint with Bhamidi and Zaman and part addresses recent work of Jog and Loh.

### On the Graph Limit Approach To Random Regular Graphs

Balazs Szegedy (Budapest, Hungary)

Let $G=G(n,d)$ denote the random $d$-regular graph on $n$ vertices. A celebrated result by J. Friedman solves Alon's second eigenvalue conjecture saying that if $d$ is fixed and $n$ is large then $G$ is close to be Ramanujan. Despite of significant effort, much less was known about the structure of the eigenvectors of $G$. We use a combination of graph limit theory and information theory to prove that every eigenvector of $G$ (when normalized to have length equal to square root of $n$) has an entry distribution that is close to some Gaussian distribution in the weak topology. Our results also work in the more general setting of almost-eigenvectors.

Joint work with A. Backhausz.

### The Phase Transition in Bounded-Size Achlioptas Processes

Lutz Warnke (Cambridge, UK)

Perhaps the best understood phase transition is that in the component structure of the uniform random graph process introduced by Erdös and Rényi around 1960. Since the model is so fundamental, it is very interesting to know which features of this phase transition are specific to the model, and which are universal', at least within some larger class of processes. Achlioptas process, a class of variants of the Erdös-Rényi process that are easy to define but difficult to analyze, have been extensively studied from this point of view. Here, settling a number of conjectures and open problems, we show that all bounded-size' Achlioptas processes share the key features of the Erdös-Rényi phase transition (in particular the asymptotic behaviour of the size of the largest component above and below the critical window). We do not expect this to hold for Achlioptas processes in general.

This is joint work with Oliver Riordan.

### Analysis of Random Processes on Regular Graphs With Large Girth

Nick Wormald (Monash Univ., Australia)

We introduce a general class of algorithms and analyse their application to regular graphs of large girth. The algorithms involve random processes which repeat a step whose description changes over time. In particular, we can transfer several results proved for random regular graphs into (deterministic) results about all regular graphs with sufficiently large girth. This reverses the usual direction, which is from the deterministic setting to the random one. In particular, this approach enables, for the first time, the achievement of results equivalent to those obtained on random regular graphs by a powerful class of algorithms which contain prioritised actions. As a result, we obtain new upper or lower bounds on the size of maximum independent sets, minimum dominating sets, maximum $k$-independent sets, minimum $k$-dominating sets and maximum $k$-separated matchings in $r$-regular graphs with large girth.

Joint work with Carlos Hoppen.

# Minicourses

### Information Diffusion on Random Graphs: Small Worlds, Percolation and Competition

Remco van der Hofstad (Eindhoven, The Netherlands)

Many phenomena in the real world can be translated in terms of networks. Examples include the World-Wide Web, social interactions, traffic and Internet, but also the interaction patterns between proteins, food webs and citation networks. The large-scale networks have, despite their diversity in backgrounds, surprisingly much in common. Many of these networks are small worlds, in the sense that one requires few links to hop between pairs of vertices. Also the variability of the number of connections between elements tends to be enormous, which is related to the scale-free phenomenon. The topology of the networks has a dramatic effect on how information spreads through the network. Information spread can be modelled by various percolation models, the prime example being smallest-weight routing or first passage percolation.

In this mini-course, we describe a few real-world networks and some of their empirical properties. We then explain results about distances and first-passage percolation in random graphs, and their implications to competition processes on them.

Joint work with Shankar Bhamidi, Mia Deijfen, Gerard Hooghiemstra.

### Friendly Frogs, Stable Marriage, and the Magic of Invariance

Alexander Holroyd (Microsoft/Seattle, USA)

I'll introduce a simple game in which two players take turns to move either one of two tokens between the points of a fixed set, with the proviso that the distance between the two tokens must decrease. This game and its variants are intimately tied to stable marriage, the topic of the 2012 Nobel prize in economics. Matters become particularly interesting if the points form a random countable set. Probabilistic tools such as invariance, ergodicity, deletion-tolerance and mass-transport provide elegant solutions to games that are seemingly inaccessible to other methods. However, we do not need to go far to reach a variant in which the outcome of the game is an open problem.

Based on joint work with Maria Deijfen and James Martin.

slides, video

### Random Embeddings of Planar Graphs

Richard Kenyon (Brown Univ., USA)

We discuss natural coordinates on the space of embeddings of a planar graph with convex faces and pinned boundary, and various probability measures on this space.

### Erdös-Rényi Percolation

Joel Spencer (NYU, USA)

The Random Graph $G(n,p)$ undergoes a macroscopic change at $p = \frac 1 n$. Why does this occur, how does this occur, how can $p$ be parametrized to "see" this change. What are the analogies to the Galton-Watson birth process, to bond percolation in $d$-space. We give a comprehensive discription, with (mostly!) proofs, of this vital phenomenon.

### Random Regular Graphs and Differential Equations

Nick Wormald (Monash Univ., Australia)

I will discuss some properties of random regular graphs and how to obtain them, in particular the "differential equation method". This lets us predict quite precisely the results of many algorithms applied to random regular graphs.