An improved upper bound for the pebbling threshold of the n-path

Abstract

Given a configuration of t indistinguishable pebbles on the n vertices of a graph G, we say that a vertex v can be reached if a pebble can be placed on it in a finite number of "moves". G is said to be pebbleable if all its vertices can be thus reached. Now given the n-path P_n how large (resp. small) must t be so as to be able to pebble the path almost surely (resp. almost never)? It was known that the threshold th(P_n) for pebbling the path satisfies n2^c√lgn ⩽ th(Pn_) ⩽ n2²√lgn, where lg = log₂ and c < 1/√2 is arbitrary. We improve the upper bound for the threshold function to th(P_n) ⩽ n2^d√lgn, where d > 1 is arbitrary.

Additional details