Mathematical Sciences - Colloquium

Given a connected graph G, and a distribution of pebbles to the vertices of G, a pebbling step consists of removing 2 pebbles from a vertex v and placing one pebble on a neighbor of v.  The “lost pebble” could represent the cost of a computation.  For a particular root vertex r, the distribution is r-solvable if it is possible to place a pebble on r after a finite number of pebbling steps.  The distribution is solvable if it is r-solvable for every r.  The pebbling number f(G) is the least integer t so that every distribution of t pebbles onto the vertices of G is solvable.  Thus, starting with f(G) pebbles --- even if placed by the devil ---  guarantees solvability.  What if we place the pebbles at random and ask only for an almost sure guarantee? This introductory talk will explore these ideas and questions, revealing their connections with familiar mathematical ideas.
 
 

Colloquium home | Mathematical Sciences home | The University of Montana home