The replica symmetric solution for hypergraph independent sets in the critical regime

Source 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 $K_r$, when suitably normalized, approach the set of optimizing graphons in cut distance.