Seminars and Colloquia by Series

Pebbling graphs of diameter three

Series
Graph Theory Seminar
Time
Thursday, September 18, 2008 - 12:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Luke Postle – School of Mathematics, Georgia Tech
Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex, and the placement of one of these on an adjacent vertex. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves so that at least one pebble can be placed on vertex v. The pebbling number of a graph G is the smallest integer k such that G is pebbleable given any configuration of k pebbles on G. We improve on the bound of Bukh by showing that the pebbling number of a graph of diameter 3 on n vertices is at most the floor of 3n/2 + 2, and this bound is best possible. We give an alternative proof that the pebbling number of a graph of diameter 2 on n vertices is at most n + 1. This is joint work with Noah Streib and Carl Yerger.

Markov bases for series-parallel graphs

Series
Graph Theory Seminar
Time
Thursday, August 28, 2008 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Sergey Norin – Mathematics, Princeton University
The problem of generating random integral tables from the set of all nonnegative integral tables with fixed marginals is of importance in statistics. The Diaconis-Sturmfels algorithm for this problem performs a random walk on the set of such tables. The moves in the walk are referred to as Markov bases and correspond to generators of a certain toric ideal. When only one and two-way marginals are considered, one can naturally associate a graph to the model. In this talk, I will present a characterization of all graphs for which the corresponding toric ideal can be generated in degree four, answering a question of Develin and Sullivant. I will also discuss some related open questions and demonstrate applications of the Four Color theorem and results on clean triangulations of surfaces, providing partial answers to these questions. Based on joint work with Daniel Kral and Ondrej Pangrac.

Pages