graph_pebbling_step
def
A pebbling step on a graph G turns the configuration c : V → ℕ into c' when some edge uv has c(u) ≥ 2 and c' is c with two pebbles removed from u and one added at v.
Statement
def graph_pebbling_step {V : Type*} [DecidableEq V] (G : SimpleGraph V) (c c' : V → ℕ) : Prop
- Defined in
- arXiv:2610.09650 (The Almost Stacked Hypothesis: A Conjectural Analogue of Sjöstrand's Cover Pebbling Theorem), Sec. 2 (pebbling step u ⇒ v).
- Verified
- 12 Oct 2026
- Axioms
- none listed
- Used by 8
- graph_config_stackableA configuration c on G is stackable if a sequence of pebbling steps (possibly empty) turns it into a stacked configuration, one whose…
- path_graph_two_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the path on two vertices: stack(P₂) = estim(P₂) (both equal 3).
- star_graph_one_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the single-vertex tree K₁: stack(K₁) = estim(K₁) (both equal 2).
- graph_pebbling_step_sumA pebbling step lowers the size ‖c‖ = Σ_v c(v) by exactly one.
- not_graph_config_stackable_zeroThe empty configuration is not stackable: no step applies and its support is empty.
- graph_config_stackable_singleA configuration with m ≥ 1 pebbles all on one vertex is stackable (it is already stacked).
- path_graph_three_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the path on three vertices: stack(P₃) = estim(P₃) (both equal 7).
- star_graph_four_stacking_number_eq_tree_estimateConjecture 5.6 (OP-144) holds for the star K₁,₃ (center 0, leaves 1, 2, 3), the smallest tree that is not a path: stack(K₁,₃) =…
Lean source view module on GitHub
/-- One pebbling step `c ⟶ c'` on `G`: along some edge `uv` with `c u ≥ 2`, remove two pebbles from `u` and add one to `v`. -/ def graph_pebbling_step {V : Type*} [DecidableEq V] (G : SimpleGraph V) (c c' : V → ℕ) : Prop := ∃ u v, G.Adj u v ∧ 2 ≤ c u ∧ c' = Function.update (Function.update c u (c u - 2)) v (c v + 1)