Notation

The notion that graphs with very few edges tend to have large pebbling number and graphs with very many edges tend to have small pebbling number can be made precise as follows. Let $\mathbf{G}_{n,p}$ be the random graph model in which each of the ${n \choose 2}$ possible edges of a random graph having $n$ vertices appears independently with probability $p$. For functions $f$ and $g$ on the natural numbers we write that $f \ll g$ (or $g \gg f$) when $f/g \rightarrow 0$ as $n \rightarrow \infty$. Let $o(G)=\{f | f \ll g \}$ and define $O(g)$ (resp., $\Omega(G)$) to be the set of functions $f$ for which there are constants $c,N$ such that $f(n) \leq cg(n)$ (resp., $f(n) \geq cg(n)$) whenever $n > N$. Finally, let $\Theta(g) = O(g) \cap \Omega(g)$.

Thresholds

Let $\mathbf{P}$ be a property of graphs and consider the probability ${\rm Pr}[\mathbf{P}]={\rm Pr}_p[\mathbf{P}]$ that the random graph $\mathbf{G}_{n,p}$ has $\mathbf{P}$. For large $p$ it may be that ${\rm Pr}[\mathbf{P}] \rightarrow 1$ as $n \rightarrow \infty$, and for small $p$ it may be that ${\rm Pr}[\mathbf{P}] \rightarrow 0$ as $n \rightarrow \infty$. More precisely, define the threshold of $\mathbf{P}$, $t(\mathbf{P})$, to be the set of functions $t$ for which $p \gg t$ implies that ${\rm Pr}[\mathbf{P}] \rightarrow 0$ as $n \rightarrow \infty$.

Class 0 Threshold

It is not clear that such thresholds exist for arbitrary $\mathbf{P}$. However, we observe that Class 0 is a monotone property (adding edges to a Class 0 graph maintains the property), and a theorem of Bollobas and Thomason [BoTh] states that $t(\mathbf{P})$ is nonempty for every monotone $\mathbf{P}$. It is well known [ErRe] that $t({\rm connected}) = \Theta(\log n/n)$, and since connectedness is required for Class 0, we see that $t({\rm Class}$ $0) \subset \Omega(\log n/n)$. In [CHH] it is noted that $t({\rm Class}$ $0) \subset O(1)$. In [CHKT] the Diameter-Connectivity Theorem was used to prove the following result.

Class 0 Threshold Theorem.   For all $d > 0$, $t({\rm Class}$ $0) \subset ((n\log n)^{1/d}/n)$.

References

B. Bollobas and A. Thomason Threshold Functions Combinatorica 7 (1987), 35--38

P. Erdos and A. Renyi On Random Graphs I Publ. Math. Debrecen 6 (1959), 290--297