University of Delaware
Discrete Mathematics Seminar

Lower bounding inertia sets of graphs
Steve Butler
Iowa State University
Tuesday, October 9, 2012
Ewing Hall 336 4.00 - 5.00 pm

ABSTRACT: We say a symmetric matrix is associated with a (labelled) graph if the off-diagonal nonzero entries correspond to edges in the graph. Given such a matrix its inertia is a pair $(p,q)$ where $p$ is the number of positive eigenvalues and $q$ is the number of negative eigenvalues. We will consider the problem of determining the inertia set of a graph which is the collection of all possible $(p,q)$ that are achievable by some matrix associated with a graph. To show a point $(p,q)$ is in the inertia set we only need to produce a matrix with the proper count of positive and negative eigenvalues. A more difficult problem is showing that a point $(p,q)$ is not in the inertia set. We will introduce a combinatorial game, which is a generalization of zero forcing, which allows us to show that some points are not in the inertia set and use this to give lower bounds for the inertia set.

This is joint work with Jason Grout and Tracy Hall.