0}$ is the unique
$T_i$ satisfying $\nu_{T_i}(M_i)=\frac{1}{2}$. (We will see in $\S 2$ and $\S 3$ that these
definitions are sensible.)
All graphs considered in this paper will be undirected and finite; also, we will
take the graph with no vertices to be disconnected.
For a given graph, $d(x,y)$ will mean the distance between vertices $x$ and $y$ in the graph, and,
in a given distribution on the graph, ${\cal Z}(x)$ will mean the number of pebbles on vertex $x$.
\section{Improved thresholds for multisets}
The main result of this section is the following, which can be used to improve estimates
like those used in the proof of \cite[Theorem 1.5]{bek2003}.
\begin{theorem} \label{thm1}
If $B$ is nonempty and finite, $T\in\omega$, $x\in \RR_{\ge 0}$,
$S\subseteq \omega^B$, and $\mu_{T+1}(S)\ge x/(T+1+x)$, then $\mu_T(\partial S)\ge x/(T+x)$.
(Here we take $0/0=0$ in the case where $T=x=0$.)
\end{theorem}
\begin{lemma}
\label{l1}
Given $x\in\RR_{\ge 0}$, $r\in\omega$ and positive integers $t$, $n$ and $d_0\ge d_1\ge \cdots \ge d_{r-1}$
with $t\ge r$ and (if $d_0$ exists) $n>d_0$,
let
$$
p:=\left.\sum_{0\le i 1)\\
&=& \PP(Y_\infty<(r+3)\lambda)+\PP(Y_\infty>2^L\lambda)\\
&\le& \PP(Y_\infty<(r+3)\lambda)+{\cal N} \exp -2^L\lambda,
\end{eqnarray*}
by Proposition \ref{thm13}.
\end{proof}
Suppose now as before that we place $Z_i$ pebbles on each vertex $i$,
where the $Z_i$'s are i.i.d.~geometric random variables with parameter
$p$, and let $M\le L$ be positive integers with $n\ge 2(L+M)+1$. If
$i\le L+M$, if $i$ is unpebblable, then $\sum_{0\le k\le L-1} Z_{i+k} 2^{-k}$
must be less than 1, and if $i\ge n-(L+M)+1$, if $i$ is unpebblable, then
$\sum_{0\le k\le L-1} Z_{i-k} 2^{-k}$ must be less than 1. In both
cases, then, since the $Z_i$'s are i.i.d.,
$$
\PP(\hbox{$i$ unpebblable})\le {\cal X}(L,p,1).
$$
If $L+M+1\le i \le n-(L+M)$, we observe that for $i$ to be unpebblable,
$Z_{i-M}$, \dots, $Z_{i+M}$ must all be less than $2^M$, and
$\sum_{0\le k\le L-1} Z_{i+M+1+k} 2^{-k}$ and
$\sum_{0\le k\le L-1} Z_{i-M-1-k} 2^{-k}$ must both be less than $2^{M+1}$.
In this case, then,
$$
\PP(\hbox{$i$ unpebblable})\le \PP(Z_1<2^M)^{2M+1} {\cal X}(L,p,2^{M+1})^2.
$$
Summing these probabilities, and using
$$
\PP(Z_1<2^M)= \sum_{0\le j<2^M} \PP(Z_1=j) \le 2^M p,
$$
we find that the probability that our random distribution is
unsolvable is no more than
\begin{eqnarray}
&\ &2(L+M){\cal X}(L,p,1)+(n-2(L+M))(2^M p)^{2M+1} {\cal X}(L,p,2^{M+1})^2\nonumber\\
&\le& 4L {\cal X}(L,p,1)+n (2^M p)^{2M+1} {\cal X}(L,p,2^{M+1})^2.\label{upper1}
\end{eqnarray}
We now let $n$ be large, set $L:=\floor{\log_2 n}$, $M:=\floor{(\log_2 n)^{1/16}}$,
$c'':=\sqrt{\log_2 n}$, and $p:=(c''-\sqrt{c''})/(e 2^{c''})$,
and estimate ${\cal X}(L,p,r)$ using (\ref{xest}).
To estimate the first term in (\ref{xest}), we use
Proposition \ref{thm12}, setting $y:=(r+3)\lambda(1-c''^{-1/2})/(ep)$.
In the case $r=1$ we have $1\le y\le 2$ for all sufficiently large $n$
so
\begin{equation}
\label{upper2}
{\cal X}(L,p,1)=\Theta(\frac{1}{\sqrt{c''n}} 2^{3 c''/2} \Delta'^{c''})+O(e^{-\sqrt{n}}),
\ \ \hbox{where} \ \Delta' := \frac{\lambda}{p} (1-\frac{1}{\sqrt{c''}}).
\end{equation}
In the case $r=2^{M+1}$, $\log_2 y = O(M)$ so
\begin{equation}
\label{upper3}
{\cal X}(L,p,2^{M+1})=\Theta(\frac{1}{\sqrt{c''n}} (2^{M+1}+3)^{c''} 2^{-c''/2}
2^{O(M^2)} \Delta'^{c''})
+O(e^{-\sqrt{n}}).
\end{equation}
Combining (\ref{upper1}), (\ref{upper2}), (\ref{upper3}), and
$\Delta'^{c''}=\Theta(e^{-\sqrt{c''}})$
shows that our random distribution is unsolvable with a probability that
approaches 0 at $n\to\infty$, so,
for this choice of $p$,
$$n(\frac{1}{p}-1)=e\frac{2^{\sqrt{\log_2 n}}}{\sqrt{\log_2 n}} n(1 + O(\frac{1}{(\log n)^{1/4}}))$$
is eventually above the geometric threshold of the sequence of families of solvable
distributions of the $n$-paths. Together with our previous lower bound
on the geometric threshold, this proves
\begin{theorem}
\label{penult} For all positive integers $n$, let the $n$-path
have $n$ vertices, 1, \dots, $n$, and edges between vertices $i$ and $i+1$
for $i=1$, \dots, $n-1$. Then the geometric threshold of the
sequence of families of solvable distributions of the $n$-paths is
$$
e\frac{2^{\sqrt{\log_2 n}}}{\sqrt{\log_2 n}} n(1 + O(\frac{1}{(\log n)^{1/4}})).$$
\end{theorem}
\begin{corollary}
The pebbling threshold of the sequence of $n$-paths is
$$
\Theta(\frac{2^{\sqrt{\log_2 n}}}{\sqrt{\log_2 n}} n).
$$
\end{corollary}
\begin{proof}
Use Theorem \ref{penult}, Theorem \ref{thm10} and
\cite[Theorem 1.3]{bek2003}.
\end{proof}
\section{One-ended path estimates}
\begin{lemma}
\label{lembp1}
Let $H$ be a graph which contains $L\ge 1$ vertices, $v_1$, \dots, $v_L$,
such that $d(v_1, v_i)=i-1$ for all $i=2$, \dots, $L$.
There exists some absolute constant $G_{-}\ge 3$ such that, if $g\ge G_{-}$
and an independent, geometrically distributed number of pebbles with parameter
$p:=(1+(2^{\sqrt{2 \log_2 g}}e/(2(1+(\log_2 g)^{-1/4})\sqrt{\log_2 g})))^{-1}$
is placed on each of $v_1$, \dots, $v_L$, then, with probability at least $2/g$,
$v_1$ is unpebblable, provided that, for the set of vertices $V$ of $H$ apart from
$v_1$, \dots, $v_L$,
\begin{equation}
\label{ehyp}
\sum_{x\in V} {\cal Z}(x) 2^{-d(x,v_1)}\le \frac{2e}{\sqrt{\log_2 g}}.
\end{equation}
\end{lemma}
\begin{proof} This is similar to the first half of the proof of Theorem \ref{penult}.
Let $Z_i$ be the number of pebbles on $v_i$, $i=1$, \dots, $L$.
The quantity $$Q:=\sum_{\hbox{\small $x$ a vertex of $H$}} {\cal Z}(x) 2^{-d(x,v_1)}$$ is at least 1 if there is a pebble
on $v_1$, and it cannot be increased by pebbling moves. It follows that $v_1$ will be unpebblable
provided that $Q<1$, which, by (\ref{ehyp}), will certainly be true if
$\sum_{1\le i\le L} Z_i 2^{-(i-1)} < 1-(2e/\sqrt{\log_2 g})$; so, if we let $Z_{L+1}$, $Z_{L+2}$, \dots be
additional independent geometric random variables with parameter $p$, $v_1$ will be be
unpebblable if $\sum_{i\ge 1} Z_i 2^{-(i-1)} < 1-(2e/\sqrt{\log_2 g})$.
As in \S 4, we can now set $Z_i:=\floor{W_i/\lambda}$, where $\lambda:=-\log(1-p)$
and $W_1$, $W_2$, {\dots} are i.i.d.~standard exponential random variables,
so it suffices for unpebblability that $$Y_{\infty} < \lambda(1-\frac{2e}{\sqrt{\log_2 g}}).$$
We can compute the probability $q$ of this event using Proposition \ref{thm12}, setting
$$c'':=\sqrt{2 \log_2 g},\ \
p':=(p^{-1}-1)^{-1}=\frac{2\sqrt{\log_2 g}}{e 2^{\sqrt{2 \log_2 g}}} (1 + (\log_2 g)^{-1/4}), $$
$$ y:=\frac{\sqrt{2}}{e}\Delta, \ \ \ \Delta:= \frac{\lambda}{p} \frac{1}{p' + 1} (1 + (\log_2 g)^{-1/4}) (1-\frac{2e}{\sqrt{\log_2 g}}).$$
For large $g$, $\Delta$ will be close to 1, so
after choosing $G_{-}$ appropriately, $y$ will be between $\frac 12$ and 1.
According then to the proposition, if we choose $G_{-}$ so as to make $c''$ sufficiently large,
there is some positive constant $C$ such that
$$q\ge C (ey)^{c''} 2^{-c''(c''+1)/2}/\sqrt{c''},$$
or such that $q\ge C \Delta^{c''} /(g\sqrt{c''})$.
Now $\Delta$ is a function only of $g$ and,
for large $g$,
$\log \Delta=2^{1/4} c''^{-1/2} + O(c''^{-1})$,
so choose $G_{-}$ large enough to ensure that
$\Delta^{c''}/\sqrt{c''} \ge 2/C$.
\end{proof}
\begin{lemma}
\label{lembp2}
Let $H$ be a graph which contains a path with $L\ge 1$ vertices, $v_1$, \dots, $v_L$.
Then there exists some absolute constant $G_{+}\ge 3$ such that, if $g\ge G_{+}$
and an independent, geometrically distributed number of pebbles with parameter
$p:=(1+(2^{\sqrt{2 \log_2 g}}e/(2(1-(\log_2 g)^{-1/4})\sqrt{\log_2 g})))^{-1}$
is placed on each of $v_1$, \dots, $v_L$, then
(A) if $L\ge 1.1\sqrt{2 \log_2 g}$, with probability at least $1-1/(4g)$,
$v_1$ is pebblable, and (B) if
$$
2.2\sqrt{2 \log_2 g}\le L\le \exp (2 \log_2 g)^{1/4},
$$
with probability at least $1-1/(4g)$,
all of $v_1$, \dots, $v_L$ are pebblable.
\end{lemma}
\begin{proof} This is similar to the second half of the proof of Theorem \ref{penult}.
We start with (A).
Let $Z_j$ be the number of pebbles on $v_j$, $j=1$, \dots, $L$.
Set $M:=\floor{(\log_2 g)^{1/16}}$. Since $L\ge 1.1\sqrt{2 \log_2 g}$, we can choose
$G_{+}$ large enough to ensure that $L\ge M+1$.
For $v_1$ to be unpebblable, we must have $Z_{j}<2^M$, $j=1$, \dots, $M+1$, and
$\sum_{0\le j\le L-M-2} Z_{M+2+j} 2^{-j} < 2^{M+1}$;
since the $Z_j$'s are independent and geometrically distributed with
parameter $p$,
this will have probability no more than
$(2^Mp)^{M+1} X$, where $X:={\cal X}(L-M-1,p,2^{M+1}),$
and by Lemma \ref{lemnew}, $X\le q+X'$, where
$$
q:= \PP(Y_\infty < (2^{M+1}+3)\lambda),\ \ \
X':= {\cal N}\exp - 2^{L-M-1} \lambda,
$$
$$
\lambda:=-\log(1-p).
$$
For an appropriate choice of $G_{+}$, we will have
$X'\le {\cal N} \exp -2^{0.09\sqrt{2 \log_2 g}},$
so by choosing $G_{+}$ large enough, we can force $X'$
to be less than $\frac 18$ when multiplied by $(2^Mp)^{M+1} g$.
To estimate $q$, use Proposition \ref{thm12}, setting
$$c'':=\sqrt{2 \log_2 g},\ \
p':=(p^{-1}-1)^{-1}=\frac{2\sqrt{\log_2 g}}{e 2^{\sqrt{2 \log_2 g}}} (1 - (\log_2 g)^{-1/4}), $$
$$ y:=2^{M+1}\frac{\sqrt{2}}{e}\Delta', \ \ \ \Delta':= \frac{\lambda}{p} \frac{1}{p' + 1} (1 - (\log_2 g)^{-1/4}) (1 + \frac{3}{2^{M+1}}).$$
For large $g$, $\Delta'$ will be close to 1, so $2^M\le y\le 2^{M+1}$, and
by the proposition, if we choose $G_{+}$ appropriately, we will have, for some constant $C>0$,
$$
q\le \frac{C}{g \sqrt{c''}} 2^{(M+1)c''} 2^{-(M-1)M/2} \Delta'^{c''},
$$
so
\begin{equation}
\label{e002}
(2^Mp)^{M+1}qg\le \frac{C}{\sqrt{c''}} (\frac{\sqrt{2}}{e} c'')^{M+1} 2^{M(M+3)/2} \Delta''^{M+1} \Delta'^{c''},
\end{equation}
where
$$
\Delta'':= \frac{1}{p'+1} (1-(\log_2 g)^{-1/4}).
$$
The logarithm of the right-hand side of (\ref{e002})
is $$-2^{1/4} c''^{1/2} + \frac{M(M+3)\log 2}{2} + O(M \log \log g),$$
so we can choose $G_{+}$ so that the right-hand side of (\ref{e002}) is less than $\frac 18$.
For (B), it will suffice to show that for each $i=1$, \dots, $L$, $v_i$
is unpebblable with probability no more than $1/(4gL)$. We fix some $i$ and let
$\delta:=1$ if $i\le L/2$, $\delta:=-1$ if $i>L/2$; we now try to move pebbles
onto $v_i$ from $v_{i+\delta}$, $v_{i+2\delta}$, \dots, $v_{i+\floor{L/2}\delta}$.
The proof is then similar to (A), except that $L-M-1$ is replaced by $\floor{L/2}-M$;
also, since we have assumed that $L\le e^{\sqrt{c''}}$, we must bound $e^{\sqrt{c''}} (2^M p)^{M+1} X$
instead of $(2^M p)^{M+1} X$.
\end{proof}
\section{The bouquet of paths}
For positive $n$ and $L$ and nonnegative $g$ such that $g(L-1)+1\le n$,
let the graph ${\cal B}_{n,g,L}$ be the graph which has $n$ vertices
and is made by taking $g$ paths with $L$ vertices each and a complete graph, choosing one vertex from
the complete graph and one end-vertex from each of the paths, and identifying these $g+1$ vertices into
a single vertex. Also,
for a graph $H$ with $n>0$ vertices, we define the {\em geometric pebbling threshold} of $H$ to be the
unique positive real $x$ for which, if an independent, geometrically distributed number of pebbles with
parameter $(1+x/n)^{-1}$ is placed on each of the vertices of $H$, the probability of the
distribution being solvable is $\frac 12$. (See Theorem \ref{thm6} for a proof that
this probability is strictly increasing with $x$ and that this definition is sensible.)
\begin{lemma}
\label{lemc}
For all $\delta>0$ there is some $m_0=m_0(\delta)$ such that,
if $\alpha\in\RR_{\ge 0}$,
$N$ is a sum of $m$ independent geometric random variables with parameter $(1+\alpha)^{-1}$,
and both $m$ and $\alpha m$ exceed $m_0$,
then $$\PP(|N-\alpha m|\le \delta \alpha m)\ge \frac 89.$$
\end{lemma}
\begin{proof} A geometric random variable with parameter $(1+\alpha)^{-1}$ has mean $\alpha$
and variance $\alpha(1+\alpha)$, so $N$ has mean $m\alpha$ and variance $m\alpha(1+\alpha)$.
Then, use Chebyshev's inequality. \end{proof}
\begin{proposition}
\label{tbouquet1}
There is some integer $G_0\ge 3$ such that if $g\ge G_0$,
$2gL\le n$, and
$$
\sqrt{2 \log_2 g} \le L - \log_2 n\le \exp (2\log_2 g)^{1/4},
$$
then the geometric pebbling threshold of ${\cal B}_{n,g,L}$ is
$\alpha n$, where
$$
\alpha:=\beta (1+\eta)^{-1}, \ \
\beta:=\frac{2^{\sqrt{2\log_2 g}} e}{2 \sqrt{\log_2 g}},\ \
\qquad |\eta|\le (\log_2 g)^{-1/4}.
$$
\end{proposition}
\begin{proof}
Let $H:={\cal B}_{n,g,L}$ and let
$\alpha:=\beta (1+\eta)^{-1}$, where $\eta$ is now arbitrary but satisfies
$|\eta|\le (\log_2 g)^{-1/4}$.
We have $L\ge 2$ and
by taking $G_0$ large enough we can ensure that $g\ge G_{-}$, $g\ge G_{+}$,
$\beta\ge 12$, $\alpha\ge 1$, $\log_2 n\ge 1.2 \sqrt{2 \log_2 g}$,
and $\exp (2 \log_2 g)^{1/4}\ge \ceil{2.2 \sqrt{2 \log_2 g}}.$
Suppose that an independent, geometrically distributed number of pebbles with parameter $(1+\alpha)^{-1}$
is placed on each vertex of $H$.
Set $\eta:=(\log_2 g)^{-1/4}$, consider one of the paths
$v_1$, \dots, $v_L$ which was identified to make $H$, and let its unidentified end-vertex be $v_1$.
Let the total number of pebbles on $H$ be $N$, assume that $N\le 2\alpha n$,
and let $V$ be the set of vertices of $H$ apart from $v_1$, \dots, $v_{L-1}$.
Then
$$
\sum_{x\in V} {\cal Z}(x) 2^{-d(x,v_1)}\le 2^{-(L-1)} \sum_{x\in V}{\cal Z}(x)\le N 2^{-(L-1)}
\le 2\alpha n 2^{-(L-1)}
$$
and
$$
2\alpha n 2^{-(L-1)} \le 4 \beta 2^{-\sqrt{2 \log_2 g}} =
\frac{2e}{\sqrt{\log_2 g}},
$$
so we can apply Lemma \ref{lembp1} to this path (with $L$ decreased by 1) to show that
$v_1$ is unpebblable with probability at least $2/g$.
After doing this
to each of the paths in $H$ in turn
we can conclude that the probability that the distribution is solvable is
no more than
\begin{equation}
\label{lbd}
\PP(N>2\alpha n) + (1-\frac{2}{g})^g\le \PP(N>2\alpha n)+e^{-2}.
\end{equation}
If we apply Lemma \ref{lemc} (with $m:=n$), then, since $\alpha\ge 1$ and $n\ge 2gL$,
we can choose $G_0$ so that $n$ and $\alpha n$ are forced to be so large that
$\PP(|N-\alpha n|\le\alpha n)\ge \frac 89$. Since $\frac 19+e^{-2}<\frac 12$,
(\ref{lbd}) then implies that the geometric pebbling threshold of ${\cal B}_{n,g,L}$ is at least
$\beta n(1+(\log_2 g)^{-1/4})^{-1}$.
Set $\eta:=-(\log_2 g)^{-1/4}$.
Let $N'$ be the total number of pebbles on the vertices of the complete graph which was identified to make $H$,
and let there be $m$ of these vertices. If $N'\ge \alpha m/2$, then,
since $m=n-g(L-1)\ge n-gL\ge n/2$,
$$N'\ge \frac{\alpha m}{2}\ge \frac{\alpha n}{4}\ge \frac{\beta n}{4}\ge 3 n.$$
By moving from vertices in the complete graph to any vertex $w$ of the complete graph, we can
then place at least $(3n-m)/2\ge (3n-n)/2=n$ pebbles on $w$.
Now, again consider one of the paths
$v_1$, \dots, $v_L$ which was identified to make $H$, letting its unidentified end-vertex be $v_1$.
By moving from vertices in the complete graph to $v_L$, we can place at least $n$ pebbles on $v_L$;
by moving along the path,
we can then place at least one pebble on $v_{L-j}$, for any $j=1$, \dots, $\ceil{\log_2 n}-1$.
If $L-\ceil{\log_2 n}\ge 2.2 \sqrt{2 \log_2 g}$, we can apply Lemma \ref{lembp2} to the path
with $L$ decreased by $\ceil{\log_2 n}$ and conclude that, with probability at least $1-1/(4g)$,
each of $v_1$, \dots, $v_{L-\ceil{\log_2 n}}$ are pebblable; otherwise, we can apply Lemma \ref{lembp2}
to the path with $L$ replaced by $\ceil{2.2 \sqrt{2 \log_2 g}}$ and conclude that, with probability at least
$1-1/(4g)$, each of $v_1$, \dots, $v_{\ceil{2.2 \sqrt{2 \log_2 g}}}$ are pebblable.
Applying this reasoning to each path, then, the probability that $H$ is solvable is at least
$$
\PP(N'\ge \frac{\alpha m}{2})-g\frac{1}{4g}=\PP(N'\ge \frac{\alpha m}{2})-\frac14.
$$
If we apply Lemma \ref{lemc}, since $m\ge n/2$, we can choose $G_0$ so that
$\PP(|N'-\alpha m|\le\frac 12 \alpha m)\ge \frac 89$. Since $\frac89 -\frac 14>\frac 12$, this
means that the geometric pebbling threshold of ${\cal B}_{n,g,L}$ is no more than
$\beta n(1-(\log_2 g)^{-1/4})^{-1}$, completing the proof.
\end{proof}
\begin{lemma}
\label{lemfxn}
If we define $\Phi: \RR_{\ge 0}\to \RR_{\ge 0}$ by $$\Phi(\alpha):=\frac{\alpha^2}{2\alpha+1},$$
then $\Phi$ is a strictly increasing bijection, and if $\alpha_2>\alpha_1>0$,
$$
(\frac{\alpha_2}{\alpha_1})^2\ge \frac{\Phi(\alpha_2)}{\Phi(\alpha_1)} \ge \frac{\alpha_2}{\alpha_1}.
$$
\end{lemma}
\begin{proof} Easy. \end{proof}
The following result is similar to \cite[Theorem 4]{czy2008}.
\begin{proposition}
\label{tbouquet2}
For any $0<\epsilon<1$, there is some
integer $L_0=L_0(\epsilon)\ge 2$ such that if $g\ge 1$, $2gL\le \epsilon n$,
and $L_0\le L\le (\log_2 n)-L_0$,
then the geometric pebbling threshold of ${\cal B}_{n,g,L}$ is
$\alpha n$, where
$$
\alpha:=\beta (1+\eta), \ \
\beta>0\hbox{\ and \ } \Phi(\beta)=\frac{2^{L-1}}{n},\ \
\qquad |\eta|\le \epsilon.
$$
\end{proposition}
\begin{proof}
Fix $\epsilon$, let $H:={\cal B}_{n,g,L}$ and
$\alpha:=\beta (1+\eta)$, where $\eta$ is arbitrary such that $|\eta|\le \epsilon$,
and suppose that an independent, geometrically
distributed number of pebbles with parameter $(1+\alpha)^{-1}$
is placed on each vertex of $H$.
Set $\eta:=-\epsilon$ and let $v_1$, \dots, $v_L$ be one of the paths which was identified to make $H$,
with $v_1$ being the unidentified end vertex. If $V$ is the set of vertices in $H$ other than
$v_1$, \dots, $v_L$, then
$$
{\cal Z}(v_1) +\frac{{\cal Z}(v_2)}{2} +
\cdots+\frac{{\cal Z}(v_L)}{2^{L-1}} + 2^{-(L-1)} \sum_{x\in V} \floor{\frac{{\cal Z}(x)}{2}}
$$
is at least 1 if there is a pebble on $v_1$, and it cannot be increased by pebbling moves.
Arguing as in Lemma \ref{lembp1}, then, the probability that $v_1$ is unpebblable conditioned on the distribution on $V$ is
at least
$$\PP(Y_\infty<\lambda(1-2^{-(L-1)} N)),$$
where
$$
N:= \sum_{x\in V} \floor{\frac{{\cal Z}(x)}{2}}, \ \ \ \lambda:=\log(1+\alpha^{-1}).
$$
Now, for each $x$, $\floor{{\cal Z}(x)/2}$ is independently
geometrically distributed
with parameter $1-(1-(1+\alpha)^{-1})^2=(1+\Phi(\alpha))^{-1}$.
Also, $n\ge 2gL\ge 2 L_0$, so if $m$ is the number of vertices in $V$, then
$$m\ge n-gL\ge n(1-\frac{\epsilon}{2})\ge L_0,$$
and, by Lemma \ref{lemfxn},
$$\Phi(\alpha) m
\le \Phi(\beta) (1-\epsilon) m=\frac{2^{L-1}m}{n}(1-\epsilon)\le 2^{L-1}(1-\epsilon)$$
and
$$\Phi(\alpha) m\ge \Phi(\beta)(1-\epsilon)^2 m = \frac{2^{L-1}m}{n}(1-\epsilon)^2\ge
2^{L_0-1}(1-\epsilon)^2(1-\frac{\epsilon}{2}).$$
Using Lemma \ref{lemc}, then, we can choose $L_0$ large enough so that
$N$ is no more than $2^{L-1} (1-(\epsilon/2))$
with probability at least $\frac 89$, so the probability that $v_1$ is unpebblable is at least
\begin{equation}
\label{e3}
\frac{8}{9} \PP(Y_\infty<\frac{\lambda\epsilon}{2}).
\end{equation}
Since $L\le (\log_2 n)-L_0$, we have
$\Phi(\beta)\le 2^{-L_0-1}$, so we may choose $L_0$ large enough so that $\beta$ is forced
to be small enough, and $\lambda\epsilon/2$ large enough, so that (\ref{e3}) is greater than $\frac 12$.
This proves that, for an appropriate choice of $L_0$, the geometric pebbling threshold of ${\cal B}_{n,g,L}$
is at least $\beta n (1-\epsilon)$.
Now, set $\eta:=\epsilon$, let $V'$ be the set of vertices on the complete graph which was identified to make $H$,
let $V'$ have size $m'$,
and let $N':=\sum_{x\in V'} \floor{{\cal Z}(x)/2}$. If $N'\ge 2^{L-1}$, we can place $2^{L-1}$ pebbles on the
identified vertex in $H$, and from there place at least one pebble on any vertex in $H$. We need then to show
that $\PP(N'\ge 2^{L-1})>\frac 12$. As before, for each $x$, $\floor{{\cal Z}(x)/2}$ is
independently geometrically distributed
with parameter $(1+\Phi(\alpha))^{-1}$, so since
$$m'\ge n-gL\ge n(1-\frac{\epsilon}{2})\ge L_0$$
and, by Lemma \ref{lemfxn},
\begin{eqnarray*}
\Phi(\alpha) m'\ge \Phi(\beta)(1+\epsilon)m'\ge 2^{L-1}(1+\epsilon)(1-\frac{\epsilon}{2})
&=& 2^{L-1}(1+ \frac{\epsilon(1-\epsilon)}{2})\\
&\ge& 2^{L_0-1},
\end{eqnarray*}
we can choose $L_0$ large enough so that, by Lemma \ref{lemc},
$\PP(N'\ge 2^{L-1})\ge \frac 89$. This proves that the geometric pebbling threshold
of ${\cal B}_{n,g,L}$ is no more than $\beta n (1+\epsilon)$, completing the proof.
\end{proof}
\section{The pebbling threshold spectrum}
\begin{lemma}
\label{distlem}
Let $H$ be a connected graph with $n\ge 2$ vertices, let $v$ be a vertex of $H$ such that
all vertices of $H$ are within distance $d\in\ZZ$ of $v$, $d\ge 2$, and let each vertex of $H$ have
a number of pebbles which is independently geometrically distributed with parameter $(1+\alpha)^{-1}$,
$\alpha\in\RR_{>0}$. Then
$v$ is unpebblable
with probability at most
$$
\left(
\frac{
e(2^{d-1}+\ceil{n^{1/d}-1}-1)
}{
\ceil{n^{1/d}-1}(1+\Phi(\alpha))
}
\right)^{\ceil{n^{1/d}-1}}.
$$
\end{lemma}
\begin{proof}
For $i=0$, 1, \dots, let $D_i$ be the number of vertices at distance $i$
from $v$ and let $D'_i:=\sum_{0\le j\le i} D_j$. Since $\log D'_0=0$ and
$\log D'_d=\log n$, there must be some $0\le i\le d-1$ for which
$(\log D'_{i+1})-(\log D'_i)\ge (\log n)/d$,
and then $D_{i+1}/D'_i = (D'_{i+1}/D'_i)-1\ge n^{1/d}-1$. Since $D'_i\ge D_i$,
$D_{i+1}/D_i$ is also at least $n^{1/d}-1$. This means that there must be some vertex $w$ at
distance $i$ from $v$ which has at least $\ceil{n^{1/d}-1}$ neighbors at distance $i+1$. Letting a set
of $\ceil{n^{1/d}-1}$ of these neighbors be $V$, $v$ will be pebblable if
\begin{equation}
\label{e301}
\sum_{x\in V} \floor{{\cal Z}(x)/2}\ge 2^{d-1},
\end{equation}
since if so we can move $2^{d-1}$ pebbles to
$w$ and then place a pebble on $v$. Each $\floor{{\cal Z}(x)/2}$ is independently
geometrically distributed with
parameter $p:=(1+\Phi(\alpha))^{-1}$, so the probability of (\ref{e301}) is the probability that,
if we flip a coin with success probability $p$, it takes at least $2^{d-1}+\ceil{n^{1/d}-1}$
flips to get $\ceil{n^{1/d}-1}$ successes. Another way of saying this is that there are no more than
$\ceil{n^{1/d}-1}-1$ successes in $2^{d-1}+\ceil{n^{1/d}-1}-1$ flips, so if (\ref{e301}) is false,
there must be at least $\ceil{n^{1/d}-1}$ successes in this number of flips. Set
$$p':=\ceil{n^{1/d}-1}/(2^{d-1}+\ceil{n^{1/d}-1}-1).$$
If $\ceil{n^{1/d}-1}(1+\Phi(\alpha))\le 2^{d-1}+\ceil{n^{1/d}-1}-1$,
then the claimed bound on the probability of unpebblability is 1 or greater
and there is nothing to prove. We can assume then that
$\ceil{n^{1/d}-1}(1+\Phi(\alpha))>2^{d-1}+\ceil{n^{1/d}-1}-1$;
now $p 0}}$ is any sequence of connected graphs such that the
number of vertices in $H_i$ is strictly increasing with $i$, then the sequence has
some pebbling threshold $t(n)$ which is $\Omega(\sqrt{n})$ and
$O(2^{\sqrt{2 \log_2 n}} n/\sqrt{\log_2 n})$, where $n$ is the number of vertices in a
graph in the sequence.
\end{corollary}
\begin{proof} By Theorems \ref{geoub} and \ref{geolb}, for sufficiently large $i$,
the geometric pebbling threshold $T_i$ of $H_i$ satisfies
$$\sqrt{n_i \log 2}\le T_i \le
\frac{2^{\sqrt{2\log_2 n_i}} e}{2\sqrt{\log_2 n_i}}(1 - (\log_2 n_i)^{-1/4})^{-1}n_i,$$ where
$n_i$ is the number of vertices in $H_i$. Define the function $t(n)$ by
$t(n_i):=T_i$ for each $i\in\ZZ_{>0}$ and $t(n):=n$ if $n$ is not equal to any $n_i$.
Now apply Theorem \ref{thm10} and
argue as in the proof of \cite[Theorem 1.3]{bek2003} to prove that $t(n)$ is a pebbling threshold
for $(H_i)_{i\in\ZZ_{>0}}$.
\end{proof}
\begin{theorem} \label{tbouquet3}
There is some constant $K>1$ such that,
if $n\ge 2$ is an integer and
$$\sqrt{n} \le t \le \frac{2^{\sqrt{2\log_2 n}}}{\sqrt{\log_2 n}}n,$$
then there is some connected graph $H$ with $n$ vertices whose geometric pebbling
threshold is between $t/K$ and $K t$.
\end{theorem}
\begin{proof}
Set $L_0:=L_0(\frac 12)$.
We are free to choose an arbitrary connected graph for $H$
for a finite number of values of $n$,
at the cost of worsening $K$, so we can assume that $n\ge 2^{2 L_0}$ and $n/(4\log_2 n)\ge G_0$.
Then, we will always choose $H$ to be some ${\cal B}_{n,g,L}$. Set $\beta:=t/n$
and $\beta_c:=2^{\sqrt{2 \log_2 G_0}}e/(2 \sqrt{\log_2 G_0})$.
\begin{enumerate}
\item If $\beta<\beta_c$, $g$ will always be 1. Let ${\hat L}:=1+\log_2(\Phi(\beta)n)$.
Then
we let $L$ be $L_0$ if ${\hat L}< L_0$, $\floor{\hat L}$ if $L_0\le {\hat L}\le (\log_2 n)-L_0$,
and $\floor{\log_2 n}-L_0$ if ${\hat L}> (\log_2 n)-L_0$.
\item If $\beta\ge \beta_c$, let $g$ be the maximal integer in $G_0$, $G_0+1$, \dots,
$\floor{n/(4\log_2 n)}$ with $2^{\sqrt{2\log_2 g}}e/(2 \sqrt{\log_2 g})\le \beta$.
Let $L$ be $\ceil{(\log_2 n)+\sqrt{2 \log_2 g}}$.
\end{enumerate}
It is straightforward to verify that, regardless of $t$ or $n$,
the geometric pebbling threshold $t'$ of $H$ can then be computed with Proposition \ref{tbouquet1} or
Proposition \ref{tbouquet2}, and that there is some absolute constant $K>1$ such that
$t'/t$ is always in $[1/K, K]$.
\end{proof}
\begin{corollary} If $t(n)$ is any positive function of integral $n\ge 1$ which is
$\Omega(\sqrt{n})$ and $O(2^{\sqrt{2\log_2 n}}n/\sqrt{\log_2 n})$, then
there is some sequence of
connected graphs $(H_n)_{n\in\ZZ_{>0}}$ with pebbling threshold $t(n)$
such that $H_n$ has $n$ vertices for each $n$.
\end{corollary}
\begin{proof} Let $t'(1):=1$ and for all integral $n\ge 2$, let
$$t'(n):=\min(\max(t(n),\sqrt{n}), 2^{\sqrt{2\log_2 n}}n/\sqrt{\log_2 n}).$$
Let $H_1$ be the 1-vertex graph, which has geometric pebbling threshold $t''(1):=1$,
and, for each $n\ge 2$, let $H_n$ be the
connected graph
given by Theorem \ref{tbouquet3} which has $n$ vertices and geometric pebbling threshold $t''(n)$ between
$t'(n)/K$ and $K t'(n)$. Then, apply Theorem \ref{thm10} and \cite[Theorem 1.3]{bek2003}
to prove that $t''(n)$ is a pebbling threshold of $(H_n)_{n\in\ZZ_{>0}}$.
It follows that $t'(n)$ and $t(n)$ are also pebbling thresholds for $(H_n)_{n\in\ZZ_{>0}}$.
\end{proof}
\begin{thebibliography}{9}
\bibitem{arr1989}
R. Arratia, L. Gordon,
Tutorial on large deviations for the binomial distribution,
{\em Bulletin of Mathematical Biology} {\bf 51} (1989), pp.~125--131.
\bibitem{bek2003}
Airat Bekmetjev, Graham Brightwell, Andrzej Czygrinow, and Glenn Hurlbert,
Thresholds for families of multisets, with an application to graph pebbling,
{\em Discrete Mathematics} {\bf 269} (2003), pp.~21--34.
\bibitem{buck1963}
J.~D.~Buckholtz,
Concerning an approximation of Copson,
{\em Proceedings of the American Mathematical Society} {\bf 14} (1963), pp.~564--568.
\bibitem{clem1984}
G.~F.~Clements,
A generalization of the Kruskal-Katona theorem,
{\em Journal of Combinatorial Theory, Series A} {\bf 37} (1984), pp.~91--97.
\bibitem{czy2002}
Andrzej Czygrinow, Nancy Eaton, Glenn Hurlbert, and P. Mark Kayll,
On pebbling threshold functions for graph sequences,
{\em Discrete Mathematics} {\bf 247} (2002),
pp.~93--105.
\bibitem{czy2008}
Andrzej Czygrinow and Glenn H. Hurlbert,
On the pebbling threshold of paths and the pebbling threshold spectrum,
{\em Discrete Mathematics} {\bf 308} (2008), pp.~3297--3307.
\bibitem{fel1971}
William Feller,
{\em An introduction to probability theory and its applications},
vol.~2, John Wiley \& Sons, 2nd ed., 1971.
\bibitem{hurl2014}
Glenn Hurlbert,
Graph pebbling, in {\em Handbook of graph theory}, edited by
Jonathan L. Gross, Jay Yellen and Ping Zhang, CRC Press, Boca Raton, 2nd ed., 2014.
\bibitem{whit1927}
E.~T.~Whittaker and G.~N.~Watson,
{\em A course of modern analysis},
Cambridge University Press, 4th ed., 1927.
\bibitem{wier2004}
Adam Wierman, Julia Salzman, Michael Jablonski, and Anant P. Godbole,
An improved upper bound for the pebbling threshold of the $n$-path,
{\em Discrete Mathematics} {\bf 275} (2004), pp.~367--373.
\end{thebibliography}
\end{document}