Interlude: The Infamous Upper Tail
9.1 Motivation: Non-Lipschitz Functions
Consider the random graph G(n, p) with p = p(n) = n−3/4. Let X be the number of triangles in this graph. We have . The random variable X is a function of the independent variables corresponding to whether a particular edge is present or not. Changing any of these variables could change the value of X by as much as n − 2 in the worst case. Applying the method of bounded differences with these Lipschitz coefficients is useless to obtain a non-trivial concentration result ...