Graham’s pebbling conjecture

Imagine pebbles placed on the vertices of a network. To move one pebble along an edge, spend two at its starting vertex: one arrives and one disappears. Enough starting pebbles must guarantee delivery to any chosen destination, even when their placement is inconvenient. When two networks form a coordinate grid, does multiplying their separate guaranteed supplies always suffice for the grid?[1] [2]

Pebbles move through a network at a two-for-one cost: carrying one across two consecutive edges can require four at the starting vertex. When network states have two coordinates and a move changes just one, can the two separate worst-placement delivery guarantees always be multiplied? For a configuration $C:V(G)\to\mathbb{Z}_{\geq0}$, a legal move subtracts two at a vertex and adds one at a neighbor. The pebbling number $\pi(G)$ is the least total that solves every target from every configuration of that size. The Cartesian product has vertices $(g,h)$, adjacent when exactly one coordinate changes along a factor edge. Graham’s conjecture is $\pi(G\square H)\leq\pi(G)\pi(H)$ for all finite connected factor graphs.[1] [2]

The proposed supply works for many kinds of combined networks. For arbitrary pairs, a general theorem guarantees delivery with twice that proposed supply. Removing the extra factor remains open: the guarantee must survive every starting placement, including many small piles that cannot yet make a move.[1]

The 2018 product paper supplies a universal bound π(G □ H) ≤ 2π(G)π(H), together with stronger bounds using factor size and special structure. These estimates do not imply the factor-one conjecture. Generalized t-pebbling asks for several pebbles at the target and leads to related product conjectures; the 2025 results for specific total graphs do not resolve the ordinary one-pebble inequality for all G and H.[1] [3]

A guarantee for a small network can become a building block for a much larger one with several coordinates. An extra safety factor at each combination can accumulate as more coordinates are added. The conjecture would let the separate guarantees compose without that extra loss, even though moving pebbles already consumes resources.[1] [2]

The distribution of a supply matters as well as its total: small separated piles may be unusable, while concentrating them loses pebbles along paths. Cartesian products test whether that distribution-sensitive guarantee composes across independent coordinates. If the conjecture holds, repeating a factor $G$ in $k$ coordinates gives $\pi(G^{\square k})\leq\pi(G)^k$. An extra factor at each product step would instead accumulate with the number of coordinates. The conjecture therefore controls the growth of guaranteed delivery costs in whole families of larger state spaces, not just one two-factor instance.[1]