Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to make my way through Bollobás' book 'Models of Random Graphs', and unfortunately I've come entirely unstuck on one of his typical 2-line "and of course, this is entirely trivial"-style proofs. Despite spending many hours staring at it in vain, I have progressed precisely nowhere and was hoping someone could explain what's going on to me in as much detail as they can possibly summon the energy to give, so that I might finally understand it. The book's theorem (Theorem 2.2) is about switching between the $\mathcal{G}(n,p)$ and $\mathcal{G}(n,m)$ models of random graphs, and goes as follows:

Theorem: (i) Let Q be any graph property and suppose $pqN \to \infty$ (where we have $n$ vertices and $N={n \choose 2}$ possible edges). Then the following 2 assertions are equivalent (my comments in italics):

a) Almost every graph in $\mathcal{G}(n,p)$ has Q. (Here $\mathcal{G}(n,p)$ represents the probability space of random graphs on $n$ vertices with edges distributed randomly with probability $p$, i.e. edge-number binomially distributed $\operatorname{Bin} (N,p)$)

b) Given $x>0$ and $\epsilon > 0$, if $n$ is sufficiently large, there are $l \geq (1- \epsilon) 2x(pqN)^{1/2}$ integers $M_1,\ldots,\,M_l$ with $pN-x(pqN)^{1/2}<M_1<M_2<\ldots < M_l<pN + x(pqN)^{1/2}$ such that $P_{M_i}(Q)>1-\epsilon$ for every $1 \leq i \leq l$.

Proof: (i) By the De Moivre-Laplace theorem, for every fixed $x > 0$, $\mathbb{P}_p(|e(G)-pN|<x(pqN)^{-1/2})\sim \Phi(x) - \Phi(-x).$ Since also $\mathbb{P}_p(e(G)=M) = b(M;N,p) < (pqN)^{-1/2}$ for every M, the equivalence follows.

So, where to start. With regards to what he did say, I believe the statement of $\Phi$ which we get from the De Moivre-Laplace theorem; I'm happy with that. I can't however see why that probabilty stated is $< (pqN)^{1/2}$ - I can believe it's true, but I can't see the most obvious way to prove it.

With regards to the proof of (i) as a whole: I guess the intuitive notion of this part of the theorem is to be able to say 'This property holds iff it holds for lots of graphs close to the mean number of edges', i.e. we can focus on just the behaviour near the mean. So, we do the obvious thing and approximate by a normal distribution, since then we can say lots of nice things in terms of 'number of variances away from the mean'. Sadly though, I can't even figure out which direction he's trying to deal with in his proof, let alone fill in the gaps. We know roughly how likely we are to land within $x(Npq)^{1/2}$ of the mean, and we know an upper bound for the probability of getting $M$ edges: is that really sufficient to just say "result follows"?

So I think that's everything - sorry for the substantial length of this question, if there's anything you think I can remove for brevity then I'll be happy to. As above, I've spent hours and hours getting nowhere with what's meant to be a pretty straightforward theorem here, the material is new to me so maybe that's why, but what I'd be extremely grateful for is a very thorough (and fairly basic if possible) explanation of what's going on here, what I'm missing in the proof and why it is indeed true. Sincere thanks for your help in advance.

(Edit: removed second half of theorem due to misunderstanding)

share|improve this question
1  
That is one hard book to go through on your own! –  Aryabhata Feb 28 '12 at 8:41
    
Convex means that if graphs $A$ and $C$ have the property and $A\subset B \subset C$ then $B$ has the property. –  Colin McQuillan Feb 28 '12 at 8:46
    
"M is bigger than all our M_i" - no, you can choose negative $x$. (Sorry for not being more helpful, by the way!) –  Colin McQuillan Feb 28 '12 at 9:00
    
@Colin: Ah, apologies, I assumed convex was equivalent to monotone because I saw an exercise somewhere which was similar but with 'monotone', maybe that's where my misunderstanding for the second part lies, and indeed I also assumed x was positive. I'll remove that bit now and have a look at the second half of the proof again and see if it makes more sense. –  T. Hughes Feb 28 '12 at 9:01
    
@Aryabhata: Yes, I'm finding Bollobás isn't exactly one to underestimate his readers' mathematical abilities unfortunately! –  T. Hughes Feb 28 '12 at 9:02

1 Answer 1

(a)=>(b)

I think what we actually want here is a lower bound, say $b(N,M,p)>C(x)(pqN)^{-1/2}$ whenever $|M-nP|\leq x(pqN)^{1/2}$. Then for all $\delta>0$, if $P_p(Q)>1-\delta\epsilon$, then by a union bound, at most $\delta(pqN)^{1/2}/C$ values of $M$ satisfy $P_M(Q)\leq 1-\epsilon$.

(b)=>(a)

Let $\delta>0$. We will show $P_p(Q) > 1-\delta$ for sufficiently large $n$. Pick $x,\epsilon$, such that $(1-\epsilon)(\Phi(x)-\Phi(-x))>1-\delta/2$. For sufficiently large $n$, $P_p(Q)$ is at least $(1-\epsilon).P(|M-pN| \leq x(pqN)^{1/2})$, and $P(|M-pN|\leq x(pqN)^{1/2})$ is at least $\Phi(x)-\Phi(-x)-\delta/2$. So $P_p(Q)\geq (1-\epsilon)(\Phi(x)-\Phi(-x))>1-\delta$.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.