The Mathematics of Chip-Firing is a textbook in mathematics on chip-firing games and abelian sandpile models. It was written by Caroline Klivans, and published in 2018 by the CRC Press.
The Mathematics of Chip-Firing is a textbook in mathematics on chip-firing games and abelian sandpile models. It was written by Caroline Klivans, and published in 2018 by the CRC Press.
A chip-firing game, in its most basic form, is a process on an undirected graph, with each vertex of the graph containing some number of chips. At each step, a vertex with more chips than incident edges is selected, and one of its chips is sent to each of its neighbors. If a single vertex is designated as a "black hole", meaning that chips sent to it vanish, then the result of the process is the same no matter what order the other vertices are selected. The stable states of this process are the ones in which no vertex has enough chips to be selected; two stable states can be added by combining their chips and then stabilizing the result. A subset of these states, the so-called critical states, form an abelian group under this addition operation. The abelian sandpile model applies this model to large grid graphs, with the black hole connected to the boundary vertices of the grid; in this formulation, with all eligible vertices selected simultaneously, it can also be interpreted as a cellular automaton. The identity element of the sandpile group often has an unusual fractal structure. [1]
The book covers these topics, and is divided into two parts. The first of these parts covers the basic theory outlined above, formulating chip-firing in terms of algebraic graph theory and the Laplacian matrix of the given graph. It describes an equivalence between states of the sandpile group and the spanning trees of the graph, and the group action on spanning trees, as well as similar connections to other combinatorial structures, and applications of these connections in algebraic combinatorics. And it studies chip-firing games on other classes of graphs than grids, including random graphs. [1]
The second part of the book has four chapters devoted to more advanced topics in chip-firing. The first of these generalizes chip-firing from Laplacian matrices of graphs to M-matrices, connecting this generalization to root systems and representation theory. The second considers chip-firing on abstract simplicial complexes instead of graphs. The third uses chip-firing to study graph-theoretic analogues of divisor theory and the Riemann–Roch theorem. And the fourth applies methods from commutative algebra to the study of chip-firing. [1] [2]
The book includes many illustrations, and ends each chapter with a set of exercises making it suitable as a textbook for a course on this topic. [3]
Although the book may be readable by some undergraduate mathematics students, reviewer David Perkinson suggests that its main audience should be graduate students in mathematics, for whom it could be used as the basis of a graduate course or seminar. He calls it "a thorough introduction to an exciting and growing subject", with "clear and concise exposition". [1] Reviewer Paul Dreyer calls it a "deep dive" into "incredibly deep mathematics". [3]
Another book on the same general topic, published at approximately the same time, is Divisors and Sandpiles: An Introduction to Chip-Firing by Corry and Perkinson (American Mathematical Society, 2018). It is written at a lower level aimed at undergraduate students, covering mainly the material from the first part of The Mathematics of Chip-Firing, and framed more in terms of algebraic geometry than combinatorics. [2]
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related and 0 if they are not. There are variations; see below.
In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.
In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.
In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.
In the mathematical field of algebraic graph theory, the degree matrix of an undirected graph is a diagonal matrix which contains information about the degree of each vertex—that is, the number of edges attached to each vertex. It is used together with the adjacency matrix to construct the Laplacian matrix of a graph: the Laplacian matrix is the difference of the degree matrix and the adjacency matrix.
The theory of association schemes arose in statistics, in the theory of experimental design for the analysis of variance. In mathematics, association schemes belong to both algebra and combinatorics. In algebraic combinatorics, association schemes provide a unified approach to many topics, for example combinatorial designs and coding theory. In algebra, association schemes generalize groups, and the theory of association schemes generalizes the character theory of linear representations of groups.
The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is. It has been used in analyzing the robustness and synchronizability of networks.
In mathematics, a representation is a very general relationship that expresses similarities between mathematical objects or structures. Roughly speaking, a collection Y of mathematical objects may be said to represent another collection X of objects, provided that the properties and relationships existing among the representing objects yi conform, in some consistent way, to those existing among the corresponding represented objects xi. More specifically, given a set Π of properties and relations, a Π-representation of some structure X is a structure Y that is the image of X under a homomorphism that preserves Π. The label representation is sometimes also applied to the homomorphism itself.
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y. Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith.
The nullity of a graph in the mathematical subject of graph theory can mean either of two unrelated numbers. If the graph has n vertices and m edges, then:
In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G. A covering map f is a surjection and a local isomorphism: the neighbourhood of a vertex v in C is mapped bijectively onto the neighbourhood of in G.
The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). BTW model was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.
Norman Linstead Biggs is a leading British mathematician focusing on discrete mathematics and in particular algebraic combinatorics.
The chip-firing game is a one-player game on a graph which was invented around 1983 and since has become an important part of the study of structural combinatorics.
Combinatorics: The Rota Way is a mathematics textbook on algebraic combinatorics, based on the lectures and lecture notes of Gian-Carlo Rota in his courses at the Massachusetts Institute of Technology. It was put into book form by Joseph P. S. Kung and Catherine Yan, two of Rota's students, and published in 2009 by the Cambridge University Press in their Cambridge Mathematical Library book series, listing Kung, Rota, and Yan as its authors. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.