Upper tails for subgraph counts in random graphs
From MaRDI portal
Let \(X\) be the number of copies of a fixed graph \(G\) contained in the random graph on \(n\) vertices with edge probability \(p\). The upper tail of the probability distribution of \(X\) is shown to have best possible (in a certain sense) upper and lower bounds in terms of \(n\) and \(p\). Similar bounds are also proved for the random graph on \(n\) vertices with a fixed number of edges.
Recommendations
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- On Subgraph Sizes in Random Graphs
- Subgraph counts for dense random graphs with specified degrees
- Upper tails and independence polynomials in random graphs
- On extremal subgraphs of random graphs
- Subgraph counts in random graphs using incomplete U-statistics methods
- Extremal subgraphs of random graphs
- Extremal subgraphs of random graphs
- Anti-concentration for subgraph counts in random graphs
Cites work
- A large deviation result on the number of small subgraphs of a random graph
- A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
- Counting extensions
- Deviation inequality for monotonic Boolean functions with application to the number ofk-cycles in a random graph
- Divide and conquer martingales and the number of triangles in a random graph
- scientific article; zbMATH DE number 3911357 (Why is no real title available?)
- scientific article; zbMATH DE number 54803 (Why is no real title available?)
- On the number of copies of one hypergraph in another
- On the number of subgraphs of prescribed type of graphs with a given number of edges
- Poisson approximation for large deviations
- Random graphs with monochromatic triangles in every edge coloring
- Some intersection theorems for ordered sets and graphs
- The deletion method for upper tail estimates
- The infamous upper tail
- The number of large graphs with a positive density of triangles
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The strange logic of random graphs
- Threshold Functions for Ramsey Properties
- Threshold functions for small subgraphs
- When are small subgraphs of a random graph normally distributed?
Cited in
(78)- When are small subgraphs of a random graph normally distributed?
- Concentration for Poisson \(U\)-statistics: subgraph counts in random geometric graphs
- Upper tails for arithmetic progressions in random subsets
- Threshold functions for small subgraphs: an analytic approach
- Moment inequalities for functions of independent random variables
- Detecting local network motifs
- Anti-concentration for subgraph counts in random graphs
- Regular graphs with many triangles are structured
- Supersaturation for subgraph counts
- Upper tails via high moments and entropic stability
- Localization in random geometric graphs with too many edges
- Threshold functions for small subgraphs in simple graphs and multigraphs
- Nonlinear large deviations: beyond the hypercube
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
- On the number of weakly connected subdigraphs in random \(k\)NN digraphs
- On the missing log in upper tail estimates
- Bivariate fluctuations for the number of arithmetic progressions in random sets
- Limit laws for the number of triangles in the generalized random graphs with random node weights
- Upper tail bounds for stars
- Upper tails and independence polynomials in random graphs
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- The deletion method for upper tail estimates
- Nonlinear large deviations
- A large deviation result on the number of small subgraphs of a random graph
- The lower tail: Poisson approximation revisited
- An introduction to large deviations for random graphs
- The missing log in large deviations for triangle counts
- Upper tails for triangles
- Sub-Gaussian tails for the number of triangles in G( n, p)
- A concentration result with application to subgraph count
- Tight upper tail bounds for cliques
- On replica symmetry of large deviations in random graphs
- scientific article; zbMATH DE number 4212111 (Why is no real title available?)
- Vertex Ramsey properties of randomly perturbed graphs
- Note on a problem of M. Talagrand
- Combinatorial theorems in sparse random sets
- On the upper tail of counts of strictly balanced subgraphs
- Divide and conquer martingales and the number of triangles in a random graph
- On the KŁR conjecture in random graphs
- Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
- An improved upper bound on the density of universal random graphs
- Rate of convergence to the Poisson law of the numbers of cycles in the generalized random graphs
- On limits of sparse random graphs
- Upper tail bounds for cycles
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- A counterexample to the DeMarco-Kahn upper tail conjecture
- On the lower tail variational problem for random graphs
- When does the \(K_{4}\)-free process stop?
- CLT-related large deviation bounds based on Stein's method
- On the variational problem for upper tails in sparse random graphs
- On a conjecture of Nagy on extremal densities
- Many \(T\) copies in \(H\)-free graphs
- Applications of Stein's method for concentration inequalities
- On the upper tail problem for random hypergraphs
- Upper tail for homomorphism counts in constrained sparse random graphs
- Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes
- scientific article; zbMATH DE number 7763253 (Why is no real title available?)
- Fluctuations of subgraph counts in graphon based random graphs
- Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph
- Lower tails via relative entropy
- 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
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Threshold graphs maximise homomorphism densities
- Exponential inequalities for the tail probabilities of the number of cycles in generalized random graphs
- A large deviation principle for block models
- Universality in prelimiting tail behavior for regular subgraph counts in the Poisson regime
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)
- Large deviations of the empirical spectral measure of supercritical sparse Wigner matrices
- Large deviation principles for graphon sampling
- Large deviations for subgraphs in inhomogeneous random graphs
- Sparse random graphs with many triangles
- Upper tail bounds for irregular graphs
- Simonovits's theorem in random graphs
- Spectral theory of dense hypergraph limits
- Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence
This page was built for publication: Upper tails for subgraph counts in random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1881736)
