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!

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

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .