Convergence of graphs with intermediate density

Frenkel, Péter

doi:10.1090/tran/7036

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