The critical group of a topological graph: an approach through delta-matroid theory
Lead Research Organisation:
Birkbeck, University of London
Department Name: Economics, Mathematics and Statistics
Abstract
The Sandpile Model is a widely studied model in physics and used in economics to model the consequences for a network of banks when one of them defaults. It has a simple intuitive description as follows.
Suppose we pile up grains of sand on a number of sites. At some point one pile becomes too large to stay upright, it topples, an avalanche occurs and sand gets transferred to adjacent sites. What happens next? Is the amount of sand transferred to the adjacent sites enough to make them topple? For how long does the process continue until all the sites become stable again and what configuration of grains of sand do we end up with?
What are the systems and patterns underlying this situation?
Now suppose we have a network (comprising, for example, computer servers or wind farms connected by cables). How many cables must fail before the network becomes disconnected? If each cable has a certain probability of failure, what is the probability that the network becomes disconnected?
What are the systems and patterns underlying this situation?
It turns out that the patterns underlying these two situations and many others are closely related to algebraic structures called 'Critical Groups'. Networks are modelled in mathematics by objects called 'graphs'. Each graph has a Critical Group associated with it. Critical Groups arise in many different ways and in many different applications of graphs in mathematics and physics; for example, through Chip-Firing or the Sandpile Model, Flow and Cut Spaces, counting spanning trees and even mathematical models of car parking.
In the situations we have described so far there is no geometry: all that matters is adjacency and which sites receive extra sand when another topples and which pairs of computers are linked by a cable. The way that the networks look is not important for the models we have described.
However, in many settings a graph comes equipped with geometric structure provided by an embedding of it in a surface (for example, a network may come drawn on a torus), and the geometric structure as well as the adjacencies determine the key properties of the graph. Examples include graphs that model the actions of enzymes or certain forms of DNA strands.
Some recent work has hinted at the possibility that there are deep links between the geometric structure of graphs and Critical Groups. When one moves away from graphs that can be drawn on a plane, some of the fundamental objects associated with the graph change profoundly: specifically one studies spanning quasi-trees rather than spanning trees. So far, the study of Critical Groups for graphs embedded on surfaces has not taken into account these changed fundamental structures. We aim to explore this space, realising the full potential of the geometric structure by developing a theory of the Critical Group that takes into account the embedding.
Suppose we pile up grains of sand on a number of sites. At some point one pile becomes too large to stay upright, it topples, an avalanche occurs and sand gets transferred to adjacent sites. What happens next? Is the amount of sand transferred to the adjacent sites enough to make them topple? For how long does the process continue until all the sites become stable again and what configuration of grains of sand do we end up with?
What are the systems and patterns underlying this situation?
Now suppose we have a network (comprising, for example, computer servers or wind farms connected by cables). How many cables must fail before the network becomes disconnected? If each cable has a certain probability of failure, what is the probability that the network becomes disconnected?
What are the systems and patterns underlying this situation?
It turns out that the patterns underlying these two situations and many others are closely related to algebraic structures called 'Critical Groups'. Networks are modelled in mathematics by objects called 'graphs'. Each graph has a Critical Group associated with it. Critical Groups arise in many different ways and in many different applications of graphs in mathematics and physics; for example, through Chip-Firing or the Sandpile Model, Flow and Cut Spaces, counting spanning trees and even mathematical models of car parking.
In the situations we have described so far there is no geometry: all that matters is adjacency and which sites receive extra sand when another topples and which pairs of computers are linked by a cable. The way that the networks look is not important for the models we have described.
However, in many settings a graph comes equipped with geometric structure provided by an embedding of it in a surface (for example, a network may come drawn on a torus), and the geometric structure as well as the adjacencies determine the key properties of the graph. Examples include graphs that model the actions of enzymes or certain forms of DNA strands.
Some recent work has hinted at the possibility that there are deep links between the geometric structure of graphs and Critical Groups. When one moves away from graphs that can be drawn on a plane, some of the fundamental objects associated with the graph change profoundly: specifically one studies spanning quasi-trees rather than spanning trees. So far, the study of Critical Groups for graphs embedded on surfaces has not taken into account these changed fundamental structures. We aim to explore this space, realising the full potential of the geometric structure by developing a theory of the Critical Group that takes into account the embedding.
People |
ORCID iD |
| Steven Noble (Principal Investigator) |
| 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 |