Loading Events

« All Events

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

Siva Athreya

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

 

Agnes Backhausz

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.

 

Olga Klopp

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.

 

Daniel Kral

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)

 

Joonkyung Lee

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)

 

László Lovász

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)

 

Adrian Roellin

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.

 

Subhabrata Sen

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)

 

Joel Spencer

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

 

Mei Yin

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

Link to registration form

 

Details

Start:
Apr 6
End:
Apr 9
Event Category:

Venue

MF 11-12 (4th floor MetaForum Building, TU/e)