An e-positive classification for complete multipartite graphs

2026/07/21 by Ariel Y. Sun, David G. L. Wang, Watson Z. Y. Wang
#math.CO

paper · pdf

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^β)} 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.

Citations

• A Determinant Formula for the Number of Ways of Coloring a Map

Related

• Classes of graphs with e-positive chromatic symmetric function
• All cycle-chords are e-positive
• The e-positivity of two families of (claw, 2K₂)-free graphs
• Triangular Ladders P_d,2 are e-positive
• Schur and e-positivity of trees and cut vertices