pith. sign in

arxiv: 2108.11003 · v3 · submitted 2021-08-25 · 🧮 math.PR · cs.DM

Matchings on Random Regular Hypergraphs

Zhongyang Li This is my paper

Pith reviewed 2026-05-24 13:20 UTC · model grok-4.3

classification 🧮 math.PR cs.DM
keywords random hypergraphsmonomer-dimer partition functionquenched free energyreplica symmetryconfiguration modelmatchingsecond-moment method
0
0 comments X

The pith

For random d-regular l-uniform hypergraphs, the log of the monomer-dimer partition function converges in probability to a variational formula when the replica-symmetric saddle uniquely maximizes the second-moment rate function.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes quenched free-energy limits for the monomer-dimer partition function on the configuration model of random regular hypergraphs. It combines fixed-density first-moment asymptotics, a two-overlap second-moment variational analysis, and subgraph conditioning on short cycles of the incidence structure. The central step is to locate explicit parameter regimes in which the replica-symmetric saddle is the unique global maximizer of the second-moment rate function. In those regimes the normalized logarithm of the partition function converges in probability to an explicit variational value. The same limit holds for weighted versions whenever the optimizing density lies inside the verified replica-symmetric region.

Core claim

In regimes where the replica-symmetric saddle is the unique global maximizer of the second-moment rate function, the normalized logarithm of the total matching partition function on random d-regular l-uniform hypergraphs converges in probability to an explicit variational value. The same holds for the weighted partition function when the maximizing density is in the verified replica-symmetric region, together with a checkable criterion for membership in that region and a first-moment upper tail bound on the size of a maximum matching.

What carries the argument

the replica-symmetric saddle of the second-moment rate function, which governs the limiting free energy precisely when it is the unique global maximizer

If this is right

  • The quenched free-energy limit holds for the monomer-dimer model on these hypergraphs in the identified regimes.
  • The same limit applies to weighted partition functions whenever the optimizing density lies in the verified replica-symmetric region.
  • A checkable criterion confirms whether a given density belongs to the replica-symmetric region.
  • A first-moment method supplies an upper tail bound on the size of a maximum matching.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The two-overlap variational technique may extend to other matching or tiling models whose overlap structure admits a similar second-moment analysis.
  • Numerical maximization of the explicit variational functional for concrete small d and l would yield concrete predictions for typical matching densities.
  • Subgraph conditioning on the incidence graph controls local cycle dependencies that are common in configuration-model hypergraphs.

Load-bearing premise

The replica-symmetric saddle is the unique global maximizer of the second-moment rate function throughout the identified parameter regimes.

What would settle it

An explicit pair (d,l, density) inside the claimed regime where the replica-symmetric saddle fails to be the unique global maximizer of the second-moment rate function, or where the partition-function limit deviates from the predicted variational value.

Figures

Figures reproduced from arXiv: 2108.11003 by Zhongyang Li.

Figure 3.1
Figure 3.1. Figure 3.1: The curve det H = 0 is represented by blue lines. When β ∈ [PITH_FULL_IMAGE:figures/full_fig_p017_3_1.png] view at source ↗
Figure 3.2
Figure 3.2. Figure 3.2: The top graph represents the case when det H > 0 has a unique component in Rβ; while the bottom graph represents the case when det H > 0 has two components in Rβ [PITH_FULL_IMAGE:figures/full_fig_p020_3_2.png] view at source ↗
read the original abstract

We study the monomer--dimer partition function on the configuration model of random $d$-regular, $l$-uniform hypergraphs. For fixed $d,l\ge2$, we prove quenched free-energy limits in explicit parameter regimes. The proof combines fixed-density first-moment asymptotics, a two-overlap second-moment variational analysis, and a subgraph-conditioning argument for the short cycles of the incidence structure. The main technical point is to identify regimes in which the replica-symmetric saddle is the unique global maximizer of the second-moment rate function. In those regimes the normalized logarithm of the total matching partition function converges in probability to an explicit variational value. We also prove the corresponding result for the weighted partition function whenever the maximizing density lies in the verified replica-symmetric region, give an additional checkable criterion for that region, and record a first-moment upper tail estimate for the maximum matching size.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves quenched free-energy limits for the monomer-dimer partition function on the configuration model of random d-regular l-uniform hypergraphs. For fixed d,l≥2, the normalized logarithm of the total matching partition function converges in probability to an explicit variational value in regimes where the replica-symmetric saddle is the unique global maximizer of the second-moment rate function. The proof combines fixed-density first-moment asymptotics, a two-overlap second-moment variational analysis, and subgraph conditioning on short cycles of the incidence structure. Additional results are given for the weighted partition function when the maximizing density lies in the verified replica-symmetric region, an extra checkable criterion for that region, and a first-moment upper tail bound on the maximum matching size.

Significance. If the results hold, the work supplies explicit variational expressions for the quenched free energy of matchings on random regular hypergraphs in identified regimes, together with verifiable criteria for the replica-symmetric region. The combination of first-moment methods, two-overlap second-moment analysis, and subgraph conditioning constitutes a technically coherent approach that extends existing techniques from graphs to hypergraphs. The provision of checkable criteria and the tail bound on maximum matching size add practical value.

minor comments (3)
  1. The abstract and introduction should explicitly state the precise parameter regimes (in terms of d, l, and density) in which the replica-symmetric saddle is verified to be the unique maximizer, rather than leaving the identification entirely to the body of the paper.
  2. Notation for the two-overlap second-moment rate function and the variational expression for the free energy should be introduced with a single consolidated definition early in the manuscript to improve readability.
  3. The subgraph-conditioning argument for short cycles would benefit from a brief comparison to the corresponding argument in the graph case (e.g., reference to prior works on monomer-dimer models on random regular graphs).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No major comments were provided in the report, so there are no specific points requiring point-by-point responses or revisions to the manuscript content.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation establishes quenched convergence of the normalized log partition function to an explicit variational expression precisely in regimes where first-moment asymptotics plus two-overlap second-moment analysis show the replica-symmetric saddle is the unique global maximizer, followed by subgraph conditioning on short cycles. No quoted step reduces the claimed limit to a fitted quantity defined by the same data, nor does any load-bearing premise rest on a self-citation whose content is itself unverified or tautological. The uniqueness identification is presented as the main technical contribution rather than an imported ansatz or self-definition. External probabilistic tools on the configuration model supply independent content, consistent with a score of 2.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract invokes standard probabilistic tools (first-moment asymptotics, two-overlap second-moment variational analysis, subgraph conditioning on short cycles) without introducing new free parameters or invented entities.

axioms (1)
  • standard math Standard first- and second-moment methods and subgraph conditioning apply to the configuration model of random regular hypergraphs.
    Described as the proof ingredients in the abstract.

pith-pipeline@v0.9.0 · 5664 in / 1250 out tokens · 24200 ms · 2026-05-24T13:20:22.792337+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages

  1. [1]

    Achlioptas and C

    D. Achlioptas and C. Moore. Random k-sat: Two moments suffice to cross a sharp threshold. SIAM Journal on Computing , 36, 2006

    work page 2006

  2. [2]

    Achlioptas and A

    D. Achlioptas and A. Naor. The two possible values of the chromatic number of a random graph. Annals of Mathematics , 162:1335–1351, 2005

    work page 2005

  3. [3]

    Alberici and P

    D. Alberici and P. Contucci. Solution of the monomer–dimer model on locally tree-like graphs. rigorous results. Communications in Mathematical Physics , 331:975–1003, 2014

    work page 2014

  4. [4]

    Aldous and J.M

    D. Aldous and J.M. Steele. The objective method: probabilistic combinatorial optimization and local weak convergence. Encycl. Math. Sci. , 110:1–72, 2004

    work page 2004

  5. [5]

    Alon and J.H

    N. Alon and J.H. Spencer. The Probabilistic Method . Wiley, New York, 1992. 54 ZHONGYANG LI

    work page 1992

  6. [6]

    Bezakova, A

    I. Bezakova, A. Galanis, L.A. Goldberg, H. Guo, and D. Stefankovic. Approximation via correlation decay when strong spatial mixing fails. SIAM Journal on Computing , 48:279–349, 2019

    work page 2019

  7. [7]

    Bhatnagar, A

    N. Bhatnagar, A. Sly, and P. Tetali. Decay of correlations for the hardcore model on the d-regular random graph. Electron. J. Probab., 21:1–42, 2016

    work page 2016

  8. [8]

    Bollob´ as

    B. Bollob´ as. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Euro. J. Combinatorics , 1:311–316, 1980

    work page 1980

  9. [9]

    Bordenave, M

    C. Bordenave, M. Lelarge, and J. Salez. Matchings on infinite graphs. Probability Theory and Related Fields, 157:183–208, 2013

    work page 2013

  10. [10]

    Coja-Oghlan and L

    A. Coja-Oghlan and L. Zdeborova. The condensation transition in random hypergraph 2-coloring. SODA ’12, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , pages 241–250, 2012

    work page 2012

  11. [11]

    Cooper, A Frieze, M

    C. Cooper, A Frieze, M. Molloy, and B. Reed. Perfect matchings in random r-regular, s-uniform hyper- graphs. Combinatorics, Probability and Computing , 5:1–14, 1996

    work page 1996

  12. [12]

    Dembo and A

    A. Dembo and A. Montanari. Ising models on locally tree-like graphs. Ann. Appl. Probab. , 20:565–592, 2010

    work page 2010

  13. [13]

    Dembo, A

    A. Dembo, A. Montanari, and N. Sun. Factor models on locally treelike graphs. Ann. Probab., 41:4162– 4213, 2013

    work page 2013

  14. [14]

    J. Ding, A. Sly, and N. Sun. Maximum independent sets on random regular graphs.Acta Math., 217:263– 340, 2016

    work page 2016

  15. [15]

    Elek and G

    G. Elek and G. Lippner. Borel oracles. an analytical approach to constant-time algorithms. Proc. Amer. Math. Soc., 138:2939–2947, 2010

    work page 2010

  16. [16]

    Erd¨ os and A

    P. Erd¨ os and A. R´ enyi. On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hung. , 17:359–368, 1966

    work page 1966

  17. [17]

    A. M. Frieze and S. Janson. Perfect matchings in random s-uniform hypergraphs. Random Structures and Algorithms , 7:41–57, 1995

    work page 1995

  18. [18]

    Galanis, D

    A. Galanis, D. Stefankovic, and E. Vigoda. Inapproximability of the partition function for the antifer- romagnetic ising and hard-core models. Combinatorics, Probability and Computing , 25, 2016

    work page 2016

  19. [19]

    Gamarnik and D

    D. Gamarnik and D. Katz. Sequential cavity method for computing free energy and surface pressure. Journal of Statistical Physics , 137:205–232, 2009

    work page 2009

  20. [20]

    Grimmett and Z

    G. Grimmett and Z. Li. Critical surface of hexagonal polygon model. Journal of Statistical Physics , 163:733–753, 2016

    work page 2016

  21. [21]

    Grimmett and Z

    G. Grimmett and Z. Li. The 1-2 model. Contemporary Mathematics, 696:139–152, 2017

    work page 2017

  22. [22]

    Grimmett and Z

    G. Grimmett and Z. Li. Critical surface of the 1-2 model. Int. Math. Res. Not. IMRN , 2018:6617–6672, 2018

    work page 2018

  23. [23]

    Grimmett and C.J.H

    G.R. Grimmett and C.J.H. McDiarmid. On colouring random graphs. Math. Proc. Cambridge Phi- los.Soc., 77:313–324, 1975

    work page 1975

  24. [24]

    Grinstead and J

    C. Grinstead and J. L. Snell. Introduction to Probability. American Mathematical Society, 1997

    work page 1997

  25. [25]

    Heilmann, O.J.and Lieb

    E.H. Heilmann, O.J.and Lieb. Monomers and dimers. Phys. Rev. Lett. , 24:1412–1414, 1970

    work page 1970

  26. [26]

    Heilmann and E.H

    O.J. Heilmann and E.H. Lieb. Theory of monomer–dimer systems. Commun. Math. Phys. , 25:190–232, 1972

    work page 1972

  27. [27]

    M. Jerrum. Two-dimensional monomer-dimer systems are computationally intractable. Journal of Sta- tistical Physics, 187:121–134, 1987

    work page 1987

  28. [28]

    Kasteleyn

    P.W. Kasteleyn. The statistics of dimers on a lattice. i. the number of dimer arrangements on a quadratic lattice. Physica, 27:1209–1225, 1961

    work page 1961

  29. [29]

    Kenyon, D

    C. Kenyon, D. Randall, and A. Sinclair. Approximating the number of monomer-dimer coverings of a lattice. Journal of Statistical Physics , 83:637–659, 1996

    work page 1996

  30. [30]

    R. Kenyon. Lectures on dimers. In Statistical Mechanics, pages 191–230. American Mathematical Society, Providence, RI, 2009. MATCHINGS ON RANDOM REGULAR HYPERGRAPHS 55

    work page 2009

  31. [31]

    Z. Li. Local statistics of realizable vertex models. Commun.Math.Phys., 304:723–763, 2011

    work page 2011

  32. [32]

    Liu and P

    J. Liu and P. Lu. Fptas for counting monotone cnf. Proceedings of the 2015 Annual ACM-SIAM Sym- posium on Discrete Algorithms , pages 1531–1548, 2015

    work page 2015

  33. [33]

    R. W. Robinson and N. C. Warmald. Almost all regular graphs are hamiltonian. Random Structures and Algorithms , 5:363–374, 1994

    work page 1994

  34. [34]

    Temperley and M

    W. Temperley and M. Fisher. Dimer problem in statistical mechanics—an exact result. Philos. Mag. , 6:1061–1063, 1961

    work page 1961

  35. [35]

    D. Weitz. Counting independent sets up to the tree threshold.STOC ’06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing , pages 140–149, 2006

    work page 2006

  36. [36]

    N. Wormald. The asymptotic distribution of short cycles in random regular graphs. Journal of Combi- natorial Theory, Series B , 31:168–182, 1981. (ZL) Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269- 3009, USA Email address : zhongyang.li@uconn.edu URL: http://www.math.uconn.edu/~zhongyang/

    work page 1981