e-basis Coefficients of Chromatic Symmetric Functions

Publication date 7 October 2022

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

Abstract: A well-known result of Stanley's shows that given a graph

G

with chromatic symmetric function expanded into the basis of elementary symmetric functions as

X_{G} = s u m c_{l a m b d a} e_{l a m b d a}

, the sum of the coefficients

c_{l a m b d a}

for

l a m b d a

with exactly

k

parts is equal to the number of acyclic orientations of

G

with exactly

k

sinks. However, more is known. The

s i n k

s e q u e n c e

of an acyclic orientation of

G

is a tuple

(s_{1}, d o t s, s_{k})

such that

s_{1}

is the number of sinks of the orientation, and recursively each

s_{i}

with

i > 1

is the number of sinks remaining after deleting the sinks contributing to

s_{1}, d o t s, s_{i - 1}

. Equivalently, the sink sequence gives the number of vertices at each level of the poset induced by the acyclic orientation. A lesser-known follow-up result of Stanley's determines certain cases in which we can find a sum of

e

-basis coefficients that gives the number of acyclic orientations of

G

with a given partial sink sequence. Of interest in its own right, this result also admits as a corollary a simple proof of the

e

-positivity of

X_{G}

when the stability number of

G

is

2

. In this paper, we prove a vertex-weighted generalization of this follow-up result, and conjecture a stronger version that admits a similar combinatorial interpretation for a much larger set of

e

-coefficient sums of chromatic symmetric functions. In particular, the conjectured formula would give a combinatorial interpretation for the sum of the coefficients

c_{l a m b d a}

with prescribed values of

l a m b d {a_{1}}^{'}

and

l a m b d {a_{2}}^{'}

for any unweighted claw-free graph.

This page was built for publication: e-basis Coefficients of Chromatic Symmetric Functions

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