Regularity method and large deviation principles for the Erd\H{o}s--R\'enyi hypergraph
2021
We develop a quantitative large deviations theory for random Bernoulli tensors. The large deviation principles rest on a decomposition theorem for arbitrary tensors outside a set of tiny measure, in terms of a novel family of norms generalizing the cut norm. Combined with associated counting lemmas, these yield sharp asymptotics for upper tails of homomorphism counts in the $r$-uniform Erdős--Renyi hypergraph for any fixed $r\ge 2$, generalizing and improving on previous results for the Erdős--Renyi graph ($r=2$). The theory is sufficiently quantitative to allow the density of the hypergraph to vanish at a polynomial rate, and additionally yields (joint) upper and lower tail asymptotics for other nonlinear functionals of interest.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
3
Citations
NaN
KQI