← All papers
First page of A Fixed-Offset Transition for Random Stackability on Paths

A Fixed-Offset Transition for Random Stackability on Paths

John Fairfax-Ball

math.CO Sep 30, 2026 · v1 math.PR
Formalizes in Lean the finite deterministic deep-message necessity theorem and its fixed-total corollary for path pebbling stackability; the probabilistic asymptotics are not formalized.
We study a support-collapse version of graph pebbling on paths. A configuration is stackable if a sequence of legal pebbling moves can produce a nonzero configuration supported on a single vertex. On the path P_n, we choose a configuration uniformly from all weak compositions of total n times mu_n, where mu_n is a positive integer. We prove a two-sided fixed-offset transition for the logarithmic density. The transition is centred at sqrt(log_2 n) - (1/2) log_2 log_2 n + log_2(3e). For every fixed epsilon greater than zero, the stackability probability tends to zero when log_2 mu_n is eventually at most the centre minus epsilon, and tends to one when it is eventually at least the centre plus epsilon. No assertion is made at zero offset. The proof uses an exact recursive stackability score on trees, a one-dimensional path-message recurrence, binary-partition asymptotics for rare dyadic deficit excursions, a constant-cost regeneration argument, and an exact deep-message necessity theorem. Conditioning independent geometric occupancies on their sum returns the uniform fixed-total model. The finite deterministic necessity theorem and its exact fixed-total corollary are formalised in Lean and registered with Palomar; the full probabilistic asymptotic theorem is not part of that registration.

The paper asks how likely a uniformly random fixed-total pebble configuration on a path P_n is to be stackable, meaning legal pebbling moves can collapse it onto a single vertex. It seeks a sharp transition in the mean occupancy mu_n.

An exact recursive stackability score on trees is specialized to a one-dimensional path-message recurrence, with dyadic deficit identities governing rare failures. Binary-partition asymptotics (de Bruijn) control local excursion rates. A constant-cost regeneration argument and a product-geometric representation of the uniform weak-composition law carry the result to the fixed-total model. The finite deep-message necessity theorem and its fixed-total corollary are formalized in Lean and registered with Palomar.

A two-sided fixed-offset transition holds at log2 mu_n = sqrt(log2 n) - (1/2) log2 log2 n + log2(3e). Below the centre by any fixed epsilon the stackability probability tends to 0, and above it tends to 1. Exhaustive finite checks agree with the deep-message theorem on 307,646 nonstackable configurations.

Pathtotal tprobability
P_211
P_222/3
P_231
P_3519/21
P_3625/28
Selected exact finite stackability probabilities (illustrating nonmonotonicity)