Counterexamples to a monotonicity conjecture for the threshold pebbling number

Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move, in which two pebbles are removed from a vertex and one is placed on a neighbouring vertex. Given a graph G , the pebbling number π ( G ) is the least t such that every initial distribution of t pebbles at the vertices of G is solvable, that is for every target vertex v , there is some list of pebbling moves that ends with v having a pebble. Given a graph sequence ( G n ) , the pebbling threshold τ ( G n ) is a sequence ( a n ) such that t = a n is the smallest number of pebbles such that a random configuration of t pebbles on the vertices of G n is solvable with probability at least 1 / 2 , in the probabilistic model where each configuration of t pebbles on the vertices of G n is selected uniformly at random. This paper provides counterexamples to the following monotonicity conjecture stated by Hurlbert et al.: If ( G n ) and ( H n ) are graph sequences such that π ( G n ) ≤ π ( H n ) , then it holds that τ ( G n ) ∈ O ( τ ( H n ) ) .