2007 Algebraic Graph Theory VIGRE Group

One usually associates to a graph G on n vertices two (n x n)-matrices, the adjacency matrix A and the Laplacian matrix L. Both A and L have a set of eigenvalues, and a Smith normal form over the integers. Much has been written on the relationships between the eigenvalues and the combinatorics/topology of the graph.

Equivalent to the Smith normal form of a graph is a finite abelian group that has 'appeared' independently in several different fields, and is known under several names, such as the component group, the critical group, or the sandpile group. This interesting group is the main motivation for studying the Smith normal form of the Laplacian. Its order is the number of spanning trees of the graph.

In our VIGRE group, each participant selects one or more problems to work on dealing with the Smith normal form of the Laplacian. Often, students work together trying to solve a problem as a team. Our weekly meetings are in the style of a seminar in which a participant presents to the group. He or she may present background material, interesting problems for solving, or proofs of original work.

Links:

http://gmichaelguy.com/vigregraphs/ - 2006 Maple files created by Michael Guy