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
DOI: https://doi.org/10.1090/tran/7036
Published electronically: December 1, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1090/tran/6464
  • [2] 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, https://doi.org/10.1007/s00493-014-3066-7
  • [3] 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, https://doi.org/10.1090/S0002-9947-06-04347-9
  • [4] David Aldous and Russell Lyons, Processes on unimodular random networks, Electron. J. Probab. 12 (2007), no. 54, 1454-1508. MR 2354165, https://doi.org/10.1214/EJP.v12-463
  • [5] 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, https://doi.org/10.1016/0095-8956(86)90029-8
  • [6] 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
  • [7] 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
  • [8] 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
  • [9] 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, https://doi.org/10.4007/annals.2012.176.1.2
  • [10] 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
  • [11] 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, https://doi.org/10.1016/j.ejc.2015.07.009
  • [12] 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, https://doi.org/10.1016/j.disc.2016.11.009
  • [13] Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent Sets, Matchings, and Occupancy Fractions, arXiv: 1508.04675
  • [14] J. L. Doob, Measure theory, Graduate Texts in Mathematics, vol. 143, Springer-Verlag, New York, 1994. MR 1253752
  • [15] Ioana Dumitriu and Soumik Pal, Sparse regular random graphs: spectral density and eigenvectors, Ann. Probab. 40 (2012), no. 5, 2197-2235. MR 3025715, https://doi.org/10.1214/11-AOP673
  • [16] Gábor Elek, On limits of finite graphs, Combinatorica 27 (2007), no. 4, 503-507. MR 2359831, https://doi.org/10.1007/s00493-007-2214-8
  • [17] Gábor Elek, On the limit of large girth graph sequences, Combinatorica 30 (2010), no. 5, 553-563. MR 2776719, https://doi.org/10.1007/s00493-010-2559-2
  • [18] K. J. Falconer, The geometry of fractal sets, Cambridge Tracts in Mathematics, vol. 85, Cambridge University Press, Cambridge, 1986. MR 867284
  • [19] G. Freud, Orthogonale Polynome, Akadémiai Kiadó, Budapest, 1969.
  • [20] 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, https://doi.org/10.1016/0021-9045(87)90020-7
  • [21] C. D. Godsil, Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993. MR 1220704
  • [22] 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
  • [23] Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232. MR 0297280
  • [24] 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, https://doi.org/10.1016/j.jat.2016.07.006
  • [25] László Lovász, Combinatorial problems and exercises, 2nd ed., North-Holland Publishing Co., Amsterdam, 1993. MR 1265492
  • [26] László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035
  • [27] 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
  • [28] 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, https://doi.org/10.1016/j.jctb.2006.05.002
  • [29] Brendan D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra Appl. 40 (1981), 203-216. MR 629617, https://doi.org/10.1016/0024-3795(81)90150-6
  • [30] 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
  • [31] 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, https://doi.org/10.1007/s101140000089
  • [32] Peter Orbanz and Balazs Szegedy, Borel liftings of graph limits, Electron. Commun. Probab. 21 (2016), Paper No. 65, 4. MR 3548777, https://doi.org/10.1214/16-ECP14
  • [33] Gabor Szegö, Orthogonal Polynomials, American Mathematical Society, New York, 1939. American Mathematical Society Colloquium Publications, v. 23. MR 0000077
  • [34] 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, https://doi.org/10.1002/rsa.20406

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
Email: frenkelp@cs.elte.hu

DOI: https://doi.org/10.1090/tran/7036
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

American Mathematical Society