## Cayley graph

**Definition**
Let $G$ be a group and $S$ be a inverse-closed generating set of $G$. Then the Cayley graph of $G$ with respect to $S$, denoted by $\text{Cay}(G, S)$, is constructed as follows.
* $V(\text{Cay}(G, S))=G$
* $E(\text{Cay}(G, S))=\{ \{ g, h \}:gs=h \text{ for some } s\in S \}$

---
### Cayley graphs are vertex-transitive

For a graph $X=(V, E)$, a permutation on vertex set $V$ is called an graph automorphism of $X$ if it preserves the adjacency relation of $X$. All automorphisms of form a group, called the automorphism group of $X$ and denoted by $\text{Aut}(X)$.

Assume that $X=\text{Cay}(G, S)$ for some group $G$. For each $g$ in $G$ we may define a permutation $\bar g$ of $V(X)=G$ by the rule $\bar g(h)=gh \ (h \in G)$. This permutation is an automorphism of $X$.
> \begin{split}
> \{h, k\}\in E(X) &\Rightarrow hs=k \ \text{ for some } s\in S\\
> &\Rightarrow ghs=gk\\
> &\Rightarrow \{gh, gk\}\in E(X)\\
> &\Rightarrow \{\bar g(h), \bar g(k)\}\in E(X)
> \end{split}

The set of all $\bar g \ (g \in G)$ constitutes a group $\bar G \le\text{Aut}(X)$.

For any two vertices $x, y \in V(X)=G$, the element $\bar y \overline {x^{-1}} \in \bar G$ maps $x$ to $y$, and thus $\bar G$ acts transitively on $V(X)$. In particular, $\text{Aut}(X)$ is transitive on $V(X)$, and Cayley graphs are vertex-transitive graphs. Moreover, $\bar y \overline {x^{-1}}$ is the unique element of $\bar G$ which maps $x$ to $y$, and so $\bar G$ is a regular subgroup of $\text{Aut}(X)$ .

### Not every vertex-transitive graph is a Cayley graph
* Petersen graph

#### Petersen graph is a vertex-transitive graph
The vertices of the Petersen graph $G$ are labeled with 2-element subsets of $\{1,2,3,4,5\}$ and two vertices are adjacent if and only if their intersection is empty.

If we apply the permutation $(1,4,5,2,3)$ to the vertices, we get a clockwise rotation. Futhermore, $(1, 4, 2, 5)$ is a permutation which maps the inner 5 vertices onto the outer 5 vertices.


Hence, we are finished because we can mix the two permutations to map every vertex onto every other.

#### Petersen graph is not a Cayley graph

If the Petersen graph $P$ is a Cayley graph, i.e., $P=\text{Cay}(G, S)$ for some group $G$ with $|G|=10$ and $|S|=3$. Then $G=\mathbb{Z}_{10}$ or $D_5$, and $S=\{a, b, c\}$ is a inverse-closed generating set of $G$.
1. $G=\mathbb{Z}_{10}$：for $a\neq b^{-1}$, $a^{-1}b^{-1}ab$ gives a cycle of length 4 , but the Petersen graph has none such.
3. $G=D_5$：At least one of the generators, say $a$, must have order 2. If there is a generator $b$ of order 5 , then $(ab)^2=e$ , so again we should have a cycle of length 4 , but there is none. The only other possibility is that all generators have order 2 , but then there is no product of 5 generators equal to the identity. But the Petersen graph does have 5-cycles, contradiction.

### A graph $X$ with the vertex-set $V$ is a Cayley graph, if and only if $\text{Aut}(X)$ contains a subgroup which acts regularly on $V$.

*proof.* $(\Rightarrow)$ $\bar G \le \text{Aut}(X)$ acts regularly on $V$ by our above discussion.
$(\Leftarrow)$ Suppose $V=\{v_1, v_2, \cdots, v_n\}$, and $H$ is a subgroup of $\text{Aut}(X)$ acting regularly on $V$. Then, for $1 \le i \le n$ there is a unique $h_i \in H$ such that $h_i(v_1)=v_i$. Let $$S=\{h_i \in H \ | \ v_i \text{ is adjencent to }v_1 \text{ in }X \}$$Then the bijection $v_i \leftrightarrow h_i$ is a graph isomorphsim of $X$ with $\text{Cay}(H, S)$. $\ \square$


---

## The sandpile group

### 6.1. A first example

Let $G$ be the diamond graph pictured in Figure 1. Imagine that grains of sand can be piled onto the vertices of $G$ to form a *sandpile*. Figure 2 shows $G$ with 4 grains of sand on $v_1$, one grain on each of $v_2$ and $v_3$, and no sand on $s$.


* We allow only nonnegative amounts of sand at each vertex.

If a vertex gets too much sand, it becomes unstable, at which point it may *fire* or *topple*, sending grains of sand to its neighboring vertices.

* A vertex is unstable if it has at least as many grains of sand as its degree.

If sand were conserved, then configurations with too many grains of sand would never stabilize: no matter how vertices were fired, there would always be at least one unstable vertex.

To prevent this, we designate $s$ to be the sink vertex, stipulating that any grains of sand landing on $s$ immediately disappear.

Figure 3 shows what happens to the configuration in Figure 2 when vertex $v_1$ fires. A grain of sand is delivered to each neighbor, the grain sent to $s$ being lost.

Starting with an initial unstable sandpile, what happens if we repeatedly choose and fire unstable vertices? Whenever a vertex adjacent to the sink fires, a grain of sand is lost, which tends to make the sandpile more stable. But is it possible to have a sequence of firings that can be repeated in a never-ending cycle?

* Every initial sandpile on $G$ will, through repeated firings, eventually stabilize.
* The choice of ordering in which to fire unstable vertices has no effect on the eventual stabilization of a sandpile.

In light of above observation, by firing unstable vertices, every sandpile $c$ on $G$ eventually reaches a unique stable state. We denote the stabilization of $c$ by $c^\circ$ and write $$c \rightsquigarrow c^\circ$$ we use the jagged arrow to distinguish *legal* sequences of unstable vertex firings from more general processes that might in volve firing stable vertices; these more general processes will generically be denoted by $c \to c'$.

#### 6.1.1 Additive structure

Identify each sandpile on $G$ with a 3-tuple $c = (c_1, c_2, c_3)$ of integers by letting $c_i$ be the number of grains of sand on vertex $v_i$. Using this notation, the stabilization in Figure 4 could be written $$(4, 1, 1) \stackrel{v_1}\rightsquigarrow (1, 2, 2) \stackrel{v_3}\rightsquigarrow \cdots \stackrel{v_3}\rightsquigarrow (1, 2, 0)$$ or, for short, $$(4, 1, 1) \rightsquigarrow (1, 2, 0)$$


Let $\text{Stab}(G)$ denote the collection of the 18 stable sandpiles on $G$.
> When stable, $c_1 \in \{0, 1, 2\}, c_2 \in \{0, 1, 2\}, c_3 \in \{0, 1\}$.

Define the sum, $a \circledast b$, of two sandpiles $a, b \in \text{Stab}(G)$ by first adding vertex-wise, i.e., adding them as integer vectors, then stabilizing: $$a \circledast b=(a+b)^\circ$$ For example, $(2, 1, 1)\circledast(2,0,0) = (1,2,0)$ as illustrated in Figure 5.


* The operation $\circledast$ is commutative and associative and that the zero sandpile, $(0,0,0)$, serves as an identity element.

By above , $(\text{Stab}(G), \circledast)$ is almost an abelian group──it only lacks inverses. Such a structure is called a *commutative monoid*.

We have a model for a simple physical system: beginning with the zero sandpile on $G$, drop grains of sand randomly onto the non-sink vertices, producing a sequence of sandpiles. Whenever we reach an unstable sandpile $c$, it topples to yield a stable sandpile $c^\circ$. This model is *dissipative* because sand is lost into the sink $s$, and it is *slowly-driven* because of the ongoing addition of sand at a rate that allows for stabilization between each additional grain.

Pick a vertex of $G$ at random; drop a grain of sand on that vertex and stabilize the resulting sandpile; repeat until 100 grains of sand have been dropped. The results from ten trials of this experiment are shown in Table 1.


Interestingly, there are eight sandpiles that appear more than once in each trial. These are the *recurrent* sandpiles for $G$, denoted $S(G)$.

$S(G)$ is a group under the operation inherited from $\text{Stab}(G)$. But how could $S(G)$ be a group if it does not contain the zero sandpile, $(0,0,0)$? The answer is that $S(G)$ has an identity, but it is not the identity of $\text{Stab}(G)$. In other words, $S(G)$ is not a submonoid of $\text{Stab}(G)$ even though they share the same operation.

* addition table for $S(G) \cong \mathbb{Z}_8$

| $\circledast$ | (0,2,1) | (1,2,0) | (1,2,1) | (2,0,1) | (2,1,0) | (2,1,1) | (2,2,0) | (2,2,1) |
|:-------------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
| **(0,2,1)** | (2,2,1) | (2,1,0) | (2,1,1) | (2,2,0) | (1,2,1) | (1,2,0) | (0,2,1) | (2,0,1) |
| **(1,2,0)** | (2,1,0) | (2,0,1) | (0,2,1) | (2,1,1) | (2,2,0) | (2,2,1) | (1,2,0) | (1,2,1) |
| **(1,2,1)** | (2,1,1) | (0,2,1) | (2,0,1) | (2,1,0) | (2,2,1) | (2,2,0) | (1,2,1) | (1,2,0) |
| **(2,0,1)** | (2,2,0) | (2,1,1) | (2,1,0) | (2,2,1) | (1,2,0) | (1,2,1) | (2,0,1) | (0,2,1) |
| **(2,1,0)** | (1,2,1) | (2,2,0) | (2,2,1) | (1,2,0) | (0,2,1) | (2,0,1) | (2,1,0) | (2,1,1) |
| **(2,1,1)** | (1,2,0) | (2,2,1) | (2,2,0) | (1,2,1) | (2,0,1) | (0,2,1) | (2,1,1) | (2,1,0) |
| **(2,2,0)** | (0,2,1) | (1,2,0) | (1,2,1) | (2,0,1) | (2,1,0) | (2,1,1) | (2,2,0) | (2,2,1) |
| **(2,2,1)** | (2,0,1) | (1,2,1) | (1,2,0) | (0,2,1) | (2,1,1) | (2,1,0) | (2,2,1) | (2,2,0) |

* Note that the identity is $(2,2,0)$ and the inverse of $(a, b, c)$ is $(b, a, c)$.

---

### 6.2. Directed graphs

From now on, a graph will be a finite, connected, multidigraph. Thus, a graph is an ordered pair $G = (V,E)$ where $V$ is a finite set of vertices and $E$ is a finite multiset of directed edges. Each element of $E$ is an ordered pair $e = (u, v) \in V \times V$ where $u$ and $v$ are the tail and head of $e$, respectively. We use the notation $e^- = u$ and $e^+ = v$ and say $e$ emanates from $u$. We will sometimes write $uv \in E$ to indicate the directed edge $(u,v)$. If $u = v$, then $e$ is a loop.

The ''multi'' part of ''multidigraph'' indicates that $E$ is a multiset, so that an edge may occur multiple times. Thus, each edge $e = (u,v) \in E$ has an integer multiplicity, $\text{mult}(e) \ge 1$. Figure 7 illustrates our conventions for drawing graphs. Edges are labeled by their multiplicities. An unlabeled edge like $(u,s)$ is assumed to have multiplicity 1. The undirected edge between $v$ and $s$ represents the pair of directed edges, $(v, s)$ and $(s, v)$, each with multiplicity 2.


There are several different notions of connectedness for a digraph. For us, connected will mean what is sometimes called weakly connected: we assume that the underlying undirected graph for $G$ is connected. (This undirected graph has the same vertex set as $G$ and an edge $\{u, v\}$ for each directed edge $(u, v)$ or $(v, u)$ of $G$.)

The *outdegree* of a vertex $v$ of $G$ is $$\text{outdeg}(v) = |\{ e \in E : e^- =v \}| $$ where each edge is counted according to its multiplicity. Similarly, the *indegree* of $v$ in $G$ is $$\text{indeg}(v) = |\{ e \in E : e^+ =v \}| $$ For the graph in Figure 7, we have $\text{outdeg}(v) = 5$ and $\text{indeg}(v) = 7$.

Let $u, v \in V$. A path of length $k$ from $u$ to $v$ is an ordered list of edges, $e_1, \cdots, e_k$ such that
1. $e_1^- = u$
2. $e_i^+ = e_{i+1}^-$ for $i = 1, \cdots, k-1$
3. $e_k^+ = v$

The distance from $u$ to $v$ is the minimum of the lengths of all paths from $u$ to $v$, denoted $d(u, v)$. If there is no path from $u$ to $v$, take $d(u, v) =\infty$. If $d(u, v) < \infty$, we say $v$ is accessible from $u$. For the graph in Figure 7, we have $d(s,u)= 2$ and $d(u,s) = 1$.

---

### 6.3. Sandpile graphs

A sandpile graph is a triple $G = (V,E,s)$ where $(V,E)$ is a graph, also referred to as $G$, and $s\in V$ is the sink. For a sandpile graph we require the designated sink vertex to be globally accessible. That is, there is some directed path from each vertex to $s$.

**Notation.** We let $\tilde V$ denote the non-sink vertices: $$\tilde V :=V- \{s\}$$
Let $G$ be a sandpile graph with sink $s$. A configuration of sand on $G$ is an element of the free abelian group on its non-sink vertices:$$\text{Config}(G, s) := \text{Config}(G) := \mathbb{Z}{\tilde{V}} := \left\{\sum_{v \in \tilde{V}} c(v)v : c(v) \in \mathbb{Z} \text{ for all } v\right\}$$

If $c$ is a configuration and $v \in \tilde{V}$, then $c(v)$ will always denote the coefficient of $v$ in $c$. We think of $c(v)$ as the number of grains of sand sitting on vertex $v$, even though this number might be negative. We let $0_{\tilde{V}} := \sum_{v \in \tilde{V}} 0 \cdot v$ and $1_{\tilde{V}} := \sum_{v \in \tilde{V}} v$, the zero and all ones configurations, respectively. Of course, these two configurations are sandpiles.

The *degree* of a configuration $c$ is the net amount of sand in $c$:
$$
\text{deg}(c) = \sum_{v \in \tilde{V}} c(v) \in \mathbb{Z}
$$
Define a partial order on the group of configurations: if $a, b \in \mathbb{Z}{\tilde{V}}$, then $a \leq b$ if $a(v) \leq b(v)$ for all $v \in \tilde{V}$, and $a < b$ if $a \leq b$ and $a \neq b$. In terms of this partial order, a configuration $c$ is a sandpile if $0_{\tilde{V}} \le c$. We also sometimes use the adjective *nonnegative* to indicate that a given configuration is a sandpile.

---