Skip to main content
2 of 3
(typos--)--
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

Flooding a cycle digraph via chip-firing: $n^{k-1} + n^{k-2} + \cdots + 1$ bound (a Norway 1998-99 problem generalized)

Let $k > 1$ and $n$ be positive integers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Let $D$ be a digraph which has exactly $k$ vertices $v_0$, $v_1$, ..., $v_{k-1}$ and exactly $k$ arcs $v_0 \to v_1$, $v_1 \to v_2$, ..., $v_{k-2} \to v_{k-1}$, $v_{k-1} \to v_0$. (That is, $D$ is a directed cycle on $k$ vertices.) Let $V$ be the set of vertices of $D$. A chip configuration on $D$ will mean a map $f : V \to \mathbb{N}$. Visually, we represent a chip configuration by imagining that $f\left(v\right)$ "chips" (or coins or whatever tokens) are placed at each vertex $v \in V$. If $v$ is a vertex of $D$, then kicking $v$ will mean an operation which takes a chip configuration $f$ on $D$ satisfying $f\left(v\right) \geq n$, and returns another chip configuration $f'$ on $D$ which is defined as follows:

$f'\left(v\right) = f\left(v\right) - n$;

$f'\left(w\right) = f\left(w\right) + 1$ for every vertex $w$ such that $v \to w$ is an edge of $D$ (note that there exists only one such vertex $w$ for our graph $D$);

$f'\left(w\right) = f\left(w\right)$ for all remaining vertices $w$.

(In visual language, $f'$ is obtained from $f$ by removing $n$ chips from the vertex $v$ and adding one chip at the vertex that follows $v$ on the cycle.)

Notice that kicking $v$ is similar to the "firing $v$" operation from chip-firing (aka sandpile) theory; indeed, it can be seen as a particular case of the latter if we add a new vertex to $D$, proclaim it the sink, and add $n-1$ arcs from each $v \in V$ to this sink.

A kicking operation will mean an operation which is kicking $v$ for some $v \in V$.

If $J$ is a subset of $V$, then a chip configuration $f$ is called $J$-flooding if every $v \in J$ satisfies $f\left(v\right) > 0$.

If $f$ is a chip configuration on $D$, then $\left|f\right|$ will mean the sum $\sum\limits_{v \in V}f\left(v\right)$.

Conjecture 1. If $f$ is a chip configuration on $D$ satisfying $\left|f\right| \geq n^{k-1} + n^{k-2} + \cdots + 1$, then one can transform $f$ into a $V$-flooding chip configuration by a sequence of kicking operations.

Conjecture 2. If $J$ is a subset of $V$, and if $f$ is a chip configuration on $D$ satisfying $\left|f\right| \geq n^{k-1} + n^{k-2} + \cdots + n^{k-\left|J\right|}$, then one can transform $f$ into a $J$-flooding chip configuration by a sequence of kicking operations.

I have proven Conjecture 1 for all $k \leq 4$ and Conjecture 2 for all $k \leq 3$ by casework; at least the bound of Conjecture 1 is sharp. I am wondering if the conjectures are true in general. The motivation was a number theory problem from Norway's Abelkonkurransen 1998-99 (final problem 2b) which I tried to generalize back in 2006. The actual number theory problem, even in my generalization, is rather easy, as divisibility of integers boils down to comparing the exponents of prime powers in them; but it appears to me that there is much more substance to the combinatorial generalization that is Conjecture 1 above. Conjecture 2 was my attempt to make Conjecture 1 more amenable to induction by generalizing it even further; but so far it has just resulted in two conjectures rather than one.

The next question will probably surprise noone:

Question 3. If $D$, instead of being a cycle, is an arbitrary strongly digraph, what can we say about the smallest $N \in \mathbb{N}$ such that every chip configuration $f$ on $D$ satisfying $\left|f\right| \geq N$ can be transformed into a $V$-flooding chip configuration by a sequence of kicking operations?

darij grinberg
  • 33.8k
  • 4
  • 118
  • 253