Concentration for self-bounding functions and an inequality of Talagrand

DOI10.1002/rsa.20145zbMath1120.60015MaRDI 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 variables; concentration; certificate; self-bounding function; Talagrand

Mathematics Subject Classification ID

60E15: Inequalities; stochastic orderings

60C05: Combinatorial probability

Related Items

Modified log-Sobolev inequalities and two-level concentration, U-Processes and Preference Learning, An approximate version of the tree packing conjecture, The adjacent vertex distinguishing total chromatic number, A sharp threshold for a modified bootstrap percolation with recovery, Upper tails for arithmetic progressions in random subsets, 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, Concentration inequalities via zero bias couplings, Local tail bounds for functions of independent random variables, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

Cites Work

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