Packing $A$-paths of length zero modulo a prime

Robin Thomas; Youngho Yoo

REVIEW 3 major objections 2 minor 16 references

Packing $A$-paths of length zero modulo a prime

T0 review · 3 major / 2 minor · reviewed 2026-08-27 · deepseek-v4-flash

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

Pith's one-line read For every odd prime p, A-paths of length 0 modulo p satisfy the Erdős–Pósa property, with a complete classification for abelian group-labelled graphs.

desk verdict Theorem 1.3 looks like a real answer to Bruhn-Ulmer's Problem 22, but the Section 2 counterexample for the classification is wrong, so the only-if directions of Theorems 2.4 and 1.4 are unsupported. read the letter →

arxiv 2009.12230 v2 pith:YLZX564B submitted 2020-09-23 math.CO

Robin Thomas , Youngho Yoo This is my paper · ORCID

classification math.CO MSC 05C3805C7005C83

keywords Erdős–PósapropertyA-pathsgroup-labelledgraphsmodularpathlengthszero-weightpacking-coveringdualitytanglesandwallsCauchy–Davenporttheorem

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

An A-path is a path whose only vertices from a fixed set A are its two endpoints; the Erdős–Pósa property says that for some function f, every graph either contains k disjoint such paths or has a set of at most f(k) vertices meeting all of them. The paper proves that when p is an odd prime, A-paths of length 0 modulo p have this property, answering a question left open after the known cases m=2 and m=4 and the known failures for composite m>4. It then characterizes, in undirected graphs whose edges carry labels from an abelian group Γ, exactly which groups Γ and labels ℓ make A-paths of weight ℓ satisfy the property: elementary abelian 2-groups with label 0, Z/4Z with label 0 or 2, and Z/pZ with p prime and any label. A directed analogue is also settled: zero-weight A-paths have the property precisely when the group is finite.

What carries the argument

The proof is carried by the structure theory of large walls in group-labelled graphs, imported from the companion manuscript [15] as Theorem 3.7. A wall is a large grid-like subgraph used to model high connectivity. In a minimal counterexample, a tangle in G−A forces the presence of a very large wall, and the structure theorem says one of three things happens: a Γ-odd complete-graph model, a wall that is facially odd or carries a pure odd linkage, or a Γ-bipartite 3-block left over after deleting a bounded set. In the first two outcomes, the paper assembles many disjoint nonzero cycle-chains; because Γ=Z/pZ with p prime has every nonzero element as a generator, the Cauchy–Davenport theorem implies that a nonzero cycle-chain of length p−1 contains a zero A-path, so k disjoint zero A-paths appear. In the third outcome, a Γ-bipartite 3-block is handled by new Menger-type lemmas for A-B-paths of prescribed weight that allow the construction of k disjoint zero A-paths even when A attaches to the block in awkward ways.

What would settle it

For Γ=Z/8Z and ℓ=4, build the n×n grid-with-terminals construction of Lemma 2.1 with those labels: if, for arbitrarily large n, the resulting graph has no two disjoint A-paths of weight 4 while the smallest vertex set hitting all such paths grows with n, then Theorem 1.4 is false; the theorem predicts such a labelling cannot exist.

Watch

Extended reading notes

Core claim

The central discovery is a complete dichotomy for packing zero-weight A-paths in group-labelled graphs. Theorem 1.3 states that for every odd prime p, A-paths of length 0 mod p satisfy the Erdős–Pósa property. Theorem 1.4 states that in undirected Γ-labelled graphs with Γ abelian, A-paths of weight ℓ satisfy the property exactly in three cases: Γ ≅ (Z/2Z)^k with ℓ=0; Γ ≅ Z/4Z with ℓ∈{0,2}; or Γ ≅ Z/pZ with p prime and ℓ arbitrary. Theorem 1.5 states that in directed Γ-labelled graphs, Γ-zero A-paths satisfy the property if and only if Γ is finite. Taken together, these theorems determine all group-label regimes in which the packing-covering duality holds for A-paths of a prescribed weight.

Load-bearing premise

The load-bearing premise is the structure theorem for large walls in group-labelled graphs from the companion manuscript [15]: the proof of Theorem 1.3 invokes it as Theorem 3.7 together with Lemmas 4.2, 4.4, and 4.6, and if that result is wrong the proof of the main theorem collapses.

Editorial extensions

If this is right

For every odd prime p, the minimum hitting set for A-paths of length 0 mod p is bounded by a function of the desired number k of disjoint paths, so large disjoint families and small hitting sets cannot both be absent.
The only moduli m for which length-0-mod-m A-paths satisfy the Erdős–Pósa property are m=2, m=4, and primes; composite m>4 were already known to fail.
In undirected abelian group-labelled graphs, the property for fixed weight ℓ holds only for the three listed group-label pairs, so any other pair is guaranteed to admit counterexamples with arbitrarily large hitting number relative to packing number.
In directed group-labelled graphs, zero-weight A-paths have the property exactly for finite groups; infinite groups always produce obstructions of the grid type given in Lemma 2.1.
The reduction between A-paths of weight 2g and zero A-paths via relabelling edges incident to A means the classification transfers between these two problem families whenever 2g=ℓ in Γ.

Reading between the lines

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

Editorial inference: the same wall-structure recipe may transfer to Problem 2.6, the directed fixed-weight analogue, provided the rerouting step can be made to work without commutativity; the paper's reduction from weight ℓ to weight 0 uses shifting operations that rely on Γ being abelian, so the directed case will need a different device.
Editorial inference: the sharp p−1 bound from Cauchy–Davenport in Proposition 4.1 suggests that the Erdős–Pósa function for Z/pZ could grow with p, and it would be informative to extract an explicit f(k) from the proof and test whether the growth in the group order is necessary.
Editorial inference: if the companion wall-structure theorem [15] were formalized and checked, the entire chain from tangle to zero A-paths would rest on published, verified results; until then, the main theorem's status inherits the dependence on that manuscript's correctness.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central discovery is a complete dichotomy for packing zero-weight A-paths in group-labelled graphs. Theorem 1.3 states that for every odd prime p, A-paths of length 0 mod p satisfy the Erdős–Pósa property. Theorem 1.4 states that in undirected Γ-labelled graphs with Γ abelian, A-paths of weight ℓ satisfy the property exactly in three cases: Γ ≅ (Z/2Z)^k with ℓ=0; Γ ≅ Z/4Z with ℓ∈{0,2}; or Γ ≅

/-- @claim 1 The central discovery is a complete dichotomy for packing zero-weight A-paths in group-labelled graphs. Theorem 1.3 states that for every odd prime p, A-paths of length 0 mod p satisfy the Erdős–Pósa property. Theorem 1.4 states that in undirected Γ-labelled graphs with Γ abelian, A-paths of weight ℓ satisfy the property exactly in three cases: Γ ≅ (Z/2Z)^k with ℓ=0; Γ ≅ Z/4Z with ℓ∈{0,2}; or Γ ≅  -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

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

Two things to know. First, Theorem 1.3 is a serious piece of work: it answers an explicit open problem, and the proof strategy -- tangles, the wall structure theorem from [15], the Cauchy-Davenport cycle-chain lemma, and the Menger-type arguments in the Gamma-bipartite 3-block case -- is coherent and mostly clean. Second, the companion classification has a concrete error in its counterexample construction, and that error is internal to the paper, not just a dependency on [15].

In Theorem 2.4, the grid construction claims there are no two disjoint zero A-paths. That claim is false. Take Gamma = Z/12, g1 = 3, g2 = 4, n = 6. The paths P1 = u1-v11-v12-v13-v63-w3 and P2 = u4-v14-v15-v16-v66-w6 are vertex-disjoint, and each has weight 3 + 4 + 4 + 1 = 12 = 0 mod 12. More generally, a path from u_i to w_{i+q2-1} using q2-1 consecutive top-row edges has weight q2*g2 = 0, so disjoint blocks [1,q2], [q2+1,2q2], ... give linearly many disjoint zero A-paths. The construction therefore cannot establish failure of the Erdos-Posa property. This undermines the only-if direction of Theorem 2.4, and because Theorem 1.4 reduces nonzero weights to the zero case via the 2g shift, it also undermines the only-if direction of Theorem 1.4.

What is good: the main theorem's proof appears unaffected by this Section 2 problem, as far as I can tell. The reductions in Section 2 before the flawed construction are fine, and the authors are honest about the dependency on the unpublished companion manuscript [15]. That dependency is real fragility -- if Theorem 3.7 or its lemmas have a gap, the proof of Theorem 1.3 collapses -- but it is not itself an error. The paper also proves a clean directed analogue, Theorem 1.5, with a short frame argument.

Where this leaves us: the paper deserves a serious referee because Theorem 1.3 alone is important and likely correct. But the classification part cannot be accepted as is. The authors need to fix or replace the counterexample construction, and the classification result may or may not survive that fix. I would not desk-reject; I would send it out with this concern stated explicitly.

Referee Report

3 major / 2 minor

Summary. The paper studies the Erdős-Pósa property for A-paths of prescribed weight in group-labelled graphs. Its main results are Theorem 1.3, stating that A-paths of length 0 modulo an odd prime p satisfy the Erdős-Pósa property; Theorem 1.4, a full classification of the abelian groups Γ and elements ℓ for which A-paths of weight ℓ satisfy the property in undirected Γ-labelled graphs; and Theorem 1.5, stating that Γ-zero A-paths in directed Γ-labelled graphs satisfy the property exactly when Γ is finite. The authors reduce the classification to Theorem 1.3 via finite-group constructions, and prove Theorem 1.3 using a structure theorem for large walls in group-labelled graphs quoted from their companion manuscript [15], together with a Menger-type analysis of Γ-bipartite 3-blocks in Section 4.

Significance. If correct, Theorem 1.3 answers a question of Bruhn and Ulmer, and Theorem 1.4 gives a complete dichotomy for undirected abelian group-labelled graphs, substantially extending earlier work on A-paths of prescribed length modulo m. The paper has clear strengths: the directed case is handled by a short frame argument; the reduction in Section 2 is explicit; and the Menger-type statements for A-B-paths in Γ-bipartite 3-blocks (Lemmas 4.8–4.10) are interesting tools that may be useful beyond this paper. However, the converse directions of the classification rest on counterexample constructions that, as written, contain many disjoint A-paths; they therefore do not establish failure of the Erdős-Pósa property. In addition, the proof of Theorem 1.3 depends on the unpublished companion manuscript [15] for the main structure theorem and several lemmas, so the central claim is not self-contained.

major comments (3)

[Section 2.2, proof of Theorem 2.4] The assertion 'Clearly, there does not exist two disjoint zero A-paths' is false for the construction with γ'_n. If q2 is the order of g2 and j = i+q2−1 ≤ n, then the path u_i v_{1,i} v_{1,i+1} ... v_{1,j} v_{n,j} w_j has weight g1 + (q2−1)g2 + (g2−g1) = q2 g2 = 0, so it is a zero A-path. Taking i = 1, 1+q2, 1+2q2, ... gives pairwise disjoint zero A-paths, so the number of disjoint zero A-paths grows linearly with n. Hence this construction cannot prove failure of the Erdős-Pósa property, and the 'only if' direction of Theorem 2.4 is unsupported. Since the ℓ = 0 case of Theorem 1.4 invokes Theorem 2.4, that part of the classification is consequently also unsupported.
[Section 2.3, proof of Theorem 1.4] The counterexample for the case where there exists g with ℓ ∉ ⟨g⟩ also does not establish failure of the Erdős-Pósa property. In the graph with labelling γ''_n, for each i with 2i ≤ n the path u_{2i−1} v_{1,2i−1} v_{1,2i} v_{n,2i} w_{2i} has weight (ℓ−g)+g = ℓ, and these ⌊n/2⌋ paths are pairwise disjoint. Thus for every fixed k, taking n sufficiently large yields k disjoint A-paths of weight ℓ, so the construction does not exhibit a packing-covering gap. The only-if direction of Theorem 1.4 for nonzero ℓ is therefore not proved by the given argument.
[Section 4 / Theorem 3.7] The proof of Theorem 1.3 is built on Theorem 3.7 and Lemmas 4.2, 4.4, and 4.6, which are quoted from the authors' unpublished companion manuscript [15]. The correctness of the main theorem is conditional on these results, but their proofs are not included in the present manuscript. Referees and readers cannot verify the central claim from the submitted text alone. The authors should either make [15] available with the submission or provide self-contained proofs of the quoted results.

minor comments (2)

[Section 2.2, proof of Theorem 2.4] The sentence 'every Γ-zero A-path ... has one endpoint in {u_i : i ∈ [n]} and one endpoint in {v_i : i ∈ [n]}' should refer to {w_i : i ∈ [n]} rather than {v_i : i ∈ [n]}, because the bottom A-vertices are the w_i.
[Problem 2.6] The remark that for Γ ≅ Z/3Z and ℓ ≠ 0 the problem is equivalent to nonzero A-paths because 'one of the two directions of traversal will give the desired weight ℓ' needs a precise convention for traversing an undirected path; as written it is ambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation reduces new A-path results to independent structural statements; reliance on the authors' companion manuscript is a verification gap, not a circular step.

full rationale

The main theorems are derived by reducing zero-A-path packing problems to independent structural results, not by restating the target. Theorem 1.3 invokes the structure theorem for walls in group-labelled graphs (Theorem 3.7, cited as Theorem 2.10 of the authors' companion manuscript [15]) and the three cycle-chain lemmas (4.2, 4.4, 4.6) also from [15]. This is heavy self-citation, but under the review rules it is not circular: Theorem 3.7 is a parameter-free statement about nonzero cycles and walls, with no assumption that includes the target family of zero-weight A-paths, and the paper then performs substantial independent work (Cauchy-Davenport rerouting, Menger-type lemmas in Section 4.2, and the final tangle argument) to convert those cycle structures into disjoint zero A-paths. The reduction in Theorem 1.4 from weight-ell paths to zero A-paths by relabelling edges incident with A is a genuine bijection between path families, not a fitted input renamed as a prediction. Lemma 2.1 and the grid counterexamples in Sections 2.2-2.3 assert failure of the Erdős-Pósa property by explicit constructions; these are not circular even if the correctness of the assertion 'Clearly, there does not exist two disjoint zero A-paths' in Theorem 2.4 is questionable. A false or unsupported counterexample is a mathematical correctness risk, not a circularity. No step in the paper equates its conclusion with its inputs by definition, and no fitted parameter is relabeled as a prediction. The dependence on [15] is a fragility/verification concern because that manuscript is unpublished and not included, but the review rules count a parameter-free cited theorem with disjoint assumptions as independent support, so the circularity score remains 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard graph structure theory (walls, tangles, Menger) plus a substantial unproved structure theorem from the authors' own unpublished companion manuscript. No numerical fits or invented entities are involved; the paper is a pure mathematics proof.

assumptions (6)

domain assumption Theorem 3.7 (structure theorem for large walls in group-labelled graphs) from companion manuscript [15].
Invoked in the proof of Theorem 1.3 (Section 4, 'We apply Theorem 3.7 to (W,γ), r*, t*'). It is stated but not proved here; its three-way dichotomy is the load-bearing tool for the entire proof.
standard math Theorem 2.5: a finite p-group with a unique subgroup of order p is cyclic or generalized quaternion.
Cited from [10] and used in the proof of Theorem 1.4 to force Γ to be cyclic of prime power order.
standard math Cauchy-Davenport theorem for Z/pZ.
Used in Proposition 4.1 to show a nonzero cycle-chain of length p-1 contains a zero A-path.
standard math Wall and tangle machinery of Robertson-Seymour (Theorem 3.4, tangles induced by walls and models).
Used to translate the large tangle from Lemma 3.3 into a wall, then to apply Theorem 3.7.
standard math Menger's theorem and the Erdős-Pósa type lemmas from [3] (Lemmas 3.3, 3.5, 3.6).
Used throughout Section 4 for linkage extraction and separation arguments.
domain assumption Lemmas 4.2, 4.4, 4.6 from [15].
Stated without proof as black boxes for constructing nonzero cycle-chains in walls and models.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Packing $A$-paths of length zero modulo a prime." pith.science (2026). https://pith.science/paper/YLZX564B

@misc{pith2026200912230,
  author       = {Pith},
  title        = {Pith review of: Packing $A$-paths of length zero modulo a prime},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YLZX564B}},
  note         = {Machine review of arXiv:2009.12230}
}

abstract

It is known that $A$-paths of length $0$ mod $m$ satisfy the Erd\H{o}s-P\'osa property if $m=2$ or $m=4$, but not if $m > 4$ is composite. We show that if $p$ is prime, then $A$-paths of length $0$ mod $p$ satisfy the Erd\H{o}s-P\'osa property. More generally, in the framework of undirected group-labelled graphs, we characterize the abelian groups $\Gamma$ and elements $\ell \in \Gamma$ for which the Erd\H{o}s-P\'osa property holds for $A$-paths of weight $\ell$.

Figures

Figures reproduced from arXiv: 2009.12230 by the authors.

**Figure 1.** The black vertices constitute A and all unlabelled edges have weight 0. 2.1 Γ-zero A-paths in directed Γ-labelled graphs An A-tree is a tree whose intersection with A is exactly its set of leaves. Let ℓ(T ) denote the number of leaves of a tree T . Our proof of Theorem 1.5 applies the so-called frame argument expounded in [2]. Lemma 2.2. Let Γ be a finite group and let k be a positive integer. If (T , γ ~ ) is a dir… view at source ↗

**Figure 2.** An elementary 6-wall. The four corners are marked by squ [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[15]

Thomas, Y

R. Thomas, Y. Yoo, Packing cycles in undirected group-labelled g raphs, manuscript (2020)

work page 2020
[1]

B¨ oltz, Erd˝ os-Posa Eigenschaften auf abelschen Gruppen , Master’s thesis, Ulm University (2018)

L. B¨ oltz, Erd˝ os-Posa Eigenschaften auf abelschen Gruppen , Master’s thesis, Ulm University (2018)

work page 2018
[2]

Bruhn, M

H. Bruhn, M. Heinlein, and F. Joos, Frames, A-Paths, and the Erd˝ os–P´ osa Property,SIAM J. Disc. Math. , 32(2) (2018), 1246-1260. 21

work page 2018
[3]

Packing A-Paths of Length Zero Modulo Four

H. Bruhn and A. Ulmer, Packing A-Paths of Length Zero Modulo Four, arXiv:1805.08673

work page Pith review arXiv
[4]

Carmesin, R

J. Carmesin, R. Diestel, M. Hamann, and F. Hundertmark, k-Blocks: a connectivity invariant for graphs, SIAM J. Disc. Math. , 28(4) (2014), 1876-1891

work page 2014
[5]

Chudnovsky, J

M. Chudnovsky, J. Geelen, B. Gerards, L. Goddy, M. Lohman, a nd P. Seymour, Non-zero A-paths in group-labelled graphs, Combinatorica 26 (2006), 521-532

work page 2006
[6]

Conlon, A New Upper Bound for the Bipartite Ramsey Problem, J

D. Conlon, A New Upper Bound for the Bipartite Ramsey Problem, J. Graph Theory 58.4 (2008), 351-356

work page 2008
[7]

Davenport, On the addition of residue classes, Journal of the London Mathematical Society 22 (1947), 100-101

H. Davenport, On the addition of residue classes, Journal of the London Mathematical Society 22 (1947), 100-101

work page 1947

Show all 16 references

[8]

Erd˝ os and L

P. Erd˝ os and L. P´ osa, On independent circuits contained in a gr aph, Canad. J. Math. 17 (1965), 347-352

1965
[9]

Gallai, Maximum-minimum S¨ atze und verallgemeinerte Faktoren von Graphen, Acta Math- ematica Scientiarum Hungaricae 12 (1961) 131-173

T. Gallai, Maximum-minimum S¨ atze und verallgemeinerte Faktoren von Graphen, Acta Math- ematica Scientiarum Hungaricae 12 (1961) 131-173

1961
[10]

Hall, The Theory of Groups, AMS Chelsea Pub

M. Hall, The Theory of Groups, AMS Chelsea Pub. (1999)

1999
[11]

Huynh, F

T. Huynh, F. Joos, and P. Wollan, A Uniﬁed Erd˝ os-P´ osa Theor em for Constrained Cycles, Combinatorica 39 (2019), 91-133

2019
[12]

Mader, ¨Uber die Maximalzahl kreuzungsfreier H-Wege, Archiv der Mathematik (Basel) 31 (1978) 387-402

W. Mader, ¨Uber die Maximalzahl kreuzungsfreier H-Wege, Archiv der Mathematik (Basel) 31 (1978) 387-402

1978
[13]

Robertson and P

N. Robertson and P. Seymour, Graph minors. X. Obstructions to tree-decomposition, J. Com- bin. Theory Ser. B 52 (1991), 153-190

1991
[14]

Robertson, P

N. Robertson, P. Seymour, and R. Thomas, Quickly Excluding a P lanar Graph, J. Combin. Theory Ser. B 62 (1994), 323-348

1994
[16]

Wollan, Packing non-zero A-paths in an undirected model of group labeled graphs, J

P. Wollan, Packing non-zero A-paths in an undirected model of group labeled graphs, J. Com- bin. Theory Ser. B 100 (2010), 141-150. This material is based upon work supported by the National Science Foundation. Any opinions, ﬁndings, and conclusions or recommendations expresse...

2010

Pith tools

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

[1] [15]

Thomas, Y

R. Thomas, Y. Yoo, Packing cycles in undirected group-labelled g raphs, manuscript (2020)

work page 2020

[2] [1]

B¨ oltz, Erd˝ os-Posa Eigenschaften auf abelschen Gruppen , Master’s thesis, Ulm University (2018)

L. B¨ oltz, Erd˝ os-Posa Eigenschaften auf abelschen Gruppen , Master’s thesis, Ulm University (2018)

work page 2018

[3] [2]

Bruhn, M

H. Bruhn, M. Heinlein, and F. Joos, Frames, A-Paths, and the Erd˝ os–P´ osa Property,SIAM J. Disc. Math. , 32(2) (2018), 1246-1260. 21

work page 2018

[4] [3]

Packing A-Paths of Length Zero Modulo Four

H. Bruhn and A. Ulmer, Packing A-Paths of Length Zero Modulo Four, arXiv:1805.08673

work page Pith review arXiv

[5] [4]

Carmesin, R

J. Carmesin, R. Diestel, M. Hamann, and F. Hundertmark, k-Blocks: a connectivity invariant for graphs, SIAM J. Disc. Math. , 28(4) (2014), 1876-1891

work page 2014

[6] [5]

Chudnovsky, J

M. Chudnovsky, J. Geelen, B. Gerards, L. Goddy, M. Lohman, a nd P. Seymour, Non-zero A-paths in group-labelled graphs, Combinatorica 26 (2006), 521-532

work page 2006

[7] [6]

Conlon, A New Upper Bound for the Bipartite Ramsey Problem, J

D. Conlon, A New Upper Bound for the Bipartite Ramsey Problem, J. Graph Theory 58.4 (2008), 351-356

work page 2008

[8] [7]

Davenport, On the addition of residue classes, Journal of the London Mathematical Society 22 (1947), 100-101

H. Davenport, On the addition of residue classes, Journal of the London Mathematical Society 22 (1947), 100-101

work page 1947