Applying Hurlbert's Linear Optimization Technique to Establish Bounds on Pebbling Numbers

Lingwen Li

REVIEW 4 major objections 6 minor 13 references

Applying Hurlbert's Linear Optimization Technique to Establish Bounds on Pebbling Numbers

T0 review · 4 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper shows that a weight-function linear optimization lemma turns graph pebbling into a linear program, yielding the upper bounds π(P)≤10 for the Petersen graph and π(B4)≤66 for the fourth weak Bruhat graph, plus a tree formula.

desk verdict Expository re-derivation of known pebbling bounds, with a false tree formula and a gap in the key lemma; not a research contribution. read the letter →

arxiv 2509.11024 v1 pith:EYBQMHBN submitted 2025-09-14 math.CO

Lingwen Li This is my paper · ORCID

classification math.CO MSC 05C5705C05

keywords graphpebblingnumberweightfunctionlemmalinearoptimizationPetersenBruhattreeupperbounds

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to show that a single optimization lemma—the Weight Function Lemma—turns the graph pebbling problem on its head: instead of tracking individual pebbling moves, one assigns each vertex a doubling weight and checks a total-weight inequality. The lemma states that any configuration that cannot deliver a pebble to the root on a rooted subtree has total weight no greater than the weight of the configuration with one pebble on every non-root vertex. Summing several such inequalities over carefully chosen strategies converts the game into a linear program, and the optimal value gives an upper bound on the pebbling number. The paper uses this to derive the bound π(P)≤10 for the Petersen graph, π(B4)≤66 for the fourth weak Bruhat graph, and to argue the exact tree formula π(T,r)=Σ 2^{e_P}−|P|+1. A sympathetic reader would care because the method is a template: for any graph with a few hand-picked rooted subtrees, the same arithmetic produces a certified numeric upper bound.

What carries the argument

A strategy is a triple (T,r,ω) consisting of a rooted subtree T, a root r, and a weight function that assigns 0 to the root and doubles at each step toward the root: ω(parent)=2ω(child). The Weight Function Lemma is the load-bearing identity: it says r-unsolvable configurations lie inside the half-space ω(C)≤ω(T), where T is the canonical one-pebble-everywhere configuration. When several strategies are combined, the intersection of these half-spaces bounds the total number of pebbles; the numbers κ (minimum summed weight across vertices) and χ (total weight of the canonical configurations) make the bound explicit.

What would settle it

A single r-unsolvable configuration on B4 with 66 pebbles would disprove π(B4)≤66; a direct check of the claimed κ=6 and χ=395 for the strategies in Figure 21 would reveal whether the arithmetic or the strategy weights are wrong. At the lemma level, an r-unsolvable configuration satisfying ω(C)>ω(T) for any valid weight function would invalidate the Weight Function Lemma and, with it, the method.

Watch

Extended reading notes

Core claim

The central claim is the Weight Function Lemma (Lemma 4.4 in the paper): for any strategy S(T,r,ω) on a subtree T rooted at r, if C is an r-unsolvable configuration on the whole graph, then the weighted sum ω(C) is at most ω(T), where T denotes the configuration that puts one pebble on each vertex of T except the root. The paper's proof works by removing a pendant path P_y from T, applying the lemma to the remaining subtree and to the path separately, and combining the inequalities; the path case is the base case established earlier. From this lemma the paper derives the linear-optimization corollary: if several strategies are chosen, any r-unsolvable configuration must satisfy each weight i

Load-bearing premise

The argument rests on the Weight Function Lemma—that an r-unsolvable configuration on a rooted subtree always has total weight no greater than the configuration with one pebble on every non-root vertex—and the paper's proof of that lemma depends on a step (moving one pebble toward the root preserves unsolvability) that is stated without full justification.

Editorial extensions

If this is right

The Petersen graph's pebbling number is exactly 10: the one-pebble-on-nine-vertices configuration gives the lower bound, and the three-strategy linear program gives the matching upper bound.
The fourth weak Bruhat graph B4, whose 24 vertices are the permutations of four elements, has pebbling number at most 66.
For any tree T, the pebbling number relative to a root is π(T,r)=Σ_P 2^{e_P}−|P|+1 over an edge-disjoint path decomposition, which generalizes the path formula π(P_n)=2^{n−1}.
Any graph for which one can exhibit a finite set of rooted weight strategies inherits an integer upper bound on its pebbling number, obtained by rounding down χ/κ + 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The κ/χ recipe is a small linear program; for any graph one can automate the search for good strategies, and the 24-vertex Bruhat graph is a natural testbed for whether adding more strategies tightens the bound below 66.
For graphs with large automorphism groups, orbit-symmetric weight functions may be the efficient choice; the Petersen and Bruhat examples both use highly symmetric strategy sets.
The tree formula provides a benchmark: on any tree, one can compare the exact formula against the linear-optimization upper bound; trees where they match identify strategy sets that are optimal, and trees where they differ show where the method loses sharpness.
Extending the same weight-inequality to pebbling variants such as cover pebbling or optimal pebbling would only require reinterpreting the canonical configuration, since the lemma encodes the cost of moving pebbles toward the root.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper is a tutorial-style survey of Hurlbert's linear optimization technique, applied to the Petersen graph, the fourth weak Bruhat graph, and trees. The writing is clear and friendly, and the path, C5, and Petersen examples are mostly correct as far as they go. The intuition behind weight functions comes through well. But as a research paper it does not hold up: all the numerical results are already in the cited literature, and the one supposedly proved bound for B4 is imported from Flocco–Pulaj–Yerger. The paper adds no new theorem, no new technique, and no reproducible computation.

The soft spots are serious. Theorem 4.9, the tree pebbling formula, is false as stated. The path decomposition P is never defined uniquely, and an arbitrary edge-disjoint path cover gives the wrong answer. For K1,3 rooted at the center, the decomposition consisting of one length-2 path and one length-1 path yields 5, while the true pebbling number is 4. The proof also misuses the path lemma: placing 2^2−1 pebbles on a leaf of a length-2 path is already r-solvable, so the claimed lower-bound construction fails. This is not a minor gap; it is a wrong central statement.

The Weight Function Lemma (Lemma 4.4) also has an unjustified step: after moving a pebble from a leaf toward the root in an unsolvable configuration, the paper asserts the resulting configuration is still unsolvable. That is generally false. The lemma itself is true and due to Hurlbert, but the proof given here does not establish it. The Petersen and Bruhat weight functions are hand-picked from figures, with no machine-readable data or code, so the bounds cannot be independently reproduced from the paper.

Who should read this? Someone who wants a gentle first pass at pebbling weight functions might find the exposition useful, but they should be warned about the tree theorem. It is not a paper for peer review in its current form. The author seems capable of fixing the tree section and, if they want, turning this into a solid expository note; but as a research preprint it does not meet the bar.

Recommendation: desk reject for the research track. If the author repairs Theorem 4.9 and the Weight Function Lemma proof, it could become a useful teaching note.

Referee Report

4 major / 6 minor

Summary. The paper is an expository account of Hurlbert's linear-optimization technique for pebbling numbers, with applications to the Petersen graph, the fourth weak Bruhat graph B4, and trees. After introducing the pebbling game and standard background (Section 2-3), the paper restates a Weight Function Lemma (Lemma 4.4) and uses it to claim upper bounds π(P)≤10 for the Petersen graph (Lemma 4.7), π(B4)≤66 (Theorem 4.8), and a general formula for the pebbling number of a rooted tree (Theorem 4.9). The Petersen bound is already classical; the B4 bound is attributed to Flocco-Pulaj-Yerger [5]; and the tree formula is a version of Chung's theorem. The paper's technical core is the proof of Lemma 4.4 and the computations of the derived constants κ and χ in the applications.

Significance. If the central claims were correct, the paper would provide worked illustrations of Hurlbert's technique rather than new theorems: the Petersen number is long known, the B4 bound appears in the cited literature, and the tree formula is standard. The manuscript does offer an accessible summary of the pebbling game and a fairly faithful restatement of the weight-function framework; for a reader unfamiliar with the method, the exposition of Definition 4.3 and Corollary 4.5 is useful. However, the load-bearing proof of Lemma 4.4 is incomplete, Theorem 4.9 is false as stated, and the numerical constants in the applications are asserted, not derived. There is no machine-checked proof or reproducible code that would compensate for these gaps. The paper therefore does not meet the bar for publication in a serious journal.

major comments (4)

[Sec. 4.1, Lemma 4.4] The proof contains the unjustified step "Because C is unsolvable, C_x must also be unsolvable" after a pebble is moved from Py−x to x. A configuration obtained from an unsolvable configuration by a single move toward the root can become solvable; no argument is given to rule this out. The construction of T' is also not rigorously defined ('removing Py from T and reattaching the vertex x'), and the induction over 'r-unsolvable configurations of largest weight on T'' is not formalized. Since Lemma 4.4 is the engine for every upper bound in Section 4.3, this gap is load-bearing.
[Sec. 4.3, Theorem 4.9] Theorem 4.9 is false as stated because the path decomposition P is not uniquely or canonically defined. For T=K_{1,3} rooted at the center r, take P={leaf1-r-leaf2, leaf3-r}. This is an edge-disjoint path cover, and the theorem gives π(T,r)=2^2+2^1−2+1=5. But the true value is π(K_{1,3},r)=4: any four pebbles are r-solvable, and three pebbles on a leaf (plus no pebbles elsewhere) are r-unsolvable. The lower-bound construction in the proof also fails here: placing 2^{2}−1=3 pebbles on leaf1 permits two pebbles to be moved directly to r, so that configuration is solvable, not unsolvable.
[Sec. 4.3, Lemmas 4.7 and Theorem 4.8] The claimed upper bounds are not actually computed in the manuscript. For the Petersen graph, the proof simply states κ=4 and χ=36 from Figure 19; for B4, it states κ=6 and χ=395 from Figure 21. No verification is provided that the drawings define strategies satisfying Definition 4.3, nor is the arithmetic of the vertex weights shown. Since the text itself says the Petersen strategies come from Hurlbert [7] and the B4 strategies from [5], the paper's original contribution is reduced to asserting constants chosen to match the known or cited bounds. These assertions are not independently checkable from the figures as printed.
[Sec. 3.2, Lemma 3.6 and Petersen proof] The proof of π(C5)≤5 claims to have examined all possible configurations but presents only two figures and a verbal case split; it is not exhaustive. The subsequent Petersen-graph argument in Case 2 relies on the assertion that if C(C_r^5)≤4 and C(C_s^5)≥6, then 'even without moving the pebble from s' one can place another pebble on s; this is not justified. These gaps weaken the paper's independent derivation of π(P)=10, although the result itself is known.

minor comments (6)

[Table 15] The tree formula uses undefined symbols q_i and m; it is also inconsistent with Theorem 4.9, which uses a path decomposition P. Please align notation and give definitions.
[Sec. 4.2] The linear optimization problem is not formally defined. The symbol z_{G,r} is described by 'with a witnessing weight function', but it is not specified over which set of strategies the maximum is taken or how the optimization is performed. This makes the statement of Corollary 4.5 ambiguous.
[References] References [2] and [11] list the same paper by Clark and Milans; also, the duplicate 'B. Clark and K. Milans' / 'Milans, B. Clark' should be consolidated.
[Definition 4.3] The definition states ω(v+)=2ω(v) 'for every v∈V(G)', but the weight function is defined on the subtree T; it should be 'for every v∈V(T)'.
[Section 3.1] There is a typo: 'C(v) denotes the number of pebbles placed on vertex r' should read 'on vertex v'.
[Section 4.1, Lemma 4.1] The induction base case is written as 'fork=2' and the statement of the lemma uses n; please harmonize the variable names.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bounds are conditional on an external weight-function lemma and displayed strategies, not on the target values by construction.

full rationale

The paper's derivation chain is: the Weight Function Lemma (Lemma 4.4, imported from Hurlbert [7]) gives ω(C) ≤ ω(T) for r-unsolvable configurations; summing this over strategies gives κ|C| ≤ χ, and hence π(G) ≤ ⌊χ/κ⌋ + 1. In the applications, κ and χ are computed from explicit strategies displayed in Figure 19 (Petersen) and Figure 21 (Bruhat graph). Nothing in the paper equates the target bound to the choice of weights by construction: the displayed weight functions are proposed legal witnesses, and their legality is checkable from Definition 4.3. The Petersen bound π(P) ≤ 10 is also not forced by the earlier citation of the known result; it is verified from κ = 4, χ = 36 by the paper's own equations. There is no fitted parameter being renamed as a prediction, and no self-citation chain is used. The proof of the Weight Function Lemma in Section 4.1 contains a genuine gap ('Because C is unsolvable, C_x must also be unsolvable' is not generally true), and Theorem 4.9 is under-specified because the edge-disjoint path decomposition P is not canonical; different decompositions of K_{1,3} give different values. These are correctness/completeness concerns, not circularity: they do not make the outputs equivalent to the inputs by definition. Therefore no circular step meets the required evidentiary standard.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central claims rest on hand-picked weight functions (free parameters) and on the validity of the Weight Function Lemma and two pebbling-number facts whose proofs in the paper are incomplete.

free parameters (2)

Petersen graph weight functions (Figure 19) = κ=4, χ=36
Three hand-chosen strategies on the Petersen graph; the figures give the weights, chosen to force the bound 10.
Bruhat graph weight functions (Figure 21) = κ=6, χ=395
Strategies taken from Flocco, Pulaj, Yerger [5]; the paper does not explain how they were found, and they are effectively fitted to produce the bound 66.

assumptions (3)

domain assumption Weight Function Lemma (Lemma 4.4)
The paper's proof has an unjustified step; the lemma is imported from Hurlbert [7].
domain assumption π(C5) = 5 (Corollary 3.7)
The proof is a case-based check with informal claims; the result is used to prove the Petersen bound.
domain assumption π(Pn) = 2^{n-1} (Lemma 3.2)
The induction proof contains a gap about guaranteeing two pebbles at a vertex; the formula is standard.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Applying Hurlbert's Linear Optimization Technique to Establish Bounds on Pebbling Numbers." pith.science (2026). https://pith.science/paper/EYBQMHBN

@misc{pith2026250911024,
  author       = {Pith},
  title        = {Pith review of: Applying Hurlbert's Linear Optimization Technique to Establish Bounds on Pebbling Numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EYBQMHBN}},
  note         = {Machine review of arXiv:2509.11024}
}

read the original abstract

This paper explores the application of Hurlbert's Linear Optimization Technique to determine bounds on pebbling numbers. By applying Hurlbert's weight functions and optimization methods, we derive upper bounds for specific graph families. The study provides a comprehensive analysis of these bounds and contributes to a broader understanding of pebbling numbers in graph theory. In particular, the weight function lemma is applied to calculate upper bounds for graphs such as the Petersen graph, the Bruhat graph, and various trees.

Figures

Figures reproduced from arXiv: 2509.11024 by the authors.

**Figure 1.** The Petersen Graph P. Definition 2.5. Next, we will define some common elements in a graph. (a) A walk in a graph is a sequence of (not necessarily distinct) vertices v1, v2, ..., vk such that vivi+1 ∈ E for i = 1, 2, ..., k − 1. Such a sequence is sometimes called a v1 − vk walk, and v1 and vk are the end vertices of the walk. (b) A path is a walk in which all vertices are distinct. (c) A cycle, also called a close… view at source ↗

**Figure 2.** Examples of Complete Graphs Kn for n = 1, 2, 3, 4. (b) A cycle of order n, denoted by Cn, is a graph of a cycle on n vertices (See [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** The Cycle Graph Cn with n Vertices. (c) A path of order n, denoted by Pn, is simply a graph of a path on n vertices with n − 1 length (See [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (15 more)

**Figure 4.** Figure 4: The Path Graph [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]

**Figure 5.** Figure 5: The Tree Graph T. (e) The Petersen graph (See [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]

**Figure 6.** Figure 6: The Petersen Graph P. 3 Pebbling Numbers In this chapter, we begin by defining the pebbling number through a fun mini-game, making it easier and more enjoyable for readers to grasp the concept. After setting the stage with this playful introduction, we’ll delve into so…

**Figure 7.** Figure 7: Pebbling Rule with a Directed Move on a Path. [PITH_FULL_IMAGE:figures/full_fig_p005_7.png]

**Figure 8.** Figure 8: Comparison of r-solvable (left) and r-unsolvable (right) configurations on the Petersen graph In short, π(G) is Peter’s secret formula for winning the Pebbling Game every time, no matter where Connie tries to trip him up. For π(G), we have: π(G) = maxrπ(G, r). Alternat…

**Figure 9.** Figure 9: The Petersen Graph Highlighting Two Cyclic Structures. [PITH_FULL_IMAGE:figures/full_fig_p008_9.png]

**Figure 10.** Figure 10: The Cycle Graph C5 with a Red Root and Two Path Graphs P3. According to Lemma 3.2, we have the pebbling number formula for a path, as given by: π(Pn) = 2n−1 . Therefore, for the path P3, the pebbling number is 2 2 = 4. Given that we have 5 pebbles, they can be distrib…

**Figure 13.** Figure 13: Different Selections of C r 5 and C s 5 Cycles in the Petersen Graph. Since we have already proven that π(C5) = 5, when there are more than 5 pebbles on C r 5 , the configuration should be r-solvable. On the other hand, we have: C(C r 5 ) ≤ 4 and C(C s 5 ) ≥ 6. This …

**Figure 14.** Figure 14: The Petersen Graph with 10 Pebbles Distributed Among Red Vertices. [PITH_FULL_IMAGE:figures/full_fig_p010_14.png]

**Figure 16.** Figure 16: Representation of the Path Graph Pk with Weighted Vertices. • Case 1: If Pk+1(v2) = 1. Then, Pk will be v2-unsolvable. By induction, ω(Pk) ≤ 2 k−1 − 1 that is Pk+1 i=3 ω(vi)Pk(vi) ≤ 2 k−1 − 1. Since Pk+1(v1) = 0, Pk+1(v2) = 1 and Pk+1 i=3 ω(vi)Pk(vi) ≤ 2 k−1 − 1, we h…

**Figure 17.** Figure 17: Illustration of a Subtree T with Vertex v and Its Parent v +. Next, we will apply a weight function ω to the subtree T, which we refer to as a strategy S(T, r, ω). Definition 4.3. The strategy S(T, r, ω) of a rooted tree (T, r) is a triple (T, r, ω) including a rooted…

**Figure 18.** Figure 18: Tree T with path Py highlighted in red, and subtree T ′ in blue. Among all r-unsolvable configurations, let C be the configuration with the largest weight on T ′ . The restriction of the weight function ω to T ′ , denoted ω ′ , still represents a valid strategy for th…

**Figure 19.** Figure 19: Three distinct strategies applied to the Petersen graph. [PITH_FULL_IMAGE:figures/full_fig_p017_19.png]

**Figure 20.** Figure 20: The Structure of the Fourth Weak Bruhat Graph on 24 Vertices. [PITH_FULL_IMAGE:figures/full_fig_p018_20.png]

**Figure 21.** Figure 21: Set of strategies applied on the Fourth Weak Bruhat Graph with 24 vertices. [PITH_FULL_IMAGE:figures/full_fig_p021_21.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 3 linked inside Pith

[5]

Flocco, J

D. Flocco, J. Pulaj, C. Yerger.Automating Weight Function Generation in Graph Pebbling, arXiv:2312.12618

arXiv
[7]

Hurlbert,A linear optimization technique for graph pebbling, arXiv:1101.5641

G. Hurlbert,A linear optimization technique for graph pebbling, arXiv:1101.5641

arXiv
[1]

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

1989
[2]

Clark and K

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

2006
[3]

D. W. Cranston, L. Postle, C. Xue, C. Yerger,Modified linear programming and class 0 bounds for graph pebbling, Journal of Combinatorial Optimization43(2017) 114–132

2017
[4]

Elledge and G

S. Elledge and G. Hurlbert,An Application of Graph Pebbling to Zero-Sum Sequences in Abelian Groups, The Electronic Journal of Combinatorial Number Theory.5(2005), Paper A17

2005
[6]

Harris, J

J. Harris, J. L. Hirst, M. Mossinghoff.Combinatorics and Graph Theory. Undergraduate Texts in Mathematics, Springer, New York, 2008

2008
[8]

Hurlbert.A survey of graph pebbling, Congr

G. Hurlbert.A survey of graph pebbling, Congr. Numer.139(1999), 41–64

1999

Show all 13 references

[9]

Kenter, D

F. Kenter, D. Skipper,Integer-programming bounds on pebbling numbers of cartesian-product graphs, in: Proceedings of the 12th International Conference on Combinatorial Optimization and Applications, (2018) 681–695

2018
[10]

Lemke, D

P. Lemke, D. KleitmanAn addition theorem on the integers modulo n, J. Number Theory.31 (1989), 335-345

1989
[11]

Milans, B

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

2006
[12]

Pachter, H

L. Pachter, H. Snevily, and B. Voxman,On pebbling graphs, Congr. Numer. 107 (1995), 65–80

1995
[13]

Watson.The complexity of pebbling and cover pebbling, arXiv:math/0503511

N. Watson.The complexity of pebbling and cover pebbling, arXiv:math/0503511. 20 Figure 21: Set of strategies applied on the Fourth Weak Bruhat Graph with 24 vertices. 21

arXiv

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.

[1] [5]

Flocco, J

D. Flocco, J. Pulaj, C. Yerger.Automating Weight Function Generation in Graph Pebbling, arXiv:2312.12618

arXiv

[2] [7]

Hurlbert,A linear optimization technique for graph pebbling, arXiv:1101.5641

G. Hurlbert,A linear optimization technique for graph pebbling, arXiv:1101.5641

arXiv

[3] [1]

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

1989

[4] [2]

Clark and K

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

2006

[5] [3]

D. W. Cranston, L. Postle, C. Xue, C. Yerger,Modified linear programming and class 0 bounds for graph pebbling, Journal of Combinatorial Optimization43(2017) 114–132

2017

[6] [4]

Elledge and G

S. Elledge and G. Hurlbert,An Application of Graph Pebbling to Zero-Sum Sequences in Abelian Groups, The Electronic Journal of Combinatorial Number Theory.5(2005), Paper A17

2005

[7] [6]

Harris, J

J. Harris, J. L. Hirst, M. Mossinghoff.Combinatorics and Graph Theory. Undergraduate Texts in Mathematics, Springer, New York, 2008

2008

[8] [8]

Hurlbert.A survey of graph pebbling, Congr

G. Hurlbert.A survey of graph pebbling, Congr. Numer.139(1999), 41–64

1999