REVIEW 2 major objections 5 minor 22 references
Two infinite families of counterexamples to the Stanley--Gasharov conjecture
T0 review · 2 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read The Stanley–Gasharov conjecture is false for two infinite families of claw-free graphs, one of line graphs and one of non-line graphs, with explicit negative Schur coefficients.
desk verdict The transfer lemma is clean and gives one solid infinite family from the known G2 counterexample; the second family and minimality claims hinge on a single unshipped DP computation, so the referee should ask for code or independent verification. 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 Schur-coefficient transfer lemma (Lemma 3.3). It states that for any graph G, vertex v, and t≥1, the chromatic symmetric function of the graph B_t(G,v) obtained by joining a disjoint clique K_t to G by the single edge v–w satisfies ρ_t(X_{B_t(G,v)}) = (t−1)(t−1)! e_t(x_1,…,x_t) ρ_t(X_G), where ρ_t sets all but t variables to zero. Combined with the identity e_t s_λ = s_{λ+(1^t)} for partitions with at most t parts, this transfers a Schur coefficient of X_G to a Schur coefficient of X_{B_t(G,v)} with the same sign, scaled by (t−1)(t−1)!. This is the mechanism that turns the single counterexamples G_2 and Q into infinite ladders of counterexamples.
What would settle it
Recompute the Schur expansion of F_4 by an independent implementation and check that the coefficient of s_{(4,4,4,4)} equals −120; or rerun an independent enumeration of connected claw-free graphs on 13 to 21 vertices with 12 to 20 edges and check that none has a negative Schur coefficient.
Extended reading notes
Core claim
For every t≥4, the line graph F_t obtained by joining G_2 to a clique K_t by one edge satisfies ⟨s_{(4,4,4,4,1^{t-4})}, X_{F_t}⟩ = −40(t−1)(t−1)!, and for every t≥5, the non-line-graph Q_t obtained from Q by the same construction satisfies ⟨s_{(4,4,4,4,2,1^{t-5})}, X_{Q_t}⟩ = −144(t−1)(t−1)!. Since these coefficients are strictly negative, both families violate the conjecture. The construction is uniform: Lemma 3.3 shows that adjoining K_t to any graph at a vertex v multiplies the Schur coefficient indexed by λ by (t−1)(t−1)! and replaces λ by λ+(1^t), provided ℓ(λ)≤t. Applied to the base counterexamples G_2 (with negative coefficient −40) and Q (with −144), this yields the infinite families
Load-bearing premise
The load-bearing premise is that the exhaustive graph generation and the exact Schur-coefficient computations are complete and bug-free; if the searches missed any connected claw-free graph in the stated ranges, or if a negative coefficient were miscalculated, the minimality claims would collapse.
Editorial extensions
If this is right
- The Stanley–Gasharov conjecture is false as originally stated, and the failure is robust: there are infinitely many claw-free counterexamples, including line graphs and non-line graphs.
- The transfer lemma provides a general method to build new counterexamples from any graph with a negative Schur coefficient, so the phenomenon is not confined to the two base graphs.
- The minimality results give a complete picture of the small end: every connected claw-free graph with at most 11 vertices, or with 12 vertices and at most 20 edges, is Schur-positive; G_2 is the unique 12-vertex counterexample and Q the unique non-line-graph counterexample with 13 vertices.
- The non-line-graph family shows that even quasi-line graphs—the next structural class above line graphs—contain counterexamples, so the boundary of the conjecture lies strictly above line graphs.
Reading between the lines
- The transfer lemma is general: any graph with a negative Schur coefficient indexed by a partition with at most t parts yields an infinite family of larger graphs with negative coefficients. This suggests counterexamples to Schur-positivity are abundant and can be generated from a single seed by a uniform operation.
- The construction preserves claw-freeness only for carefully chosen attachment vertices (here v_3 in G_2 and u_1 in Q). It would be interesting to test whether the same amplification works for other claw-free base graphs with negative coefficients, or whether the choice of attachment vertex is forced by the claw-free condition.
- The exhaustive search boundaries suggest a threshold phenomenon: no counterexamples exist below sizes 12/21 or 13/27, but infinitely many exist above. A natural next question is whether every claw-free graph above some other threshold is non-Schur-positive, or whether counterexamples remain sparse in some density sense.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Stanley–Gasharov conjecture that every claw-free graph is Schur-positive, which was recently disproved by two independent pairs of authors. The manuscript constructs two infinite families of counterexamples. The first family consists of line graphs F_t (t≥4), obtained by adjoining K_t to the 12-vertex counterexample G_2 through a single bridge; the paper proves the Schur coefficient of (4,4,4,4,1^{t-4}) in X_{F_t} is −40(t−1)(t−1)!. The second family consists of non-line-graphs Q_t (t≥5), obtained from a new 13-vertex claw-free non-line-graph Q by the same bridge construction, with coefficient −144(t−1)(t−1)! of (4,4,4,4,2,1^{t-5}). The paper also reports exhaustive computations establishing that G_2 is the edge-first minimum counterexample and that Q is the minimum non-line-graph counterexample under both vertex-first and edge-first orders. The main theoretical tool is a transfer lemma (Lemma 3.3) showing that the bridge-plus-clique operation multiplies a chosen Schur coefficient by (t−1)(t−1)! and shifts the partition by a full column.
Significance. If the computational assertions are correct, the paper answers an explicit question of Matherne and Morales and gives the first infinite families of counterexamples, including a non-line-graph family. The transfer lemma is elementary, parameter-free, and rigorously proved; it is a clean contribution that may be useful beyond this example. The first family is robust because its base coefficient for G_2 comes from two independent external sources. The second family, however, rests entirely on the computed coefficient (4.3) for Q, for which no code, data, or independent verification is supplied; this is the main risk. The reported exhaustive censuses are extensive and internally consistent, but not independently auditable from the manuscript. Should the code and certificates be made available, the paper would be a solid and significant contribution. The paper is honest about the computational nature of several proofs and provides useful structural context via quasi-line graphs and Chudnovsky–Seymour theory.
major comments (2)
- [§4.1, Eq. (4.3)] The coefficient [s_(3,3,3,3,1)]X_Q = −144 is asserted from 'a direct exact computation' using the frontier-connectivity DP of §2.2, but no code, data, or independent confirmation is provided. This value is the sole base input for the second infinite family Q_t (Theorem 4.4, Eq. (4.6)) and for the non-line-graph minimality claims. If this coefficient is incorrect, the entire Q_t family and the non-line-graph minimality results collapse. Please make the computation checkable by supplying the program, the power-sum expansion of X_Q, and the final Schur-coefficient table, or provide an independent verification by a different method.
- [§2.3 and §4.1, Tables 1–3] The exhaustiveness claims for the edge-first and vertex-first censuses are not auditable. The paper states that geng generated 144,492 graphs in §2 and 16,087,992 in §4, and that a DP and a line-graph filter were applied, but no code, logs, hashes, or output files are included. Propositions 2.1 and 4.2 depend on the correctness and completeness of these computations, as does the uniqueness of Q. Please archive the full computational pipeline (generator inputs, filters, and result files) or provide a certificate, such as the list of all found negative coefficients and the exact commands used to produce each row of Tables 1–3.
minor comments (5)
- [Throughout] The conjecture is consistently called 'Lemma 1.1' after the introduction (e.g., §1, §2, Proposition 2.1, Theorem 3.4). This should be 'Conjecture 1.1'.
- [§3, proof of Theorem 3.4] The proof references 'Lemma 3.1' and 'Lemma 3.4', but the intended statements are Proposition 3.1 and Theorem 3.4. Fix the cross-references.
- [§4.1, Eq. (4.4)] The sentence 'each non-claw obstruction has at least seven edges' is terse and unsupported. Since this bound helps define the search range, please give a reference to Beineke's list or a short justification for why every claw-free non-line-graph obstruction has at least seven edges.
- [Tables 2–3] The row 'n=13, 21≤m≤27' in Table 3 overlaps the target stratum in Table 2. A sentence clarifying which computations were rerun and how the overlap was handled would improve reproducibility.
- [References [8], [11]] The two arXiv preprints [8] and [11] are cited without version identifiers or DOIs. Please add the full version numbers, as the accompanying data is versioned.
Circularity Check
No significant circularity: the infinite families are obtained by a proven transfer lemma from an externally established base coefficient and one explicitly computed base graph coefficient.
full rationale
The paper's derivation chain is self-contained and non-circular. The line-graph family in Theorem 3.4 rests on Eq. (2.1), the coefficient <s_(3,3,3,3), X_{G_2}> = -40, which is attributed to independent external sources (Prajapati; Matherne and Morales). The transfer Lemma 3.2 is proved directly by counting proper colorings, and Lemma 3.3 follows from the standard product e_t * s_mu = s_{mu+(1^t)} for partitions of length at most t. Equation (3.4) is then an explicit algebraic consequence, not a fitted or renamed input. The non-line-graph family in Theorem 4.4 similarly applies the same rigorously proved transfer lemma to Eq. (4.3), <s_(3,3,3,3,1), X_Q> = -144, which is obtained by the paper's own exact computation. That computation is a load-bearing premise for the second family, but it is not a disguised prediction: the infinite-family coefficient is derived from it by a proof, not by constructional equivalence. The minimality claims depend on exhaustive enumerations and the frontier-connectivity dynamic program, whose completeness and correctness are not independently verified; however, those are correctness risks, not circularity. No self-citation is load-bearing: Wang and Wang [22] and Qi, Tang, and Wang [12] are cited for context or motivation only. No uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via citation. Since every negative coefficient asked for is computed directly or follows from a proven lemma applied to a base coefficient, the paper does not reduce to its own assumptions in any circular way.
Assumptions & free parameters
assumptions (5)
- standard math Frobenius character formula and Murnaghan–Nakayama rule for Schur expansions
- standard math Stanley's spanning-subgraph formula for the chromatic symmetric function
- domain assumption Beineke's characterization of line graphs, including the claim that claw-free non-line-graph connected graphs have m≥n+1 and m≥7
- domain assumption Completeness of geng/nauty enumeration of connected claw-free graphs in the stated ranges
- domain assumption Correctness of Prajapati's census data for n≤12 and the target stratum (n,m)=(12,21)
Cite this review
Pith. "Pith review of Two infinite families of counterexamples to the Stanley--Gasharov conjecture." pith.science (2026). https://pith.science/paper/SJHGBCZI
@misc{pith2026260727166,
author = {Pith},
title = {Pith review of: Two infinite families of counterexamples to the Stanley--Gasharov conjecture},
year = {2026},
howpublished = {\url{https://pith.science/paper/SJHGBCZI}},
note = {Machine review of arXiv:2607.27166}
}
abstract
The Stanley--Gasharov conjecture asserts that every claw-free graph is Schur-positive. Prajapati and, independently, Matherne and Morales identified the same pair of counterexamples, both of which are line graphs, thereby disproving the conjecture. In this paper, we construct two infinite families of counterexamples to the Stanley--Gasharov conjecture, thereby answering a question of Matherne and Morales. Every graph in the first family is a line graph, whereas no graph in the second family is a line graph. Prajapati further showed that the graph $G_2$, which has $12$ vertices and $21$ edges, is the smallest counterexample under the ordering that first compares the numbers of vertices and then the numbers of edges. We show that $G_2$ is also the smallest counterexample under the reverse ordering, which first compares the edge numbers and then the vertex numbers. Similarly, we exhibit a graph $Q$ with $13$ vertices and $27$ edges and show that $Q$ is the smallest counterexample that is not a line graph under each ordering. Our two infinite families are obtained from $G_2$ and $Q$, respectively, by adjoining a clique of order at least $4$ and connecting one of its vertices to a distinguished vertex of the original graph by a single edge.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
Beineke,Characterizations of derived graphs, J
L.W. Beineke,Characterizations of derived graphs, J. Combin. Theory9(1970), no. 2, 129–135
1970
-
[2]
Chudnovsky and P
M. Chudnovsky and P. Seymour,The structure of claw-free graphs, in B.S. Webb (ed.),Surveys in Combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge University Press, Cambridge, 2005, pp. 153–171
2005
-
[3]
Gasharov,Incomparability graphs of(3 + 1)-free posets are s-positive, Discrete Math.157 (1996), no
V. Gasharov,Incomparability graphs of(3 + 1)-free posets are s-positive, Discrete Math.157 (1996), no. 1–3, 193–197
1996
-
[4]
Gasharov,On Stanley’s chromatic symmetric function and clawfree graphs, Discrete Math
V. Gasharov,On Stanley’s chromatic symmetric function and clawfree graphs, Discrete Math. 205(1999), no. 1–3, 229–234
1999
-
[5]
Gebhard and B.E
D.D. Gebhard and B.E. Sagan,A chromatic symmetric function in noncommuting variables, J. Algebraic Combin.13(2001), no. 3, 227–255
2001
-
[6]
Hikita,On the Stanley–Stembridge conjecture, S´ eminaire Lotharingien de Combinatoire93B (2025), Article 31, 12 pp
T. Hikita,On the Stanley–Stembridge conjecture, S´ eminaire Lotharingien de Combinatoire93B (2025), Article 31, 12 pp
2025
-
[7]
Macdonald,Symmetric Functions and Hall Polynomials, 2nd ed., Oxford University Press, New York, 1995
I.G. Macdonald,Symmetric Functions and Hall Polynomials, 2nd ed., Oxford University Press, New York, 1995
1995
-
[8]
J.P. Matherne and A.H. Morales,Chromatic symmetric functions of claw-free graphs are not Schur positive, arXiv:2607.21508v1, 2026. 12 D. G. L. W ANG, K. ZHANG, AND T.Y. ZHAO
arXiv 2026
Show all 22 references
-
[9]
McKay and A
B.D. McKay and A. Piperno,Practical graph isomorphism, II, J. Symbolic Comput.60(2014), 94–112
2014
-
[10]
Pawlowski,Chromatic symmetric functions via the group algebra of Sn, Algebr
B. Pawlowski,Chromatic symmetric functions via the group algebra of Sn, Algebr. Comb.5 (2022), no. 1, 1–20
2022
-
[11]
Prajapati,A counterexample to the claw-free Schur-positivity conjecture, preprint, 2026, arXiv:2607.26364v1
J. Prajapati,A counterexample to the claw-free Schur-positivity conjecture, preprint, 2026, arXiv:2607.26364v1. Verification code and census data are available at https://github.com/ infinityscroll/claw-free-schur-counterexample
2026 arXiv
-
[12]
Qi, D.Q.B
E.Y.J. Qi, D.Q.B. Tang, and D.G.L. Wang,Chromatic symmetric functions of conjoined graphs, Front. Math.21(2026), no. 1, 139–166
2026
-
[13]
Shareshian and M.L
J. Shareshian and M.L. Wachs,Chromatic quasisymmetric functions, Adv. Math.295(2016), 497–551
2016
-
[14]
Shelburne and S
E. Shelburne and S. van Willigenburg,Schur-positivity for generalized nets, Enumer. Combin. Appl.5(2025), no. 1, Article S2R8
2025
-
[15]
Shelburne and S
E. Shelburne and S. van Willigenburg,A Schur-positivity classification for complete multipartite graphs, arXiv:2604.26158, 2026
2026 arXiv
-
[16]
Stanley,Review: I.G
R.P. Stanley,Review: I.G. Macdonald, Symmetric functions and Hall polynomials, Bull. Amer. Math. Soc. (N.S.)4(1981), no. 2, 254–265
1981
-
[17]
Stanley,A symmetric function generalization of the chromatic polynomial of a graph, Adv
R.P. Stanley,A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math.111(1995), no. 1, 166–194
1995
-
[18]
R.P. Stanley,Graph colorings and related symmetric functions: ideas and applications: a description of results, interesting applications, and notable open problems, Discrete Math.193 (1998), no. 1–3, 267–286
1998
-
[19]
Stanley,Enumerative Combinatorics, volume 2, Cambridge University Press, Cambridge, 1999
R.P. Stanley,Enumerative Combinatorics, volume 2, Cambridge University Press, Cambridge, 1999
1999
-
[20]
Stanley and J.R
R.P. Stanley and J.R. Stembridge,On immanants of Jacobi–Trudi matrices and permutations with restricted position, J. Combin. Theory Ser. A62(1993), no. 2, 261–279
1993
-
[21]
Stembridge,A Maple package for symmetric functions, J
J.R. Stembridge,A Maple package for symmetric functions, J. Symbolic Comput.20(1995), no. 5–6, 755–758
1995
-
[22]
Wang and M.M.Y
D.G.L. Wang and M.M.Y. Wang,A combinatorial formula for the Schur coefficients of chromatic symmetric functions, Discrete Appl. Math.285(2020), 621–630. School of Mathematics and Statistics & MIIT Key Laboratory of Mathematical Theory and Computation in Information Security, B...
2020
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.