PhD Dissertation Defense Presentation
Title: Kirchhoff Graphs
Abstract: Kirchhoff's laws are well-studied for electrical networks with voltage and current sources. Given a network, these requirements may be encoded by the circuit matrix and cutset matrix of the network graph. The columns of these matrices are indexed by the edges of the network graph, and their row spaces are orthogonal complements. For (chemical or electrochemical) reaction networks, one must naturally study the opposite problem, beginning with the stoichiometric matrix rather than the network graph. This leads to the following question: given such a matrix, what is a suitable graphic rendering of a network that properly visualizes the underlying chemical reactions? Although we cannot expect uniqueness, the goal is to prove existence of such a graph for any matrix. Specifically, we study Kirchhoff graphs, originally introduced by Fehribach. Mathematically, Kirchhoff graphs represent the orthocomplementarity of the row space and null space of integer-valued matrices. After introducing the definition of Kirchhoff graphs, we will survey Kirchhoff graphs in the context of several diverse branches of mathematics.
Beginning with combinatorial group theory, we consider Cayley graphs of the additive group of vector spaces. In particular, we resolve the existence problem of Kirchhoff graphs for matrices over finite fields. Moreover, given an integer-valued matrix A, we demonstrate that for large enough prime p, the matrix A (mod p) has a Kirchhoff graph. Moving to linear algebra, we derive a number of properties of Kirchhoff graphs based on a purely matrix-theoretic definition. Specifically, we show that most Kirchhoff graphs must be uniform--all edges occur the same number of times--and any matrix having a Kirchhoff graph must necessarily have a uniform example. Next we will turn to algebraic combinatorics, where we study equitable partitions, quotients, and graph automorphisms. In addition to classifying the square matrices that are the quotient matrix of an equitable partition, we demonstrate that many Kirchhoff graphs arise from equitable edge-partitions of directed graphs. Finally, we study matroids. First we will review Tutte's algorithm for determining when a binary matroid is graphic, and extend this method to show that every binary matroid is Kirchhoff. The underlying theme throughout each of these investigations is determining new ways to both recognize and construct Kirchhoff graphs.
Dr. Joseph D. Fehribach (Advisor, WPI)
Dr. Randy Paffenroth (Advisor, WPI)
Dr. Brigitte Servatius (Advisor, WPI)
Dr. Umberto Mosco (WPI)
Dr. Seth Chaiken (SUNY Albany)