Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

A counterexample to the claw-free Schur-positivity conjecture

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

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

Pith's one-line read A 12-vertex claw-free graph whose chromatic symmetric function has Schur coefficient -64 at the partition (3,3,3,3) disproves the conjecture that every claw-free graph is Schur-positive.

desk verdict The computational counterexample is probably real, but the hand proof in §2.3 is not; this paper needs a major rewrite before it should be accepted. read the letter →

arxiv 2607.26364 v1 pith:PV22FDPX submitted 2026-07-29 math.CO

Jitendra Prajapati This is my paper · ORCID
classification math.CO MSC 05E0505C1505C75
keywords chromaticsymmetricfunctionSchur-positivityclaw-freegraphlinecounterexamplestablepartitionKostkainversionSchurcoefficient
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

The paper claims to disprove the long-standing conjecture that every claw-free graph has a Schur-positive chromatic symmetric function. It constructs a specific 12-vertex claw-free graph—the line graph of a 4-cycle with triangles at two opposite vertices and pendant edges at the other two—and proves by hand that the coefficient of s_(3,3,3,3) in its chromatic symmetric function is -64. Since Schur-positivity requires all coefficients to be nonnegative, this graph is a counterexample. An exhaustive computer census shows that no counterexample exists on fewer than 12 vertices and that exactly two non-Schur-positive isomorphism classes exist on 12 vertices. If correct, this settles the conjecture negatively and tightens the boundary between Schur-positive and non-positive claw-free graphs.

What carries the argument

The argument rests on the stable-partition expansion of the chromatic symmetric function: for a line graph, stable sets of vertices correspond to matchings of the root graph. The root graph H has matching number 4, so only partition shapes with parts at most 4 contribute. Counting ordered stable partitions of type (4,4,2,2), (4,3,3,2), and (3,3,3,3) gives monomial coefficients 128, 320, and 768; unitriangular Kostka inversion then yields the Schur coefficient -64. The census relies on exhaustive generation of connected graphs, filtering claw-free graphs, and exact integer Schur-coefficient computation.

What would settle it

Recompute the full Schur expansion of the 12-vertex line graph G and check whether the coefficient of s_(3,3,3,3) is -64; if it is nonnegative, the counterexample collapses. For the census claims, finding any connected claw-free graph on 11 or fewer vertices with a negative Schur coefficient, or a 12-vertex connected claw-free graph outside the two listed classes with a negative coefficient, would refute the minimality and completeness statements.

Watch

Extended reading notes

Core claim

The central discovery is a concrete counterexample: the line graph G of the graph H obtained from a 4-cycle by attaching a triangle at two opposite vertices and a pendant edge at each of the other two. G is connected and claw-free, and the Schur coefficient indexed by (3,3,3,3) in its chromatic symmetric function equals -64. The coefficient is computed by counting stable partitions of G (matchings of H) into four parts, then applying Kostka inversion. The paper further reports an exhaustive enumeration showing that every connected claw-free graph on at most 11 vertices is Schur-positive, so this graph is of minimum order, and that on 12 vertices exactly two isomorphism classes fail Schur-pos

Load-bearing premise

The load-bearing premise is that the exhaustive computer enumeration and exact arithmetic are error-free: a single misclassified graph or miscomputed Schur coefficient would invalidate the claims that 12 is the minimum order and that exactly two isomorphism classes exist on 12 vertices.

Editorial extensions

If this is right

  • The claw-free Schur-positivity conjecture is false, so a graph being claw-free no longer guarantees that its chromatic symmetric function is Schur-positive.
  • The failure already occurs for a line graph whose root graph has maximum degree four, so the obstruction is not confined to exotic or high-degree constructions.
  • No counterexample exists on fewer than 12 vertices, and exactly two exist on 12 vertices, giving a precise minimum-order boundary for the conjecture.
  • The only negative coefficient in the counterexample is indexed by (3,3,3,3), so the failure of Schur-positivity can be witnessed by a single partition shape with four parts of size 3.
  • Because disconnected graphs reduce to connected components, the census claims cover all claw-free graphs of order at most 12, not just connected ones.

Reading between the lines

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

  • If the census is correct, a refined conjecture might hold for claw-free graphs with maximum degree below some threshold, or with matching number below 4, since the counterexample requires matching number 4 in the root graph.
  • The two 12-vertex counterexamples share the same negative shape; comparing their root-graph structures may reveal a common substructure that forces Schur non-positivity, possibly generalizable to infinite families.
  • The extreme rarity of counterexamples (two among 1.7 million on 12 vertices) suggests that a characterization of Schur-positive claw-free graphs may still be feasible, perhaps by excluding a small set of induced subgraphs.
  • A non-computational proof of the census result would be valuable; until then, the minimality claim rests entirely on the correctness of the exhaustive search.
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.

Referee Report

3 major / 3 minor

Summary. The paper proposes a counterexample to the claw-free Schur-positivity conjecture of Stanley/Gasharov. The proposed graph is the line graph G = L(H) of a 10-vertex graph H built from a 4-cycle with two triangles and two pendant edges; H has 12 edges, so G has 12 vertices. The paper claims [s_(3,3,3,3)]X_G = −64, gives a hand proof based on counting stable partitions of G (matchings of H) and Kostka inversion, and reports three independent exact computations plus an exhaustive census showing that no counterexample exists on at most 11 vertices and that exactly two isomorphism classes on 12 vertices are non-Schur-positive. The result, if correct, disproves a 1998 conjecture and also its restriction to line graphs.

Significance. If the result is correct, it is a significant disproof of a well-known conjecture in chromatic symmetric function theory. The paper has notable strengths: the construction is explicit, the coefficient is reproducible by three independent exact implementations, the exhaustive census is feasible and transparently documented, and the provenance of the computation is public. These strengths make the result credible. However, the hand proof in §2.3 contains serious technical errors; as written, the proof of Theorem 1 does not establish the claimed coefficient. The computational verification may be sufficient to support the theorem, but the paper currently presents the hand proof as the derivation, and that derivation is invalid.

major comments (3)
  1. [§2.3, equations for [s_4422], [s_4332], [s_3333]] The 'triangular inversion' is not a valid inversion. From the displayed Kostka data, s_4422 = m_4422 + m_4332 + 2m_3333 + ...; with the paper's own counts this gives [s_4422] ≥ 128 + 320 + 2·768 = 1984, contradicting the claimed [s_4422] = 128. Similarly [s_4332] ≥ 320 + 3·768 = 2624, not 192. The coefficients 1, 2, 3 are Kostka numbers for expanding s_ν in the m basis; they are not the coefficients for the inverse expansion used here. The displayed subtraction is therefore unjustified and the proof of Theorem 1 fails at this step.
  2. [§2.3, first sentence] The assertion that vanishing of all [m_λ] with λ_1 ≥ 5 implies that only Schur indices with parts ≤ 4 can be nonzero is false. For example s_(5,4,3) can receive a positive contribution from m_(3,3,3,2,1). Such stable partitions do occur: H admits the proper 4-edge-coloring {ab,cd,uv}, {ad,cx}, {au,bc,dm,xy}, {av,bℓ,cy}; splitting the third class gives partitions of type (3,3,3,2,1) and (3,3,2,2,2). These m-coefficients are positive, are dominated by (3,3,3,3), and contribute to [s_3333], but they are not counted in §2.2. (The specific stress-test example with s_(5,4,3) and m_(3,3,3,3) is itself impossible, but the objection is valid via m_(3,3,3,2,1).)
  3. [§2.3, vanishing of [s_(4,4,4)] and [s_(4,4,3,1)]] The claim that [s_444] vanishes because [m_444] = 0 is logically invalid. [s_444] receives contributions from all m_λ with λ ≤ (4,4,4), including [m_3333] = 768; indeed K_(444),(3333) ≥ 1, as shown by the SSYT with three rows 1 2 3 4. Thus [m_444] = 0 does not force [s_444] = 0. A separate proof or computation is required for this vanishing, and the same issue affects [s_(4,4,3,1)].
minor comments (3)
  1. [Abstract/Introduction] Several places have missing spaces in rendered text (e.g., 'on12vertices', 's(3,3,3,3)]XG'); these are typesetting issues but should be corrected.
  2. [§2.3] The notation switches between sν, s_ν, and displayed subscripts; please use one consistent subscripted notation throughout. Also, the phrase 'Using K ... :' should clearly specify whether the matrix direction is Kostka or inverse Kostka, since the current usage is ambiguous and, as noted, not the correct inverse direction.
  3. [Computational provenance] If the hand proof is revised to rely on the computational verification, the sentence 'The graph, short proof, exact verification programs, and census logs are available' should be updated to avoid calling the invalid hand derivation a 'short proof'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the coefficient is computed directly from definitions via stable-partition counting and Kostka inversion, with no fitted inputs or load-bearing self-citations.

full rationale

I examined the claimed derivation chain. The central coefficient [s_(3,3,3,3)]X_G = -64 is derived in §2 by identifying stable partitions of G = L(H) with matchings of H, counting the four-part labelled stable partitions directly in the table of §2.2, converting these counts to monomial coefficients via N_λ ∏ m_j(λ)!, and then inverting the Kostka matrix in §2.3. This is a parameter-free computation from the definition of the chromatic symmetric function. The vanishing of monomial coefficients with λ_1 ≥ 5 is used together with unitriangularity to infer that certain Schur coefficients vanish; this is a genuine triangular-system argument, not an assumption of the conclusion. The computational census of §3 uses nauty geng and exact integer arithmetic; it does not fit any parameter to the target coefficient, and it is not presented as a prediction from fitted data. No load-bearing premise rests on a citation to the author's own prior work. The author's public repository is a verification artifact, and the paper also cites independent verification by Matherne and Morales and by D. Grinberg. The possible objection raised by a skeptic—that some monomial coefficients may contribute to Schur functions with parts larger than 4—concerns mathematical correctness of the triangular inversion, not circularity: even if the proof had a gap, that would make it incorrect, not circular. No equation is equal to its input by construction, and no 'prediction' is a renamed fit. Therefore the paper exhibits no significant circularity.

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

The paper introduces no free parameters or invented entities. The central claim rests on standard symmetric-function theory (monomial and Schur bases, Kostka inversion) and on the correctness of two computational tools: nauty geng for graph enumeration and the author's exact integer-arithmetic implementations for Schur coefficients. The hand computation in §2 is self-contained and does not depend on the census.

assumptions (5)
  • standard math The coefficient [m_λ]X_G counts ordered partitions of V(G) into independent sets of sizes λ_i.
    Used in §2.1; standard Stanley [3] expansion of the chromatic symmetric function in the monomial basis.
  • standard math Line graphs are claw-free; stable sets of L(H) are matchings of H.
    Invoked in §2 to reduce the problem to matching partitions of H.
  • standard math Kostka numbers K_{νλ} give unitriangular change of basis between Schur and monomial bases, with specific values K_{4422,4332}=1, K_{4422,3333}=2, K_{4332,3333}=3.
    Used in §2.3 for the triangular inversion; these values are known and checkable.
  • domain assumption nauty's geng enumerates all connected graphs on n vertices correctly, and the implementation of claw-free filter and Schur-positivity testing is bug-free.
    Proposition 4 relies on the exhaustive census of 164 billion connected graphs and 1.9M claw-free graphs; counts match OEIS A001349, but correctness of the custom Schur test is assumed from the supplied code.
  • domain assumption The three exact computer implementations used for verification and census compute Schur coefficients exactly.
    Section 3 states all coefficients were computed exactly in integer arithmetic; reliance on these programs is an assumption since the code is not machine-checked.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A counterexample to the claw-free Schur-positivity conjecture." pith.science (2026). https://pith.science/paper/PV22FDPX

@misc{pith2026260726364,
  author       = {Pith},
  title        = {Pith review of: A counterexample to the claw-free Schur-positivity conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PV22FDPX}},
  note         = {Machine review of arXiv:2607.26364}
}
abstract

The claw-free Schur-positivity conjecture, recorded by Stanley (1998) and credited there to Gasharov, asserts that the chromatic symmetric function of every claw-free graph is Schur-positive. We give a counterexample on 12 vertices: the line graph $G$ of the graph obtained from a 4-cycle by attaching triangles at two opposite vertices and pendant edges at the other two satisfies $[s_{(3,3,3,3)}]X_G = -64$. The coefficient follows from a short computation by hand and is also reproduced by three exact implementations. An exhaustive computation over all 216,777 connected claw-free graphs on at most 11 vertices shows that every one is Schur-positive, so 12 vertices is the minimum order of any counterexample. A complete census of the 1,728,404 connected claw-free graphs on 12 vertices finds exactly two non-Schur-positive isomorphism classes; the other has graph6 code K?`CR@`bAbRB and coefficient $[s_{(3,3,3,3)}] = -40$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Two infinite families of counterexamples to the Stanley--Gasharov conjecture

    math.CO 2026-07 conditional novelty 7.0 of 10

    Claw-free graphs, already known to disprove the Stanley--Gasharov conjecture, are shown to yield infinitely many counterexamples in both line-graph and non-line-graph families, plus minimality of the base examples.

Reference graph

Works this paper leans on

7 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [1]

    Gasharov,Incomparability graphs of(3 + 1)-free posets ares-positive, Discrete Math

    V. Gasharov,Incomparability graphs of(3 + 1)-free posets ares-positive, Discrete Math. 157 (1996) 193–197

    1996

  2. [2]

    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) 229–234, doi:10.1016/S0012-365X(99)00106-5

    work page doi:10.1016/s0012-365x(99)00106-5 1999

  3. [3]

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

    1995

  4. [4]

    R. P. Stanley,Graph colorings and related symmetric functions: ideas and applications, Discrete Math. 193 (1998) 267–286

    1998

  5. [5]

    J. P. Matherne, A. H. Morales,Chromatic symmetric functions of claw-free graphs are not Schur positive, arXiv:2607.21508 (2026),https://arxiv.org/abs/2607.21508

    arXiv 2026

  6. [6]

    MathOverflow,Is this a counterexample to the claw-free Schur-positivity conjecture?, ques- tion 513515 (2026)

    2026

  7. [7]

    Shelburne, S

    E. Shelburne, S. van Willigenburg,Schur-positivity for generalized nets, Enumerative Com- binatorics and Applications 5:1 (2025), Article S2R8, doi:10.54550/ECA2025V5S1R8. 4

    work page doi:10.54550/eca2025v5s1r8 2025

Pith tools

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