# Graph Limits

## Apr 6 - Apr 9

#### Summary

The workshop will address both the basic theory and the applications of graph limits, focusing on graphons and graphexes, as well as various applications. In the last few years several beautiful and exciting developments have taken place in this area. It is therefore time to bring together researchers from different fields, including probability theory, combinatorics, statistics and algorithmics.

The workshop will run from Monday morning 09.00 am till Thursday afternoon 17.00 pm

#### Sponsors

#### Organisers

Christian Borgs | University of California, Berkeley |

Jennifer Chayes | University of California, Berkeley |

Souvik Dhara | MIT Mathematics and Microsoft Research |

Remco van der Hofstad | NETWORKS (TU Eindhoven) |

Frank den Hollander | NETWORKS (Leiden University) |

Viresh Patel | NETWORKS (University of Amsterdam) |

#### Speakers

Siva Athreya | Indian Statistical Institute, Bangalore |

Morgane Austern | Microsoft Research |

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

Sourav Chatterjee | Stanford University |

Péter Csikvári | Eötvös Loránd University |

Jan Hladky | Czech Academy of Sciences |

Olga Klopp | CNRS |

Daniel Kral | Masaryk University and University of Warwick |

Joonkyung Lee | Universität Hamburg |

László Lovász | Eötvös Loránd University |

Asaf Nachmias | Tel Aviv University |

Sofia Olhede | University College London |

Kavita Ramanan | Brown University |

Adrian Roellin | National University of Singapore |

Subhabrata Sen | Harvard University |

Joel Spencer | New York University |

Jan Volec | Masaryk University |

Mei Yin | Denver University |

Christina Lee Yu | Cornell University |

Ilias Zadik | New York University |

#### Abstracts

**Graphon dynamics from population genetics
**In this talk we shall discuss a natural class of dynamics in dense networks arising from resampling in multi-type populations. We consider sequence of finite graphs whose dynamics are governed by the empirical type distribution of the whole population at that time and in the large-population-size limit this dynamics converges to a random process in the space of graphons. This is joint work with Frank den Hollander and Adrian Rollin

**Action convergence of graphs and random matrices
**The notion of action convergence was proposed to find limit objects for certain sequences of (either deterministic or random) graphs and matrices, which are far from being sparse and dense as well. This approach unifies several concepts of graph limit theory (e.g. local-global convergence of bounded degree graphs, and dense graph convergence), associates limit objects to graph sequences of intermediate density (e.g. hypercubes). Moreover, it can be applied to solve problems about the eigenvectors of random sign matrices (in which all entries are independent, but the norm of the matrix is much smaller than the norm of the adjacency matrix of an Erdos--Renyi graph). The goal of the talk is to present this convergence notion, the limit objects (which are bounded operators of a special form, and general representations of graphons and graphings) and connections to random matrices. Joint work with Balazs Szegedy.

**Link Prediction in Sparse Graphon Model
**Our work focuses on the study of networks generated under the sparse graphon model with missing observations. In this setting, the problem of es- timating the matrix of connections probabilities is of particular interest. Our results find a natural application in predicting the existence of non-observed edges, a commonly encountered problem called link prediction. Interaction net- works are often incomplete, as detecting interactions can require significant experimental effort. Instead of exhaustively testing for every connection, we deduce the pairs of agents which are most likely to interact based on the relations already recorded and on available covariates. When these estimations are precise enough, testing for these interactions would enable scientists to establish the network topology while substantially reducing the costs.

**Uniqueness of combinatorial limits
**We will present several results concerning combinatorial structures that are determined by finitely many density constraints. First, we will show that such graph limits can have arbitrarily complex structure in a strong sense. We use this result to provide a counterexample to a conjecture of Lovasz that optimal solutions to extremal graph theory problems can be made asymptotically unique by introducing finitely many additional constraints.

At the end of the talk, we focus on limits corresponding to quasirandom combinatorial structures. For graphs, it is well-known that quasirandomness is characterized by the edge density and the density of C_4. An analogous result holds for permutation: a permutation is quasirandom if and only if the density of every 4-pattern is 1/24+o(1). We strengthen the results by showing that a permutation is quasirandom if and only if the sum of the densities of eight specific 4-patterns is 1/3+o(1), and we characterize all sets of 4-patterns with this property.

(joint with T. Chan, J. Cooper, A. Grzesik, L. M. Lovasz, T. Martins, J. Noel, Y. Pehova, M. Sharifzadeh, J. Sosnovec and J. Volec)

**Convex graphon parameters and graph norms
**Sidorenko's conjecture states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is a quasirandom graph. A notorious example where this conjecture remains open is when H=K_{5,5}∖C_{10}. It was even unknown whether this graph possesses the strictly stronger, weakly norming property.

We take a step towards understanding the graph K_{5,5}∖C_{10} by proving that it is not weakly norming. More generally, we show that 'twisted' blow-ups of cycles, which include K_{5,5}∖C_{10} and C_{6}□K_{2}, are not weakly norming. This answers two questions of Hatami. The method relies on the analysis of Hessian matrices defined by graph homomorphisms, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that K_{t,t} minus a perfect matching, proven to be weakly norming by Lovász, is not norming for every t>3.

(joint work with Bjarne Schülke)

**Limits of graph sequences of intermediate density**

Convergence and limit objects have been defined mainly in the two extreme cases: dense graphs and bunded-degree graphs. The intermediate cases have attracted considerable interest, but it has been difficult to obtain satisfactory results. Recently it has emerged that Markov chains on measurable spaces, perhaps endowed with some additional structure like a measure on the underlying set, can capture many limiting properties of growing graph sequences. Furthermore, one can extend several graph theoretical concepts and basic theorems (on flows, harmonic functions, mixing of random walks, etc.) to this general setting.

(joint work with Agnes Backhausz, David Kunszenti-Kovács, and Balazs Szegedy)

**Higher-order fluctuations in dense graph limit theory**

Dense graph limit theory is now a well-established approach to describe the structure of large dense networks. While this theory is mainly concerned with the first-order behaviour of graphs in the same way as the Law of Large Numbers describes the first order behaviour of sums of random variables in classical limit theory, a theory to describe second or even higher-order fluctuations around those first order limits has not yet been developed. However, we argue that the tools to understand these fluctuations have already been around since the 90s, although in the more abstract form of generalised U-statistics. We discuss how this theory can be used to describe fluctuations of large graphs, and we complements these results with rates of convergence using Stein’s method and with generalisations that go beyond the framework of generalised U-statistics, but which are still relevant to dense graph limit theory.

**Large deviations for dense random graphs: beyond mean-field**

In a seminal paper, Chatterjee and Varadhan derived an LDP for the dense Erdös-Rényi random graph, viewed as a random graphon. This directly provides LDPs for continuous functionals such as subgraph counts, spectral norms, etc. In contrast, very little is understood about this problem if the underlying random graph is inhomogeneous or constrained. In this talk, we will take some preliminary steps in this direction, and study large deviations for uniform random graphs with given degrees.

(joint work with Souvik Dhara)

**(Some) Finitely Forcible Graphon
**Quasirandomness is a robust concept which is implied by the "correct" counts of edges and 4-cycles for G(n,p). We discuss the seminal work of Chung, Graham and Wilson. We give a relatively simple argument that random multipartite graphs are finitely forcible.

**Perspectives on exponential random graphs
**Exponential random graphs are powerful in the study of modern networks. By representing a complex global configuration through a set of tractable local features, these models seek to capture a wide variety of common network tendencies. This talk will look into the asymptotic structure of weighted exponential random graphs and formulate a quantitative theory of phase transitions. The main techniques that we use are variants of statistical physics. Based on joint work with multiple collaborators.

More information will follow as it becomes available.

#### Registration