In Summer 2015 I worked with Jonathan Gerhard and Noah Watson.
We spent 8 weeks working on critical groups of graphs. The
critical group is an important graph invariant that comes from the
Laplacian matrix of a graph. It can be understood in several
ways, for instance by looking at the Smith normal form of the Laplacian
matrix or by playing a certain "chip-firing" game on the vertices of
the graph. Another interesting graph invariant is the Smith
group, analogously derived from the adjacency matrix of the graph.
Jonathan and Noah worked very hard, and managed to completely
understand
both the critical group and Smith group of the square Rook's graph (and
also for the complement of this graph). See our paper here.
The analysis of the Rook's graph involved heavy use of the idea of
"chip-firing"; the students later moved on to study Biggs' so called
Dollar game in more generality. The elements of the critical
group of a graph can taken to be the critical configurations (stable
and recurrent). There is a natural partial order on these
critical configurations, and this poset was studied quite intensely by
Jonathan and Noah. There is a unique maximal element, and the
minimal critical configurations can be used to determine the entire
poset. Jonathan and Noah worked out the minimal critical
configurations for cycle graphs, complete graphs, and wheel graphs
(non-trivial).
Jonathan and Noah conjectured that, while the poset can change
depending on which vertex is designated to be the "government" or
"bank", the Whitney numbers would remain the same in all cases.
This turns out to be true, as we discovered on the last day of
our work together (see N. Biggs, "The Tutte polynomial as a growth
function." J. Algebraic Combin. 10 (1999), no. 2, 115-133). This
result is highly non-trivial. It was impressive to me to compare
results of the Biggs paper to those discovered by Jonathan and Noah.
Slides from their talk at the JMU
Summer Research Symposium. Noah also gave a talk at MathFest.
Back to my homepage