Poisson approximation for large deviations
From MaRDI portal
Publication:3977078
DOI10.1002/RSA.3240010209zbMath0747.05079DBLPjournals/rsa/Janson90aOpenAlexW2166965860WikidataQ97016101 ScholiaQ97016101MaRDI QIDQ3977078
Publication date: 25 June 1992
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240010209
Random graphs (graph-theoretic aspects) (05C80) Large deviations (60F10) Distribution theory (60E99)
Related Items (81)
Compound Poisson approximation: A user's guide ⋮ Upper tails for subgraph counts in random graphs ⋮ Higher order corrections for anisotropic bootstrap percolation ⋮ The infamous upper tail ⋮ Approximation algorithms for the covering Steiner problem ⋮ A zero‐one law for a random subset ⋮ Local connectivity of neutral networks ⋮ The missing log in large deviations for triangle counts ⋮ Optimal inter-object correlation when replicating for availability ⋮ On Sidon sets and asymptotic bases ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Random graphs with monochromatic triangles in every edge coloring ⋮ Concentration of measure and isoperimetric inequalities in product spaces ⋮ Threshold Functions for H-factors ⋮ Combinatorial theorems in sparse random sets ⋮ Moderate deviations via cumulants ⋮ Upper tails via high moments and entropic stability ⋮ For most graphs H , most H -free graphs have a linear homogeneous set ⋮ Ramsey properties of random hypergraphs ⋮ On the benefits of adaptivity in property testing of dense graphs ⋮ Upper tails for arithmetic progressions in random subsets ⋮ On \(K^ 4\)-free subgraphs of random graphs ⋮ Bounding Ramsey numbers through large deviation inequalities ⋮ Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence ⋮ On the probability of nonexistence in binomial subsets ⋮ Spanners in randomly weighted graphs: Euclidean case ⋮ Optimal stopping for many connected components in a graph ⋮ Counting extensions revisited ⋮ Moderate deviations in cycle count ⋮ Lower tails via relative entropy ⋮ On the chromatic number in the stochastic block model ⋮ Random polynomial graphs for random Turán problems ⋮ On the concentration of the chromatic number of random graphs ⋮ On the Method of Typical Bounded Differences ⋮ On the Lower Tail Variational Problem for Random Graphs ⋮ Upper Tail Bounds for Cycles ⋮ On the cycle space of a random graph ⋮ A sharp threshold for a modified bootstrap percolation with recovery ⋮ Concentration for noncommutative polynomials in random matrices ⋮ \(H(n)\)-factors in random graphs ⋮ On limits of sparse random graphs ⋮ When does the K4‐free process stop? ⋮ On Sidon sets which are asymptotic bases ⋮ Online vertex-coloring games in random graphs ⋮ On the concentration of multivariate polynomials with small expectation ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence ⋮ The discrepancy of the lex-least de Bruijn sequence ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ CLT-related large deviation bounds based on Stein's method ⋮ Moment inequalities for functions of independent random variables ⋮ Geography of local configurations ⋮ Optimal explicit small-depth formulas for the coin problem ⋮ Ramsey properties of random discrete structures ⋮ The lower tail: Poisson approximation revisited ⋮ On the missing log in upper tail estimates ⋮ Representations of integers as the sum of k terms ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ A sharp threshold for bootstrap percolation in a random hypergraph ⋮ A counterexample to the DeMarco‐Kahn upper tail conjecture ⋮ An efficient container lemma ⋮ Generating Random Networks Without Short Cycles ⋮ Vertex Ramsey properties of randomly perturbed graphs ⋮ Small Submatroids in Random Matroids ⋮ Upper tail bounds for stars ⋮ An improved upper bound on the density of universal random graphs ⋮ The Janson inequalities for general up‐sets ⋮ When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence ⋮ Concentration and Moment Inequalities for Polynomials of Independent Random Variables ⋮ Maximum antichains in random subsets of a finite set ⋮ Random Van der Waerden theorem ⋮ Explicit two-source extractors and resilient functions ⋮ The Effect of Adding Randomly Weighted Edges ⋮ Lower large deviations for geometric functionals ⋮ A concentration result with application to subgraph count ⋮ On a refinement of Waring's problem ⋮ Monotone circuit lower bounds from robust sunflowers ⋮ The covering threshold of a directed acyclic graph by directed acyclic subgraphs ⋮ Upper bounds on probability thresholds for asymmetric Ramsey properties ⋮ Tight upper tail bounds for cliques
Cites Work
This page was built for publication: Poisson approximation for large deviations
