On the Method of Typical Bounded Differences

DOI10.1017/S0963548315000103zbMath1372.60011arXiv1212.5796OpenAlexW3100754310MaRDI QIDQ5366890

Lutz Warnke

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.5796

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items

On Induced Paths, Holes, and Trees in Random Graphs, Concentration inequalities for non-causal random fields, Covering the edges of a random hypergraph by cliques, Upper tails for arithmetic progressions in random subsets, Packing nearly optimal Ramsey \(R(3,t)\) graphs, A note on long cycles in sparse random graphs, The impact of heterogeneity and geometry on the proof complexity of random satisfiability, Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry, On the efficacy of higher-order spectral clustering under weighted stochastic block models, A randomized construction of high girth regular graphs, Counting extensions revisited, The jump of the clique chromatic number of random graphs, Site percolation on pseudo‐random graphs, The number of \(n\)-queens configurations, Hamilton completion and the path cover number of sparse random graphs, A Stronger Bound for the Strong Chromatic Index, Large monochromatic components in 3‐edge‐colored Steiner triple systems, On the concentration of the chromatic number of random graphs, The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups, The \(Q_2\)-free process in the hypercube, Almost all Steiner triple systems are almost resolvable, Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝), Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process, Local convergence of random graph colorings, Cutoff for random walk on dynamical Erdős-Rényi graph, On the missing log in upper tail estimates, The condensation phase transition in random graph coloring, A sharp threshold for bootstrap percolation in a random hypergraph, Probabilistic properties of highly connected random geometric graphs, Large girth approximate Steiner triple systems, Short proofs of some extremal results III, Upper tail bounds for stars, Large triangle packings and Tuza’s conjecture in sparse random graphs, Loose cores and cycles in random hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Handbook of large-scale random networks
• The early evolution of the \(H\)-free process
• The triangle-free process
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The height of a random partial order: Concentration of measure
• On tail probabilities for martingales
• Nearly perfect matchings in regular simple hypergraphs
• A new look at independence
• Random triangle removal
• An old approach to the giant component problem
• Weighted sums of certain dependent random variables
• The deletion method for upper tail estimates
• Counting extensions
• The lower tail: Poisson approximation revisited
• Longest cycles in sparse random digraphs
• Probabilistic Analysis of Power Assignments
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• The evolution of subcritical Achlioptas processes
• Concentration Inequalities and Martingale Inequalities: A Survey
• Poisson approximation for large deviations
• A Large Deviation Inequality for Functions of Independent, Multi-Way Choices
• Divide and conquer martingales and the number of triangles in a random graph
• On the concentration of multivariate polynomials with small expectation
• Concentration of non‐Lipschitz functions and applications
• On the size of a random maximal graph
• Phase diagram for the constrained integer partitioning problem
• Random maximalH-free graphs
• Asymptotic packing via a branching process
• On Brooks' Theorem for Sparse Graphs
• On the size of a random sphere of influence graph
• The Janson inequalities for general up‐sets
• The Reverse H‐free Process for Strictly 2‐Balanced Graphs
• Probability Inequalities for Sums of Bounded Random Variables
• The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups
• When does the K₄‐free process stop?
• The C_ℓ‐free process
• A Best Possible Kolmogoroff-Type Inequality for Martingales and a Characteristic Property
• Concentration and Moment Inequalities for Polynomials of Independent Random Variables
• Concentration of Measure for the Analysis of Randomized Algorithms
• The chromatic number of random graphs
• Concentration of multivariate polynomials and its applications
• Degree sequences of random digraphs and bipartite graphs
• The condensation phase transition in random graph coloring