Matchings in Benjamini–Schramm convergent graph sequences
HTML articles powered by AMS MathViewer
- by Miklós Abért, Péter Csikvári, Péter E. Frenkel and Gábor Kun PDF
- Trans. Amer. Math. Soc. 368 (2016), 4197-4218 Request permission
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
- 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
- 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/
- Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300, DOI 10.1214/EJP.v6-96
- Béla Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83 (1981), no. 2, 433–436. MR 624948, DOI 10.1090/S0002-9939-1981-0624948-6
- 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
- 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, DOI 10.1016/j.jctb.2006.06.001
- 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, DOI 10.1145/1250790.1250809
- 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.
- 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, DOI 10.1090/S0002-9939-10-10291-3
- 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 165515
- 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, DOI 10.37236/834
- 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, DOI 10.1016/j.jcss.2010.05.002
- C. D. Godsil, Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993. MR 1220704
- Leonid Gurvits, Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all, Electron. J. Combin. 15 (2008), no. 1, Research Paper 66, 26. With a corrigendum. MR 2411443
- L. Gurvits, Unleashing the power of Schrijver’s permanental inequality with the help of the Bethe Approximation, arXiv preprint 1106.2844v11
- 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
- Monique Laurent and Alexander Schrijver, On Leonid Gurvits’s proof for permanents, Amer. Math. Monthly 117 (2010), no. 10, 903–911. MR 2759363, DOI 10.4169/000298910X523380
- 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, DOI 10.1007/978-3-662-04687-6
- Russell Lyons, Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), no. 4, 491–522. MR 2160416, DOI 10.1017/S096354830500684X
- 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
- Brendan D. McKay, Spanning trees in regular graphs, European J. Combin. 4 (1983), no. 2, 149–160. MR 705968, DOI 10.1016/S0195-6698(83)80045-6
- 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.
- Alexander Schrijver, Counting $1$-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998), no. 1, 122–135. MR 1604705, DOI 10.1006/jctb.1997.1798
- A. Schrijver and W. G. Valiant, On lower bounds for permanents, Nederl. Akad. Wetensch. Indag. Math. 42 (1980), no. 4, 425–427. MR 598000, DOI 10.1016/1385-7258(80)90043-8
- 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, DOI 10.1016/1385-7258(79)90012-X
- Ian M. Wanless, Addendum to Schrijver’s work on minimum permanents, Combinatorica 26 (2006), no. 6, 743–745. MR 2288357, DOI 10.1007/s00493-006-0040-z
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
- MR Author ID: 623969
- 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
- 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.
- © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 4197-4218
- MSC (2010): Primary 05C70; Secondary 05C31, 05C69
- DOI: https://doi.org/10.1090/tran/6464
- MathSciNet review: 3453369