\documentstyle{article}
% \newcommand{\Z}{\mbox{\sf Z\hspace{-5.5pt}Z}}
% \newcommand{\R}
% {\mbox{\sf R\makebox[0pt][r]{\rule{.25pt}{8pt}\rule{4.5pt}{0pt}}}}
\def\Z{\mbox{\bf Z}}
\def\R{\mbox{\bf R}}
\def\floor#1{\left\lfloor#1\right\rfloor}
\def\ceil#1{\left\lceil#1\right\rceil}
\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\D{\Delta}
\def\d{\delta}
\def\e{\epsilon}
\def\l{\lambda}
\def\G{\Gamma}
\def\S{\Sigma}
\def\ll{\Big(}
\def\rr{\Big)}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newenvironment{proof}{\par\noindent{\bf Proof. }}{\endbox}
\def\endbox{{\qquad\rule{0.5em}{2ex}\bigskip}}
\begin{document}
\title{Optimally pebbling hypercubes and powers}
\author{David Moews\\Center for Communications Research\\
4320 Westerra Court\\San Diego, CA 92121\\USA}
\maketitle
{\bf Abstract.} We point out that the optimal pebbling number of the
$n$-cube is $({4\over3})^{n+O(\log n)}$, and explain how to approximate the
optimal pebbling number of the $n$th cartesian power of any graph in a
similar way.
\medskip
{\bf Keywords.} optimal pebbling, powers of graphs.
\bigskip
Let $G$ be a graph. By a {\em distribution of pebbles} on $G$
we mean a function $a: V(G) \rightarrow \Z_{\ge 0}$; we usually write $a(v)$
as $a_v$, and call $a_v$ the {\em number of pebbles} on $v$. A
{\em pebbling move} on a distribution changes the distribution
by removing 2 pebbles from some vertex with at least 2 pebbles and
placing 1 additional pebble on some adjacent
vertex. Call a distribution $a$ {\em good} if, for all vertices $v$, there
is some sequence of pebbling moves starting from $a$ and ending with at least
one
pebble on $v$. The {\em pebbling number} $f(G)$ of a graph $G$ was
introduced by Chung \cite{chung}; it is the smallest $n$ such that, if
a distribution $a$ of pebbles on $G$ uses a total of $n$ pebbles, i.e.,
$\sum_v a_v=n$, then $a$ is good. Chung answered a question of Lagarias
and Saks by showing that the pebbling number $f(Q_n)$ of the $n$-cube
equals $2^n$, and used her methods to prove a number-theoretic
result of Lemke and Kleitman \cite{chung, lemke} (also, see \cite{clarke}
for a correction.)
Pachtor, Snevily and Voxman \cite{psv} introduced the dual concept of
the {\em optimal pebbling number}, $of(G)$, of a graph $G$; this is the
smallest $n$ such that there exists some good distribution $a$ of pebbles on
$G$ with a total of $n$ pebbles used. Such a distribution
is called an {\em optimal pebbling}. Pachtor et al.~also asked
what the optimal pebbling number of $Q_n$ is.
To help compute $of(Q_n)$, and later the optimal pebbling number
of the cartesian power of a graph,
we define continuous analogs of these concepts.
Define a {\em continuous distribution of pebbles} on $G$
to be a function $a:
V(G) \rightarrow \R_{\ge 0}$, and a {\em continuous pebbling move}
on a distribution $a$
to be a move that changes the distribution by, for some $\d\ge 0$
and adjacent vertices $v$ and $w$,
decreasing $a_v\ge \d$ by $\d$ and
adding $\d/2$ to $a_w$. We define good
continuous distributions just as we defined good distributions; a continuous
distribution $a$ on $G$ will evidently be good just when
$$
\sum_v a_v 2^{-d(v,w)}\ge 1
$$
for all vertices $w$ of $G$, where $d(v,w)$ is the distance between
vertices $v$ and $w$ of $G$. (We set $d(v,w)=\infty$ if $v$ and
$w$ are not connected in $G$, and we set $2^{-\infty}=0$.)
We can now define
the {\em continuous optimal pebbling number}, $ofc(G)$, and {\em
continuous optimal pebblings} in a way analogous
to $of(G)$ and optimal pebblings.
For graphs $G$ and $H$, let the {\em cartesian product}, $G
\times H$, of $G$ and $H$ have \hbox{$V(G\times H)=V(G)\times V(H)$} and
\begin{eqnarray*}
E(G\times H)&=&
\{\{(v,x),(v,y)\}|v\in V(G), \{x,y\}\in E(H)\}\\
&\cup&
\{\{(v,x),(w,x)\}|\{v,w\}\in E(G), x\in V(H)\}.
\end{eqnarray*}
Let the $n$th {\em cartesian power} of $G$, $G^{n}$, be the graph obtained by
taking the cartesian product of $n$ copies of $G$.
\begin{theorem} For all $G$ and $H$, $ofc(G\times H)=ofc(G)ofc(H)$.
\end{theorem}
\begin{proof}
($\le$): If $a$ is a continuous optimal pebbling of $G$, and $b$ of $H$, and
if we define $c$ by $c_{(v,x)}=a_v b_x$, then $c$ is a good continuous
distribution on $G\times H$ with a total of $ofc(G)ofc(H)$ pebbles.
($\ge$): Let $c$ be a good continuous distribution on $G\times H$.
Then for all $v$ and $x$,
\begin{eqnarray*}
1&\le& \sum_{w,y} c_{(w,y)} 2^{-d(v,w)-d(x,y)} \\
&=& \sum_w (\sum_y c_{(w,y)} 2^{-d(x,y)}) 2^{-d(v,w)}
\end{eqnarray*}
so for all $x$, putting $\sum_y c_{(w,y)} 2^{-d(x,y)}$ pebbles on $w$ is a good
continuous distribution on $G$, and therefore, for all $x$,
\begin{eqnarray*}
ofc(G)&\le&\sum_w \sum_y c_{(w,y)} 2^{-d(x,y)} \\
&=& \sum_y (\sum_w c_{(w,y)}) 2^{-d(x,y)}
\end{eqnarray*}
which implies that putting $\sum_w c_{(w,y)}/ofc(G)$ pebbles on $y$ is a good
continuous distribution on $H$; therefore,
$\sum_y \sum_w c_{(w,y)}/ofc(G)\ge ofc(H)$, so $\sum_{w,y} c_{(w,y)}$ is
at least $ofc(G) ofc(H)$, as desired.
\end{proof}
Since a good distribution is also a good continuous distribution,
$of(G)\ge ofc(G)$ for all $G$. Let $P_2$ be the path with two vertices; then
the $n$-cube, $Q_n$, is $P_2^n$. It is easy to see that $ofc(P_2)=
{4\over3}$ (a
continuous optimal pebbling has ${2\over3}$ of a pebble on each vertex) and
consequently $of(Q_n)\ge ofc(Q_n)=({4\over3})^n$. What is interesting is that
this is also an approximate upper bound.
Let the {\em covering radius} of a subset $W$ of $V(G)$ be the smallest
$d$ such that all vertices $v$ of $G$ are at distance no more than $d$ from
some member of $W$. In \cite{cohen} we find the following theorem:
\begin{theorem}
\label{aa}
For all $n$ and $0<\rho0}$. For
$\D=0$, \dots, $\D_0$, let $A_\D=b^n 2^{-\D} n^{\theta}$.
Define
a probability distribution on $V(G^n)$ by giving vertex
$(v_1,\ldots,v_n)$ probability $\prod_i \a_{v_i}$. For each
$\D=0$, \dots, $\D_0$, independently select, with replacement,
$\ceil{A_\D}$ vertices in $V(G^n)$ according
to this probability distribution; call the set of selected vertices $S_\D$.
For each $\D$, place $2^{\D+m^2 D}$ pebbles on each
vertex in $S_\D$. This gives us our distribution of pebbles; we use
no more than
\begin{eqnarray*}
\sum_{\D=0}^{\D_0} \ceil{A_\D} 2^{\D+m^2 D} &\le& (
(\D_0+1) b^n n^{\theta} + 2^{\D_0+1} - 1) 2^{m^2 D}\\
&=& b^{n+O(\log n)}
\end{eqnarray*}
pebbles in all.
The resultant distribution will be good if, for each $v$, there is some
$\D$ such that $v$ is within distance $\D + m^2 D$ of one of the vertices
in $S_\D$, and this will happen with positive
probability if, for each vertex $v$, the probability of such a $\D$ failing
to exist is less than $m^{-n}$. Fix a typical vertex $v=(v_1,\ldots,v_n)$,
and let $i_w$ be
the number of indices $i$ with $v_i=w$. For some other vertex
$v'=(v'_1,\ldots,v'_n)$, let $j_{wy}$ be the number of indices $i$
with $v_i=w$ and
$v'_i=y$. Consider the set $T$ of all vertices $v'$
such that, for some fixed
$l_{wy}$'s, $j_{wy}=l_{wy}$ for all $w$ and $y$.
Each member of this set has distance $\sum_{w,y} l_{wy} d(w,y)$
from $v$, and is selected with probability
$\prod_y \a_y^{\sum_w l_{wy}}$. The probability that no vertex in $T$
is in $S_\D$ is thus
$$
p = \ll 1-|T|\prod_y \a_y^{\sum_w l_{wy}}\rr^{\ceil{A_\D}},
$$
and
$$
|T|=\prod_w {i_w \choose l_{wx_1} \ldots l_{wx_m}}.
$$
Fix some nonnegative real $\l_{wy}$'s; let
$\l_{wy}=0$ if $\alpha_y=0$ or $d(w,y)=\infty$,
and let $\sum_y \l_{wy}=1$
for all $w$. For all $w$ and $y$, let $l_{wy}$ be $\l_{wy} i_w$,
rounded either to the next larger or next smaller integer
in such a way that the condition $\sum_y l_{wy}=i_w$ holds for all $w$.
We wish to find a bound for $p$ in terms of the $\l_{wy}$'s.
Since $l_{wy}$
and $\l_{wy} i_w$ are both in some interval $[r, r+1]$, $r\in \Z_{\ge 0}$,
it follows that
\hbox{$l_{wy}! \le \G(\l_{wy} i_w + 1) \max(l_{wy}, 2/\sqrt{\pi})$},
and it follows from Stirling's approximation that for $z\ge 0$,
$$\left({z\over e}\right)^z \le \G(z+1) \le
\left({z \over e}\right)^z (\sqrt{2 \pi z}+1);$$
hence,
\begin{eqnarray*}
|T|&=&\prod_w {i_w! \over l_{wx_1}! \cdots l_{wx_m}!}\\
&\ge& {1\over n^{m^2}} \prod_w{\G(i_w+1) \over \G(\l_{wx_1} i_w + 1)
\cdots \G(\l_{wx_m} i_w + 1)} \\
&\ge& {1\over n^{m^2} (\sqrt{2 \pi n} + 1)^{m^2}}
\prod_w {1 \over (\l_{wx_1}^{\l_{wx_1}} \cdots \l_{wx_m}^{\l_{wx_m}}
{{\vphantom{x^x}})}^{i_w}} \\
&=& {1\over n^{m^2} (\sqrt{2 \pi n} + 1)^{m^2}}
\prod_{\l_{wy}\ne 0} {1\over \l_{wy}^{\l_{wy} i_w}}.
\end{eqnarray*}
Also,
we will have $\sum_w l_{wy}=\sum_w \l_{wy} i_w = 0$ if $\a_y=0$; for other $y$,
\hfill\break
\hbox{$l_{wy}\le \ceil{\l_{wy} i_w} \le \l_{wy} i_w + 1$},
so $\sum_w l_{wy}\le m + \sum_w \l_{wy} i_w$; therefore,
$$
\prod_y \a_y^{\sum_w l_{wy}} \ge
\prod_{\a_y\ne 0} \a_y^m \prod_{\a_y\ne 0} \a_y^{\sum_w \l_{wy} i_w},$$
and then
\begin{equation}
\label{e1}
p \le \ll
1-{1\over n^{m^2} (\sqrt{2 \pi n} + 1)^{m^2}}
\prod_{\a_y\ne 0} \a_y^m
\prod_{\l_{wy}\ne 0} \ll {\a_y\over \l_{wy}}\rr^{\l_{wy} i_w}\rr^{A_\D}.
\end{equation}
To satisfy our distance constraint, we wish to have
\begin{equation}
\label{e2}
\sum_{w,y} l_{wy} d(w,y) \le \D + m^2 D.
\end{equation}
If $d(w,y)=\infty$, $l_{wy}=0$. Otherwise, $l_{wy}\le \l_{wy} i_w+1$,
and $d(w,y)\le D$, so
$$
\sum_{w,y} l_{wy} d(w,y) \le m^2 D + \sum_w i_w \sum_y \l_{wy} d(w,y),
$$
and to satisfy (\ref{e2}) it will do to have
\begin{equation}
\label{e4}
\sum_w i_w \sum_y \l_{wy} d(w,y) \le \D.
\end{equation}
Now set
\begin{equation}
\label{e3}
\l_{wy}={\a_y 2^{-d(w,y)}\over \sum_z \a_z 2^{-d(w,z)}}.
\end{equation}
Since $a$ is a continuous optimal pebbling on $G$, for all $w$ there must
exist some $y$ in the same connected component as $w$ with $a_y\ne 0$.
Hence the denominator in (\ref{e3}) is always nonzero. It is clear that
$\sum_y \l_{wy}=1$ for all $w$, and that $\l_{wy}=0$ if $\a_y=0$ or
$d(w,y)=\infty$. It follows from Lemma \ref{lem}
that with our choice of $\l_{wy}$'s,
the left-hand side of
(\ref{e4}) is no bigger than $n\log_2 b\le \D_0$, so we can let
$\D$ be the ceiling of the left-hand side of (\ref{e4}).
Then
\begin{eqnarray*}
\prod_{\l_{wy}\ne 0} \ll {\a_y\over \l_{wy}}\rr^{\l_{wy} i_w} &=&
\prod_{\l_{wy}\ne 0} \ll
{\sum_z \a_z 2^{-d(w,z)} \over 2^{-d(w,y)}}
\rr^{\l_{wy} i_w} \\
&\ge& 2^{\D-1} \prod_w \ll \sum_z \a_z 2^{-d(w,z)} \rr^{i_w} \\
&\ge& 2^{\D-1} b^{-n},
\end{eqnarray*}
since $a$ is a continuous optimal pebbling of $G$. Substituting this into
(\ref{e1}), we then find that
$$
p \le \ll
1-{1\over n^{m^2} (\sqrt{2 \pi n} + 1)^{m^2}}
2^{\D-1} b^{-n} \prod_{\a_y\ne 0} \a_y^m \rr^{A_\D},
$$
or, using $1-x\le e^{-x}$,
$$
p \le \exp \ll
-{1\over n^{m^2} (\sqrt{2 \pi n} + 1)^{m^2}}
2^{\D-1} b^{-n} A_\D \prod_{\a_y\ne 0} \a_y^m \rr.
$$
We want to have $\log p < -n \log m$ for large $n$. Recalling that
$A_\D 2^{\D} = b^n n^{\theta}$, we see that this will be true if
$\theta>{3\over 2}m^2+1$, so we are done.
\end{proof}
\begin{thebibliography}{9}
\bibitem{chung} F.~R.~K.~Chung, Pebbling in hypercubes,
SIAM J.\ Disc.\ Math. 2 (1989) 467--472.
\bibitem{clarke} T.~A.~Clarke, R.~A.~Hochberg, and G.~H.~Hurlbert,
Pebbling in diameter two graphs and products of paths,
J.\ Graph Theory 25 (1997) 119--128.
\bibitem{cohen} G.~D.~Cohen, A nonconstructive upper bound on
covering radius, IEEE Trans.\ Inf.\ Theory IT-29 (1983) 352--353.
\bibitem{lemke} P.~Lemke and D.~Kleitman, An addition theorem on
the integers modulo n, J. Number Theory 31 (1989) 335--345.
\bibitem{psv} L.~Pachtor, H.~S.~Snevily, and B.~Voxman, On pebbling
graphs, Congressus Numerantium 107 (1995) 65--80.
\end{thebibliography}
\end{document}