Concentration for self-bounding functions and an inequality of Talagrand

DOI10.1002/rsa.20145zbMath1120.60015OpenAlexW4245097098MaRDI QIDQ3419607

Bruce A. Reed, Colin J. H. McDiarmid

Publication date: 7 February 2007

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

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

zbMATH Keywords

independent random variablesconcentrationcertificateself-bounding functionTalagrand

Mathematics Subject Classification ID

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

Related Items (12)

An approximate version of the tree packing conjecture ⋮ Modified log-Sobolev inequalities and two-level concentration ⋮ Upper tails for arithmetic progressions in random subsets ⋮ On the concentration of the chromatic number of random graphs ⋮ The adjacent vertex distinguishing total chromatic number ⋮ U-Processes and Preference Learning ⋮ Concentration inequalities via zero bias couplings ⋮ A sharp threshold for a modified bootstrap percolation with recovery ⋮ Local tail bounds for functions of independent random variables ⋮ Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models ⋮ Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

Cites Work

• Unnamed Item
• Unnamed Item
• Graph colouring and the probabilistic method

This page was built for publication: Concentration for self-bounding functions and an inequality of Talagrand