Chromatic symmetric functions of hypertrees

MaRDI QIDQ528973zbMATH OpenFDO

Authors Jair Taylor

Publication date 18 May 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.08262, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p2

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic symmetric functiongraph colouringhypergraphhypertreequasisymmetric functionsymmetric function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Symmetric functions and generalizations (05E05)

Abstract: The chromatic symmetric function $X_H$ of a hypergraph $H$ is the generating function for all colorings of $H$ so that no edge is monochromatic. When $H$ is an ordinary graph, it is known that $X_H$ is positive in the fundamental quasisymmetric functions $F_S$, but this is not the case for general hypergraphs. We exhibit a class of hypergraphs $H$ --- hypertrees with prime-sized edges --- for which $X_H$ is $F$-positive, and give an explicit combinatorial interpretation for the $F$-coefficients of $X_H$.

Review text

Summary: The chromatic symmetric function \(X_H\) of a hypergraph \(H\) is the sum of all monomials corresponding to proper colorings of \(H\). When \(H\) is an ordinary graph, it is known that \(X_H\) is positive in the fundamental quasisymmetric functions \(F_S\), but this is not the case for general hypergraphs. We exhibit a class of hypergraphs \(H\) -- hypertrees with prime-sized edges -- for which \(X_H\) is \(F\)-positive, and give an explicit combinatorial interpretation for the \(F\)-coefficients of \(X_H\).

Recommendations

• \(H\)-chromatic symmetric functions
• A quasisymmetric function generalization of the chromatic symmetric function
• Chromatic posets
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Chromatic symmetric functions via the group algebra of \(S_n\)

Cites work

• A chromatic symmetric function in noncommuting variables
• A symmetric function generalization of the chromatic polynomial of a graph
• Chromatic quasisymmetric functions
• Chromatic quasisymmetric functions and Hessenberg varieties
• Counting permutations with given cycle structure and descent set
• Formal group laws and chromatic symmetric functions of hypergraphs
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3895079 (Why is no real title available?)
• Hypergraphs and a functional equation of Bouwkamp and de Bruijn
• Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
• On distinguishing trees by their chromatic symmetric functions
• Ordered structures and partitions
• Proper caterpillars are distinguished by their chromatic symmetric function
• Scheduling problems

Cited in

(7)

• \(H\)-chromatic symmetric functions
• Plethysms of chromatic and Tutte symmetric functions
• Plurigraph coloring and scheduling problems
• Chromatic symmetric functions via the group algebra of \(S_n\)
• Formal group laws and chromatic symmetric functions of hypergraphs
• Marked Graphs and the Chromatic Symmetric Function
• The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Chromatic symmetric functions of hypertrees

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