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?)


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