×

On the method of bounded differences. (English) Zbl 0712.05012

Surveys in combinatorics, Inv. Pap. 12th Br. Comb. Conf., Norwich/UK 1989, Lond. Math. Soc. Lect. Note Ser. 141, 148-188 (1989).
[For the entire collection see Zbl 0673.00008.]
In the beginning B. Maurey [C. R. Acad. Sci., Paris, Ser. A 289, 679-681 (1979; Zbl 0421.46015)] used an inequality for bounded martingale difference sequences to prove an isoperimetric inequality for the symmetric group \(S_ n\); this isoperimetric inequality was then used in investigating normed spaces [for related work, see V. Milman and G. Schechtman, Asymptotic theory of finite dimensional normed spaces (1986; Zbl 0606.46013)]. Then E. Schamir and J. Spencer [Combinatorica 7, 121-129 (1987; Zbl 0632.05024)] and W. T. Rhee and M. Talagrand [e.g. Math. Oper. Research 12, 177-181 (1987)] introduced this bounded difference method to a wide public of researchers in combinatorics and the mathematics of operational research and computer science, with dramatic impact. The purpose of this paper is to discuss the method and some of its applications. The underlying martingale result is due to W. Hoeffding [J. Am. Stat. Assoc. 58, 13-30 (1963; Zbl 0127.106)] and K. Azuma [TĂ´huku Math. J., II. Ser. 19, 357-367 (1967; Zbl 0178.211)] and has often been referred to as Azuma’s inequality.

MSC:

05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)