Loading Events

« All Events

Graph Limits

Apr 6, 2020 - Apr 9, 2020

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 Microsoft Research
Jennifer Chayes Microsoft Research
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
László Miklós Lovász Massachusetts Institute of Technology
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
Katalin Vesztergombi Eötvös Loránd University
Mei Yin Denver University
Christina Lee Yu Cornell University
Ilias Zadik New York University

Abstracts

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)

More information will follow as it becomes available.

Registration

Link to registration form

 

Details

Start:
Apr 6, 2020
End:
Apr 9, 2020
Event Category:

Venue

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