The critical group of a topological graph: an approach through delta-matroid theory

Lead Research Organisation: Royal Holloway University of London
Department Name: Mathematics

Abstract

Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.

Publications

10 25 50
 
Description The "critical group" or "sandpile group" is a finite Abelian group associated with a graph. The group is well-established in combinatorics and physics arising in, for example, the theory of the chip-firing game (known as the sandpile model in physics), parking functions, flow spaces and cut spaces. Although the critical group is defined as a purely graph theoretic notion, depending entirely on the abstract structure of a graph, many of the proofs in the area are rather topological in nature. We believe in order to achieve the full potential of the theory one must extend the definition of the critical group so that it no longer depends only on the adjacencies of the graph but instead takes into account an embedding.

We have developed a version of the critical group that takes into account the topological information contained in an embedding. The technical challenges in defining such a critical group were overcome by drawing on methods from delta-matroid theory to show that the collection of fundamental cycles and cocycles taken together may be extended to embedded graphs. Our theory for embedded graphs parallels that for abstract graphs. In particular, a key consequence of this new theory is the statement and proof of a version of Kirchhoff's Matrix-Tree Theorem for graphs in surfaces, where the number of spanning trees is replaced by the number of spanning quasi-trees in an embedded graph.

We have also been able to demonstrate the surprising finding that critical groups of embedded graphs do not depend solely on the underlying delta-matroid. A key feature of the critical group of an abstract graph is that it appears in multiple guises. Perhaps the most important are the definition through fundamental cycles and cocyles, and through the graph Laplacian and the related chip-firing game. Our initial approach developed the critical group of an embedded graph using a notion of fundamental cycles and cocycles. We are also able to develop it through a version of the Laplacian and thus through a related chip-firing game, thereby achieving our main goal. Our most significant technical achievement has been to verify that these two approaches to the critical group are guaranteed to lead to the same group.

By exploiting the properties of the matrix encoding fundamental cycles and cocycles, we have extended Berman's theorem relating the dimension of the bicycle space of a graph with its number of spanning to graphs embedded in an orientable surface. In a very general setting, we have established new links between the activities of quasi-trees and the transition polynomial, a polynomial of embedded graph closely related to the Bollobas-Riordan polynomial.

Papers based upon the findings are currently under peer review and are available on the ArXiv preprint server.
Exploitation Route We expect our current research findings to be taken forward by academic researchers in mathematics and in physics. In particular, our findings bring novel techniques into the theory of the chip-firing process from mathematics, or the sandpile model from physics. We anticipate our findings to find application to these models.

Our approach, using techniques from topological graph theory and delta-matroid theory, broadens the landscape of the critical group. We believe that this is likely to attract researchers from a broader range of backgrounds to the problem and take it in new directions crossing the boundaries between mathematical disciplines.
Sectors Digital/Communication/Information Technologies (including Software)

Other