Using error-correcting codes to construct solvable pebbling distributions.

In pebbling problems, pebbles are placed on the vertices of a graph. A pebbling move consists of removing two pebbles from one vertex, throwing one away, and moving the other pebble to an adjacent vertex. We say a distribution D is solvable if starting from D , we can move a pebble to any vertex by a sequence of pebbling moves. The optimal pebbling number of a graph G is the smallest number of pebbles in a solvable distribution on G . It is known that every solvable distribution on the n -dimensional hypercube Q n contains at least ( 4 3 ) n pebbles. Fu, Huang, and Shiue, building on the work of Moews, used probabilistic methods to show that there are solvable distributions where the number of pebbles is in O ( ( 4 3 ) n n 3 2 ) , but hitherto, the number of pebbles in the best constructed distributions was in O ( 1.37 7 n ) . We use error-correcting codes to construct solvable distributions of pebbles on Q n in which the number of pebbles is in O ( 1.3 4 n ) . [ABSTRACT FROM AUTHOR]