Off on a Tangent 17.5 (part b)

Graph Pebbling colloquium this week!

  • Title: Graph Pebbling
  • Speaker: Dr. Airat Bekmetjev, Hope College
  • When/Where: 11 am on Thur, Nov 29 in VanderWerf 104
AbstractPebbling is a process defined on a connected graph. Pebbles are configured on vertices of the graph and are moved along the edges. A pebbling move consists of taking two pebbles from a vertex, placing one on an adjacent vertex, and discarding the other. The objective of pebbling is to put at least one pebble on a designated vertex, called the root. A configuration is called solvable if any vertex can get at least one pebble through a sequence of moves. Pebbling can be used in transportation and communication networks and optimal resource allocation.
Some interesting questions arise: How many pebbles are enough to guarantee that any configuration is solvable ? What are the optimal ways to move pebbles? Can we construct an algorithm that determines if a given pebbling configuration is solvable? In this colloquium we will try to answer some of these questions along with the discussion about the existence of the threshold phenomenon in pebbling. We will see how the solvability of a random pebbling configuration dramatically changes after the number of pebbles reaches a certain value called the pebbling threshold. We will also discuss new results in pebbling related to the two-pebbling property and Graham’s Conjecture on the product of graphs.

Leave a Reply

Your email address will not be published. Required fields are marked *