Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
We derive a variational formula for the logarithmic asymptotics of non-existence probabilities in combinatorial problems, specifically for hypergraph independent sets in the critical regime. This formula interpolates between existing results from Janson's inequality and the method of hypergraph containers, providing a unified framework. The proof employs novel techniques involving entropy methods for upper bounds and Belief Propagation-guided random greedy algorithms for lower bounds.
A replica-symmetric Bethe free energy formula precisely quantifies independent set probabilities in hypergraphs across the entire critical regime.
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.