The infamous upper tail

DOI10.1002/rsa.10031zbMath0996.60023WikidataQ60060516 ScholiaQ60060516MaRDI QIDQ4537625

Publication date: 1 July 2002

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10031

zbMATH Keywords

random graphs; tail probabilities

Mathematics Subject Classification ID

60E15: Inequalities; stochastic orderings

60C05: Combinatorial probability

Related Items

Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms, Upper Tail Bounds for Cycles, Almost all Steiner triple systems are almost resolvable, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, A counterexample to the DeMarco‐Kahn upper tail conjecture, When does the K₄‐free process stop?, On the variational problem for upper tails in sparse random graphs, Concentration and Moment Inequalities for Polynomials of Independent Random Variables, Substructures in Latin squares, On the upper tail problem for random hypergraphs, Upper tail for homomorphism counts in constrained sparse random graphs, Counting extensions revisited, Moderate deviations in cycle count, Bounds on Ramsey games via alterations, The upper tail problem for induced 4‐cycles in sparse random graphs, Large deviations in random latin squares, Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime, Combinatorial theorems in sparse random sets, Moderate deviations via cumulants, Equitable and list equitable colorings of planar graphs without 4-cycles, Limit behaviors of random connected graphs driven by a Poisson process, Colorful triangle counting and a \textsc{MapReduce} implementation, Noncommutative martingale concentration inequalities, Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, A refinement of a result of Corrádi and Hajnal, A fast algorithm for equitable coloring, Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture, Equitable colorings of Kronecker products of graphs, Applications of Stein's method for concentration inequalities, Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs, Equitable colorings of Cartesian products of graphs, On equitable \(\Delta\)-coloring of graphs with low average degree, \(t\)-wise independence with local dependencies, Ore-type versions of Brooks' theorem, Concentration inequalities using the entropy method, Upper tails for arithmetic progressions in random subsets, Total equitable list coloring, Upper tails for subgraph counts in random graphs, A note on the equitable choosability of complete bipartite graphs, On list equitable total colorings of the generalized theta graph, Proportional 2-choosability with a bounded palette, Regular graphs with many triangles are structured, On the equitable choosability of the disjoint union of stars, Concentration inequalities on the multislice and for sampling without replacement, Equitable distinguishing chromatic number, Upper tails via high moments and entropic stability, A simple characterization of proportionally 2-choosable graphs, Concentration and consistency results for canonical and curved exponential-family models of random graphs, Localization in random geometric graphs with too many edges, Large deviations of subgraph counts for sparse Erdős-Rényi graphs, Maximizing the expected number of components in an online search of a graph, On the missing log in upper tail estimates, Bivariate fluctuations for the number of arithmetic progressions in random sets, Upper tail bounds for stars, Proportional choosability: a new list analogue of equitable coloring, Upper tails and independence polynomials in random graphs, Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs, An Ore-type theorem on equitable coloring, Nonlinear large deviations, Proportional choosability of complete bipartite graphs, The missing log in large deviations for triangle counts, Upper tails for triangles, Equitable coloring of random graphs, Sub-Gaussian Tails for the Number of Triangles inG(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, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝), A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring

Cites Work