Thresholds for random distributions on graph sequences with applications to pebbling (Q1861202)

Let \(G= (G_1,\dots, G_n)\) be a sequence of graphs with \(G_n\) having \(n\) vertices with a random distribution of \(t(n)\) pebbles to its vertices. A function \(f\) is called threshold for \(G\) if \(\lim_{n\to\infty} P_G(n,t)= 1\) (with \(P_G(n,t)\) the proportion of all distributions of \(t\) pebbles onto \(G_n\) that are solvable) for \(\lim_{n\to\infty} {f(n)\over t(n)}= 0\), and \(\lim_{n\to\infty} P_G(n,t)= 0\) for \(\lim_{n\to\infty} {t(n)\over f(n)}= 0\). For a survey of definitions and known results see, i.e., \textit{A. Czygrinow}, \textit{N. Eaton}, \textit{G. Hurlbert} and \textit{P. M. Kayll} [Discrete Math. 247, 93-105 (2002; Zbl 1002.05037)]. Here the author proves that for all \(n\) and some \(p\in (0,1]\), if for some \(d\) with \(\text{diameter}(G_n)\leq d\) the maximum degree of \(G_n\subseteq \Omega(n^p)\), then the threshold of \(G\) for the solvability of \(G\) is in \(O(n^{1-0.5p})\).