pith. sign in

arxiv: 2604.13949 · v1 · submitted 2026-04-15 · 🧮 math.CO

General formulas for the instability minimum of Chip-firing games

Merlin Michalski , Christophe Dubussy This is my paper

Pith reviewed 2026-05-10 12:50 UTC · model grok-4.3

classification 🧮 math.CO
keywords chip-firing gamesinstability minimumdirected multigraphsinfinite firingEulerian graphscombinatorial algorithmsgraph theorytermination criteria
0
0 comments X

The pith

Three formulas compute the smallest number of chips that force an infinite chip-firing sequence on directed graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper supplies three explicit formulas that give the minimum total chips guaranteeing an initial configuration exists for which firing never stops. These apply to any strongly connected directed loop-free multigraph and extend the earlier formulas that worked only when every vertex had equal in-degree and out-degree. Knowing this threshold determines whether a chip-firing process on the graph must eventually stabilize or can run forever. The authors also examine algorithmic ways to evaluate the minimum from the graph description.

Core claim

The authors establish three formulas that calculate the instability minimum for strongly connected directed loop-free multigraphs. The instability minimum is the smallest integer M such that some placement of M chips admits an infinite firing sequence. The formulas generalize the known expressions from the Eulerian case by incorporating the directed structure and possible degree imbalances.

What carries the argument

The instability minimum, the least total chips allowing an infinite firing sequence to exist; the formulas compute it directly from the directed multigraph by summing appropriate degree terms and edge multiplicities.

If this is right

  • The minimum can now be calculated exactly for any strongly connected directed loop-free multigraph rather than only Eulerian ones.
  • Algorithms that compute the instability minimum become practical for this larger family of graphs.
  • Predictions about termination versus perpetual activity extend to unbalanced directed networks.
  • The same approach may help classify configurations that lead to finite versus infinite runs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The formulas could help analyze resource-flow models on directed networks where perpetual activity corresponds to deadlock or overload.
  • Removing the strongly-connected requirement would likely split the problem into components whose individual minima must be combined.
  • Links to other token-moving processes on directed graphs, such as rotor-routing or abelian sandpiles, may become easier to quantify.

Load-bearing premise

The graph must be strongly connected, directed, and loop-free for the three formulas to hold.

What would settle it

Take a small strongly connected directed multigraph with known firing behavior, apply the formulas to obtain M, place M chips in the configuration that should fire forever, and check whether the sequence is indeed infinite while every placement of M-1 chips reaches a stable state.

read the original abstract

In this article, we provide three formulas allowing to compute the minimum amount of initial chips leading to an infinite Chip-firing game. These formulas hold for strongly connected directed loop-free multigraphs and generalize what was already known in the Eulerian case. In addition to the many theoretical aspects, some algorithmic consequences are also investigated.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper derives three explicit formulas for the instability minimum—the smallest total number of chips on a strongly connected directed loop-free multigraph that permits a non-terminating firing sequence—and shows that these formulas generalize the known Eulerian case. It also examines algorithmic consequences of the formulas.

Significance. If the derivations hold, the work supplies the first general closed-form expressions for the instability minimum outside the Eulerian setting, where chip conservation and cycle structure are simpler. The explicit formulas, together with their proofs and the algorithmic corollaries, constitute a concrete advance that could be used to decide termination questions and to compute minimal recurrent configurations on a broader class of digraphs.

minor comments (3)
  1. [Abstract] The abstract states that the formulas hold for strongly connected directed loop-free multigraphs but does not preview the precise algebraic form of the three expressions; adding one sentence that indicates their dependence on out-degrees or Laplacian minors would improve immediate readability.
  2. [Main theorems section] In the statement of the main theorems, the notation for the instability minimum (presumably denoted something like m(G) or I_min) should be introduced once and used consistently; occasional switches to descriptive phrases make cross-referencing the three formulas harder.
  3. [Algorithmic consequences] The algorithmic section would benefit from a small complexity table or explicit statement of the running time in terms of the number of vertices and edges, even if the formulas are already polynomial-time evaluable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our work and for recommending minor revision. The report does not list any specific major comments, so we have no individual points to address point-by-point at this stage. We remain available to implement any minor editorial changes requested by the editor.

Circularity Check

0 steps flagged

No significant circularity; formulas derived independently from graph properties

full rationale

The paper derives three explicit formulas for the instability minimum (minimal initial chips for non-terminating firing) on strongly connected directed loop-free multigraphs. These build on chip conservation and strong connectivity to preclude sinks, generalizing the Eulerian case via direct combinatorial arguments rather than redefinition or fitting. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear; the central claims remain independent of the inputs by construction. The derivation is self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of chip-firing on directed multigraphs plus the domain restriction to strongly connected loop-free graphs; no free parameters or invented entities are visible from the abstract.

axioms (1)
  • domain assumption The graph is strongly connected, directed, and loop-free.
    Explicitly stated as the setting in which the three formulas hold.

pith-pipeline@v0.9.0 · 5331 in / 1146 out tokens · 42388 ms · 2026-05-10T12:50:40.603285+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    (1991),Chip-firing games on graphs, Eur

    A. Björner, L. Lovász and P. W. Shor,Chip-firing games on graphs, European J. Com- bin.12(1991), n o4, 283-291,https://doi.org/10.1016/S0195-6698(13)80111-4

    work page doi:10.1016/s0195-6698(13)80111-4 1991

  2. [2]

    Björner and L

    A. Björner and L. Lovász,Chip-firing games on directed graphs, J. Algebraic Combin. 1(1992), no 4, 305-328,https://doi.org/10.1023/A:1022467132614

    work page doi:10.1023/a:1022467132614 1992

  3. [3]

    F. J. Brandenburg and K. Hanauer,Sorting heuristics for the feedback arc set problem, Technical Report MIP-1104, University of Passau Germany, 2011

    work page 2011

  4. [4]

    Eades, X

    P. Eades, X. Lin and W. F. Smyth,A fast and effective heuristic for the feedback arc set problem, Inf. Process. Lett.47(1993), n o6, 319-323,https://doi:10.1016/ 0020-0190(93)90079-O

    work page 1993

  5. [5]

    Geladoris, P

    V. Geladoris, P. Lionakis and I. Tollis,Effective computation of a feedback arc set using PageRank, J. Graph Algorithms Appl.27(2023), no8, 737-757,https://doi.org/10. 7155/jgaa.00641

    work page 2023

  6. [6]

    Hujter and L

    B. Hujter and L. Tóthmérész,Chip-firing based methods in the Riemann–Roch theory of directed graphs, European J. Combin.78(2019), no1,https://doi.org/10.1016/ j.ejc.2019.01.007

    work page 2019

  7. [7]

    C. J. Klivans,The Mathematics of Chip-Firing, Chapman and Hall/CRC, New York, 2018,https://doi.org/10.1201/9781315206899

    work page doi:10.1201/9781315206899 2018

  8. [8]

    Minc,Nonnegative Matrices, J

    H. Minc,Nonnegative Matrices, J. Wiley and Sons, New York, 1988

    work page 1988

  9. [9]

    Perrot and T

    K. Perrot and T. Van Pham,Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs, Ann. Comb.19 (2015), 373-396,https://doi.org/10.1007/s00026-015-0266-9. 31

    work page doi:10.1007/s00026-015-0266-9 2015