## Convergence of graphs with intermediate density

HTML articles powered by AMS MathViewer

- by Péter E. Frenkel PDF
- Trans. Amer. Math. Soc.
**370**(2018), 3363-3404 Request permission

## Abstract:

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

- Miklós Abért, Péter Csikvári, Péter E. Frenkel, and Gábor Kun,
*Matchings in Benjamini-Schramm convergent graph sequences*, Trans. Amer. Math. Soc.**368**(2016), no. 6, 4197–4218. MR**3453369**, DOI 10.1090/tran/6464 - Miklós Abért and Tamás Hubai,
*Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs*, Combinatorica**35**(2015), no. 2, 127–151. MR**3347464**, DOI 10.1007/s00493-014-3066-7 - J. M. Aldaz and J. Pérez Lázaro,
*Functions of bounded variation, the derivative of the one dimensional maximal function, and applications to inequalities*, Trans. Amer. Math. Soc.**359**(2007), no. 5, 2443–2461. MR**2276629**, DOI 10.1090/S0002-9947-06-04347-9 - David Aldous and Russell Lyons,
*Processes on unimodular random networks*, Electron. J. Probab.**12**(2007), no. 54, 1454–1508. MR**2354165**, DOI 10.1214/EJP.v12-463 - B. Bollobás and B. D. McKay,
*The number of matchings in random regular graphs and bipartite graphs*, J. Combin. Theory Ser. B**41**(1986), no. 1, 80–91. MR**854605**, DOI 10.1016/0095-8956(86)90029-8 - Béla Bollobás and Oliver Riordan,
*Metrics for sparse graphs*, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge Univ. Press, Cambridge, 2009, pp. 211–287. MR**2588543** - C. Borgs, J.T. Chayes, H. Cohn, and Y. Zhao: An $L_p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions, preprint, 2014. arXiv:1401.2906
- C. Borgs, J.T. Chayes, H. Cohn, Y. Zhao: An $L_p$ theory of sparse graph convergence II: LD convergence, quotients and right convergence preprint, 2014. arXiv: 1408.0744
- C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi,
*Convergent sequences of dense graphs II. Multiway cuts and statistical physics*, Ann. of Math. (2)**176**(2012), no. 1, 151–219. MR**2925382**, DOI 10.4007/annals.2012.176.1.2 - L. H. Clark, J. C. George, and T. D. Porter,
*On the number of $1$-factors in the $n$-cube*, Proceedings of the Twenty-eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1997), 1997, pp. 67–69. MR**1604993** - Péter Csikvári and Péter E. Frenkel,
*Benjamini-Schramm continuity of root moments of graph polynomials*. part B, European J. Combin.**52**(2016), no. part B, 302–320. MR**3425982**, DOI 10.1016/j.ejc.2015.07.009 - Péter Csikvári, Péter E. Frenkel, Jan Hladký, and Tamás Hubai,
*Chromatic roots and limits of dense graphs*, Discrete Math.**340**(2017), no. 5, 1129–1135. MR**3612454**, DOI 10.1016/j.disc.2016.11.009 - Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent Sets, Matchings, and Occupancy Fractions, arXiv: 1508.04675
- J. L. Doob,
*Measure theory*, Graduate Texts in Mathematics, vol. 143, Springer-Verlag, New York, 1994. MR**1253752**, DOI 10.1007/978-1-4612-0877-8 - Ioana Dumitriu and Soumik Pal,
*Sparse regular random graphs: spectral density and eigenvectors*, Ann. Probab.**40**(2012), no. 5, 2197–2235. MR**3025715**, DOI 10.1214/11-AOP673 - Gábor Elek,
*On limits of finite graphs*, Combinatorica**27**(2007), no. 4, 503–507. MR**2359831**, DOI 10.1007/s00493-007-2214-8 - Gábor Elek,
*On the limit of large girth graph sequences*, Combinatorica**30**(2010), no. 5, 553–563. MR**2776719**, DOI 10.1007/s00493-010-2559-2 - K. J. Falconer,
*The geometry of fractal sets*, Cambridge Tracts in Mathematics, vol. 85, Cambridge University Press, Cambridge, 1986. MR**867284** - G. Freud, Orthogonale Polynome, Akadémiai Kiadó, Budapest, 1969.
- Wolfgang Gawronski,
*On the asymptotic distribution of the zeros of Hermite, Laguerre, and Jonquière polynomials*, J. Approx. Theory**50**(1987), no. 3, 214–231. MR**892220**, DOI 10.1016/0021-9045(87)90020-7 - C. D. Godsil,
*Algebraic combinatorics*, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993. MR**1220704** - I. S. Gradshteyn and I. M. Ryzhik,
*Table of integrals, series, and products*, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1980. Corrected and enlarged edition edited by Alan Jeffrey; Incorporating the fourth edition edited by Yu. V. Geronimus [Yu. V. Geronimus] and M. Yu. Tseytlin [M. Yu. Tseĭtlin]; Translated from the Russian. MR**582453** - Ole J. Heilmann and Elliott H. Lieb,
*Theory of monomer-dimer systems*, Comm. Math. Phys.**25**(1972), 190–232. MR**297280**, DOI 10.1007/BF01877590 - Miklós Kornyik and György Michaletzky,
*Wigner matrices, the moments of roots of Hermite polynomials and the semicircle law*, J. Approx. Theory**211**(2016), 29–41. MR**3547630**, DOI 10.1016/j.jat.2016.07.006 - László Lovász,
*Combinatorial problems and exercises*, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. MR**1265492** - László Lovász,
*Large networks and graph limits*, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR**3012035**, DOI 10.1090/coll/060 - L. Lovász and M. D. Plummer,
*Matching theory*, North-Holland Mathematics Studies, vol. 121, North-Holland Publishing Co., Amsterdam; North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29. MR**859549** - László Lovász and Balázs Szegedy,
*Limits of dense graph sequences*, J. Combin. Theory Ser. B**96**(2006), no. 6, 933–957. MR**2274085**, DOI 10.1016/j.jctb.2006.05.002 - Brendan D. McKay,
*The expected eigenvalue distribution of a large regular graph*, Linear Algebra Appl.**40**(1981), 203–216. MR**629617**, DOI 10.1016/0024-3795(81)90150-6 - James Propp,
*Enumeration of matchings: problems and progress*, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 255–291. MR**1731819** - Cheng Qin Qu, Hui Rao, and Wei Yi Su,
*Hausdorff measure of homogeneous Cantor set*, Acta Math. Sin. (Engl. Ser.)**17**(2001), no. 1, 15–20. MR**1831742**, DOI 10.1007/s101140000089 - Peter Orbanz and Balazs Szegedy,
*Borel liftings of graph limits*, Electron. Commun. Probab.**21**(2016), Paper No. 65, 4. MR**3548777**, DOI 10.1214/16-ECP14 - Gabor Szegö,
*Orthogonal Polynomials*, American Mathematical Society Colloquium Publications, Vol. 23, American Mathematical Society, New York, 1939. MR**0000077**, DOI 10.1090/coll/023 - Linh V. Tran, Van H. Vu, and Ke Wang,
*Sparse random graphs: eigenvalues and eigenvectors*, Random Structures Algorithms**42**(2013), no. 1, 110–134. MR**2999215**, DOI 10.1002/rsa.20406

## 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
- Email: frenkelp@cs.elte.hu
- 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.
- © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**370**(2018), 3363-3404 - MSC (2010): Primary 05C15, 05C50, 05C60, 05C99, 05C31; Secondary 05C81, 05C80, 05C76, 05C70, 05C63
- DOI: https://doi.org/10.1090/tran/7036
- MathSciNet review: 3766852