The infamous upper tail. (English) Zbl 0996.60023

Authors’ summary: Let \(\Gamma\) be a finite index set and \(k\geq 1\) a given integer. Let further \({\mathcal S}\subseteq [\Gamma]^{\leq k}\) be an arbitrary family of \(k\) element subsets of \(\Gamma\). Consider a (binomial) random subset \(\Gamma_{{\mathbf p}}\) of \(\Gamma\), where \({\mathbf p}= (p_i:i\in \Gamma)\), and a random variable \(X\) counting the elements of \({\mathcal S}\) that are contained in this random subset. We survey techniques of obtaining upper bounds on the upper tail probabilities \(\mathbb{P} (X\geq \lambda+ t)\) for \(t> 0\). Seven techniques, ranging from Azuma’s inequality to the purely combinatorial deletion method, are described, illustrated, and compared against each other for a couple of typical applications. As one application, we obtain essentially optimal bounds for the upper tails for the numbers of subgraphs isomorphic to \(K_4\) or \(C_4\) in a random graph \(G(n,p)\), for certain ranges of \(p\).


60E15 Inequalities; stochastic orderings
60C05 Combinatorial probability
Full Text: DOI


[1] Bennett, J Am Stat Assoc 57 pp 33– (1962)
[2] Boucheron, Random Struct Alg 16 pp 277– (2000) · Zbl 0954.60008
[3] Erd?s, Publ Math Inst Hung Acad Sci 5 pp 17– (1960)
[4] and Sharp thresholds for Ramsey properties, in preparation.
[5] and Ramsey games against one-armed bandit, in preparation.
[6] and Proof of a conjecture of Erd?s, Combinatorial theory and its applications, Vol. II, and (Editors), Colloq. Math. Soc. J?nos Bolyai 4, North-Holland, Amsterdam, 1970, pp. 601-623.
[7] Hoeffding, J Am Stat Assoc 58 pp 13– (1963)
[8] Janson, Random Struct Alg 1 pp 221– (1990) · Zbl 0747.05079
[9] and Random graphs, Wiley, New York, 2000.
[10] and The deletion method for upper tail estimates, Technical Report U.U.D.M. 2000: 28, Uppsala University, Uppsala, Sweden. · Zbl 1074.60006
[11] Kim, Combinatorica 20 pp 417– (2000) · Zbl 0969.60013
[12] On the method of bounded differences, Surveys in combinatorics (Proceedings, Norwich 1989), London Math. Soc. Lecture Note Ser. 141, Cambridge University Press, Cambridge, 1989, pp. 148-188.
[13] Concentration, Probabilistic methods for algorithmic discrete mathematics, and (Editors), Springer-Verlag, Berlin, 1998, pp. 195-248.
[14] R?dl, Random Struct Alg 5 pp 253– (1994) · Zbl 0790.05079
[15] R?dl, J Am Math Soc 8 pp 917– (1995)
[16] Spencer, J Combin Theor A 55 pp 247– (1990) · Zbl 0721.05033
[17] Talagrand, Inst Hautes ?tudes Sci Publ Math 81 pp 73– (1995) · Zbl 0864.60013
[18] Vu, Random Struct Alg 16(4) pp 344– (2000) · Zbl 0958.60028
[19] Vu, Random Struct Alg 17 pp 29– (2000) · Zbl 0953.05056
[20] Vu, Combin Probab Comput
[21] Vu, Random Struct Alg
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.