The replica symmetric solution for hypergraph independent sets in the critical regime
Abstract
We prove a variational formula for the logarithmic asymptotics of a non-existence probability in a broad class of combinatorial problems such as avoiding cliques in random graphs and k-term arithmetic progressions in random subsets of integers. These results follow from a formula for the probability that a binomial random subset of the vertices of a locally sparse hypergraph is an independent set. The formula holds throughout the critical regime, interpolating between the regimes in which Janson's inequality and the method of hypergraph containers give the respective asymptotics. The formula is the replica-symmetric Bethe free energy formula from statistical physics applied to a hypergraph hardcore model. The proof uses two new techniques. The first, for the upper bound, involves revealing a small `window' of a random independent set and then applying entropy methods. The second, for the lower bound, involves the analysis of a random greedy algorithm guided by a Belief Propagation fixed point. In the case of avoiding cliques in random graphs, the variational formula can be expressed as an optimization problem over graphons. Moreover, typical random graphs conditioned on not containing Kr, when suitably normalized, approach the set of optimizing graphons in cut distance.
Related
- Approximating the Gibbs Measure of Spherical Spin Glasses to Within o(N−1/2) in the Replica Symmetric Phase
- Interference Queueing Networks: A Replica Mean-Field Approach in the Symmetric Setting
- Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
- A quantitative replica-symmetric bound for Sherrington--Kirkpatrick model in the entire de Almeida--Thouless region
BibTeX
@misc{jenssen2026replica,
title = {{The replica symmetric solution for hypergraph independent sets in the critical regime}},
author = {Matthew Jenssen and Will Perkins and Aditya Potukuchi and Michael Simkin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10433},
eprint = {2610.10433},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10433},
}
RIS
TY - UNPB
TI - The replica symmetric solution for hypergraph independent sets in the critical regime
AU - Matthew Jenssen
AU - Will Perkins
AU - Aditya Potukuchi
AU - Michael Simkin
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10433
UR - https://arxiv.org/abs/2610.10433
AB - We prove a variational formula for the logarithmic asymptotics of a non-existence probability in a broad class of combinatorial problems such as avoiding cliques in random graphs and k-term arithmetic progressions in random subsets of integers. These results follow from a formula for the probability that a binomial random subset of the vertices of a locally sparse hypergraph is an independent set. The formula holds throughout the critical regime, interpolating between the regimes in which Janson's inequality and the method of hypergraph containers give the respective asymptotics. The formula is the replica-symmetric Bethe free energy formula from statistical physics applied to a hypergraph hardcore model. The proof uses two new techniques. The first, for the upper bound, involves revealing a small `window' of a random independent set and then applying entropy methods. The second, for the lower bound, involves the analysis of a random greedy algorithm guided by a Belief Propagation fixed point. In the case of avoiding cliques in random graphs, the variational formula can be expressed as an optimization problem over graphons. Moreover, typical random graphs conditioned on not containing K_r, when suitably normalized, approach the set of optimizing graphons in cut distance.
ER -