On the upper tail problem for random hypergraphs
From MaRDI portal
Abstract: The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an ErdH{o}s--R'enyi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not seen in random graphs. We conjecture a formula for the large deviation rate, i.e., the first order asymptotics of the log-probability that the number of copies of fixed subgraph in a sparse ErdH{o}s--R'enyi random -uniform hypergraph exceeds its expectation by a constant factor. This conjecture turns out to be significantly more intricate compared to the case for graphs. We verify our conjecture when the fixed subgraph being counted is a clique, as well as when is the 3-uniform 6-vertex 4-edge hypergraph consisting of alternating faces of an octahedron, where new techniques are required.
Recommendations
Cites work
- A generalization of Hölder's inequality and some probability inequalities
- Best constants in Young's inequality, its converse, and its generalization to more than three functions
- Gaussian width bounds with applications to arithmetic progressions in random settings
- Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Nonlinear large deviations
- On replica symmetry of large deviations in random graphs
- On the lower tail variational problem for random graphs
- On the variational problem for upper tails in sparse random graphs
- The infamous upper tail
- The large deviation principle for the Erdős-Rényi random graph
- The missing log in large deviations for triangle counts
- Upper tail large deviations for arithmetic progressions in a random set
- Upper tails and independence polynomials in random graphs
- Upper tails for triangles
- Upper tails via high moments and entropic stability
Cited in
(17)- Subgraphs in non-uniform random hypergraphs
- Upper tails via high moments and entropic stability
- Replica symmetry in upper tails of mean-field hypergraphs
- Upper tails and independence polynomials in random graphs
- A concentration result with application to subgraph count
- Note on upper density of quasi-random hypergraphs
- A counterexample to the DeMarco-Kahn upper tail conjecture
- On the lower tail variational problem for random graphs
- On the variational problem for upper tails in sparse random graphs
- Upper tail for homomorphism counts in constrained sparse random graphs
- The upper tail problem for induced 4‐cycles in sparse random graphs
- Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime
- Regularity method and large deviation principles for the Erd\H{o}s--R\'enyi hypergraph
- Typical structure of sparse exponential random graph models
- A large deviation principle for block models
- Normal approximation for subgraph count in random hypergraphs
- Union-free hypergraphs and probability theory
This page was built for publication: On the upper tail problem for random hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6073628)
