Description:
<p>We introduce the <italic>matching measure</italic> 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.</p>
<p>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 <italic>perfect</italic> matchings already fails for <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d">
<mml:semantics>
<mml:mi>d</mml:mi>
<mml:annotation encoding="application/x-tex">d</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>–regular bipartite graphs for any fixed <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d greater-than-or-equal-to 3">
<mml:semantics>
<mml:mrow>
<mml:mi>d</mml:mi>
<mml:mo>≥<!-- ≥ --></mml:mo>
<mml:mn>3</mml:mn>
</mml:mrow>
<mml:annotation encoding="application/x-tex">d\ge 3</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>. The latter result relies on analyzing the probability that a randomly chosen perfect matching contains a particular edge.</p>
<p>However, for any sequence of <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d">
<mml:semantics>
<mml:mi>d</mml:mi>
<mml:annotation encoding="application/x-tex">d</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>–regular bipartite graphs converging to the <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d">
<mml:semantics>
<mml:mi>d</mml:mi>
<mml:annotation encoding="application/x-tex">d</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>–regular tree, we prove that the normalized logarithm of the number of perfect matchings converges. This applies to random <inline-formula content-type="math/mathml">
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d">
<mml:semantics>
<mml:mi>d</mml:mi>
<mml:annotation encoding="application/x-tex">d</mml:annotation>
</mml:semantics>
</mml:math>
</inline-formula>–regular bipartite graphs. We show that the limit equals the exponent in Schrijver’s lower bound on the number of perfect matchings.</p>
<p>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.</p>