Chromatic posets

DOI10.1016/J.JCTA.2021.105496MaRDI QIDQ2049439zbMATH OpenOpenAlexFDO

Authors Samantha Dahlberg, Adrian She, Stephanie van Willigenburg

Publication date 25 August 2021

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

chromatic symmetric functionelementary symmetric functionpositivitySchur function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Symmetric functions and generalizations (05E05) Combinatorics of partially ordered sets (06A07)

Abstract: In 1995 Stanley introduced the chromatic symmetric function $X_G$ of a graph $G$, whose $e$-positivity and Schur-positivity has been of large interest. In this paper we study the relative $e$-positivity and Schur-positivity between connected graphs on $n$ vertices. We define and investigate two families of posets on distinct chromatic symmetric functions. The relations depend on the $e$-positivity or Schur-positivity of a weighed subtraction between $X_G$ and $X_H$. We find a biconditional condition between $e$-positivity or Schur-positivity and the relation to the complete graph. This gives a new paradigm for $e$-positivity and for Schur-positivity. We show many other interesting properties of these posets including that trees form an independent set and are maximal elements. Additionally, we find that stars are independent elements, the independence number increases as we increase in the poset and that the family of lollipop graphs form a chain.

Recommendations

• Schur and \(e\)-positivity of trees and cut vertices
• Chromatic symmetric functions and \(H\)-free graphs
• On \(e\)-positivity and \(e\)-unimodality of chromatic quasisymmetric functions
• Chromatic quasisymmetric functions
• The \(e\)-positivity and Schur positivity of some spiders and broom trees

Cites work

• A chromatic symmetric function in noncommuting variables
• A Robinson-Schensted algorithm for a class of partial orders
• A symmetric function generalization of the chromatic polynomial of a graph
• A tight upper bound on the cover time for random walks on graphs
• Acyclic orientations of graphs
• Chromatic quasisymmetric functions
• 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 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1436000 (Why is no real title available?)
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• Lollipop and lariat symmetric functions
• Maximum hitting time for random walks on graphs
• On $e$-Positivity and $e$-Unimodality of Chromatic Quasi-symmetric Functions
• On distinguishing trees by their chromatic symmetric functions
• On immanants of Jacobi-Trudi matrices and permutations with restricted position
• On Stanley's chromatic symmetric function and clawfree graphs
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
• Proper caterpillars are distinguished by their chromatic symmetric function
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
• Symmetric functions and Hall polynomials. With contributions by A. V. Zelevinsky
• The cohomology of abelian Hessenberg varieties and the Stanley-Stembridge conjecture

Cited in

(17)

• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• The \(e\)-positivity and Schur positivity of some spiders and broom trees
• Positivity of chromatic symmetric functions associated with Hessenberg functions of bounce number 3
• A combinatorial formula for the Schur coefficients of chromatic symmetric functions
• New invariants for permutations, orders and graphs
• 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
• Chromatic symmetric functions via the group algebra of \(S_n\)
• The \(e\)-positivity of two classes of cycle-chord graphs
• A remark on the chromatic polynomials of incomparability graphs of posets
• Lollipop and lariat symmetric functions
• Chromatic symmetric functions of hypertrees
• The chromatic symmetric function of a graph centred at a vertex
• The e-positivity of some new classes of graphs
• A signed e-expansion of the chromatic quasisymmetric function
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs
• Characters and chromatic symmetric functions

This page was built for publication: Chromatic posets

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