An improved upper bound for the pebbling threshold of the n-path
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.
© 2003 Elsevier B.V. Under an Elsevier user license. Received 3 January 2002, Revised 17 September 2002, Accepted 7 October 2002, Available online 16 October 2003. The research of each of the four authors was supported by NSF Grant DMS-0049015, and was conducted at East Tennessee State University in the Summers of 2000 and 2001, when Salzman, Wierman and Jablonski were undergraduate students at Princeton University, Carnegie Mellon University and the University of Tennessee (Knoxville), respectively. We thank the anonymous referees for a most meticulous appraisal of the paper, and for several useful suggestions.