Equitable colorings extend Chernoff-Hoeffding bounds
Sriram V. Pemmaraju · Symposium on Discrete Algorithms · 2001
Chernoff-Hoeffding bounds are sharp tail probability bounds for sums of bounded independent random variables. Often we cannot avoid dependence among random variables involved in the sum. In some cases the theory of martingales has been used to obtain sharp bounds when there is a limited amount of dependence. This paper will present a simple but powerful new technique that uses the existence of small sized equitable graph colorings to prove sharp Chernoff-Hoeffding type concentration results for sums of random variables with dependence. This technique also allows us to focus on the dependency structure of the random variables and in cases where the dependency structure is a tree or an outerplanar graph, it allows us to derive bounds almost as sharp as those obtainable had the random variables been mutually independent. This technique connects seemingly unrelated topics: extremal graph theory and concentration inequalities. The technique also motivates several open questions in equitable graph colorings, positive answers for which will lead to surprisingly strong Chernoff-Hoeffding type bounds.