MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


This is exercise 1.7.1 of Tao/Vu's Additive Combinatorics, generally considered a graduate level math textbook.

My question is not "How do I solve this exercise?"

My question is "What is this exercise even looking for?"


We define a graph $G(n,p)$ as follows: for each pair of nodes, we independently decide, with probability $p=n^{-1+\epsilon}$, whether to assign edge between the pair of nodes.

Let $Y$ be the number of triangles in the graph.


Provide upper and lower bonds for $P(Y > 3/2 E(Y))$.

What I have so far (the upper bound):

Proving $P(Y > 3/2 E(Y)) < ... $ is fairly easy. This is a matter of calculating $E(Y)$, $E_1(Y)$, $E_2(Y)$, ... and applying theorem 1.37 (bounds on correlation of polynomials.) To avoid ruining the exercise, more will not be said about the upper bound.

What I'm stuck on (the lower bound):

I can't figure out what $...$ should look like in $P(Y > 3/2E(Y)) > ... $.

Everything I've seen in the book so far deals with proving statements of the form:

$P( | Y - E(Y) | > ... ) < ... $ -- it provides an upper bound on deviation from the mean.

Now, however, I want to prove a lower bound on deviation from the mean.


What types of inequalities should I be looking into?

Is there some trivial way to "flip" the bounds that I'm not seeing?


share|cite|improve this question
Having computed the upper bound, I would look for an ad hoc feature that would result in a somewhat comparable lower bound. How could you get a lot of triangles? By concentrating the edges on a smaller subset of the vertices for example – Anthony Quas Sep 5 '12 at 1:31
Are you suggesting something like: to get k^3 triangles, look for a k-clique? – user26147 Sep 5 '12 at 1:43
How tight do you want the bound to be? Have you looked at Chernoff bounds? – Michael Biro Sep 5 '12 at 1:59
it's easy to get $P(Y \geq 3/2 E(Y) > p^{n^\epsilon}$. How would you chernoff here? Chernoff would I've us $P(Y \geq 3/2 E(Y) < .. $ -- chernoff gives us < ... whereas we're after > ... – user26147 Sep 5 '12 at 2:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.