Daniel Král': First order convergence of graphs
Time: Mon 2014-04-14 12.10 - 13.00
Location: Room 4523, Lindstedsvägen 5, KTH CSC
Participating: Daniel Král', University of Warwick
Practicalities
Lunch is served at 12:00 noon (register at this doodle by Sunday April 13 at 8 pm). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.
Abstract
Nesetril and Ossona de Mendez introduced the notion of the first order (FO) convergence of graphs. This notion can be viewed as a unified notion of the existing notions of convergence of dense and sparse graphs. In particular, every FO convergent sequence of graphs is convergent in the sense of left convergence of dense graphs, and every FO convergent sequence of sparse graphs is convergent in the Benjamini-Schramm sense.
During the talk, we will provide a brief introduction to the theory of graph limits and its applications in extremal combinatorics and theoretical computer science. We will then present our results on the FO convergence of trees, the FO convergence of matroids and we will also discuss the relation of the limit object to the convergent sequence. In particular, our results yield answers to several problems raised by Nesetril and Ossona de Mendez.
The presented results were obtained jointly with Demetres Christofides, Frantisek Kardos, Martin Kupec, Anita Liebenau, Lukas Mach and Vojtech Tuma.