Improved Upper Bounds on the Pebbling Numbers of the Blanu\v{s}a Snarks

Tong Niu

arxiv: 2605.07014 · v2 · submitted 2026-05-07 · 🧮 math.CO

Improved Upper Bounds on the Pebbling Numbers of the Blanuv{s}a Snarks

Tong Niu This is my paper

Pith reviewed 2026-05-15 06:35 UTC · model grok-4.3

classification 🧮 math.CO

keywords pebbling numberBlanuša snarksweight function lemmalinear programmingsnark graphsgraph theory

0 comments

The pith

Weight-function optimization per orbit tightens pebbling bounds on the two Blanuša snarks to 28 and 29.

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

The paper shows that the pebbling numbers of the two 18-vertex Blanuša snarks satisfy π(B1) ≤ 28 and π(B2) ≤ 29. It obtains these upper bounds by applying Hurlbert's Weight Function Lemma separately to each automorphism orbit and solving a linear program that chooses optimal weights from a corpus of roughly 30,000 rooted-subtree strategies. The authors retain the known lower bound of 23 after re-deriving the witnessing configurations and confirming them by exhaustive state-space search plus a sound MILP encoding that enforces acyclicity. A sympathetic reader cares because these numbers quantify the worst-case pebble resources needed to move a pebble to every possible target vertex in these small snark graphs, and shrinking the interval [23,31] to [23,28] and [23,30] to [23,29] narrows the remaining gap for exact computation.

Core claim

Optimizing per-orbit weight functions for Hurlbert's Weight Function Lemma via linear programming over a large corpus of rooted-subtree strategies yields the improved upper bounds π(B1) ≤ 28 and π(B2) ≤ 29.

What carries the argument

Hurlbert's Weight Function Lemma applied orbit-by-orbit, with weights chosen by linear program over a corpus of rooted-subtree strategies.

Load-bearing premise

Hurlbert's Weight Function Lemma still holds when the weight function is allowed to differ across automorphism orbits and is chosen by linear programming over the given set of strategies.

What would settle it

An explicit configuration of 27 pebbles on B1 (or 28 on B2) together with a proof that no sequence of pebbling moves can place a pebble on every vertex.

read the original abstract

The two Blanu\v{s}a snarks $B_1$ and $B_2$ are 3-regular graphs on 18 vertices. Dantas, Lordelo, Niedermaier and Nogueira (Discrete Appl. Math. 361, 2025, pp. 336-346) established the first systematic bounds $23 \le \pi(B_i) \le 34$ for $i=1,2$. Bridi, Marquezino and Figueiredo (arXiv:2505.16050, 2025) then sharpened the upper side to $\pi(B_1) \le 31$ and $\pi(B_2) \le 30$ via a Weight Function Lemma heuristic. We push the upper bounds further to $\pi(B_1) \le 28$ and $\pi(B_2) \le 29$. The route is again Hurlbert's Weight Function Lemma, but applied one automorphism orbit at a time, with optimal weight functions coming from a linear program over a corpus of roughly $30{,}000$ rooted-subtree strategies per target. For the lower bound $\pi(B_i) \ge 23$ we re-derive the witnesses of Dantas et al. and re-verify them with two independent oracles: an exhaustive forward state-space search, and a sound-and-complete MILP encoding whose acyclicity constraint is motivated by the Milans-Clark No-Cycle Lemma. The interval for $B_1$ shrinks from $[23, 31]$ to $[23, 28]$, and for $B_2$ from $[23, 30]$ to $[23, 29]$.

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.

Desk Editor's Note private letter to a colleague

The paper tightens the upper bounds on pebbling numbers for the two Blanuša snarks to 28 and 29 via LP-optimized per-orbit weights under Hurlbert's lemma, with independent lower-bound checks.

read the letter

The main point is that this work improves the upper bounds on the pebbling numbers of the two 18-vertex Blanuša snarks from the previous 31 and 30 down to 28 and 29, while keeping the lower bound at 23. The interval shrinks noticeably for both graphs. They achieve the new upper bounds by applying Hurlbert's Weight Function Lemma with weights chosen separately for each automorphism orbit and pulled from a linear program over roughly 30,000 rooted-subtree strategies. The lower bounds are re-derived from earlier witnesses and then cross-checked with exhaustive state-space search plus a MILP encoding that enforces acyclicity via the Milans-Clark lemma. Both oracles agree, which adds some reassurance. The paper reports the explicit weight functions that satisfy the lemma, so the upper-bound claims rest on concrete, checkable objects rather than black-box computation. The per-orbit split is just a symmetry reduction and does not invalidate the global application of the lemma once the combined weights are verified. This is honest incremental work. The concrete numbers are new, the verification steps are independent, and the LP setup is described clearly enough that someone could reproduce the weights. At the same time, the contribution stays narrow: two specific small graphs, an extension of existing techniques rather than a new method, and no claimed generalization or application beyond these instances. The computational corpus is large but finite, and the paper does not explore whether the same approach scales or yields insight for other snarks. Readers already working on pebbling numbers or on computational bounds for small cubic graphs will get the most out of it; the LP-plus-lemma combination is a useful data point for that community. The paper is coherent on its own terms, the evidence supports the stated claims, and the improvements are real even if modest. It deserves a serious referee rather than a desk reject.

Referee Report

0 major / 2 minor

Summary. The paper improves the upper bounds on the pebbling numbers of the two Blanuša snarks B1 and B2 from 31 and 30 down to 28 and 29, respectively, by applying Hurlbert's Weight Function Lemma to weights obtained from linear programs over a corpus of roughly 30,000 rooted-subtree strategies, with weights assigned separately per automorphism orbit. The lower bound of 23 is re-derived from prior witnesses and independently verified via exhaustive forward state-space search and a sound-and-complete MILP encoding that incorporates the Milans-Clark No-Cycle Lemma for acyclicity.

Significance. If the stated bounds hold, the work narrows the intervals for these 18-vertex snarks from [23,31] to [23,28] for B1 and from [23,30] to [23,29] for B2, constituting a concrete advance in the computational study of graph pebbling. The approach receives credit for combining the standard Weight Function Lemma with explicit LP-derived weights, symmetry reduction via orbits, and two independent oracles for the matching lower bounds, all of which support reproducibility and verification.

minor comments (2)

The description of the LP corpus and orbit decomposition would benefit from an explicit statement confirming that the reported weight vectors attain the LP optimum and that the combined weights satisfy all hypotheses of the Weight Function Lemma (e.g., non-negative weights and the required covering inequalities for every strategy).
A short table listing the final per-orbit weights together with the achieved objective value for each target vertex would make the upper-bound certificates easier to inspect without re-running the solver.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our manuscript and for recommending acceptance. We appreciate the recognition of the concrete improvement in the pebbling number bounds for the Blanuša snarks and the value placed on the combination of LP-derived weights, orbit-based symmetry reduction, and independent lower-bound verifications.

Circularity Check

0 steps flagged

No significant circularity; bounds rest on external lemma plus independent computation

full rationale

The derivation applies Hurlbert's Weight Function Lemma (external prior result) to weight functions obtained by solving an LP over a corpus of ~30,000 rooted-subtree strategies. The LP produces explicit weights that are then verified to satisfy the lemma's hypotheses, yielding the stated upper bounds. Lower bounds are re-derived from prior witnesses and cross-checked with two independent oracles (exhaustive search and MILP). No step reduces by construction to a fitted parameter inside the paper's own equations, no self-citation is load-bearing, and the per-orbit decomposition is a symmetry reduction that preserves validity of the external lemma. The argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on Hurlbert's Weight Function Lemma applied orbit-wise and on the correctness of the MILP encoding of the No-Cycle Lemma for lower-bound verification. No new entities are postulated.

axioms (2)

domain assumption Hurlbert's Weight Function Lemma provides a valid upper bound on the pebbling number when weights are assigned per automorphism orbit
Invoked to convert optimal LP weights into the stated upper bounds of 28 and 29.
domain assumption The Milans-Clark No-Cycle Lemma justifies the acyclicity constraint in the MILP encoding
Used to certify that the MILP solutions correspond to valid pebbling configurations for the lower bound of 23.

pith-pipeline@v0.9.0 · 5609 in / 1414 out tokens · 40918 ms · 2026-05-15T06:35:13.951932+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We push the upper bounds further to π(B1) ≤ 28 and π(B2) ≤ 29 via Hurlbert’s Weight Function Lemma applied one automorphism orbit at a time, with optimal weight functions coming from a linear program over a corpus of roughly 30,000 rooted-subtree strategies
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_strictMono_of_one_lt unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The route is again Hurlbert’s Weight Function Lemma... basic strategies... canonical weight wT(v) := 2^{D-dT(r,v)}

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages · 1 internal anchor

[1]

Blanuša.Problem četiriju boja

D. Blanuša.Problem četiriju boja. Glasnik Mat. Fiz. Astr. Ser. II 1 (1946), 31–42

work page 1946
[2]

G. A. Bridi, F. L. Marquezino, C. M. H. de Figueiredo.A weight function lemma heuristic for graph pebbling. arXiv:2505.16050 (2025)

work page arXiv 2025
[3]

F. R. K. Chung.Pebbling in hypercubes. SIAM J. Discrete Math. 2 (1989), 467–472

work page 1989
[4]

Discrete Appl

S.Dantas, L.F.R.Lordelo, T.Niedermaier, R.Nogueira.On the pebbling numbers of Flower, Blanuša and Watkins snarks. Discrete Appl. Math. 361 (2025), 336–346. arXiv:2303.13292

work page arXiv 2025
[5]

A linear optimization technique for graph pebbling

G. Hurlbert.The Weight Function Lemma for graph pebbling. J. Combin. Optim. 34 (2017), 343–361. arXiv:1101.5641

work page internal anchor Pith review Pith/arXiv arXiv 2017
[6]

Milans, B

K. Milans, B. Clark.The complexity of graph pebbling. SIAM J. Discrete Math. 20 (2006), 769–798

work page 2006
[7]

sorted

L. Pachter, H. Snevily, B. Voxman.On pebbling graphs. Congr. Numer. 107 (1995), 65–80. A Edge lists forB 1 andB 2 Vertex set{0,1,...,17}for both graphs. B1: E(B1) ={(0,1),(0,5),(0,16),(1,2),(1,17),(2,3),(2,14), (3,4),(3,8),(4,5),(4,17),(5,6),(6,7),(6,11), (7,8),(7,17),(8,9),(9,10),(9,13),(10,11), (10,15),(11,12),(12,13),(12,16),(13,14), (14,15),(15,16)}. ...

work page 1995

[1] [1]

Blanuša.Problem četiriju boja

D. Blanuša.Problem četiriju boja. Glasnik Mat. Fiz. Astr. Ser. II 1 (1946), 31–42

work page 1946

[2] [2]

G. A. Bridi, F. L. Marquezino, C. M. H. de Figueiredo.A weight function lemma heuristic for graph pebbling. arXiv:2505.16050 (2025)

work page arXiv 2025

[3] [3]

F. R. K. Chung.Pebbling in hypercubes. SIAM J. Discrete Math. 2 (1989), 467–472

work page 1989

[4] [4]

Discrete Appl

S.Dantas, L.F.R.Lordelo, T.Niedermaier, R.Nogueira.On the pebbling numbers of Flower, Blanuša and Watkins snarks. Discrete Appl. Math. 361 (2025), 336–346. arXiv:2303.13292

work page arXiv 2025

[5] [5]

A linear optimization technique for graph pebbling

G. Hurlbert.The Weight Function Lemma for graph pebbling. J. Combin. Optim. 34 (2017), 343–361. arXiv:1101.5641

work page internal anchor Pith review Pith/arXiv arXiv 2017

[6] [6]

Milans, B

K. Milans, B. Clark.The complexity of graph pebbling. SIAM J. Discrete Math. 20 (2006), 769–798

work page 2006

[7] [7]

sorted

L. Pachter, H. Snevily, B. Voxman.On pebbling graphs. Congr. Numer. 107 (1995), 65–80. A Edge lists forB 1 andB 2 Vertex set{0,1,...,17}for both graphs. B1: E(B1) ={(0,1),(0,5),(0,16),(1,2),(1,17),(2,3),(2,14), (3,4),(3,8),(4,5),(4,17),(5,6),(6,7),(6,11), (7,8),(7,17),(8,9),(9,10),(9,13),(10,11), (10,15),(11,12),(12,13),(12,16),(13,14), (14,15),(15,16)}. ...

work page 1995