Critical group of a graph

My postdoc mentor suggested me to think about some problems regarding the critical graph of a random graph, so I decided to sit down and read some basic words about this. I might write more on this if I want to store more summaries.

Critical group of a graph. When we consider a graph, we always mean a finite graph. Let $G$ be a graph with $n$ verticies. Given a vertex $v,$ the degree $\deg(v)$ is the number of paths ending at $v$ in an arbitrarily small neighborhood of $v.$ Order the vertices $v_{1}, \dots, v_{n}$ of $G.$ The diagonal matrix $D = D(G)$ of $G$ is the $n \times n$ diagonal matrix whose diagonal entries are given by $\deg(v_{1}), \dots, \deg(v_{n}).$ The adjacent matrix $A = A(G)$ of $G$ is the $n \times n$ matrix whose entries are given by defining its $(i,j)$ entry to be the number of edges between $v_{i}$ and $v_{j}.$ The Laplacian $L = L(G)$ of $G$ is defined to be $D - A.$

Convention. We will only deal with graphs whose vertices don't have self nodes. Moreover, we will assume that every pair of vertices have at max $1$ edge in between. With this convention, note that

• $A(G)$ is a $(0, 1)$ symmetric matrix with $0$'s on the diagonal, and
• The entries of any row or column of $L(G) = D(G) - A(G)$ add up to $0.$

Theorem 1. If $G$ is connected, then $\ker(L(G))$ is a cyclic group generated by $(1, 1, \dots, 1).$

Proof. Since the entries of any row of $L = L(G)$ add up to $0,$ we have $(1, 1, \dots, 1) \in \ker(L).$ Conversely, say $x = (x_{1}, \dots, x_{n}) \in \ker(L) \subset \mathbb{Z}^{n}.$ Even without connectedness hypothesis, we have $$0 = x^{T}Lx = \sum (x_{i} - x_{j})^{2},$$ where the sum is over $1 \leq i, j \leq n$ such that $v_{i}$ and $v_{j}$ are connected by an edge. Since $G$ is connected, all the distinct pairs of indices $(i, j)$ must appear in the sum, and since we work over $\mathbb{Z},$ we must have $x_{i} = x_{j}.$ Thus, we have $m := x_{1} = \cdots = x_{n},$ so $(x_{1}, \dots, x_{n}) = m (1, 1, \dots, 1) \in \mathbb{Z}(1, 1, \dots, 1),$ as desired. $\Box$

Remark. Note that if $G$ is not connected, a similar proof to Theorem 1 shows that $\ker(G)$ is generated by tuples that consist of $0$'s and $1$'s, where $1$'s are located in the coordinates corresponding to vertices that belong to each connected component.

Corollary. The rank of the cokernel $\mathrm{cok}(L(G))$ of $L(G)$ is $1$ so that $$\mathrm{cok}(L(G)) \simeq \mathbb{Z} \oplus K(G),$$ where $K(G)$ is a finite abelian group.

We call $K(G)$ (up to an isomorphism) the critical group of $G.$

A divisor of $G$ is an element of $\mathbb{Z}^{|V(G)|},$ where $V(G)$ is the set of vertices of $G.$ We write $\mathrm{Div}(G) := \mathbb{Z}^{|V(G)|}.$ Writing $n := |V(G)|,$ the degree of a divisor $D = (m_{1}, \dots, m_{n})$ is defined to be $\deg(D) := m_{1} + \cdots + m_{n}.$

Remark. It seems that the dual graph of an algebraic curve (whose vertices correspond to the irreducible components) contains quite a bit of information about the curve, which could be a motivation for studying these graph invariants for algebraic geometors. I would not try to make any analogy before I understand this story a bit better. (For example, see p.12 of this article; here, there are also graphs we do not consider in this post.)

The subgroup of divisors of degree $0$ is denoted as $\mathrm{Div}^{0}(G).$ Given a divisor $(x_{1}, \dots, x_{n})$ of $G,$ there are two kinds of chip-firing moves at each vertex $v_{i}$:

1. Fire at $v_{i}$: takes $x_{i} \mapsto x_{i} - \deg(v_{i})$ and then add $1$ to any adjacent vertex.
2. Borrow to $v_{i}$: takes $x_{i} \mapsto x_{i} + \deg(v_{i})$ and then subtract $1$ to any adjacent vertex.

Any two divisors of $G$ that can be achieved from one to another by a sequence of chip-firing moves are said to be equivalent, and note that this indeed defines an equivalence relation to all divisors. Note that chip-firing moves do not change the degree of a divisor, so this also defines an equivalence relation on the degree $0$ divisors.

Theorem 2. If $G$ is connected, then $K(G) \simeq \mathrm{Div}^{0}(G)/\sim.$

Proof. Since columns of $L(G)$ sum up to $0,$ we have $\mathrm{im}(L(G)) \subset \mathrm{Div}^{0}(G),$ so $$\mathrm{Div}^{0}(G)/\mathrm{im}(L(G)) \hookrightarrow \mathbb{Z}^{n}/\mathrm{im}(L(G)) \simeq \mathbb{Z} \oplus K(G).$$ Since $\mathrm{Div}^{0}(G)/\mathrm{im}(L(G))$ is of rank $0,$ it must sit inside the subgroup of $\mathbb{Z}^{n}/\mathrm{im}(L(G))$ corresponding to $K(G),$ which we may also write as $K(G).$ This implies that $$\mathbb{Z} \simeq \mathbb{Z}^{n}/\mathrm{Div}^{0}(G) \simeq \frac{\mathbb{Z}^{n}/\mathrm{im}(L(G))}{\mathrm{Div}^{0}(G)/\mathrm{im}(L(G))} \simeq \mathbb{Z} \oplus  \frac{K(G)}{\mathrm{Div}^{0}(G)/\mathrm{im}(L(G))}.$$ Thus, we have $$\frac{K(G)}{\mathrm{Div}^{0}(G)/\mathrm{im}(L(G))} = 0,$$ so $$\mathrm{Div}^{0}(G)/\mathrm{im}(L(G)) = K(G).$$ Hence, to finish the proof, it suffices to show that $\mathrm{im}(L(G))$ is equal to the set of degree $0$ divisors of $G$ that are equivalent to $(0, 0, \dots, 0).$ This immediately follows from observing that firing at $v_{i}$ for an $n$-tuple (i.e., a divisor) is identical to subtracting the $i$-th column of $L(G)$ from it. This finishes the proof. $\Box$

Smith normal forms. Recall that given an $n \times n$ matrix $L$ over $\mathbb{Z},$ there always exists $U, V \in \mathrm{GL}_{n}(\mathbb{Z})$ such that $ULV = \mathrm{diag}(s_{1}, \dots, s_{r}, 0, 0, \dots, 0)$ with nonzero positive integers $s_{1}, \dots, s_{r}$ satisfying $s_{1} | \cdots | s_{r}.$ This implies that $$\mathrm{cok}(L) \simeq \mathrm{cok}(ULV) \simeq \mathbb{Z}^{n - r} \oplus \mathbb{Z}/(s_{1}) \oplus \cdots \oplus \mathbb{Z}/(s_{r}),$$ which shows the uniqueness of $s_{1}, \dots, s_{n}$. We call the diagonal matrix with the entries $s_{1}, \dots, s_{r}, 0, 0, \dots, 0$ the Smith normal form of $L.$ One may note that $r$ is the rank of $L$ and recall that $U$ is given by the row operations on $L$ while $V$ is given by the column operations on $L$ over $\mathbb{Z}$ when it comes to achieving the diagonal matrix form. 

Thus, if $L = L(G)$ for some connected graph $G,$ we have $$K(G) \simeq \mathbb{Z}/(s_{1}) \oplus \cdots \oplus \mathbb{Z}/(s_{r}).$$

Lemma. Keeping the notations as above, for any $1 \leq i \leq r,$ we have $$s_{1}s_{2} \cdots s_{i} = \gcd(i \times i \text{ minors of } L).$$

Proof. This immediately follows from noticing that the gcd of $i \times i$ minors of $L$ is unchanged after any row or column operation. To see the invariance under the row operations, denote by $[R_{1} | \cdots | R_{i}]$ be an $i \times i$ submatrix of $L,$ where $R_{1}, \dots, R_{i}$ are the rows. A row operation turns this matrix into a matrix of the form $$[R_{1} | \cdots | R_{j} + cR'_{j} | \cdots | R_{i}],$$ and thus the corresponding minor is equal to $$\det[R_{1} | \cdots | R_{j} | \cdots | R_{i}] + c\det[R_{1} | \cdots | R'_{j} | \cdots | R_{i}].$$ The proof ends by noticing that $\det[R_{1} | \cdots | R'_{j} | \cdots | R_{i}]$ is one of the $i \times i$ minors before we perform the row operation. The invariance under the column operations can be similarly observed. $\Box$

Example. Let $K_{n}$ be the complete graph on $n$ vertices. To keep up with our convention, we assume that $n \geq 3.$ We have $$L(K_{n}) = \begin{bmatrix} n-1 & -1 & -1 & \cdots & -1 \\ -1 & n-1 & -1 & \cdots & -1 \\ \vdots & \vdots & \vdots & \cdots & \vdots \\ -1 & -1 & -1 & \cdots & n-1 \end{bmatrix}.$$ Using Lemma, it is immediate that $s_{1} = 1.$ The only $2 \times 2$ minors are $0, n, n(n-2),$ so Lemma implies that $s_{2} = s_{1}s_{2} = n.$ We already know $r = n-1$ and since $s_{1} | \cdots | s_{n-1},$ we have $$n^{n-2} = s_{2}^{n-2} | s_{1}s_{2} \cdots s_{n-1}.$$ By induction, we can compute that once we delete the first row and the last column of $L(K_{n-1}),$ the determinant of the resulting $(n - 1) \times (n - 1)$ matrix is $\pm n^{n-2}.$ Lemma guarantees that this number is divisible by $s_{1} \cdots s_{n-1},$ so we have $$n^{n-2} | s_{1}s_{2} \cdots s_{n-1} | n^{n-2}.$$ Thus, we have $s_{2} \cdots s_{n-1} = s_{1}s_{2} \cdots s_{n-1} = n^{n-2}.$ Since $s_{2} | \cdots | s_{n-1},$ this implies that $$s_{2} = s_{3} = \cdots = s_{n-1} = n.$$ Thus, we have $$K(K_{n}) \simeq (\mathbb{Z}/(n))^{n-2}.$$

Theorem 3. Given a connected graph $G$ with $n$ vertices, the critical group can be computed by taking the cokernel of the $(n - 1) \times (n - 1)$ matrix $L_{ij}(G)$ obtained by deleting the $i$-th row and the $j$-th column of $L(G)$ for any $1 \leq i, j \leq n.$ In particular, we have $\mathrm{cok}(L_{ij}(G)) = |K(G)|.$

Proof. This only uses the fact that the entries of any row or column of $L(G)$ add up to $0.$ If we add all the rows other then the $i$-th row to the $i$-th row of $L(G),$ the resulting matrix will only have $0$'s on its $i$-th row. This is because the entries of each column add up to $0.$ Then if we add all the columns other than the $j$-th column to the $j$-th column of this matrix, the resulting matrix will only have $0$'s on its $j$-th column. This is because the entries of each row add up to $0.$ This finishes the proof because we already know the rank of $L(G)$ is $n-1.$ $\Box$

Theorem 4 (Kirchhoff). If $G$ is connected, then $|K(G)|$ is the number of spanning trees of $G.$

Corollary (Cayley). The number of spanning trees of $K_{n}$ is $n^{n-2}.$