REVIEW 1 major objections 3 minor 1 cited by
The vertex sets of subtrees of a tree
T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A family of subsets is the vertex-set family of subtrees of one tree exactly when its intersection graph is chordal, it has the finite Helly property, and it is well-founded.
desk verdict Strong ideas and clean writing, but the proof of the infinite main theorem has an unproven minimality step; worth a careful referee, not acceptance as is. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument is carried by the notion of a 'fleet': a family satisfying the two conditions, well-foundedness, and containing the ground set $W$. Any fleet can be extended to a maximal fleet by adding only two-element 'edge-ships'. The critical structural object is a 'disconnected meeting' — a nonempty intersection of finitely many ships whose edge-ships form a disconnected graph. Picking a minimal such meeting, the proof derives a contradiction either from the finite Helly property (if a short path joins two components) or from the chordal property (if a longer cycle appears), forcing every ship to induce a connected subgraph and hence a subtree of one tree.
What would settle it
To disprove Theorem 2.1, one would need a well-founded family $\mathcal{F}$ of subsets of some set $W$ satisfying both the chordal property and the finite Helly property for which no tree on $W$ realizes every member as a subtree vertex set. A concrete route would be to take the paper's counterexample 1.2, which fails only by an infinite descending chain, and attempt to eliminate the chain while preserving the two properties.
Extended reading notes
Core claim
The central result, Theorem 2.1, states that if a family $\mathcal{F}$ of subsets of a set $W$ has the chordal property, the finite Helly property, and is well-founded, then there exists a tree $T$ with vertex set $W$ such that every member of $\mathcal{F}$ is the vertex set of a subtree of $T$. The finite case is the special case where $W$ is finite, and the abstract's broader condition — no element of $W$ belongs to infinitely many infinite sets of $\mathcal{F}$ — also fits within the theorem. The proof attaches $W$ itself to the family, extends to a maximal 'fleet' by Zorn's lemma, and shows that a minimal disconnected 'meeting' would contradict either the Helly property or the chordal property.
Load-bearing premise
The load-bearing hypothesis is well-foundedness — that there is no countably infinite descending chain of intersections of family members; if it is dropped, the theorem is false, as the paper's counterexample shows.
Editorial extensions
If this is right
- Every finite family of subsets of a finite set with the chordal property and finite Helly property is representable as the vertex sets of subtrees of a single tree.
- The same holds for infinite families in which each element of the ground set belongs to only finitely many infinite member sets.
- A chordal graph with no countably infinite clique ordered in the special 'bad' way is the intersection graph of subtrees of a tree (Theorem 2.2).
- If every finite subgraph of a graph has path-width at most $k$, then the graph has a line-decomposition of width at most $k$ (Theorem 4.1).
Reading between the lines
- The well-foundedness hypothesis looks like the right infinite substitute for finiteness, and similar conditions may govern other compactness-style representation theorems beyond the line-width compactness proved here.
- The 'fleet' and 'minimal disconnected meeting' machinery might be adapted to the paper's open problem about representing sets as vertex sets of paths in a tree, or to produce a counterexample if its three natural necessary conditions are not sufficient.
- The line-width compactness result suggests that path-width for infinite graphs is better measured by line-width, and that other width parameters may have analogous well-foundedness-based proofs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper characterizes when a family F of subsets of a set W can be represented as the vertex sets of subtrees of a tree on the vertex set W. The finite case (and the case where no element of W belongs to infinitely many infinite members of F) is settled in Theorem 1.1, as a consequence of the more general Theorem 2.1: if F has the chordal property, the finite Helly property, and is well-founded in the sense defined in Section 2, then the desired tree exists. The paper also proves an infinite analogue of Tucker's interval-order theorem (Theorem 3.2), a strengthened version of Halin's theorem (Theorem 2.2), and applies these results to obtain a Thomas-type compactness theorem for the line-width of infinite graphs (Theorem 4.1).
Significance. The finite characterization is elegant and sharp: Example 1.2 shows that the two natural necessary conditions are not sufficient in general, so the well-foundedness hypothesis in Theorem 2.1 is meaningful and not vacuous. The paper is largely elementary and uses standard tools (Zorn's lemma, Tucker's theorem, Halin's example) in a clean way. The interval-ships theorem and the line-width compactness theorem are useful and interesting in their own right. The statements are parameter-free and the counterexample in 1.2 is convincing. However, the proof of the main theorem contains a gap at a load-bearing point, so the paper cannot be accepted in its present form.
major comments (1)
- [Section 2, proof of Theorem 2.1, after the definition of meetings] The proof asserts that well-foundedness implies the existence of a disconnected meeting A with no proper disconnected sub-meeting. This inference is not justified. The stated well-foundedness condition only rules out bad sequences of ships whose total intersection is nonempty; equivalently, it rules out descending chains of meetings with nonempty total intersection. It does not rule out a descending chain A_1 superset A_2 superset ... with empty intersection. For example, let W={1,2,3,...} and F={S_i={i,i+1,i+2,...}: i>=1} union {W}. This F has the chordal property and the finite Helly property, and it is well-founded, since any bad sequence would need strictly increasing indices, which forces the total intersection to be empty. Yet each S_i is a disconnected meeting (no edge-ships are present), and S_1 superset S_2 superset ... has empty intersection, so there is no minimal disconnected meeting. This example is not a maximal fleet, but the proof does not yet invoke maximality at the point where the minimality inference is made, and no argument is supplied to show that maximality repairs the inference. The step is load-bearing: in the proof of (3), the k=1 case uses 'no proper subset of A is a disconnected meeting' to obtain a contradiction, and the final contradiction relies on (3). The authors need to either prove that in a maximal fleet every descending chain of disconnected meetings has nonempty intersection, or replace the minimality argument with a different device.
minor comments (3)
- [Section 4, proof of Theorem 4.1] The statement 'By 3.2 applied to {S_v}, this is true if and only if for every finite subset U of W and every finite subset X of V(G), there is a linear order of U ...' is not the literal statement of Theorem 3.2; it is a compactness form that is essentially proved in the course of the proof of 3.2. Please state this compactness corollary explicitly or rephrase the citation so that the reader sees the exact theorem being used.
- [Section 2, definition of meeting] The parenthetical claim that well-foundedness implies every nonempty intersection of ships is an intersection of finitely many ships is stated without proof. If this fact is not needed for the argument, it should be deleted or marked as not used; if it is needed, a proof should be supplied.
- [End of proof of Theorem 2.1, chordal-violation case] In the paragraph where adding {a,b} is said to violate the chordal property, the family {P_1,...,P_m,{a,b}} should be specified to form an induced cycle of length at least four, since the chordal property only forbids induced cycles. As written, a non-induced cycle would not contradict chordality.
Circularity Check
No circularity: the proof derives the tree representation from independent hypotheses and standard prior results; no fitted input is renamed as a prediction.
full rationale
I found no circular step. Theorem 2.1 is a new sufficiency result: it assumes the chordal property, the finite Helly property, and well-foundedness, and constructs a tree via Zorn's lemma and maximal fleets. The construction does not presuppose the desired representation; the only uses of outside results are classical characterizations of chordal graphs as subtree intersection graphs (Suranyi/Gavril/Buneman), Halin's counterexample construction, and Tucker's finite interval theorem. The finite corollary is not assumed but follows from the same theorem. The self-citation to [6] is merely a pointer saying that the line-width definition was used there; it is not load-bearing for Theorem 4.1. The skeptical concern about the inference from well-foundedness to a minimal disconnected meeting is a proof-validity issue, not circularity: it questions whether the hypothesis implies the asserted minimality, but does not amount to the theorem assuming its conclusion or to a fitted parameter being relabeled as a prediction. Hence the appropriate finding is no significant circularity.
Assumptions & free parameters
assumptions (4)
- standard math Zorn's lemma (or the axiom of choice)
- standard math Tucker's finite interval characterization theorem (Theorem 3.1)
- standard math Finite chordal graph representation theorem (Surányi, Buneman, Gavril, Walter)
- standard math Halin's infinite chordal graph example and theorem
Cite this review
Pith. "Pith review of The vertex sets of subtrees of a tree." pith.science (2026). https://pith.science/paper/NHMW32K2
@misc{pith2026250603603,
author = {Pith},
title = {Pith review of: The vertex sets of subtrees of a tree},
year = {2026},
howpublished = {\url{https://pith.science/paper/NHMW32K2}},
note = {Machine review of arXiv:2506.03603}
}
abstract
Let $\mathcal{F}$ be a set of subsets of a set $W$. When is there a tree $T$ with vertex set $W$ such that each member of $\mathcal{F}$ is the set of vertices of a subtree of $T$? It is necessary that $\mathcal{F}$ has the Helly property and the intersection graph of $\mathcal{F}$ is chordal. We will show that these two necessary conditions are together sufficient in the finite case, and more generally, they are sufficient if no element of $W$ belongs to infinitely many infinite sets in $\mathcal{F}$.
Forward citations
Cited by 1 Pith paper
-
Asymptotic structure. III. Excluding a fat tree
Any graph lacking a c-fat tree minor can be quasi-isometrically approximated by a graph with line-width bounded in terms of the tree and c.
Reference graph
Works this paper leans on
-
[1]
A characterization of rigid circuit graphs
P. Buneman, “A characterization of rigid circuit graphs”,Discrete Math.9(1974), 205–212
work page 1974
-
[2]
The intersection graphs of subtrees in trees are exactly the chordal graphs
F. Gavril, “The intersection graphs of subtrees in trees are exactly the chordal graphs”,J. Combinatorial Theory, Ser. B16(1974), 47–56
work page 1974
-
[3]
A. Gy´ arf´ as and J. Lehel, “A Helly type problem in trees”, in:Combinatorial Theory and Appli- cations(P. Erd˝ os, A. R´ enyi and V. T. S´ os, eds.),Coll. Math. Soc. J. Bolyai4(1970), 571–584
work page 1970
-
[4]
On the representation of triangulated graphs in trees
R. Halin, “On the representation of triangulated graphs in trees”,European J. Combinatorics 5(1984), 23–28
work page 1984
-
[5]
Representation of a finite graph by a set of intervals on the real line
C. Lekkerkerker and J. Boland, “Representation of a finite graph by a set of intervals on the real line”,Fundamenta Mathematicae51(1962), 45–64
work page 1962
-
[6]
Path-width and additive quasi-isometries
T. Nguyen, A. Scott and P. Seymour, “Path-width and additive quasi-isometries”, manuscript, January 2025
work page 2025
-
[7]
The tree-width compactness theorem for hypergraphs
R. Thomas, “The tree-width compactness theorem for hypergraphs”, unpublished manuscript, https://thomas.math.gatech.edu/PAP/twcpt.pdf
-
[8]
Configurations in graphs of large minimum degree, connectivity, or chromatic Number
C. Thomassen. “Configurations in graphs of large minimum degree, connectivity, or chromatic Number”, inCombinatorial Mathematics: Proceedings of the Third International Conference, Annals of the New York Academy of Sciences555:1(1989), 402–412. 7
work page 1989
Show all 11 references
-
[9]
A structure theorem for the consecutive 1’s property
A. Tucker, “A structure theorem for the consecutive 1’s property”,J. Combinatorial Theory, Ser. B12(1972), 153–262
1972
-
[10]
Matroids and graphs
W. T. Tutte, “Matroids and graphs”,Trans. American Math. Soc.90(1959), 527–552
1959
-
[11]
Representations of chordal graphs as subtrees of a tree
J. R. Walter, “Representations of chordal graphs as subtrees of a tree”,J. Graph Theory2 (1978), 265–267. 8
1978
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.