In random graph what do we mean by almost every graph in G(n,p) has a property Q?

134 Views Asked by At

I am reading the book random graph by Bollobas. There it is said that almost every graph in G(n,p) has a property Q if P(Q)$\rightarrow$ 1 as n $\rightarrow \infty$. Now, I don't understand the meaning clearly. I mean how the condition P(Q)$\rightarrow$ 1 as n $\rightarrow \infty$ implies that almost every graph in G(n,p) has the property Q? Any suggestion or advice would be appreciated.

2

There are 2 best solutions below

0
On

I think of it as follows: Fix some very large $N$. As the probability tends to 1 it is very likely that any graph larger than $N$ has the desired property. On the other hand this large $N$ is very very far from being infinite, in other words there are only finitely many graphs (those smaller than $N$) for which the property is unlikely, while there are infinitely many (those larger than $N$), for which the property is very likely. Hence the class of graphs without the property consists of a very small percentage + finitely many exceptions, ie. almost all graphs have the property...

1
On

It is the definition, so there is nothing to be implied there. To be more explicit, we say that almost every graph in $G(n,p)$ has the property $Q$ if: $$\lim_{n\to\infty}\dfrac{\#\{\text{ Graphs in G(n,p) with property Q}\}}{\#\text{ G(n,p)}} = 1.$$