7
$\begingroup$

A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a configuration on a hypergraph $(V,\mathcal{E})$ is a map $c:V\rightarrow\mathbb{Z}$. For $v\in V$ let $A(v)=\{E\in\mathcal{E}: v\in E\}$ and let $D(v)=\vert A(v)\vert$. Given a configuration $c$ on a hypergraph $(V,\mathcal{E})$ and a vertex $v\in V$, there are in general many ways to fire $c$ at $v$. Specifically, write $c\rightarrow_vc'$ iff there is a function $f: A(v)\rightarrow V$ such that

  • $c'(v)=c(v)-D(v)$,

  • $f(E)\in E\setminus\{v\}$ for each $E\in A(v)$, and

  • for $w\not=v$ we have $c'(w)=c(w)+\vert f^{-1}(\{w\})$.

Basically, vertex $v$ gives up $D(v)$ "coins," one per "hyperedge." Note that we can have $c'(w)-c(w)>1$ by having multiple "hyperedges" containing both $w$ and the firing vertex $v$.

This notion of firing gives rise to two versions of the chip-firing game, a "solitaire" version and a "competitive" version.

  • Solitaire version $\mathsf{S}(H,c_0)$: A single player, given a starting configuration $c_0$ on a hypergraph $H$, tries to build a sequence $$c_0\rightarrow_{v_0}c_1\rightarrow _{v_1}...\rightarrow_{v_n}c_{n+1}$$ with final configuration having nonnegative range; if they have a strategy for doing this, $\mathsf{S}(H, c_0)$ is winnable.

  • Competitive version $\mathsf{C}(H,c_0)$: Again we have a starting configuration $c_0$ on a hypergraph $H$, but now there are two players. At round $i$, having already built configuration $c_i$ player $1$ picks a vertex $v_i$ and player $2$ decides how to fire (that is, player $2$ picks some configuration $c_{i+1}$ with $c_i\rightarrow_{v_i}c_{i+1}$). Player $1$ wins a play if some configuration in the play ever has nonnegative range.

I'm generally interested in any information about these games, but to keep things concrete here's a particular question:

Which hypergraphs $H$ have the property that, for some configuration $c_0$ on $H$, the solitaire game $\mathsf{S}(H,c_0)$ is winnable but player $1$ does not have a winning strategy in the competitive game $\mathsf{C}(H,c_0)$?

$\endgroup$
0

0

You must log in to answer this question.