- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Seminar

For an undirected graph G=(V,E) with V={1,...,n} let S(G) be the set of all symmetric n x n matrices A=[a_i,j] with a_i,j non-zero for distinct i,j if and only if ij is an edge. The inertia of a symmetric matrix is the triple (p_+,p_-,p_0), where p_+, p_-,p_0 are the number of positive, negative, and null eigenvalues respectively. The inverse inertia problem asks which inertias can be obtained by matrices in S(G). This problem has been studied intensively by Barrett, Hall, and Loewy. In this talk I will present new results on the inverse inertia problem, among them a Colin de Verdiere type invariant for the inertia set (this is the set of all possible inertias) of a graph, a formula for the inertia set of graphs with a 2-separation, and a formula for the inertia set of the join of a collection of graphs.
The Colin de Verdiere type invariant for the inertia set is joint work with F. Barioli, S.M. Fallat, H.T. Hall, D. Hershkowitz, L. Hogben, and B. Shader, and the formula for the inertia set of the join of a collection of graphs is joint work with W. Barrett and H.T. Hall.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.