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

positivityelementary symmetric functionSchur functionchromatic symmetric function

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Coloring of graphs and hypergraphs (05C15) 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

• 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?)
• A Robinson-Schensted algorithm for a class of partial orders
• A chromatic symmetric function in noncommuting variables
• 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
• 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 Stanley's chromatic symmetric function and clawfree graphs
• On distinguishing trees by their chromatic symmetric functions
• On immanants of Jacobi-Trudi matrices and permutations with restricted position
• 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

(16)

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

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)