McDiarmid, Colin 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. Cited in 2 ReviewsCited in 291 Documents MSC: 05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) Keywords:bounded martingale difference sequences; isoperimetric inequality; symmetric group; bounded difference method; martingale result; Azuma’s inequality Citations:Zbl 0673.00008; Zbl 0421.46015; Zbl 0606.46013; Zbl 0632.05024; Zbl 0127.106; Zbl 0178.211 PDFBibTeX XML