2
$\begingroup$

Context

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?"

Definition

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.

Problem:

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.

Question:

What types of inequalities should I be looking into?

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

Thanks!

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Sep 5, 2012 at 1:31
  • $\begingroup$ Are you suggesting something like: to get k^3 triangles, look for a k-clique? $\endgroup$
    – user26147
    Sep 5, 2012 at 1:43
  • $\begingroup$ How tight do you want the bound to be? Have you looked at Chernoff bounds? $\endgroup$ Sep 5, 2012 at 1:59
  • $\begingroup$ 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 > ... $\endgroup$
    – user26147
    Sep 5, 2012 at 2:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.