Resolving Stanley's e-positivity of claw-contractible-free graphs

DOI10.4171/JEMS/974MaRDI QIDQ783748zbMATH OpenOpenAlexFDO

Authors Samantha Dahlberg, Angèle M. Foley, Stephanie van Willigenburg

Publication date 4 August 2020

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.05770

zbMATH Keywords

chromatic symmetric functionclaw-contractible graphclaw-free graphelementary symmetric function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75) Symmetric functions and generalizations (05E05) Algebraic aspects of posets (06A11) Connections of Hopf algebras with combinatorics (16T30) Representations of finite symmetric groups (20C30)

Abstract: In Stanley's seminal 1995 paper on the chromatic symmetric function, he stated that there was no known graph that was not contractible to the claw and whose chromatic symmetric function was not $e$-positive, namely, not a positive linear combination of elementary symmetric functions. We resolve this by giving infinite families of graphs that are not contractible to the claw and whose chromatic symmetric functions are not $e$-positive. Moreover, one such family is additionally claw-free, thus establishing that the $e$-positivity of chromatic symmetric functions is in general not dependent on the existence of an induced claw or of a contraction to a claw.

Review text

Summary: In Stanley's seminal paper on the chromatic symmetric function [\textit{R. P. Stanley}, Adv. Math. 111, No. 1, 166--194 (1995; Zbl 0831.05027)], he stated that there was no known graph that was not contractible to the claw and whose chromatic symmetric function was not \(e\)-positive, that is, not a positive linear combination of elementary symmetric functions. We resolve this by giving infinite families of graphs that are not contractible to the claw and whose chromatic symmetric functions are not \(e\)-positive. Moreover, one such family is additionally claw-free, thus establishing that the \(e\)-positivity of chromatic symmetric functions is in general not dependent on the existence of an induced claw or of a contraction to a claw.

Recommendations

• Chromatic symmetric functions and \(H\)-free graphs
• On Stanley's chromatic symmetric function and clawfree graphs
• Chromatic posets
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs

Cites work

• A chromatic symmetric function in noncommuting variables
• A quasisymmetric function generalization of the chromatic symmetric function
• A symmetric function generalization of the chromatic polynomial of a graph
• A weighted graph polynomial from chromatic invariants of knots
• Characterizations of derived graphs
• Chromatic quasisymmetric functions
• Contractibility and NP-completeness
• Evaluations of Hecke algebra traces at Kazhdan-Lusztig basis elements
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Graphs with equal chromatic symmetric functions
• Hook coefficients of chromatic functions
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1181673 (Why is no real title available?)
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• Intersection theory for graphs
• Lollipop and lariat symmetric functions
• On distinguishing trees by their chromatic symmetric functions
• On immanants of Jacobi-Trudi matrices and permutations with restricted position
• Polynomial graph invariants and the KP hierarchy
• Power sum expansion of chromatic quasisymmetric functions
• Proper caterpillars are distinguished by their chromatic symmetric function
• Scheduling problems
• Schur and \(e\)-positivity of trees and cut vertices
• The cohomology of abelian Hessenberg varieties and the Stanley-Stembridge conjecture
• The interchange graph of a finite graph
• The polychromate and a chord diagram polynomial
• The Potts model and chromatic functions of graphs
• Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties

Cited in

(24)

• Chromatic symmetric functions and \(H\)-free graphs
• On the \(e\)-positivity of \((claw, 2K_2)\)-free graphs
• Chromatic posets
• The twinning operation on graphs does not always preserve e-positivity
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• On the \(e\)-positivity of trees and spiders
• A combinatorial expansion of vertical-strip LLT polynomials in the basis of elementary symmetric functions
• A combinatorial formula for the Schur coefficients of chromatic symmetric functions
• Schur and \(e\)-positivity of trees and cut vertices
• A new formula for Stanley's chromatic symmetric function for unit interval graphs and E-positivity for triangular ladder graphs
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs
• The \(e\)-positivity of two classes of cycle-chord graphs
• A rooted variant of Stanley's chromatic symmetric function
• The e-positivity of some new classes of graphs
• Graphs missing a connected partition
• Chromatic symmetric functions of conjoined graphs
• The chromatic symmetric function in the star-basis
• A signed e-expansion of the chromatic quasisymmetric function
• The kromatic symmetric function: a K-theoretic analogue of X_G
• The e-positivity of the chromatic symmetric function for twinned paths and cycles
• A composition method for neat formulas of chromatic symmetric functions
• A signed e-expansion of the chromatic symmetric function and some new e-positive graphs
• On e-positivity of trees and connected partitions

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q783748)