Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
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
  • 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