On the reconstruction of trees from their chromatic symmetric functions

Mario Tomba; Michael Gonzalez; Rosa Orellana

REVIEW 3 major objections 5 minor 14 references

On the reconstruction of trees from their chromatic symmetric functions

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The smallest star-basis term of a tree's chromatic symmetric function is its leaf-component partition, and this yields a reconstruction of every tree of diameter less than six.

desk verdict A compact FPSAC proceedings paper whose main theorems live in the authors' companion preprint, with a new shorter proof of the diameter-five case that depends on a black-box proposition deferred to that companion. read the letter →

arxiv 2507.15986 v1 pith:IY2UVZ54 submitted 2025-07-21 math.CO

Michael Gonzalez , Rosa Orellana , Mario Tomba This is my paper · ORCID

classification math.CO MSC 05E0505C0505C1505A17

keywords chromaticsymmetricfunctionstarbasistreestreeisomorphismconjecturereconstructionleadingpartitionleafcomponentsdeletion-near-contraction

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 studies how much of a tree is visible in its chromatic symmetric function when the function is expanded in the star basis, the basis formed by chromatic symmetric functions of forests of stars. Its central claim is a structural theorem: for any forest $F$, the lexicographically smallest partition with a nonzero coefficient is always the leaf-component partition $\lambda_{\mathrm{LC}}(F)$, obtained by deleting all internal edges, and that coefficient equals $(-1)^m\prod_{i=1}^m(\deg(u_i)-1)$, where $u_1,\ldots,u_m$ are the deep vertices of $F$. From that theorem the paper reads off adjacencies between leaf components from nearby coefficients, and then proves that every tree of diameter less than six can be explicitly reconstructed from its chromatic symmetric function. This matters because a long-standing conjecture predicts that the chromatic symmetric function distinguishes all non-isomorphic trees; the paper adds a new infinite family for which the distinction is not just true but constructive.

What carries the argument

The load-bearing object is the leading partition $\lambda_{\mathrm{lead}}(X_T)$, the lexicographically smallest partition with nonzero star-basis coefficient; Theorem 4.4 identifies it with the leaf-component partition $\lambda_{\mathrm{LC}}(T)$, the orders of the star components of $T\setminus I(T)$. The coefficient formula $(-1)^m\prod(\deg(u_i)-1)$ is the matching number that certifies which terms matter. The computational engine is the deletion-near-contraction (DNC) relation, which writes $X_G$ as a signed combination of $X_{G\setminus e}$, $X_{(G\odot e)\setminus \ell_e}$, and $X_{G\odot e}$, giving star-basis coefficients as signed counts of paths in a DNC tree. For reconstruction, the adjacent leaf-component endpoints are recovered via the adjacency multisets $E_\mu =\lambda_{\mathrm{lead}}-\mu$ from Proposition 4.13, and for diameter five the proof splits the tree along the central internal edge using Proposition 5.8, which recovers the product $X_{T_1}X_{T_2}$ and the two vertex counts from $X_T$.

What would settle it

Enumerate all non-isomorphic trees with at most twelve vertices, compute the star-basis expansion of each via deletion-near-contraction, and check two conditions: (1) the lexicographically smallest nonzero-indexing partition always equals $\lambda_{\mathrm{LC}}(T)$ with coefficient $(-1)^m\prod(\deg(u_i)-1)$; (2) no two non-isomorphic trees of diameter five have identical chromatic symmetric functions. The first failure of either condition would falsify the paper's central claim.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the star-basis expansion of the chromatic symmetric function of a tree $T$ is ordered by the tree's coarse shape. The connected components of $T\setminus I(T)$, where $I(T)$ is the set of internal edges, are stars; their orders form a partition $\lambda_{\mathrm{LC}}(T)$ called the leaf-component partition. Theorem 4.4 states that $\lambda_{\mathrm{LC}}(T)$ is exactly the leading partition, the smallest partition in lexicographic order with $c_\lambda\neq 0$ in $X_T=\sum_{\lambda\vdash n} c_\lambda \mathrm{st}_\lambda$, and that the leading coefficient is $(-1)^m\prod_{i=1}^m(\deg(u_i)-1)$ over the deep vertices. Proposition 4.13 then shows that certain other nonzero coefficients encode the adjacencies between leaf components, and Theorems 5.5 and 5.9 use these data to reconstruct all trees of diameter four and five, with diameter at most three already reduced to stars and bi-stars. The proof is constructive: the reconstruction algorithm reads the leading partition and the relevant coefficients directly from $X_T$ and assembles the tree.

Load-bearing premise

The reconstruction argument depends on a companion-paper result: for a diameter-five tree $T$ with central internal edge $e$, the chromatic symmetric function of $T$ determines the product $X_{T_1}X_{T_2}$ of the two halves of $T\setminus e$, together with the two vertex counts. If that recovery step fails, the proof that all diameter-five trees can be reconstructed falls apart.

Editorial extensions

If this is right

Corollary 4.6: two trees with different leaf-component partitions cannot have the same chromatic symmetric function.
Corollary 4.9: bi-stars and extended bi-stars are distinguished from all trees by their chromatic symmetric function, giving an infinite family for which the isomorphism conjecture holds.
Corollary 4.15: if the leading partition has no parts equal to 1 and all parts distinct, the tree is fully reconstructible from its chromatic symmetric function.
Theorems 5.5 and 5.9: every tree of diameter four or five is reconstructible from its chromatic symmetric function, so together with stars and bi-stars all trees of diameter less than six are reconstructible.
Because the diameter itself can be computed from the chromatic symmetric function, the algorithm knows which reconstruction case applies without extra input.

Reading between the lines

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

The diameter-five reconstruction succeeds because the internal subgraph has exactly two leaf components; for diameter six the internal subgraph has more leaf components, and the paper leaves open whether the same coefficient-reading strategy yields enough adjacency data to recurse.
The coefficient formula offers a cheap invariant: for a tree with a given leading partition and a claimed multiset of deep-vertex degrees, any mismatch in the corresponding star-basis coefficient rules out isomorphism before any coloring is built.
One testable extension is to check whether Proposition 5.8's product-recovery statement holds for diameter-six trees when the central edge is replaced by a central path of length three; if it does, the inductive reconstruction could climb one more diameter class.

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

Quick take: this is a proceedings abstract that reads like an advertisement for the authors' longer preprint [8]. The genuinely new item here is a shorter proof of the diameter-five reconstruction (Theorem 5.9), and it's a nice proof sketch—but it leans on Proposition 5.8, which is quoted from [8] with no in-paper support. The other main results (leading partition formula, adjacency-multiset description, diameter-five theorem itself) are all stated as already proved in [8]. That's not a fatal flaw in a proceedings contribution, but it means the present text is not self-contained.

What's good: the exposition is clean, the examples are helpful, and the leading-partition theorem (Theorem 4.4) is a genuinely appealing result—if it's in [8], fine, but here it's stated without proof. The reconstruction algorithm for diameter at most 4 is actually executable from the data described, and the diameter-5 proof has a clever lexicographic extraction: from X_T1 X_T2, you read off λ_lead(X_T1) as the smallest α with c_{(N2,α)} ≠ 0. That's a smart move.

The soft spot is exactly what the stress-test note flags: Proposition 5.8 is load-bearing for the entire diameter-5 case, and the paper gives no sketch of it, just a citation to [8, Prop 5.26]. If that proposition is wrong, the whole section collapses. I checked the examples in the paper and the logic up to that point; nothing is circular, and the claimed formula for the leading coefficient matches the examples. But the reader can't verify the core step from the text alone.

The other worry is novelty accounting. The paper itself says the main theorems already appear in [8]. So as a standalone contribution, what's new is the shorter proof and the packaging. For an FPSAC proceedings, that's arguably fine; for a journal, the authors would need to either include the proofs or make clear this is a summary.

Verdict: worth sending to a referee, if the companion paper [8] is also available for checking. The referee should be asked to verify Proposition 5.8 and the leading-partition theorem. I would not cite this text in my own work; I'd cite [8] for the main results.

Referee Report

3 major / 5 minor

Summary. The paper studies the chromatic symmetric function X_T of a tree T in the star basis {st_λ}. It defines the leaf component partition λLC(T), states a theorem (quoted from [8]) identifying the leading partition of X_T with λLC(T), and gives a formula for its coefficient in terms of deep vertices. The paper then uses the leading partition and associated coefficient data to define adjacency multisets, and it provides algorithms for reconstructing trees of diameter at most five. The diameter-five reconstruction is presented as a shorter proof than the one in the authors' companion paper [8].

Significance. If the results quoted from [8] are correct, the paper gives an explicit reconstruction algorithm for all trees of diameter less than six, and the leading partition formula provides a compact and elegant invariant with consequences such as Corollary 4.6 and Corollary 4.9. The paper is well motivated, and the examples are helpful in illustrating the proposed constructions. Its main weakness is that nearly all load-bearing theorems are quoted from the companion paper, so the present text functions as an extended abstract rather than as a complete proof of the reconstruction claim.

major comments (3)

[Section 5, Proposition 5.8] The proof of Theorem 5.9, the paper's main new result, rests entirely on Proposition 5.8, which asserts that for a diameter-five tree T the product X_{T1}X_{T2} of the chromatic symmetric functions of the two components of T\e, together with the vertex counts N1 and N2, can be recovered from X_T. The proposition is cited as [8, Proposition 5.26] and no proof or sketch is given, even though it is the step that makes the entire inductive split possible. If that recovery step fails, the rest of the diameter-five reconstruction collapses. The manuscript therefore does not establish the diameter-five reconstruction on its own; at minimum, a proof or a detailed sketch of Proposition 5.8 should be included, or the dependency should be stated as an explicit assumption.
[Section 4, Theorem 4.4 and Proposition 4.13] The leading-partition theorem and the adjacency-multiset interpretation are quoted from [8] with no proofs: Theorem 4.4 is cited to [8, Theorems 4.16 and 4.29], and Proposition 4.13 is cited to [8, Proposition 5.14]. These results underpin Corollaries 4.6, 4.9, and 4.15, and also Theorem 5.4, which is used in both the diameter-four and diameter-five reconstructions. The examples in the paper are illustrative but do not replace a proof. The paper should either provide the missing arguments or explicitly separate the results proved here from those imported from [8].
[Section 5.1.2, proof of Theorem 5.9] Even accepting Proposition 5.8, the step extracting λlead(XT1) from the recovered product X_{T1}X_{T2} is not justified. The coefficient notation c_{(N2,α)} presumes an expansion of the product in the star basis, but no expansion rule is stated, and the claim that the smallest α with c_{(N2,α)}≠0 equals λlead(XT1) requires controlling all terms of X_{T2}, not only its leading term. This is a genuine gap in the proof as written.

minor comments (5)

[Title page] The e-mail address for the third author contains a typo: 'dartmouh.edu' should be 'dartmouth.edu'.
[Example 3.2] The DNC tree diagram is hard to read; labeling the root tree T and the star-forest leaves would make the displayed expansion easier to verify.
[Remark 5.3] The statement that 'the multiplicity of Eµ in ET is cµ' should be made more carefully, since cµ is in general a signed coefficient; the reader needs the nonnegativity that follows from Proposition 4.13 for the particular µ considered.
[Lemma 5.7] Lemma 5.7 is used in the proof of Theorem 5.9 but is stated without proof; a short argument or an explicit citation would improve readability.
[Proof of Theorem 5.9] The final uniqueness assertion ('it is clear that ...') would benefit from a sentence explaining why the two displayed trees are non-isomorphic when the leading partitions differ.

Circularity Check

3 steps flagged · score 4.0 of 10

No definitional circularity, but the flagship reconstruction proof is heavily load-bearing on the same authors' companion paper [8], especially Proposition 5.8.

self citation load bearing [Section 4, Theorem 4.4 and the paragraph after Example 4.3]
"In Section 4 of [8], we prove that this is always the case. We also give an elegant combinatorial formula for the leading coefficient. ... Theorem 4.4. [8, Theorem 4.16 and Theorem 4.29] Let F be a forest with n vertices. Then λlead(XF) = λLC(F). If in addition, F has deep vertices u1, . . . , um, then: cλlead = (−1)^m ∏ (deg(ui) − 1)."

This is the paper's first main structural result: the leading partition in the star-basis expansion is exactly the leaf-component partition, with a closed-form leading coefficient. The proof is not included here; it is wholly delegated to [8], a companion paper by the same authors. Every subsequent reconstruction step (Corollary 4.9, Proposition 4.13, Theorem 5.4, Theorem 5.9) relies on this theorem, so the derivation chain for the central claim terminates in a same-author citation rather than an in-paper proof.
self citation load bearing [Section 4, Proposition 4.13]
"Proposition 4.13. [8, Proposition 5.14] Assume that XT is the CSF of a tree of order n with leading partition λlead(XT) = (n^{m_n}, . . . , 1^{m_1}). Let µ ⊢ n such that c_µ ≠ 0 in XT, ℓ(µ) = ℓ(λlead(XT)) − 1, and µ contains no 1s. Then, (a) If m1 = 0, then E_µ = { {p, q} }, where p and q are orders of two adjacent leaf components in T. And c_µ is the number of internal edges with leaf component endpoints of orders p and q."

The adjacency-recovery proposition is the mechanism by which the paper turns coefficients of XT into leaf-component adjacencies and computes N(p) in Equation (5.1). It is quoted from the same authors' companion [8] without proof. The diameter-4 and diameter-5 reconstruction algorithms depend directly on this proposition, so again the core input-to-structure step is supported only by a self-citation.

1 more flagged steps

self citation load bearing [Section 5, Proposition 5.8 and the proof of Theorem 5.9]
"In [8], we prove the result below. However, we include here a shorter inductive proof that did not appear in [8]. ... Proposition 5.8. [8, Proposition 5.26] Let XT be the CSF of a tree T with diameter five and λlead = λlead(XT) = (n^{m_n}, . . . , 1^{m_1}). Let e be the internal edge in IT, the internal subgraph of T, and let T \ e = T1 ⊔ T2. Then, XT1 XT2 can be recovered from XT. Further, #V(T1) and #V(T2) can be recovered from XT."

This is the hinge of the paper's flagship new proof: Theorem 5.9 splits T along the central internal edge e and assumes the product XT1 XT2 and the two vertex counts are recoverable from XT. All subsequent extraction of λlead(XT1), the leaf-component orders, and the final reconstruction depends on this proposition. Yet no proof or even a sketch is given in this paper; it is cited as [8, Proposition 5.26]. If that proposition were not independently established, the diameter-five reconstruction would be unsupported. This is the clearest case of a load-bearing same-author citation in the paper.

full rationale

There is no definitional circularity: no coefficient is defined so that λlead automatically equals λLC, no equation is engineered to reproduce the target tree, and no fitted parameter is renamed as a prediction. The reconstruction algorithm genuinely processes XT into structural data. However, the paper is not self-contained: Theorem 4.4, Proposition 4.13, Theorem 5.4, and Proposition 5.8, which form the backbone of the reconstruction, are all imported from the same authors' companion paper [8] with no in-paper proofs. In particular, Proposition 5.8 is the unproved black box that makes the inductive split in Theorem 5.9 work. This raises the circularity score to 4: substantial same-author self-citation is load-bearing, but the cited statements are external mathematical claims with independent content rather than renamings of the paper's own inputs. If [8] is correct, the conclusions follow without any reduction-by-construction.

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

No free parameters, fitted constants, or invented entities appear. The paper is a purely combinatorial derivation that relies on prior theorems, especially the DNC relation from [1] and several results from the authors' companion paper [8].

assumptions (4)

standard math The DNC relation X_G = X_{G\e} - X_{(G⊙e)\ℓe} + X_{G⊙e} holds for any edge e, and leaf-edge reductions X_G = X_{G⊙e} hold.
Quoted from [1] and used for all star-basis coefficient computations in Section 3.
standard math The star functions {st_λ} form a basis of the space of degree-n symmetric functions.
From Cho and van Willigenburg [3]; the entire expansion X_T = Σ c_λ st_λ depends on it.
domain assumption Coefficients c_λ count signed paths in a DNC tree, as stated in Remark 3.3.
This path-counting interpretation is used to justify combinatorial formulas and is inherited from the DNC algorithm in [1] and [8].
domain assumption Theorem 4.4, Corollary 4.9, Proposition 4.13, Theorem 5.4, and Proposition 5.8 are correct as stated in the companion paper [8].
These are load-bearing for reconstruction and are cited to [8] without proof in the present text.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the reconstruction of trees from their chromatic symmetric functions." pith.science (2026). https://pith.science/paper/IY2UVZ54

@misc{pith2026250715986,
  author       = {Pith},
  title        = {Pith review of: On the reconstruction of trees from their chromatic symmetric functions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IY2UVZ54}},
  note         = {Machine review of arXiv:2507.15986}
}

read the original abstract

We study Stanley's chromatic symmetric function (CSF) for trees when expressed in the star basis. We use the deletion-near-contraction (DNC) algorithm to compute coefficients that occur in the CSF in the star basis. In particular, one of our main results determines the smallest partition in lexicographic order that occurs as an indexing partition in the CSF, and we also give a formula for its coefficient. In addition to describing properties of trees encoded in the coefficients of the star basis, we give an algorithm for reconstructing trees of diameter less than six.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

[8]

The chromatic symmetric function in the star- basis

M. Gonzalez, R. Orellana, and M. Tomba. “The chromatic symmetric function in the star- basis”. 2024. arXiv:2404.06002

arXiv 2024
[1]

Marked Graphs and the Chromatic Symmetric Function

J. Aliste-Prieto, A. de Mier, R. Orellana, and J. Zamora. “Marked Graphs and the Chromatic Symmetric Function”. SIAM Journal on Discrete Mathematics 37.3 (2023), pp. 1881–1919

work page 2023
[2]

Proper caterpillars are distinguished by their chromatic symmetric function

J. Aliste-Prieto and J. Zamora. “Proper caterpillars are distinguished by their chromatic symmetric function”. Discrete Mathematics 315 (2014), pp. 158–164

work page 2014
[3]

Chromatic bases for symmetric functions

S. Cho and S. van Willigenburg. “Chromatic bases for symmetric functions”. Electron. J. Combin. 23.1 (2016), Paper 1.15, 7

work page 2016
[4]

A note on distinguishing trees with the chromatic symmetric function

L. Crew. “A note on distinguishing trees with the chromatic symmetric function”. Discrete Math. 345.2 (2022), Paper No. 112682, 4. doi

work page 2022
[5]

A deletion–contraction relation for the chromatic symmetric func- tion

L. Crew and S. Spirkl. “A deletion–contraction relation for the chromatic symmetric func- tion”. European Journal of Combinatorics 89 (2020), p. 103143

work page 2020
[6]

Schur and e-positivity of trees and cut vertices

S. Dahlberg, A. She, and S. van Willigenburg. “Schur and e-positivity of trees and cut vertices”. Electron. J. Combin. 27.1 (2020), Paper No. 1.2, 22. doi

work page 2020
[7]

A chromatic symmetric function in noncommuting vari- ables

D. D. Gebhard and B. E. Sagan. “A chromatic symmetric function in noncommuting vari- ables”. J. Algebraic Combin. 13.3 (2001), pp. 227–255. doi

work page 2001

Show all 14 references

[9]

On an algorithm for comparing the chromatic symmetric functions of trees

S Heil and C Ji. “On an algorithm for comparing the chromatic symmetric functions of trees”. Australasian Journal of Combinatorics 75.2 (2019), pp. 210–222

2019
[10]

Isomorphism of Weighted Trees and Stanley’s Isomorphism Conjecture for Caterpillars

M. Loebl and J.-S. Sereni. “Isomorphism of Weighted Trees and Stanley’s Isomorphism Conjecture for Caterpillars”. Annales de l’Institut Henri Poincaré D (Jan. 2018). doi

2018
[11]

A rooted variant of Stanley’s chromatic symmetric function

N. A. Loehr and G. S. Warrington. “A rooted variant of Stanley’s chromatic symmetric function”. Discrete Math. 347.3 (2024), Paper No. 113805, 18. doi

2024
[12]

On distinguishing trees by their chromatic symmetric functions

J. L. Martin, M. Morin, and J. D. Wagner. “On distinguishing trees by their chromatic symmetric functions”. Journal of Combinatorial Theory, Series A 115.2 (2008), pp. 237–253

2008
[13]

A symmetric function generalization of the chromatic polynomial of a graph

R. P . Stanley. “A symmetric function generalization of the chromatic polynomial of a graph”. Adv. Math. 111.1 (1995), pp. 166–194

1995
[14]

D. West. Introduction to Graph Theory. Prentice Hall, 1996

1996

Pith tools

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

[1] [8]

The chromatic symmetric function in the star- basis

M. Gonzalez, R. Orellana, and M. Tomba. “The chromatic symmetric function in the star- basis”. 2024. arXiv:2404.06002

arXiv 2024

[2] [1]

Marked Graphs and the Chromatic Symmetric Function

J. Aliste-Prieto, A. de Mier, R. Orellana, and J. Zamora. “Marked Graphs and the Chromatic Symmetric Function”. SIAM Journal on Discrete Mathematics 37.3 (2023), pp. 1881–1919

work page 2023

[3] [2]

Proper caterpillars are distinguished by their chromatic symmetric function

J. Aliste-Prieto and J. Zamora. “Proper caterpillars are distinguished by their chromatic symmetric function”. Discrete Mathematics 315 (2014), pp. 158–164

work page 2014

[4] [3]

Chromatic bases for symmetric functions

S. Cho and S. van Willigenburg. “Chromatic bases for symmetric functions”. Electron. J. Combin. 23.1 (2016), Paper 1.15, 7

work page 2016

[5] [4]

A note on distinguishing trees with the chromatic symmetric function

L. Crew. “A note on distinguishing trees with the chromatic symmetric function”. Discrete Math. 345.2 (2022), Paper No. 112682, 4. doi

work page 2022

[6] [5]

A deletion–contraction relation for the chromatic symmetric func- tion

L. Crew and S. Spirkl. “A deletion–contraction relation for the chromatic symmetric func- tion”. European Journal of Combinatorics 89 (2020), p. 103143

work page 2020

[7] [6]

Schur and e-positivity of trees and cut vertices

S. Dahlberg, A. She, and S. van Willigenburg. “Schur and e-positivity of trees and cut vertices”. Electron. J. Combin. 27.1 (2020), Paper No. 1.2, 22. doi

work page 2020

[8] [7]

A chromatic symmetric function in noncommuting vari- ables

D. D. Gebhard and B. E. Sagan. “A chromatic symmetric function in noncommuting vari- ables”. J. Algebraic Combin. 13.3 (2001), pp. 227–255. doi

work page 2001