The deletion method for upper tail estimates
Let \(\{Y_\alpha,\alpha\in \mathcal A\}\) be a family of nonnegative random variables, where \(\mathcal A\) is a finite set with a symmetric relation \(\sim\). Assume that every \(Y_\alpha\) is independent of \(\{Y_\beta:\beta\sim\alpha\}\). Set \(X=\sum_\alpha Y_\alpha\) and \(\mu=EX\). An upper tail estimate \[ P(X\geq \mu+t)\leq (1+t/2\mu)^{-r}+P \left(\max_\alpha\sum_{\beta\sim\alpha}Y_\beta>t/2r\right) \] with arbitrary \(r>0\) is obtained. This basic estimate is proved by a new method called deletion method. The rest of the paper is devoted to derivations of several estimates from this basic one in the case \(\mathcal A\) consists of subsets of some index set and \(\alpha\sim\beta\) means that \(\alpha \cap\beta\) has some minimal cardinality. A comparison of the obtained results with that of \textit{J. H. Kim} and \textit{V. H. Vu} [Combinatorica 20, 417--434 (2000; Zbl 0969.60013)] is proved. Applications to the number \(X_G\) of copies of a graph \(G\) in the random graph \(G(n,p)\) are given. In particular, some known upper bounds for the cases \(G=K_4\) and \(G=C_4\) are essentially improved.
- Upper tails for subgraph counts in random graphs
- The infamous upper tail
- Tight upper tail bounds for cliques
- A large deviation result on the number of small subgraphs of a random graph
- Upper tails for triangles
- A concentration result with application to subgraph count
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- When are small subgraphs of a random graph normally distributed?
- Many cliques in \(H\)-free subgraphs of random graphs
- Random deletion does not affect asymptotic normality or quadratic negligibility
- Concentration inequalities using the entropy method
- Upper tails for arithmetic progressions in random subsets
- Moment inequalities for functions of independent random variables
- Upper tails for subgraph counts in random graphs
- Regular graphs with many triangles are structured
- Upper tails via high moments and entropic stability
- On the missing log in upper tail estimates
- Upper tail bounds for stars
- On the average-case complexity of parameterized clique
- Upper tails and independence polynomials in random graphs
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- Nonlinear large deviations
- The lower tail: Poisson approximation revisited
- Upper bounds on probability thresholds for asymmetric Ramsey properties
- The missing log in large deviations for triangle counts
- Upper tails for triangles
- Combinatorial estimates by the switching method
- Tight upper tail bounds for cliques
- On replica symmetry of large deviations in random graphs
- Combinatorial theorems in sparse random sets
- General deletion lemmas via the Harris inequality
- The infamous upper tail
- A counterexample to the DeMarco-Kahn upper tail conjecture
- On the method of typical bounded differences
- When does the \(K_{4}\)-free process stop?
- Approximation algorithms for channel allocation problems in broadcast networks
- The Cℓ‐free process
- On the variational problem for upper tails in sparse random graphs
- Upper tail for homomorphism counts in constrained sparse random graphs
- Large deviations in random latin squares
- A large deviation principle for block models
- On the upper tail of star counts in random graphs
- Large deviation principles for graphon sampling
- Large deviations for subgraphs in inhomogeneous random graphs
This page was built for publication: The deletion method for upper tail estimates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2567402)
