Pith. sign in

REVIEW 5 minor 1 cited by

An $e$-positive classification for complete multipartite graphs

T0 review · 0 major / 5 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 This paper proves that, for every β ≥ 1, the complete multipartite graph K_{(3,2^β)} is e-positive, and that together with the known Schur-positivity classification this completely characterizes which complete multipartite graphs have e-pos

desk verdict Resolves the last open e-positivity case for complete multipartite graphs with an explicit, checkable expansion; the only real caveat is that the 'if and only if' classification rests on an external Schur-positivity theorem. read the letter →

arxiv 2607.19110 v1 pith:K6OX5TBB submitted 2026-07-21 math.CO

Ariel Y. Sun , David G.L. Wang , Watson Z.Y. Wang This is my paper · ORCID
classification math.CO MSC 05E0505C1505A15
keywords chromaticsymmetricfunctione-positivitycompletemultipartitegraphSchurpositivityrestricted-injectionnumbersDicksonpolynomialscoefficientextractionacyclicorientations
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 settles the last open case in the e-positivity problem for complete multipartite graphs. The chromatic symmetric function X_{K_{(3,2^β)}} is proved to expand in the elementary basis with explicitly given nonnegative integer coefficients for every β≥1. The coefficients are built from the restricted-injection numbers a_d, and the proof is a marker-variable coefficient extraction that reduces the calculation to three finite coefficient families evaluated with Dickson polynomials. Together with the previously established Schur-positivity classification for complete multipartite graphs, this yields a complete characterization: X_{K_λ} is e-positive exactly when λ has one part, all parts are 1 or 2, or λ=(3,2^β).

What carries the argument

The main device is a marker-variable coefficient-extraction formula for arbitrary complete multipartite graphs, derived from the elementary–monomial Cauchy identity. Each partite set is assigned a marker variable, and the chromatic symmetric function is recovered by extracting one marker monomial from a product whose factors are the elementary symmetric functions of a root sequence; by Vieta's formulas those elementary symmetric functions are expressed directly in the markers. For K(3,2^β) the calculation is carried out modulo the square of the degree-three elementary symmetric function, which collapses the surviving terms to three coefficient families. The power sums that appear are rewritt

What would settle it

Independently compute the chromatic symmetric function of K_{(3,2,2)} (β=2) in the monomial or power-sum basis and convert to the elementary basis. The paper predicts X = 1988 e_7 + 268 e_{(6,1)} + 12 e_{(5,2)} + 4 e_{(4,3)} + 12 e_{(5,1,1)} + 2 e_{(3,3,1)}; likewise, counting acyclic orientations with exactly three sinks should give β!a_β = 14. Any mismatch falsifies the main theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for every β≥1, X_{K(3,2^β)} equals β! times a sum of elementary symmetric functions whose coefficients are manifestly nonnegative and are expressed through the restricted-injection numbers a_d. This proves that K(3,2^β) is e-positive. Since e-positivity implies Schur-positivity, the family K(3,2^β) also becomes Schur-positive. Combining this with the existing Schur-positivity classification, the paper obtains Corollary 1.3: a complete multipartite graph K_λ has an e-positive chromatic symmetric function if and only if λ has length one, all parts lie in {1,2}, or λ=(3,2^β) for some β≥1.

Load-bearing premise

The completeness of the e-positivity classification depends on the previously proved statement that a complete multipartite graph is Schur-positive only when all its parts are 1 or 2 or it has the form (3,2^β); if that statement had a missing case, the 'only if' direction would fail.

Editorial extensions

If this is right

  • The e-positive complete multipartite graphs are now exactly those with one part, all parts in {1,2}, or shape (3,2^β).
  • Every K_{(3,2^β)} is Schur-positive, giving an infinite family of Schur-positive complete multipartite graphs beyond the parts-1-or-2 case.
  • The explicit coefficients provide a finite arithmetic description of all e-expansion coefficients of K_{(3,2^β)} via the recurrence for a_d, so positivity can be checked without case-by-case computation.
  • The appendix's orientation interpretation shows β!a_β acyclic orientations of K_{(3,2^β)} have exactly three sinks, and the top coefficient counts acyclic orientations with a unique sink.
  • The marker-variable extraction formula (Theorem 3.2) applies to every complete multipartite graph, giving a reusable engine for future e-coefficient computations.

Reading between the lines

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

  • A natural testable extension is to run the same marker-root computation on K_{(a,2^β)} for fixed a≥4; the cubic quotient would become a degree-a quotient, and the point where coefficients turn negative would reveal what is special about a=3.
  • The derangement-like nature of a_d hints at a direct bijective model for the e-coefficients, for instance through acyclic orientations or nonattacking rook placements, that would re-derive the expansion without analytic identities.
  • The theorem's separation of 'if' from 'only if' means the classification is only as strong as the Schur-positivity classification it invokes; a reader who trusts that classification gets the complete picture, while the K(3,2^β) expansion remains valid even if the classification were revised.
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

0 major / 5 minor

Summary. The paper proves that the chromatic symmetric function of the complete multipartite graph K_{(3,2^β)} is e-positive for every β≥1, giving an explicit expansion in the elementary basis with coefficients expressed through restricted-injection numbers a_d. The proof introduces a marker-variable coefficient-extraction formula for arbitrary complete multipartite graphs, derived from the elementary–monomial Cauchy identity, and reduces the calculation to three coefficient families evaluated via Dickson polynomials. Combining the main theorem with the Shelburne–van Willigenburg Schur-positivity classification yields a complete classification of e-positive complete multipartite graphs.

Significance. If the result holds, it resolves an open case in e-positivity of complete multipartite graphs and completes the classification. The explicit Cauchy-identity based coefficient extraction (Theorem 3.2) is a useful tool that may apply to other families. The proof is self-contained for the main theorem, with detailed lemmas; the small cases β=1,2,3 in the introduction match the formula. The classification's 'only if' direction is inherited from an external theorem (Theorem 1.1(ii)), which is clearly stated; this is a dependence, not a gap in the paper.

minor comments (5)
  1. [§1, displayed expansions] The formula for β=3 is split over two lines in the text; ensure the typeset version aligns the display. Also, use consistent notation for elementary symmetric functions, e.g., e_{...} rather than e9 in running text.
  2. [Theorem 3.2] The phrase 'multiplying by the scalar factor η! to restore the labelings within the partite sets' is correct but terse. A one-sentence explanation of the multinomial count (η_i! / ∏_c j_c!) would help readers see why the η! factor is the right normalization.
  3. [Lemma 3.3, proof] In the r=0 second case, the count implicitly includes an (s−1)! assignment of the selected variables to the remaining E_2 factors. Spelling this out would prevent reader confusion about the origin of the s! factor in the formula.
  4. [Corollary 1.3] The necessity direction relies entirely on Theorem 1.1(ii), which is imported from a preprint. The authors may wish to state this conditionality explicitly in the abstract or in the proof of the corollary, so that readers know the classification is only as strong as that external theorem.
  5. [General typography] The title appears with unwanted spacing as 'ANe-POSITIVE CLASSIFICATION FOR COMPLETE MUL TIP AR TITE GRAPHS'; please fix the title formatting in the final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the e-positivity proof is self-contained; the only-if direction uses an external prior classification.

full rationale

The paper's central derivation, Theorem 1.2, is self-contained. It derives a marker-variable coefficient-extraction formula (Theorem 3.2) from the elementary-monomial Cauchy identity, uses the Alpha-Omega Lemma to restrict the possible partitions, and evaluates the three surviving coefficient families using Dickson polynomials, standard transitions, and recurrences for the restricted-injection numbers a_d. The a_d are independent combinatorial counts (nonattacking rook placements on a deleted-diagonal board); they are not fitted to the desired e-coefficients. The manifest nonnegativity of the final expansion follows from the positivity of these counts and the explicit coefficients. The only-if direction of Corollary 1.3 relies on Shelburne and van Willigenburg's Theorem 1.1(ii), which is an external prior classification, not a self-citation, and is used legitimately because e-positivity implies Schur-positivity. Self-citations appearing in the introduction are historical background and are not load-bearing in any proof. No step reduces a claimed prediction to its own input, and no load-bearing argument depends on a self-citation chain. Therefore there is no significant circularity.

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

The paper is a derivation-based proof. It relies on standard symmetric-function identities and the external Schur-positivity classification of Shelburne–van Willigenburg, but does not introduce any new entities, forces, or fitted constants. The only combinatorial quantities, a_d, are known restricted-injection numbers with explicit recurrences.

assumptions (6)
  • domain assumption Shelburne–van Willigenburg classification (Theorem 1.1): K_λ is Schur-positive iff all parts are in {1,2} or λ=(3,2^β); and K_λ is e-positive when all parts are in {1,2}.
    Corollary 1.3's necessity and part of sufficiency rest on this external theorem; cited in the introduction and used in the proof of Corollary 1.3.
  • domain assumption Alpha–Omega Lemma (Sagan–Tom, Lemma 2.6): nonzero e-coefficients satisfy α_k(G) ≥ μ'_1+...+μ'_k and ω_k(G) ≤ μ_1+...+μ_k.
    Used in Lemma 3.1 to restrict the support of e-coefficients to partitions of length at most 3.
  • standard math Elementary–monomial Cauchy identity (Macdonald, Proposition 2.3).
    Basis for Theorem 3.2, the marker-variable coefficient-extraction formula.
  • standard math Girard–Waring, Nägelsbach–Kostka, Newton–Girard, and Vieta formulas.
    Used throughout to convert between power sums, complete homogeneous, and elementary symmetric functions; Propositions 2.1, 2.2, 2.4, 2.5.
  • standard math Dickson polynomial expansions (Eqs. 2.3, 2.4).
    Used in Section 4 to evaluate coefficient extractions for power sums and complete homogeneous functions in two variables.
  • domain assumption Restricted-injection number recurrences (Eqs. 2.9–2.11) from Chao et al. and Efimov.
    Used to identify the final alternating sums with the numbers a_d; these are external published identities.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An $e$-positive classification for complete multipartite graphs." pith.science (2026). https://pith.science/paper/K6OX5TBB

@misc{pith2026260719110,
  author       = {Pith},
  title        = {Pith review of: An $e$-positive classification for complete multipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K6OX5TBB}},
  note         = {Machine review of arXiv:2607.19110}
}
abstract

Shelburne and van Willigenburg (arXiv:2604.26158) characterize the Schur-positive complete multipartite graphs and leave open whether the graphs~$G=K_{(3,\,2^\beta)}$ are $e$-positive. We resolve this question and, together with their classification, characterize all $e$-positive complete multipartite graphs. Our main result is an explicit, manifestly nonnegative $e$-expansion of~$X_G$ whose coefficients are expressed in terms of the restricted-injection numbers. Our main idea is to derive a marker-variable coefficient-extraction formula for the $e$-coefficients of arbitrary complete multipartite graphs from the elementary--monomial Cauchy identity. For the particular graph~$G$, this formula reduces the proof to three coefficient families, which we evaluate using Dickson polynomials and recurrences for these numbers.

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

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

  1. [1]

    Alexandersson,LLT polynomials, elementary symmetric functions and melting lollipops, J

    P. Alexandersson,LLT polynomials, elementary symmetric functions and melting lollipops, J. Algebraic Combin.53(2021), no. 2, 299–325. 1

    2021

  2. [2]

    G. D. Birkhoff,A determinant formula for the number of ways of coloring a map, Ann. of Math. (2)14(1912/13), no. 1/4, 42–46. 5

    1912

  3. [3]

    Carballosa, F

    W. Carballosa, F. A. Reyes, and J. Khera,Encoding and enumerating acyclic orientations of graphs, Util. Math.125(2025), 21–41. 19

    2025

  4. [4]

    L. Chao, P. DesJarlais, and J. L. Leonard,89.45 A binomial identity, via derangements, Math. Gaz.89(2005), no. 515, 268–270. 7

    2005

  5. [5]

    L. Chen, Y. T. He, and D. G. L. Wang,Clocks aree-positive, Discrete Math.349(2026), no. 1, Article 114723. 2

    2026

  6. [6]

    Crew and S

    L. Crew and S. Spirkl,A complete multipartite basis for the chromatic symmetric function, SIAM J. Discrete Math.35(2021), no. 4, 2647–2661. 3

    2021

  7. [7]

    Dahlberg and S

    S. Dahlberg and S. van Willigenburg,Lollipop and lariat symmetric functions, SIAM J. Discrete Math.32(2018), no. 2, 1029–1039. 1

    2018

  8. [8]

    L. E. Dickson,The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group, Ann. of Math.11(1896/97), no. 1–6, 65–120. 6

Show all 35 references
  1. [9]

    D. V. Efimov,Hafnian of some three-parameter Toeplitz matrices and perfect matchings of arc and chord diagrams, Proceedings of the Komi Science Centre of the Ural Division of the Russian Academy of Sciences (2021), no. 6 (52), 5–13. 7

    2021

  2. [10]

    Gasharov,On Stanley’s chromatic symmetric function and clawfree graphs, Discrete Math.205(1999), no

    V. Gasharov,On Stanley’s chromatic symmetric function and clawfree graphs, Discrete Math.205(1999), no. 1–3, 229–234. 2

    1999

  3. [11]

    D. D. Gebhard and B. E. Sagan,A chromatic symmetric function in noncommuting variables, J. Algebraic Combin.13(2001), no. 3, 227–255. 1

    2001

  4. [12]

    S. Y. M. Gong, D. G. L. Wang, and K. Zhang,The trinacria graphsT(b+2)b2 aree-positive, arXiv:2512.21864, 2025. 2

    2025

  5. [13]

    Greene and T

    C. Greene and T. Zaslavsky,On the interpretation of Whitney numbers through arrange- ments of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Amer. Math. Soc.280(1983), no. 1, 97–126. 19

    1983

  6. [14]

    Hikita,A proof of the Stanley–Stembridge conjecture, arXiv:2410.12758, 2024

    T. Hikita,A proof of the Stanley–Stembridge conjecture, arXiv:2410.12758, 2024. 1

    2024

  7. [15]

    Hikita,On the Stanley–Stembridge conjecture, Séminaire Lotharingien de Combinatoire 93B(2025), Article 31, 12 pp

    T. Hikita,On the Stanley–Stembridge conjecture, Séminaire Lotharingien de Combinatoire 93B(2025), Article 31, 12 pp. 1

    2025

  8. [16]

    R. Lidl, G. L. Mullen, and G. Turnwald,Dickson Polynomials, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 65, Longman Scientific & Technical, Harlow, 1993. 6

    1993

  9. [17]

    I. G. Macdonald,Symmetric Functions and Hall Polynomials, 2nd ed., Oxford Mathe- matical Monographs, Oxford University Press, Oxford, 1995. 4 and 5 ANe-POSITIVE CLASSIFICATION FOR COMPLETE MULTIPARTITE GRAPHS 21

    1995

  10. [18]

    G. L. Mullen and D. Panario, eds.,Handbook of Finite Fields, CRC Press, Boca Raton, FL, 2013. 6

    2013

  11. [19]

    3 and 19

    OEIS Foundation Inc.,The On-Line Encyclopedia of Integer Sequences, entries A002119 and A033815, https://oeis.org/A002119 and https://oeis.org/A033815, accessed July 20, 2026. 3 and 19

    2026

  12. [20]

    E. Y. Qi, D. Q. Tang, and D. G. L. Wang,Chromatic symmetric functions of conjoined graphs, Front. Math. (2025), doi:10.1007/s11464-024-0088-3. 2

    2025 doi

  13. [21]

    B. E. Sagan and F. Tom,Chromatic symmetric functions and change of basis, Algebr. Comb.9(2026), no. 1, 307–325. 5

    2026

  14. [22]

    Schur,Über den Zusammenhang zwischen einem Problem der Zahlentheorie und einem Satz über algebraische Funktionen, Sitzungsber

    I. Schur,Über den Zusammenhang zwischen einem Problem der Zahlentheorie und einem Satz über algebraische Funktionen, Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Klasse (1923), 123–134. 6

    1923

  15. [23]

    Shareshian and M

    J. Shareshian and M. L. Wachs,Chromatic quasisymmetric functions, Adv. Math.295 (2016), 497–551. 1

    2016

  16. [24]

    Shelburne and S

    E. Shelburne and S. van Willigenburg,Schur-positivity for generalized nets, Enumer. Combin. Appl.5(2025), no. 1, Article S2R8. 2

    2025

  17. [25]

    Shelburne and S

    E. Shelburne and S. van Willigenburg,A Schur-positivity classification for complete multipartite graphs, arXiv:2604.26158, 2026. 2

    2026 arXiv

  18. [26]

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

    1995

  19. [27]

    R. P. Stanley,Graph colorings and related symmetric functions: ideas and applications: a description of results, interesting applications, & notable open problems, Discrete Math. 193(1998), no. 1–3, 267–286. 2

    1998

  20. [28]

    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. 1

    1993

  21. [29]

    Thibon and D

    J.-Y. Thibon and D. G. L. Wang,A noncommutative approach to the Schur positivity of chromatic symmetric functions, arXiv:2305.07858, 2023. 2

    2023 arXiv

  22. [30]

    Tom,A signede-expansion of the chromatic quasisymmetric function, Combin

    F. Tom,A signede-expansion of the chromatic quasisymmetric function, Combin. Theory 5(2025), no. 2. 2

    2025

  23. [31]

    Tom and A

    F. Tom and A. Vailaya,The chromatic symmetric function of graphs glued at a single vertex, arXiv:2503.19344, 2025. 2

    2025 arXiv

  24. [32]

    D. G. L. Wang,All cycle-chords aree-positive, Ann. Comb. (2025), doi:10.1007/s00026- 025-00753-2. 2

    2025 doi

  25. [33]

    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. 2

    2020

  26. [34]

    D. G. L. Wang and M. M. Y. Wang,Thee-positivity and Schur positivity of some spiders and broom trees, Discrete Appl. Math.325(2023), 226–240. 2

    2023

  27. [35]

    D. G. L. Wang and J. Z. F. Zhou,A composition method for neat formulas of chromatic symmetric functions, Adv. in Appl. Math.167(2025), Article 102886. 2 22 ARIEL Y. SUN, DA VID G.L. W ANG *, AND W ATSON Z.Y. W ANG School of Mathematics and Statistics, Beijing Institute of Tech...

    2025

Pith tools

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