기초과학연구원 이산수학그룹
On September 26, 2023, Carl R. Yerger from Davidson College gave a talk at the Discrete Math Seminar on graph pebbling. The title of his talk was “Solving Problems in Graph Pebbling Using Optimization and Structural Techniques“. He will stay at the IBS Discrete Mathematics Group until October 12.
Graph pebbling is a combinatorial game played on an undirected graph with an initial configuration of pebbles. A pebbling move consists of removing two pebbles from one vertex and placing one pebbling on an adjacent vertex. The pebbling number of a graph is the smallest number of pebbles necessary such that, given any initial configuration of pebbles, at least one pebble can be moved to a specified target vertex.
In this talk, we will give a survey of several streams of research in pebbling, including describing a theoretical and computational framework that uses mixed-integer linear programming to obtain bounds for the pebbling numbers of graphs. We will also discuss improvements to this framework through the use of newly proved weight functions that strengthen the weight function technique of Hurlbert. Finally, we will discuss some open extremal problems in pebbling, specifically related to Class 0 graphs and describe how structural graph theoretic techniques such as discharging can be used to obtain results.
Collaborators on these projects include Dan Cranson, Dominic Flocco, Luke Postle, Jonad Pulaj, Chenxiao Xue, Marshall Yang, Daniel Zhou.