Compactness and finitely forcible graphons

Combinatorics Seminar
Friday, September 27, 2013 - 15:05
1 hour (actually 50 minutes)
Skiles 005
University of Warwick
Graphons are limit objects that are associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible graphons. In 2011, Lovasz and Szegedy asked several questions about the complexity of the topological space of so-called typical vertices of a finitely forcible graphon can be. In particular, they conjectured that the space is always compact. We disprove the conjecture by constructing a finitely forcible graphon such that the associated space of typical vertices is not compact. In fact, our construction actually provides an example of a finitely forcible graphon with the space which is even not locally compact. This is joint work with Roman Glebov and Dan Kral.