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)

Request Permissions   Purchase Content 
 
 

 

Matchings in Benjamini-Schramm convergent graph sequences


Authors: Miklós Abért, Péter Csikvári, Péter E. Frenkel and Gábor Kun
Journal: Trans. Amer. Math. Soc. 368 (2016), 4197-4218
MSC (2010): Primary 05C70; Secondary 05C31, 05C69
DOI: https://doi.org/10.1090/tran/6464
Published electronically: October 5, 2015
MathSciNet review: 3453369
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce the matching measure of a finite graph as the uniform distribution on the roots of the matching polynomial of the graph. We analyze the asymptotic behavior of the matching measure for graph sequences with bounded degree.

A graph parameter is said to be estimable if it converges along every Benjamini-Schramm convergent sparse graph sequence. We prove that the normalized logarithm of the number of matchings is estimable. We also show that the analogous statement for perfect matchings already fails for $ d$-regular bipartite graphs for any fixed $ d\ge 3$. The latter result relies on analyzing the probability that a randomly chosen perfect matching contains a particular edge.

However, for any sequence of $ d$-regular bipartite graphs converging to the $ d$-regular tree, we prove that the normalized logarithm of the number of perfect matchings converges. This applies to random $ d$-regular bipartite graphs. We show that the limit equals the exponent in Schrijver's lower bound on the number of perfect matchings.

Our analytic approach also yields a short proof for the Nguyen-Onak (also Elek-Lippner) theorem saying that the matching ratio is estimable. In fact, we prove the slightly stronger result that the independence ratio is estimable for claw-free graphs.


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

  • [1] 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
  • [2] M. Abért, A. Thom and B. Virág, Benjamini-Schramm convergence and pointwise convergence of the spectral measure, preprint at http://www.math.uni-leipzig.de/MI/thom/
  • [3] Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13 pp. (electronic). MR 1873300 (2002m:82025), https://doi.org/10.1214/EJP.v6-96
  • [4] Béla Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83 (1981), no. 2, 433-436. MR 624948 (82m:05079), https://doi.org/10.2307/2043545
  • [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 (87i:05151), https://doi.org/10.1016/0095-8956(86)90029-8
  • [6] Maria Chudnovsky and Paul Seymour, The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B 97 (2007), no. 3, 350-357. MR 2305888 (2008c:05130), https://doi.org/10.1016/j.jctb.2006.06.001
  • [7] Mohsen Bayati, David Gamarnik, Dimitriy Katz, Chandra Nair, and Prasad Tetali, Simple deterministic approximation algorithms for counting matchings, STOC'07--Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 122-127. MR 2402435 (2009e:68117), https://doi.org/10.1145/1250790.1250809
  • [8] P. Csikvári and P. E. Frenkel, Benjamini-Schramm continuity of root moments of graph polynomials, European Journal of Combinatorics (2015), DOI 10.1016/j.ejc.2015.07.009.
  • [9] Gábor Elek and Gábor Lippner, Borel oracles. An analytical approach to constant-time algorithms, Proc. Amer. Math. Soc. 138 (2010), no. 8, 2939-2947. MR 2644905 (2011g:03117), https://doi.org/10.1090/S0002-9939-10-10291-3
  • [10] Paul Erdős and Horst Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 12 (1963), 251-257 (German). MR 0165515 (29 #2797)
  • [11] S. Friedland, E. Krop, and K. Markström, On the number of matchings in regular graphs, Electron. J. Combin. 15 (2008), no. 1, Research Paper 110, 28. MR 2438582 (2009f:05017)
  • [12] David Gamarnik and Dmitriy Katz, A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix, J. Comput. System Sci. 76 (2010), no. 8, 879-883. MR 2722354 (2011i:68164), https://doi.org/10.1016/j.jcss.2010.05.002
  • [13] C. D. Godsil, Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993. MR 1220704 (94e:05002)
  • [14] Leonid Gurvits, Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all, with a corrigendum, Electron. J. Combin. 15 (2008), no. 1, Research Paper 66, 26. MR 2411443 (2009e:15015)
  • [15] L. Gurvits, Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation, arXiv preprint 1106.2844v11
  • [16] Ole J. Heilmann and Elliott H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232. MR 0297280 (45 #6337)
  • [17] Monique Laurent and Alexander Schrijver, On Leonid Gurvits's proof for permanents, Amer. Math. Monthly 117 (2010), no. 10, 903-911. MR 2759363 (2012c:15002), https://doi.org/10.4169/000298910X523380
  • [18] Wolfgang Lück, $ L^2$-invariants: theory and applications to geometry and $ K$-theory, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 44, Springer-Verlag, Berlin, 2002. MR 1926649 (2003m:58033)
  • [19] Russell Lyons, Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), no. 4, 491-522. MR 2160416 (2006j:05048), https://doi.org/10.1017/S096354830500684X
  • [20] Brendan D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra Appl. 40 (1981), 203-216. MR 629617 (84h:05089), https://doi.org/10.1016/0024-3795(81)90150-6
  • [21] Brendan D. McKay, Spanning trees in regular graphs, European J. Combin. 4 (1983), no. 2, 149-160. MR 705968 (85d:05194), https://doi.org/10.1016/S0195-6698(83)80045-6
  • [22] H. N. Nguyen and K. Onak, Constant-time approximation algorithms via local improvements, 49th Annual IEEE Symposium on Foundations of Computer Science (2008), pp. 327-336.
  • [23] Alexander Schrijver, Counting $ 1$-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998), no. 1, 122-135. MR 1604705 (99b:05117), https://doi.org/10.1006/jctb.1997.1798
  • [24] A. Schrijver and W. G. Valiant, On lower bounds for permanents, Nederl. Akad. Wetensch. Indag. Math. 42 (1980), no. 4, 425-427. MR 598000 (82a:15004)
  • [25] M. Voorhoeve, A lower bound for the permanents of certain $ (0,\,1)$-matrices, Nederl. Akad. Wetensch. Indag. Math. 41 (1979), no. 1, 83-86. MR 528221 (80c:15005)
  • [26] Ian M. Wanless, Addendum to Schrijver's work on minimum permanents, Combinatorica 26 (2006), no. 6, 743-745. MR 2288357, https://doi.org/10.1007/s00493-006-0040-z

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C70, 05C31, 05C69

Retrieve articles in all journals with MSC (2010): 05C70, 05C31, 05C69


Additional Information

Miklós Abért
Affiliation: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 13-15 Reáltanoda u., 1053 Budapest, Hungary
Email: abert@renyi.hu

Péter Csikvári
Affiliation: Department of Mathematics, Massachusets Institute of Technology, Cambridge Massachusetts 02139 – and – Department of Computer Science, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary
Email: peter.csikvari@gmail.com

Péter E. Frenkel
Affiliation: Department of Algebra and Number Theory, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary – and – Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 13-15 Reáltanoda u., 1053 Budapest, Hungary
Email: frenkelp@cs.elte.hu

Gábor Kun
Affiliation: Department of Computer Science, Eötvös Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary
Address at time of publication: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 13-15 Reáltanoda u., 1053 Budapest, Hungary
Email: kungabor@cs.elte.hu, kungabor@renyi.hu

DOI: https://doi.org/10.1090/tran/6464
Keywords: Matchings, matching polynomial, Benjamini--Schramm convergence, expander graphs
Received by editor(s): January 6, 2014
Received by editor(s) in revised form: April 15, 2014
Published electronically: October 5, 2015
Additional Notes: The first and third authors were partially supported by ERC Consolidator Grant 648017. The first three authors were partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant no. K109684. The second author was partially supported by the National Science Foundation under grant no. DMS-1500219 and the Hungarian National Foundation for Scientific Research (OTKA), grant no. K81310. The fourth author was partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant No. PD 109731, by the János Bolyai Scholarship of the Hungarian Academy of Sciences, by the Marie Curie IIF Fellowship, grant No. 627476, and by ERC Advanced Research, grant No. 227701. All authors were partially supported by MTA Rényi “Lendület” Groups and Graphs Research Group.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society