Looking at the Configuation space

(David here!)

I was reading up about chip-firing recently (this article is great), and I realized that the main theorem used the trick of looking at the configuration space, which is really interesting but rarely used.

As a quick recap: the setting of chip-firing places a number of chips on the vertices of a graph, and if a vertex has at least as many chips as neighbors we can "fire" it by sending each neighbor a chip.

Then the main theorem is as follows:

(Main fact of Chip-Firing) If by some finite sequence of firings, we can reach a stable configuration $S$, then, all sequences of firings will end in $S$ after a finite sequence of moves.

That is:

1. If a sequence of firings is terminating, then all sequences of firings terminate.
2. The end position of all sequences of firings is unique.

Solution. Imagine a graph, $G$, where every vertex represents a specific configuration of chips across various nodes. An edge connects two vertices if one configuration can transition to the other through a single firing.

1. If a sequence of firings is terminating, then all sequences of firings terminate.

Suppose otherwise. Then, there is some configuration $A$ such that one of its child configurations, $B$, leads to only terminating chains, while another child, $C$, leads to an infinite chain.

Assume $B$ is obtained by firing vertex $v$ from $A$, and $C$ is derived by firing vertex $w$ from $A$. If we follow the sequence of firings leading from $C$, which supposedly creates an infinite chain, and apply it starting from $B$, we will continue until we reach the point where we fire $v$ again. Let's call this new configuration $D$. Note that the order of firings doesn't affect the resulting configuration, so $D$ is also a part of the sequence from $C$. But this implies that $D$, too, would lead to an infinite sequence, contradicting the claim that firing from $B$ results in a terminating chain.

2. The end position of all sequences of firings is unique.

In other words, no configuration exists which has two descendant chains leading to different final configurations.

Suppose such a configuration does exist. Let's identify the configuration at the deepest level in our graph where this divergence happens and call it $A$. Assume $A$'s child configurations $B$ and $C$ end up in distinct final states. If $B$ is the result of firing vertex $v$ and $C$ is the result of firing vertex $w$, then the sequences obtained by firing $vw$ and $wv$ from $A$ should converge to the same configuration. However, our assumption leads us to conclude they'd end in different configurations, which is illogical.

Remark. Check out Newman's lemma on abstract rewriting systems. There is kind of a "latttice" structure going on.

---

I'm reminded of another problem:

(ARMO 2014 11.4)
In a deck, each card can win against certain cards and lose against others, similar to rock-paper-scissors. Given two piles with known card orders, you are allowed to move the two top cards to the bottom of the winning pile, but you may choose their order. Prove that you can accumulate all cards into one pile.

Solution. Imagine a graph, $G$, depicting all possible arrangements of the deck between the two piles. Each point (or vertex) in this graph represents a specific distribution and sequence of cards between the two piles. An edge connects two vertices if one card arrangement can transition to the other in just one move.

A "terminal" vertex is where all cards have been accumulated into a single pile. Every non-terminal vertex will have two outgoing edges because, after a move, there are two distinct ways to order the top pair of cards at the bottom of the winning pile.

Conversely, each vertex can have a maximum of two incoming edges. For instance, if one pile won the previous move, then the two cards that were at the top in that move are now uniquely positioned at the bottom of the winning pile. This specific card arrangement is unique to that move. The only exception might be when one pile has only one card left, which might reduce the number of incoming edges.

Now, if our claim (that all cards can be accumulated into one pile) were incorrect, let's think of a subgraph, $H$, within $G$. This subgraph contains all the card arrangements reachable from the starting position by making moves. All vertices in H will have two outgoing edges, assuming we can't reach a terminal vertex. Additionally, they'll have at most two incoming edges.

However, the sum of outgoing edges always equals the sum of incoming edges. This implies every vertex in $H$ must have precisely two incoming edges. Given that every vertex has two incoming edges, we can effectively "reverse-play" the game, ensuring all cards end up in one pile.

Consider a point in $H$ where one pile has its maximum card count. If we backtrack to an earlier setup where the other pile had won, it implies the first pile had even more cards then. This challenges our initial point being the maximum. Therefore, the assumption that we can't combine all cards into one pile is flawed, confirming the claim.