Regularity method and large deviation principles for the Erd\H{o}s--R\'enyi hypergraph

DOI10.1215/00127094-2023-0029MaRDI QIDQ6360913zbMATH OpenFDO

Authors Nicholas A. Cook, Amir Dembo, Huy-Tuan Pham

Publication date 17 February 2021

Full work available at URL https://doi.org/10.1215/00127094-2023-0029

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Multilinear algebra, tensor calculus (15A69) Large deviations (60F10)

Abstract: 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 ErdH{o}s--R'enyi hypergraph for any fixed $rge2$, generalizing and improving on previous results for the ErdH{o}s--R'enyi graph ($r=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.

Recommendations

• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• On the upper tail problem for random hypergraphs
• The large deviation principle for the Erdős-Rényi random graph
• Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
• Upper tail for homomorphism counts in constrained sparse random graphs

Cited in

(4)

• Deviation probabilities for arithmetic progressions and other regular discrete structures
• On the upper tail of star counts in random graphs
• Large deviations of the empirical spectral measure of supercritical sparse Wigner matrices
• Normal approximation for subgraph count in random hypergraphs

This page was built for publication: Regularity method and large deviation principles for the Erd\H{o}s--R\'enyi hypergraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360913)