The infamous upper tail

DOI10.1002/rsa.10031zbMath0996.60023OpenAlexW1912401063WikidataQ60060516 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

Inequalities; stochastic orderings (60E15) Combinatorial probability (60C05)

Related Items

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

Cites Work