On Calculating the Chromatic Symmetric Function

Nima Amoei Mobaraki; Sina Ghasemi Nezhad; Yasaman Gerivani

REVIEW 3 major objections 5 minor 19 references

On Calculating the Chromatic Symmetric Function

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

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

Pith's one-line read This paper claims a route-based identity that expands any graph's chromatic symmetric function in a forest basis, plus a subgraph-count formula for monomial coefficients.

desk verdict The route/march framework is a genuine contribution, but Section 4's m-basis formula is wrong as stated; the paper needs major revision before it can be used reliably. read the letter →

arxiv 2411.13411 v2 pith:T24GFS3Y submitted 2024-11-20 math.CO

Nima Amoei Mobaraki , Yasaman Gerivani , Sina Ghasemi Nezhad This is my paper · ORCID

classification math.CO MSC 05E0505C3105C15

keywords chromaticsymmetricfunctionforest-basisroutemarchU-polynomialmonomialbasisreconstructionconjecture

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 establish that the chromatic symmetric function of every graph can be computed in a basis made from forests, using a graph-level operation instead of algebraic machinery. The operation is a 'route': a sequence of valid edge swaps from one graph to another, with each swap accompanied by two smaller remainder graphs; applying the step relation along a route expresses one graph's CSF as another graph's CSF plus an alternating sum of smaller CSFs. From this identity, the paper derives that any infinite family of trees with one tree of each size gives a $\mathbb{Q}$-basis of the symmetric functions in $n$ variables, with algebraically independent generators, and it gives a separate formula for monomial coefficients in terms of induced-subgraph counts. If the arguments hold, they put forest-basis coefficient extraction on a purely graph-theoretic footing, recover the known U-polynomial equivalence for forests combinatorially, and subsume an earlier star-basis algorithm as a special case.

What carries the argument

The central object is a 'step' between graphs: if $v_1v_2$ and $v_1v_3$ are edges while $v_2v_3$ is not, the step replaces $v_1v_3$ by $v_2v_3$ and records remainders $P_1 = G - v_1v_2$ and $N_1 = G - \{v_1v_2, v_1v_3\} + v_2v_3$, each with one fewer edge. A 'route' is a sequence of valid steps and a 'march' is the list of all remainders; the march identity (Equation (2)) is the load-bearing relation, reducing a CSF to a target graph plus an alternating sum of smaller graphs. This reduction drives the forest-basis expansions and the spanning arguments. For the monomial-coefficient theorem, the mechanism is a double-counting of independent partitions: every independent partition of $G$ with nontrivial parts is inherited from an independent partition of some $k$-vertex induced subgraph, and the binomial factor $\binom{n-m}{k-m}$ counts how many ways the $1$-parts are chosen.

What would settle it

Compute both sides of Theorem 4.3 by hand for a small graph, such as a 5-vertex tree and all 3-vertex graphs: if $c^G_{\lambda_1}$ differs from $\binom{n-m}{k-m}^{-1} \sum_H c^H_{\lambda_2} \binom{G}{H}$, the formula is false. Separately, run Proposition 3.7 on the 4-cycle: the prescribed first step removes and re-adds edge $v_2v_3$, and the second step tries to remove an edge that is no longer present, so the claimed route fails; that failure exposes the gap in the spanning proof.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a route identity: if $R = (G_1, \ldots, G_k)$ is a route between graphs, then $X_{G_1} = X_{G_k} + \sum_{i=1}^{k-1} X_{P_i} - \sum_{i=1}^{k-1} X_{N_i}$, where every $P_i$ and $N_i$ has one fewer edge than $G_1$. Iterating this identity along a route to a path forest or star forest produces expansions in a forest-basis; Theorem 3.11 then asserts that for any infinite family of trees $\{T_k\}$ with $|V(T_k)| = k$, the set $\{X_{T_\lambda} : \lambda \vdash n\}$ is a $\mathbb{Q}$-basis of $\Lambda_n$ and the $X_{T_k}$ are algebraically independent. In the monomial basis, Theorem 4.3 asserts $c^G_{\lambda_1} = \binom{n-m}{k-m}^{-1} \sum_H c^H_{\lambda_2} \binom{G}{H}$, where $\lambda_1 \sim \lambda_2$, $\lambda_1^* \vdash m$, $\lambda_2 \vdash k$, and the sum runs over all $k$-vertex graphs $H$. The same machinery gives combinatorial proofs of the known chromatic-basis theorem and of the equivalence between the CSF and the U-polynomial on forests, and it frames an existing DNC-based algorithm as one routing strategy.

Load-bearing premise

The load-bearing premise is that every graph containing a cycle of length greater than 3 can be turned into a triangle-containing graph by the paper's prescribed sequence of valid edge swaps, one step at a time, on simple graphs; if that sequence is not a valid route for some graph, the inductive proof that forest-bases span all graphs has a gap.

Editorial extensions

If this is right

If Theorem 3.11 is right, coefficient extraction in any forest-basis becomes a finite graph-theoretic elimination process: route to a forest in the basis, record remainders, and repeat.
The route identity also holds for the U-polynomial on forests, so the paper's combinatorial proof that equal CSF and equal U-polynomial coincide for forests goes through.
Theorem 4.3 turns monomial-basis coefficients of a graph into induced-subgraph counts of smaller graphs, making the coefficients computable from a triangular linear system.
The earlier star-basis algorithm falls out as one choice of routing, so changing bases corresponds to changing the routing strategy.
As a corollary, the ring of symmetric functions is generated by the CSFs of any chosen infinite family of trees, with no algebraic relations among those generators.

Reading between the lines

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

Beyond the paper: the step relation is almost an axiomatic identity; any graph invariant satisfying the same one-step equation would inherit forest-basis expansions and the rank consequences, so one can screen other polynomials for this property.
Beyond the paper: Theorem 4.3 suggests a concrete algorithm for monomial coefficients, assembling the triangular $\lambda$-matrix from complete multipartite graphs and solving for a graph's coefficient vector from its induced-subgraph counts; the complexity of that elimination is not analyzed in the paper.
Beyond the paper: the reconstruction-inspired counting may be testable as a constraint solver: for a tree, the coefficient vector plus the full-rank matrix restricts but does not determine the deck, and the paper's dimension argument shows exact reconstruction is impossible.

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

Thanks for the report. I read the full arXiv version. The route/march idea in Section 3 is the real contribution. Defining a step via the Orellana–Scott relation and iterating it to get Equation (2) is clean, and the proof of Lemma 3.16 — that the same step identity holds for the U-polynomial — is a genuinely nice observation. The result that these routes connect forests exactly when their partitions match is correct, and the DNC algorithm of Aliste-Prieto et al. really does appear as a special case. I also think the authors' decision to state their basis theorem as weaker than Cho–van Willigenburg is honest and appropriate.

That said, the paper has two serious problems. The first is in Section 4. Theorem 4.3 is stated for m_λ-basis coefficients, but the proof counts independent λ-partitions. Those two numbers differ by ∏ m_i!. You can see it immediately with K_2: the number of independent (1,1)-partitions is 1, yet X_{K_2}=2m_{(1,1)}. So Theorem 4.3, Lemma 4.5, and the proof of Corollary 4.6 are false as written. The full-rank claim is salvageable because the true transition matrix from the K_λ to the m-basis is a column scaling of the independent-partition matrix, so both have full rank. But the paper does not say this, and Lemma 3.9 rests on the invalid proof. The second issue is Proposition 3.7: the construction that routes any cyclic graph to a triangle is not well-defined — after the first step the edge v2v3 is gone, and the case where a chord already exists makes the proposed operation invalid on simple graphs. This leaves a real gap in the proof that forests generate all of Λ_n. A third, smaller point: Corollary 3.22 is supposed to follow from Theorem 3.21, but when X_F1=X_F2 the corner number is not finite, so the theorem does not apply.

The surprising thing is that the central claims are probably true. The route framework is sound, and the full-rank result can be repaired. But the paper as written is not reliable: the m-basis formula is simply wrong. This is not a desk-reject-level manuscript. It deserves a serious referee, and if the authors fix the Section 4 factor and repair the routing proof, it could become a usable paper for people computing CSFs in forest and star bases.

Referee Report

3 major / 5 minor

Summary. The paper introduces graph-theoretic 'steps' and 'routes' and derives a marching formula (Equation (2)) that expresses the chromatic symmetric function (CSF) of a graph in terms of the CSF of another graph connected by a route plus a telescoping sum of remainder graphs with one fewer edge. On this basis, the paper aims to prove that for any family of trees {T_k}, the set {X_{T_λ} : λ⊢n} is a Q-basis of Λ_n; to give a combinatorial proof that X_{F1}=X_{F2} iff U_{F1}=U_{F2} for forests; and to provide a relation for computing coefficients of X_G in the m_λ-basis. The paper also claims as applications a proof of the Cho–van Willigenburg chromatic-basis theorem for forests and a reinterpretation of the Aliste-Prieto–de Mier–Orellana–Zamora star-basis algorithm.

Significance. If the main claims hold, the route formula (Equation (2)) is a clean and useful identity for computing chromatic symmetric functions in forest bases, and the paper would supply a combinatorial proof of the known forest-basis theorem and of the Noble–Welsh equivalence between the U-polynomial and the CSF on forests. The proof of Lemma 3.16, showing that the step relation holds also for U-polynomials on forests, is a genuine contribution. The proposed m-basis computation in Section 4 is currently incorrect as stated, but the underlying counting idea is close to a correct method after inserting the standard multiplicity factor. Because each of the identified problems is local and repairable, the paper has the potential to become a solid contribution, but the current version requires substantial revision.

major comments (3)

[Proposition 3.7] The proof that every graph containing a cycle can be routed to a triangle-containing graph is invalid. The sequence G_i is defined by 'removing the edge v2v3 and adding the edge v2v_{i+2}' for each i, but after the first operation the edge v2v3 is no longer present, and if v2v_{i+2} is already an edge, the operation is not a legal step on simple graphs. Therefore the displayed sequence is not a route, and the proofs of Lemma 3.8 and Corollary 3.13, which rely on this proposition, have a gap. The statement itself is likely true and can be repaired by a different argument: a cycle of length g>3 can be shortened to a cycle of length g-1 in one step (remove v_i v_{i+1} and add v_{i-1} v_{i+1}), so the proposition is salvageable, but the proof as written must be replaced.
[Theorem 4.3 / Lemma 4.5 / Corollary 4.6] The paper conflates the number of independent λ-partitions of G with the coefficient c^G_λ of m_λ in X_G. These differ by the factor ∏_i m_i!, where m_i is the multiplicity of part i in λ. For example, for G=K_2 and λ=(1,1), there is one independent partition but c^G_{(1,1)}=2. The proof of Theorem 4.3 enumerates independent λ1-partitions, so it proves a statement about p^G_λ, not about m-basis coefficients; the stated binomial factor is correct for p. Lemma 4.5's assertion that c^{K_λ}_λ=1 is false in the m-basis when λ has repeated parts (for instance, c^{K_{(2,2)}}_{(2,2)}=2 for C_4), and therefore Corollary 4.6's proof of full rank, which is used in Lemma 3.9 and hence in Theorem 3.11, is invalid as written. The full-rank conclusion is repairable: the actual coefficient matrix is a column scaling of the independent-partition matrix with nonzero diagonal entries, but the manuscript must state the corrected relation and redo the proof.
[Corollary 3.22 / Theorem 3.21] The advertised proof of the equivalence X_{F1}=X_{F2} iff U_{F1}=U_{F2} is incomplete. If X_{F1}=X_{F2} and X_{F2}∈B, then the corner number in Definition 3.20 is not finite, so Theorem 3.21 cannot be invoked. The forward direction can be recovered by applying Proposition 3.19 for every k, but this argument is not given. The reverse direction is also not covered, because Theorem 3.21 only provides equality of coefficients at levels up to the corner level and says nothing about the level at which the first difference occurs; one must use the definition of the corner number to rule out that difference, which the proof does not do. Thus the paper's claim to provide a combinatorial proof of the U-polynomial/CSF equivalence rests on a load-bearing gap.

minor comments (5)

[Definition 3.20] There is a typo in the definition of the corner number: 'X^k_{G,B} ≠ X_{F'}' should read 'X^k_{F,B} ≠ X_{F'}'. The definition should also explicitly state what happens when no such finite k exists, since that case is needed in Corollary 3.22.
[Lemma 3.2] The base case for n=1,2 is not handled, since P_n has no stepable graph for those n; the proof should treat these small cases separately.
[Proposition 3.15] The indexing in the observation 'N_i = P_{i+1} for each 0 ≤ i ≤ k-2' does not match the index ranges of the march (P_i and N_i are indexed from 0 to k-1), which makes the cancellation argument hard to follow.
[Definition 4.1] In Definition 4.1, the phrase 'for every P ∈ A' uses an undefined symbol A; it should refer to the collection P of blocks.
[Throughout] There are numerous typographical errors (e.g., 'chroma tic', 'U niversity', 'deﬁned'), and the statement of Theorem 3.21 contains an apparent dimension mismatch: it says 'for all λ ⊢ n such that ℓ(λ) ≤ k', where k is the corner number, but the meaningful bound should involve ℓ(μ)+k.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the route and basis arguments derive from the Orellana–Scott relation and induction on edge count, not from the conclusions.

full rationale

The central route formula (Eq. (2)) is obtained by iterating Corollary 2.9, an external relation of Orellana and Scott that follows from the definition of the chromatic symmetric function; it does not assume the forest-basis or m-basis results it is used to prove. Lemma 3.6 and Lemma 3.8 establish spanning by induction on the number of edges: every route remainder has one fewer edge, the terminal basis graph is a member of the basis, and the triangle case is handled by Theorem 2.8. The dimension bound needed for Theorem 3.11 is Lemma 3.9, proved in Section 4 through the full-rank λ-matrix of complete multipartite graphs Kλ; the triangular support argument for Kλ is independent of the forest-basis theorem. The paper cites prior work by Orellana–Scott, Noble–Welsh, Cho–van Willigenburg, and Aliste-Prieto–de Mier–Orellana–Zamora, all external to the present authors, and none of the citations replaces a step that the paper must prove. The reader-identified weaknesses—the routing argument in Proposition 3.7 for cycles of girth greater than 3, and the conflation in Theorem 4.3 between independent-partition counts and m_λ coefficients—are potential correctness gaps, not circular derivations: in neither case is the target identity fed back as an assumption. Accordingly, no circular step is exhibited, and the appropriate score is 0.

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

No numbers are fitted: this is a pure combinatorics paper. The framework imports two external facts, the Orellana-Scott relation and the forest U-polynomial identity, and uses the standard interpretation of monomial coefficients as counts of independent set partitions. No new entities are postulated.

assumptions (4)

standard math The Orellana-Scott triangle relations, Theorem 2.8 and Corollary 2.9, correctly express the CSF of a graph in terms of graphs with one fewer edge.
Invoked in Definition 3.1 and Equation (1) to build the march formula; accepted external theorem.
domain assumption For a forest F, the U-polynomial equals the sum over edge subsets A of x^{lambda(A)}, and coefficients in the monomial basis of a forest obey the zero-or-one support property used in Lemma 3.17.
Used in Remark 2.2 and Lemma 3.16; this identity is specific to forests and is imported from the cited literature.
standard math The CSF's monomial-basis coefficient c^G_lambda equals the number of independent set partitions of type lambda.
Underpins Theorem 4.3 and the lambda-matrix; follows from Stanley's definition after grouping colorings by color-class sizes.
standard math The symmetric function space Lambda_n over Q has dimension p(n), and graph vector spaces V(G_n) are finite-dimensional subspaces.
Used in Lemma 3.9 to convert spanning plus rank into a basis statement.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Calculating the Chromatic Symmetric Function." pith.science (2026). https://pith.science/paper/T24GFS3Y

@misc{pith2026241113411,
  author       = {Pith},
  title        = {Pith review of: On Calculating the Chromatic Symmetric Function},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T24GFS3Y}},
  note         = {Machine review of arXiv:2411.13411}
}

abstract

This paper investigates methods for calculating the chromatic symmetric function (CSF) of a graph in chromatic-bases and the $m_\lambda$-basis. Our key contributions include a novel approach for calculating the CSF in chromatic-bases constructed from forests and an efficient method for determining the CSF in the $m_\lambda$-basis. As applications, we present combinatorial proofs for two known theorems that were originally established using algebraic techniques. Additionally, we demonstrate that an algorithm introduced by Aliste-Prieto, de Mier, Orellana, and Zamora can be viewed as a case of our proposed method.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 16 canonical work pages

[1]

A symmetric function generalization of the ch romatic polynomial of a graph

Richard P Stanley. “A symmetric function generalization of the ch romatic polynomial of a graph”. In: Advances in Mathematics 111.1 (1995), pp. 166–194

work page 1995
[2]

A weighted graph polynomial f rom chromatic invariants of knots

Steven D Noble and Dominic JA Welsh. “A weighted graph polynomial f rom chromatic invariants of knots”. In: Annales de l’institut Fourier . Vol. 49. 3. 1999, pp. 1057–1087

work page 1999
[3]

A chromatic symmetric func tion in noncommuting variables

David D Gebhard and Bruce E Sagan. “A chromatic symmetric func tion in noncommuting variables”. In: Journal of Algebraic Combinatorics 13.3 (2001), pp. 227–255

work page 2001
[4]

Introduction to graph theory

Douglas Brent West et al. Introduction to graph theory . Vol. 2. Prentice hall Upper Saddle River, 2001

work page 2001
[5]

A survey of the reconstruction conjecture

Frank Harary. “A survey of the reconstruction conjecture” . In: Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973 . Springer. 2006, pp. 18–28

work page 1973
[6]

On dist inguishing trees by their chromatic symmetric functions

Jeremy L Martin, Matthew Morin, and Jennifer D Wagner. “On dist inguishing trees by their chromatic symmetric functions”. In: Journal of Combinatorial Theory, Series A 115.2 (2008), pp. 237–253

work page 2008
[7]

Graphs with equal chromatic symmetric functions

Rosa Orellana and Geoﬀrey Scott. “Graphs with equal chromatic symmetric functions”. In: Discrete Mathematics 320 (2014), pp. 1–14

work page 2014
[8]

Chromatic bases for symmetric functions

Soojin Cho and Stephanie van Willigenburg. “Chromatic bases for s ymmetric functions”. In: arXiv preprint arXiv:1508.07670 (2015)

work page Pith review arXiv 2015

Show all 19 references

[9]

Chromatic quasisymmetric functions

John Shareshian and Michelle L Wachs. “Chromatic quasisymmetric functions”. In: Advances in Math- ematics 295 (2016), pp. 497–551

2016
[10]

On tree s with the same restricted U-polynomial and the Prouhet–Tarry–Escott problem

Jos´ e Aliste-Prieto, Anna de Mier, and Jos´ e Zamora. “On tree s with the same restricted U-polynomial and the Prouhet–Tarry–Escott problem”. In: Discrete Mathematics 340.6 (2017), pp. 1435–1441

2017
[11]

On an algorithm for comparing the chromat ic symmetric functions of trees

Sam Heil and Caleb Ji. “On an algorithm for comparing the chromat ic symmetric functions of trees”. In: arXiv preprint arXiv:1801.07363 (2018)

2018 arXiv
[12]

Isomorphism of we ighted trees and Stanley’s isomorphism conjecture for caterpillars

Martin Loebl and Jean-S´ ebastien Sereni. “Isomorphism of we ighted trees and Stanley’s isomorphism conjecture for caterpillars”. In: Annales de l’institut Henri Poincar´ e D 6.3 (2019), pp. 357–384

2019
[13]

A deletion–contraction relation f or the chromatic symmetric function

Logan Crew and Sophie Spirkl. “A deletion–contraction relation f or the chromatic symmetric function”. In: European Journal of Combinatorics 89 (2020), p. 103143

2020
[14]

Marked graphs and the chromatic sy mmetric function

Jos´ e Aliste-Prieto et al. “Marked graphs and the chromatic sy mmetric function”. In: SIAM Journal on Discrete Mathematics 37.3 (2023), pp. 1881–1919

2023
[15]

A graph polynomial from chromatic s ymmetric functions

William Chan and Logan Crew. “A graph polynomial from chromatic s ymmetric functions”. In: Journal of Graph Theory 105.4 (2024), pp. 633–651

2024
[16]

The chroma tic symmetric function in the star- basis

Michael Gonzalez, Rosa Orellana, and Mario Tomba. “The chroma tic symmetric function in the star- basis”. In: arXiv preprint arXiv:2404.06002 (2024)

2024 arXiv
[17]

A proof of the Stanley-Stembridge conjec ture

Tatsuyuki Hikita. “A proof of the Stanley-Stembridge conjec ture”. In: arXiv preprint arXiv:2410.12758 (2024)

2024
[18]

A rooted variant o f Stanley’s chromatic symmetric function

Nicholas A Loehr and Gregory S Warrington. “A rooted variant o f Stanley’s chromatic symmetric function”. In: Discrete Mathematics 347.3 (2024), p. 113805

2024
[19]

Chromatic symmetric function s and change of basis

Bruce E Sagan and Foster Tom. “Chromatic symmetric function s and change of basis”. In: arXiv preprint arXiv:2407.06155 (2024). 17

2024 arXiv

Pith tools

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

[1] [1]

A symmetric function generalization of the ch romatic polynomial of a graph

Richard P Stanley. “A symmetric function generalization of the ch romatic polynomial of a graph”. In: Advances in Mathematics 111.1 (1995), pp. 166–194

work page 1995

[2] [2]

A weighted graph polynomial f rom chromatic invariants of knots

Steven D Noble and Dominic JA Welsh. “A weighted graph polynomial f rom chromatic invariants of knots”. In: Annales de l’institut Fourier . Vol. 49. 3. 1999, pp. 1057–1087

work page 1999

[3] [3]

A chromatic symmetric func tion in noncommuting variables

David D Gebhard and Bruce E Sagan. “A chromatic symmetric func tion in noncommuting variables”. In: Journal of Algebraic Combinatorics 13.3 (2001), pp. 227–255

work page 2001

[4] [4]

Introduction to graph theory

Douglas Brent West et al. Introduction to graph theory . Vol. 2. Prentice hall Upper Saddle River, 2001

work page 2001

[5] [5]

A survey of the reconstruction conjecture

Frank Harary. “A survey of the reconstruction conjecture” . In: Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973 . Springer. 2006, pp. 18–28

work page 1973

[6] [6]

On dist inguishing trees by their chromatic symmetric functions

Jeremy L Martin, Matthew Morin, and Jennifer D Wagner. “On dist inguishing trees by their chromatic symmetric functions”. In: Journal of Combinatorial Theory, Series A 115.2 (2008), pp. 237–253

work page 2008

[7] [7]

Graphs with equal chromatic symmetric functions

Rosa Orellana and Geoﬀrey Scott. “Graphs with equal chromatic symmetric functions”. In: Discrete Mathematics 320 (2014), pp. 1–14

work page 2014

[8] [8]

Chromatic bases for symmetric functions

Soojin Cho and Stephanie van Willigenburg. “Chromatic bases for s ymmetric functions”. In: arXiv preprint arXiv:1508.07670 (2015)

work page Pith review arXiv 2015