pith. sign in

arxiv: 2604.04652 · v1 · submitted 2026-04-06 · 🧮 math.CO · math.PR

Non-existence probabilities and lower tails in the critical regime via Belief Propagation

Matthew Jenssen , Will Perkins , Aditya Potukuchi , Michael Simkin This is my paper

Pith reviewed 2026-05-10 19:43 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords non-existence probabilitylower tailbelief propagationBethe free energyrandom hypergraphscritical regimearithmetic progressions
0
0 comments X

The pith

The probability that a random hypergraph subset induces far fewer edges than expected can be approximated by the Bethe free energy at the unique fixed point of belief propagation.

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

This paper computes the logarithmic asymptotics of non-existence probabilities and lower-tail events for combinatorial structures in the critical regime, where container methods and Janson's inequality no longer suffice. It works in the general setting of a p-random subset of vertices in a k-uniform hypergraph that contains significantly fewer hyperedges than its expectation. The method requires only simple structural conditions on the hypergraph together with an upper bound on p set by a phase transition in the hard-core model on an infinite regular hypertree. When these hold, the log probability equals the Bethe free energy evaluated at the unique fixed point of the belief-propagation operator defined on the hypergraph itself.

Core claim

Under simple structural conditions on the hypergraph and an upper bound on p determined by a phase transition in the hard-core model on the infinite k-uniform, Delta-regular, linear hypertree, the lower-tail probability that a p-random subset induces significantly fewer hyperedges than expected is accurately approximated by the Bethe free energy evaluated at the unique fixed point of a Belief Propagation operator on the hypergraph.

What carries the argument

The unique fixed point of the Belief Propagation operator on the hypergraph, where the Bethe free energy is evaluated to obtain the logarithmic asymptotics.

If this is right

  • Logarithmic asymptotics for non-existence probabilities of subgraphs in random graphs become computable via belief propagation.
  • The same asymptotics apply to the number of k-term arithmetic progressions in random subsets of the integers.
  • The method fills the gap between hypergraph container techniques and Janson's inequality for a wide range of parameters.
  • Efficient numerical evaluation of the fixed point replaces direct enumeration or moment calculations for these tail events.

Where Pith is reading between the lines

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

  • The same fixed-point analysis could supply tail estimates for non-uniform or weighted hypergraph models.
  • Variational characterizations of the Bethe free energy may link these combinatorial tails to phase-transition phenomena studied in statistical physics.
  • Numerical solution of the belief-propagation equations on finite instances could be used to test the sharpness of the derived asymptotics.

Load-bearing premise

The hypergraph satisfies simple structural conditions and the density parameter p remains below the phase-transition threshold of the hard-core model on the infinite regular hypertree.

What would settle it

For any concrete hypergraph meeting the stated conditions, compute the true lower-tail probability numerically and check whether its logarithm equals the Bethe free energy value at the unique belief-propagation fixed point.

Figures

Figures reproduced from arXiv: 2604.04652 by Aditya Potukuchi, Matthew Jenssen, Michael Simkin, Will Perkins.

Figure 1
Figure 1. Figure 1: The function x ∗ 3,1 from Lemma 1.5 with k = 3, c = 1, representing the density of elements in a random 3-AP-free subset of [n] chosen with prior density n −1/2 . Unlike in the case of H-freeness (with χ(H) ≥ 3) we do not prove the existence of a phase transition for k-AP-freeness. In fact, we conjecture there is no phase transition for this problem or for C2k-freeness in G(n, p) for k ≥ 2. Conjecture 1. T… view at source ↗
Figure 2
Figure 2. Figure 2: A 3-uniform linear hypertree. 2.2. Gibbs measures and partition functions. For λ ≥ 0 and ζ ∈ [0, 1] and hypergraph G, recall the definition of the Gibbs measure µG,λ,ζ and partition function ZG(λ, ζ) from (1.11) and (1.12). These objects naturally extend to the setting of multihypergraphs where now we interpret the parameter E(S) = {e ∈ E(G) : e ⊆ S} with multiplicity. For v ∈ V , let Z in v (G, λ, ζ), Zou… view at source ↗
read the original abstract

We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of parameters in the `critical regime' between the regime amenable to hypergraph container methods and that amenable to Janson's inequality. Examples include lower tails and non-existence probabilities for subgraphs of random graphs and for $k$-term arithmetic progressions in random sets of integers. Our methods apply in the general framework of estimating the probability that a $p$-random subset of vertices in a $k$-uniform hypergraph induces significantly fewer hyperedges than expected. We show that under some simple structural conditions on the hypergraph and an upper bound on $p$ determined by a phase transition in the hard-core model on the infinite $k$-uniform, $\Delta$-regular, linear hypertree, this probability can be accurately approximated by the Bethe free energy evaluated at the unique fixed point of a Belief Propagation operator on the hypergraph.

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 / 2 minor

Summary. The paper claims to compute the logarithmic asymptotics of non-existence probabilities (and more generally lower-tail probabilities) for combinatorial problems in the critical regime between hypergraph container methods and Janson's inequality. In the general setting of a p-random subset of vertices in a k-uniform hypergraph inducing significantly fewer hyperedges than expected, the log-asymptotics equal the Bethe free energy evaluated at the unique fixed point of a Belief Propagation operator, provided the hypergraph satisfies simple structural conditions and p is bounded above by the phase transition threshold of the hard-core model on the infinite k-uniform, Δ-regular, linear hypertree. The result is illustrated on lower tails for subgraphs of random graphs and for k-term arithmetic progressions in random sets of integers.

Significance. If the central approximation holds, the work supplies a new analytic tool for tail probabilities in a regime where existing combinatorial methods are known to be insufficient. The explicit link to the hard-core model phase transition on the infinite hypertree and the use of the Bethe free energy at the BP fixed point provide a concrete, computable expression for the rate function. This framework has the potential to unify and extend results across several areas of probabilistic combinatorics, including random graphs and additive combinatorics, and the absence of free parameters or ad-hoc fitting in the stated claim is a methodological strength.

minor comments (2)
  1. [Abstract] The abstract and introduction would benefit from a brief, explicit statement of the error term (or the sense in which the approximation is 'accurate') rather than leaving it implicit in the phrase 'accurately approximated'.
  2. [Introduction] Notation for the BP message-update rule and the precise definition of the Bethe free energy functional should be introduced with a self-contained display equation early in the technical sections to assist readers who are not already familiar with the statistical-physics literature.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the assessment of significance, and the recommendation of minor revision. We are pleased that the potential of the Bethe free energy approximation at the BP fixed point to unify results across probabilistic combinatorics is recognized. Since the report lists no specific major comments, we have no points requiring rebuttal or revision at this stage.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives the logarithmic asymptotics of the non-existence probability by showing it equals the Bethe free energy at the unique fixed point of a Belief Propagation operator on the hypergraph, under structural conditions on the hypergraph and an upper bound on p taken from the hard-core model phase transition on the infinite k-uniform Δ-regular linear hypertree. This reference is external and independent; the target probability is not defined in terms of the Bethe free energy or BP fixed point, nor is any parameter fitted to the result itself and then relabeled as a prediction. No load-bearing step reduces by construction to a self-citation, ansatz smuggled via citation, or renaming of a known result. The central claim is self-contained and externally falsifiable on the listed combinatorial examples.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central approximation rests on the existence of a unique BP fixed point and the validity of the Bethe free energy as an asymptotic proxy, plus the phase-transition threshold from the hard-core model; these are treated as given under the stated structural conditions.

axioms (2)
  • domain assumption simple structural conditions on the hypergraph
    Invoked to guarantee the BP operator has a unique fixed point and the approximation holds; location: abstract statement of the main result.
  • domain assumption upper bound on p from hard-core phase transition on infinite hypertree
    Determines the regime where the method applies; treated as an external input from the hard-core model.

pith-pipeline@v0.9.0 · 5474 in / 1431 out tokens · 55073 ms · 2026-05-10T19:43:12.045906+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

62 extracted references · 62 canonical work pages

  1. [1]

    Anari, K

    N. Anari, K. Liu, and S. O. Gharan. Spectral independence in high-dimensional expanders and applica- tions to the hardcore model.SIAM Journal on Computing, (0):FOCS20–1, 2021. 14

    work page 2021

  2. [2]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs.Journal of the American Math- ematical Society, 28(3):669–709, 2015. 3, 4, 5, 8, 15

    work page 2015

  3. [3]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij. The method of hypergraph containers. InProceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3059–3092. World Scientific, 2018. 8

    work page 2018

  4. [4]

    Balogh, R

    J. Balogh, R. Morris, W. Samotij, and L. Warnke. The typical structure of sparseK r+1-free graphs. Transactions of the American Mathematical Society, 368(9):6439–6485, 2016. 2

    work page 2016

  5. [5]

    Bencs and P

    F. Bencs and P. Buys. Optimal zero-free regions for the independence polynomial of bounded degree hypergraphs.Random Structures & Algorithms, 66(4):e70018, 2025. 16, 18, 19

    work page 2025

  6. [6]

    Bennett and T

    P. Bennett and T. Bohman. A note on the random greedy independent set algorithm.Random Structures & Algorithms, 49(3):479–502, 2016. 8, 15

    work page 2016

  7. [7]

    Bez´ akov´ a, A

    I. Bez´ akov´ a, A. Galanis, L. A. Goldberg, H. Guo, and D. Stefankovic. Approximation via correlation decay when strong spatial mixing fails.SIAM Journal on Computing, 48(2):279–349, 2019. 14

    work page 2019

  8. [8]

    Bohman and P

    T. Bohman and P. Keevash. The early evolution of the H-free process.Inventiones mathematicae, 181(2):291–336, 2010. 43

    work page 2010

  9. [9]

    Chatterjee and S

    S. Chatterjee and S. S. Varadhan. The large deviation principle for the Erd˝ os-R´ enyi random graph. European Journal of Combinatorics, 32(7):1000–1017, 2011. 4

    work page 2011

  10. [10]

    Z. Chen, K. Liu, N. Mani, and A. Moitra. Strong spatial mixing for colorings on trees and its algorithmic applications. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 810–845. IEEE, 2023. 14

    work page 2023

  11. [11]

    Coja-Oghlan and W

    A. Coja-Oghlan and W. Perkins. Belief propagation on replica symmetric random factor graph models. Annales de l’institut Henri Poincare D, 5(2):211–249, 2018. 15

    work page 2018

  12. [12]

    Dembo and A

    A. Dembo and A. Montanari. Ising models on locally tree-like graphs.The Annals of Applied Probability, 20(2):565–592, 2010. 15

    work page 2010

  13. [13]

    Dembo, A

    A. Dembo, A. Montanari, A. Sly, and N. Sun. The replica symmetric solution for Potts models on d-regular graphs.Communications in Mathematical Physics, 327(2):551–575, 2014. 12, 15

    work page 2014

  14. [14]

    Dembo, A

    A. Dembo, A. Montanari, and N. Sun. Factor models on locally tree-like graphs.The Annals of Probability, pages 4162–4213, 2013. 12, 15

    work page 2013

  15. [15]

    M. Dyer, A. Sinclair, E. Vigoda, and D. Weitz. Mixing in time and space for lattice spin systems: A combinatorial view.Random Structures & Algorithms, 24(4):461–479, 2004. 13

    work page 2004

  16. [16]

    Erd˝ os, D

    P. Erd˝ os, D. Kleitman, and B. Rothschild. Asymptotic enumeration ofK n-free graphs.Colloquio Inter- nazionale sulle Teorie Combinatorie (Rome, 1973), (17):19–27, 1973. 2

    work page 1973

  17. [17]

    Galanis, D

    A. Galanis, D. ˇStefankoviˇ c, and E. Vigoda. Inapproximability of the partition function for the antifer- romagnetic Ising and hard-core models.Combinatorics, Probability and Computing, 25(4):500–559, July

    work page

  18. [18]

    Galanis, D

    A. Galanis, D. Stefankovic, E. Vigoda, and L. Yang. Ferromagnetic Potts model: Refined #-BIS-hardness and related results.SIAM Journal on Computing, 45(6):2004–2065, 2016. 15

    work page 2004

  19. [19]

    Galvin, G

    D. Galvin, G. McKinley, W. Perkins, M. Sarantis, and P. Tetali. On the zeroes of hypergraph independence polynomials.Combinatorics, Probability and Computing, 33(1):65–84, 2024. 14

    work page 2024

  20. [20]

    Gamarnik and D

    D. Gamarnik and D. Katz. Correlation decay and deterministic FPTAS for counting list-colorings of a graph. InProceedings of the eighteenth annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1245–1254, 2007. 14

    work page 2007

  21. [21]

    Georgii.Gibbs measures and phase transitions, volume 9

    H.-O. Georgii.Gibbs measures and phase transitions, volume 9. Walter de Gruyter, 2011. 13

    work page 2011

  22. [22]

    Gerschenfeld and A

    A. Gerschenfeld and A. Montanari. Reconstruction for models on random graphs. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 194–204. IEEE, 2007. 15

    work page 2007

  23. [23]

    Gl¨ ockner

    H. Gl¨ ockner. Implicit functions from topological vector spaces to banach spaces.Israel Journal of Math- ematics, 155(1):205–252, 2006. 27

    work page 2006

  24. [24]

    Hermon, A

    J. Hermon, A. Sly, and Y. Zhang. Rapid mixing of hypergraph independent sets.Random Structures & Algorithms, 54(4):730–767, 2019. 14

    work page 2019

  25. [25]

    S. Janson. Poisson approximation for large deviations.Random Structures & Algorithms, 1(2):221–229,

    work page

  26. [26]

    4, 8 52 NON-EXISTENCE PROBABILITIES AND LOWER TAILS IN THE CRITICAL REGIME

    work page

  27. [27]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski. An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. In J. J. M. Karo´ nski and A. Ruci´ nski, editors,Random graphs 87, Pozn´ an, pages 73–87, 1987. 2, 3, 4, 5, 8

    work page 1987

  28. [28]

    Janson and L

    S. Janson and L. Warnke. The lower tail: Poisson approximation revisited.Random Structures & Algo- rithms, 48(2):219–246, 2016. 4

    work page 2016

  29. [29]

    Jenssen, W

    M. Jenssen, W. Perkins, and A. Potukuchi. On the evolution of structure in triangle-free graphs.Advances in Mathematics, 480:110499, 2025. 2

    work page 2025

  30. [30]

    Jenssen, W

    M. Jenssen, W. Perkins, A. Potukuchi, and M. Simkin. Lower tails for triangles inside the critical window. arXiv preprint arXiv:2411.18563, 2024. 3, 4, 14, 44

    work page arXiv 2024

  31. [31]

    Jenssen, W

    M. Jenssen, W. Perkins, A. Potukuchi, and M. Simkin. Sampling, counting, and large deviations for triangle-free graphs near the critical density. InFoundations of Computer Science (FOCS 2024), 2024. 14

    work page 2024

  32. [32]

    Kelley and R

    Z. Kelley and R. Meka. Strong bounds for 3-progressions. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 933–973. IEEE, 2023. 5

    work page 2023

  33. [33]

    F. P. Kelly. Stochastic models of computer communication systems.Journal of the Royal Statistical Society. Series B (Methodological), pages 379–395, 1985. 13

    work page 1985

  34. [34]

    D. J. Kleitman and K. J. Winston. On the number of graphs without 4-cycles.Discrete Mathematics, 41(2):167–172, 1982. 8

    work page 1982

  35. [35]

    Kohayakawa, T

    Y. Kohayakawa, T. Luczak, and V. R¨ odl. OnK 4-free subgraphs of random graphs.Combinatorica, 17(2):173–213, 1997. 4

    work page 1997

  36. [36]

    Koller and N

    D. Koller and N. Friedman.Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. 12

    work page 2009

  37. [37]

    Kozma and W

    G. Kozma and W. Samotij. Lower tails via relative entropy.The Annals of Probability, 51(2):665–698,

    work page

  38. [38]

    J. Leng, A. Sah, and M. Sawhney. Improved bounds for Szemer´ edi’s theorem.arXiv preprint arXiv:2402.17995, 2024. 5

    work page arXiv 2024

  39. [39]

    L. Li, P. Lu, and Y. Yin. Correlation decay up to uniqueness in spin systems. InProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 67–84. SIAM, 2013. 14

    work page 2013

  40. [40]

    Liu and P

    J. Liu and P. Lu. FPTAS for counting monotone CNF. InProceedings of the Twenty-Sixth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 1531–1548. SIAM, 2014. 14, 18

    work page 2014

  41. [41]

    J. Liu, A. Sinclair, and P. Srivastava. Fisher zeros and correlation decay in the Ising model.Journal of Mathematical Physics, 60(10), 2019. 14

    work page 2019

  42. [42]

    J. Liu, C. Wang, Y. Yin, and Y. Yu. Phase transitions via complex extensions of Markov chains. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 903–914, 2025. 14

    work page 2025

  43. [43]

    T. Luczak. On triangle-free random graphs.Random Structures & Algorithms, 16(3):260–276, 2000. 3, 4

    work page 2000

  44. [44]

    W. Mantel. Problem 28.Wiskundige Opgaven, 10(60-61):320, 1907. 2

    work page 1907

  45. [45]

    Mezard and A

    M. Mezard and A. Montanari.Information, physics, and computation. Oxford University Press, 2009. 10, 12

    work page 2009

  46. [46]

    Mousset, A

    F. Mousset, A. Noever, K. Panagiotou, and W. Samotij. On the probability of nonexistence in binomial subsets.Annals of Probability, 48(1):493–525, 2020. 2, 8

    work page 2020

  47. [47]

    Osthus, H

    D. Osthus, H. J. Pr¨ omel, and A. Taraz. For which densities are random triangle-free graphs almost surely bipartite?Combinatorica, 23(1):105–150, 2003. 2

    work page 2003

  48. [48]

    Peters, G

    H. Peters, G. Regts, et al. On a conjecture of sokal concerning roots of the independence polynomial.The Michigan Mathematical Journal, 2019. 14

    work page 2019

  49. [49]

    Saxton and A

    D. Saxton and A. Thomason. Hypergraph containers.Inventiones mathematicae, 201(3):925–992, 2015. 3, 4, 5, 8, 15

    work page 2015

  50. [50]

    Shao and Y

    S. Shao and Y. Sun. Contraction: A unified perspective of correlation decay and zero-freeness of 2-spin systems.Journal of Statistical Physics, 185:1–25, 2021. 14

    work page 2021

  51. [51]

    Sinclair, P

    A. Sinclair, P. Srivastava, and M. Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs.Journal of Statistical Physics, 155(4):666–686, 2014. 14

    work page 2014

  52. [52]

    A. Sly. Computational transition at the uniqueness threshold. InProceedings of the Fifty-first Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pages 287–296. IEEE, 2010. 13

    work page 2010

  53. [53]

    Sly and N

    A. Sly and N. Sun. Counting in two-spin models on d-regular graphs.The Annals of Probability, 42(6):2383–2416, 2014. 13

    work page 2014

  54. [54]

    Sly and N

    A. Sly and N. Sun. Counting in two-spin models on d-regular graphs.Annals of Probability, 42(6):2383– 2416, 2014. 15 NON-EXISTENCE PROBABILITIES AND LOWER TAILS IN THE CRITICAL REGIME 53

    work page 2014

  55. [55]

    Stark and N

    D. Stark and N. Wormald. The probability of non-existence of a subgraph in a moderately sparse random graph.Combinatorics, Probability and Computing, 27(4):672–715, 2018. 2

    work page 2018

  56. [56]

    Szemer´ edi

    E. Szemer´ edi. On sets of integers containing no k elements in arithmetic progression.Acta Arith, 27(199- 245):2, 1975. 5

    work page 1975

  57. [57]

    S. C. Tatikonda and M. I. Jordan. Loopy belief propagation and Gibbs measures. InProceedings of the Eighteenth conference on Uncertainty in artificial intelligence, pages 493–500, 2002. 12

    work page 2002

  58. [58]

    D. Weitz. Counting independent sets up to the tree threshold. InProceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pages 140–149. ACM, 2006. 13

    work page 2006

  59. [59]

    N. C. Wormald. The perturbation method and triangle-free random graphs.Random Structures & Algo- rithms, 9(1-2):253–270, 1996. 2

    work page 1996

  60. [60]

    J. S. Yedidia, W. T. Freeman, Y. Weiss, et al. Understanding belief propagation and its generalizations. Exploring artificial intelligence in the new millennium, 8(236-239):0018–9448, 2003. 12

    work page 2003

  61. [61]

    S. Zhang. Hypergraph independence polynomials with a zero close to the origin.Combinatorics, Proba- bility and Computing, pages 1–5, 2025. 14

    work page 2025

  62. [62]

    Y. Zhao. On the lower tail variational problem for random graphs.Combinatorics, Probability and Com- puting, 26(2):301–320, 2017. 4 AppendixA.Proof of Lemma 8.4 Proof of Lemma 8.4.Recall that we define the operatorF=F (k) c,ζ on the set of bounded measurable functionsf: [0,1]→R >0 by F f(t) =cexp  − ζ αk kX ℓ=1 Z w(t,ℓ) 0 Y i∈Iℓ f(t+is)ds   , whereα k...

    work page 2017