Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Convergence of graphs with intermediate density

Author: Péter E. Frenkel
Journal: Trans. Amer. Math. Soc. 370 (2018), 3363-3404
MSC (2010): Primary 05C15, 05C50, 05C60, 05C99, 05C31; Secondary 05C81, 05C80, 05C76, 05C70, 05C63
Published electronically: December 1, 2017
MathSciNet review: 3766852
Full-text PDF

Abstract | References | Similar Articles | Additional Information


We propose a notion of graph convergence that interpolates between the Benjamini–Schramm convergence of bounded degree graphs and the dense graph convergence developed by László Lovász and his coauthors. We prove that spectra of graphs, and also some important graph parameters such as numbers of colorings or matchings, behave well in convergent graph sequences. Special attention is given to graph sequences of large essential girth, for which asymptotics of coloring numbers are explicitly calculated. We also treat numbers of matchings in approximately regular graphs.

We introduce tentative limit objects that we call graphonings because they are common generalizations of graphons and graphings. Special forms of these, called Hausdorff and Euclidean graphonings, involve geometric measure theory. We construct Euclidean graphonings that provide limits of hypercubes and of finite projective planes, and, more generally, of a wide class of regular sequences of large essential girth. For any convergent sequence of large essential girth, we construct weaker limit objects: an involution invariant probability measure on the sub-Markov space of consistent measure sequences (this is unique), or an acyclic reversible sub-Markov kernel on a probability space (non-unique). We also pose some open problems.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C15, 05C50, 05C60, 05C99, 05C31, 05C81, 05C80, 05C76, 05C70, 05C63

Retrieve articles in all journals with MSC (2010): 05C15, 05C50, 05C60, 05C99, 05C31, 05C81, 05C80, 05C76, 05C70, 05C63

Additional Information

Péter E. Frenkel
Affiliation: Faculty of Science, Institute of Mathematics, ELTE Eötvös Loránd University, 1117 Budapest, Hungary, Pázmány Péter sétány 1/C – and – Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 1053 Budapest, Hungary Reáltanoda u. 13-15. ORCID iD: 0000-0003-2672-8772
MR Author ID: 623969

Received by editor(s): March 19, 2016
Received by editor(s) in revised form: July 31, 2016
Published electronically: December 1, 2017
Additional Notes: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No. 648017), from the MTA Rényi Lendület Groups and Graphs research group, and from the Hungariain National Research, Development and Innovation Office – NKFIH, OTKA grants no. K104206 and K109684.
Article copyright: © Copyright 2017 American Mathematical Society