# Lower bound on P(Y > 3/2 E(Y)) where Y = # of triangles in graph

## 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!

-
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