REGULARITY METHOD AND LARGE DEVIATION PRINCIPLES FOR THE ERDŐS–RÉNYI HYPERGRAPH

We develop a quantitative large deviations theory for random hypergraphs, which rests on tensor decomposition and counting lemmas under a novel family of cut-type norms. As our main application, we obtain sharp asymptotics for joint upper and lower tails of homomorphism counts in the r-uniform Erdős–Rényi hypergraph for any fixed r ≥ 2, generalizing and improving on previous results for the Erdős–Rényi graph (r D 2). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields tail asymptotics for other nonlinear functionals, such as induced homomorphism counts.

Duke Scholars

Author Nicholas A Cook Mathematics