Concentration of non‐Lipschitz functions and applications
From MaRDI portal
Publication:4537624
DOI10.1002/rsa.10032zbMath0999.60027OpenAlexW2037289762MaRDI QIDQ4537624
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.10032
random graphsconcentration inequalitiesadditive basesfinite projective planesstrong concentrationmatching and coloring
Random graphs (graph-theoretic aspects) (05C80) Large deviations (60F10) Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Additive bases, including sumsets (11B13)
Related Items
On Induced Paths, Holes, and Trees in Random Graphs ⋮ Sandwiching random graphs: universality between random graph models ⋮ Nonlinear large deviations ⋮ The missing log in large deviations for triangle counts ⋮ Upper tails via high moments and entropic stability ⋮ Logarithmic Sobolev inequalities for finite spin systems and applications ⋮ A sequential algorithm for generating random graphs ⋮ Concentration and consistency results for canonical and curved exponential-family models of random graphs ⋮ Upper tails for arithmetic progressions in random subsets ⋮ Variations and extensions of the Gaussian concentration inequality, Part I ⋮ Random points and lattice points in convex bodies ⋮ On the Method of Typical Bounded Differences ⋮ Anti-concentration for polynomials of independent random variables ⋮ Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order ⋮ When almost all sets are difference dominated ⋮ Avoiding small subgraphs in Achlioptas processes ⋮ On the missing log in upper tail estimates ⋮ Sub-Gaussian Tails for the Number of Triangles inG(n, p) ⋮ A sharp threshold for bootstrap percolation in a random hypergraph ⋮ Random constructions and density results ⋮ A counterexample to the DeMarco‐Kahn upper tail conjecture ⋮ Generating Random Networks Without Short Cycles ⋮ Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set ⋮ An introduction to large deviations for random graphs ⋮ Concentration and Moment Inequalities for Polynomials of Independent Random Variables ⋮ Freiman Homomorphisms of Random Subsets of ⋮ A concentration result with application to subgraph count ⋮ Concentration inequalities for nonlinear matroid intersection ⋮ Random matrices: universality of local spectral statistics of non-Hermitian matrices ⋮ Unnamed Item ⋮ Random Euclidean embeddings in finite-dimensional Lorentz spaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nearly-perfect hypergraph packing is in NC
- On the completeness of certain plane arcs. II
- Le geometrie di Galois
- New examples of complete k-arcs in PG(2,q)
- Asymptotic behavior of the chromatic index for hypergraphs
- On a packing and covering problem
- Near perfect coverings in graphs and hypergraphs
- When are small subgraphs of a random graph normally distributed?
- Nonsingular plane cubic curves over finite fields
- More-than-nearly-perfect packings and partial designs
- A dense infinite Sidon sequence
- A bound on the total chromatic number
- A bound on the strong chromatic index of a graph
- Nearly perfect matchings in regular simple hypergraphs
- On small complete arcs in a finite plane
- On a refinement of Waring's problem
- Asymptotically good list-colorings
- Concentration of measure and isoperimetric inequalities in product spaces
- List coloring of random and pseudo-random graphs
- Majorizing measures: The generic chaining
- Counting extensions
- On the Choice Number of Random Hypergraphs
- Random regular graphs of high degree
- Intersection Theorems for Systems of Sets
- THIN SUBBASES
- Graph colorings with local constraints -- a survey
- On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
- New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
- On the concentration of multivariate polynomials with small expectation
- The Ramsey number R(3, t) has order of magnitude t2/log t
- On Brooks' Theorem for Sparse Graphs
- The Choice Number of Dense Random Graphs
- On the Choice Number of Random Hypergraphs
- Representations of integers as the sum of k terms
- On a Problem of Sidon in Additive Number Theory, and on some Related Problems
- Concentration of multivariate polynomials and its applications
