The path-cycle symmetric function of a digraph
type: Item
instance of: scholarly article
title: The path-cycle symmetric function of a digraph
zbMATH Open document ID: 0847.05098
published in: Advances in Mathematics
publication date: 1996-06-16T00:00:00Z
review text: Recently, \textit{R. P. Stanley} [Adv. Math. 111, No. 1, 166-194 (1995; Zbl 0831.05027)] has defined a symmetric function generalization of the chromatic polynomial of a graph. Independently, \textit{F. Chung} and \textit{R. Graham} [On digraph polynomials, preprint (1993)] have defined a digraph polynomial called the cover polynomial which is closely related to the chromatic polynomial of a graph (in fact, as we shall see, the cover polynomial of a certain digraph associated to a poset \(P\) coincides with the chromatic polynomial of the incomparability graph of \(P\)) and also to rook polynomials. The starting point for the present paper is the suggestion in Chung and Graham's paper that the cover polynomial might generalize to a symmetric function in much the same way that the chromatic polynomial does. This is indeed the case, and in this paper we shall study this symmetric function generalization of the cover polynomial. As one would expect, there are a number of generalizations and analogues of known results about the cover polynomial, the rook polynomial, and Stanley's chromatic symmetric function. In addition, however, we will obtain some unexpected dividends, such as a combinatorial reciprocity theorem that answers a question of Chung and Graham and ties together a number of known results that previously seemed unrelated, and a new symmetric function basis that appears to be a natural counterpart of the polynomial basis \({x+n \choose d}_{n = 0,\dots, d}\). One reason for these unexpected results is that this topic lies at the intersection of several branches of combinatorics; their interaction naturally gives rise to new connections and ideas. We shall indicate several directions for further research in this potentially very rich area of study.
Mathematics Subject Classification ID: 05E05
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 889811
zbMATH Keywords: symmetric function
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: digraph polynomial
zbMATH Keywords: cover polynomial
zbMATH Keywords: incomparability graph
zbMATH Keywords: rook polynomials
zbMATH Keywords: chromatic symmetric function
zbMATH Keywords: combinatorial reciprocity theorem
author: Timothy Y. Chow
MaRDI profile type: Publication
OpenAlex ID: W2147911079
DOI: 10.1006/AIMA.1996.0018
Recommended article: The cycle-path indicator polynomial of a digraph
Recommended article: Q4710112
Recommended article: Symmetrical path-cycle covers of a graph and polygonal graphs
Recommended article: Symmetric Dyck paths and Hooley's \(\varDelta\)-function
Recommended article: Almost symmetric cycles in large digraphs
Recommended article: Cycle-factorization of symmetric complete multipartite digraphs
Recommended article: A bijection on Dyck paths and its cycle structure
Recommended article: Q4293929
Recommended article: Symmetric Walks on Paths and Cycles
Recommended article: Q5135774
description: scientific article; zbMATH DE number 889811