Equitable colorings extend Chernoff-Hoeffding bounds (Q2768401)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Equitable colorings extend Chernoff-Hoeffding bounds |
scientific article; zbMATH DE number 1699319
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Equitable colorings extend Chernoff-Hoeffding bounds |
scientific article; zbMATH DE number 1699319 |
Statements
5 July 2003
0 references
tail probabilities
0 references
sums of dependent variables
0 references
dependency graph
0 references
equitable chromatic number
0 references
Equitable colorings extend Chernoff-Hoeffding bounds (English)
0 references
Chernoff-Hoeffding bounds on tail probabilities of sums of mutually independent random variables are extended to sums of random variables with \(d\)-bounded dependence: Each variable is mutually independent of all but at most \(d\) other variables. The extension is proved by using a theorem of Hajnal-Szemerédi on upper bounds on the equitable chromatic number of a graph.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].
0 references
