• Source: Chromatic symmetric function

The chromatic symmetric function is a symmetric function invariant of graphs studied in algebraic graph theory, a branch of mathematics. It is the weight generating function for proper graph colorings, and was originally introduced by Richard Stanley as a generalization of the chromatic polynomial of a graph.




Definition


For a finite graph



G
=
(
V
,
E
)


{\displaystyle G=(V,E)}

with vertex set



V
=
{

v

1


,

v

2


,
…
,

v

n


}


{\displaystyle V=\{v_{1},v_{2},\ldots ,v_{n}\}}

, a vertex coloring is a function



κ
:
V
→
C


{\displaystyle \kappa :V\to C}

where



C


{\displaystyle C}

is a set of colors. A vertex coloring is called proper if all adjacent vertices are assigned distinct colors (i.e.,



{
i
,
j
}
∈
E

⟹

κ
(
i
)
≠
κ
(
j
)


{\displaystyle \{i,j\}\in E\implies \kappa (i)\neq \kappa (j)}

). The chromatic symmetric function denoted




X

G


(

x

1


,

x

2


,
…
)


{\displaystyle X_{G}(x_{1},x_{2},\ldots )}

is defined to be the weight generating function of proper vertex colorings of



G


{\displaystyle G}

:




X

G


(

x

1


,

x

2


,
…
)
:=

∑



κ
:
V
→

N


proper




x

κ
(

v

1


)



x

κ
(

v

2


)


⋯

x

κ
(

v

n


)




{\displaystyle X_{G}(x_{1},x_{2},\ldots ):=\sum _{\underset {\text{proper}}{\kappa :V\to \mathbb {N} }}x_{\kappa (v_{1})}x_{\kappa (v_{2})}\cdots x_{\kappa (v_{n})}}





Examples


For



λ


{\displaystyle \lambda }

a partition, let




m

λ




{\displaystyle m_{\lambda }}

be the monomial symmetric polynomial associated to



λ


{\displaystyle \lambda }

.




= Example 1: complete graphs

=
Consider the complete graph




K

n




{\displaystyle K_{n}}

on



n


{\displaystyle n}

vertices:

There are



n
!


{\displaystyle n!}

ways to color




K

n




{\displaystyle K_{n}}

with exactly



n


{\displaystyle n}

colors yielding the term



n
!

x

1


⋯

x

n




{\displaystyle n!x_{1}\cdots x_{n}}


Since every pair of vertices in




K

n




{\displaystyle K_{n}}

is adjacent, it can be properly colored with no fewer than



n


{\displaystyle n}

colors.
Thus,




X


K

n




(

x

1


,
…
,

x

n


)
=
n
!

x

1


⋯

x

n


=
n
!

m

(
1
,
…
,
1
)




{\displaystyle X_{K_{n}}(x_{1},\ldots ,x_{n})=n!x_{1}\cdots x_{n}=n!m_{(1,\ldots ,1)}}





= Example 2: a path graph

=
Consider the path graph




P

3




{\displaystyle P_{3}}

of length



3


{\displaystyle 3}

:

There are



3
!


{\displaystyle 3!}

ways to color




P

3




{\displaystyle P_{3}}

with exactly



3


{\displaystyle 3}

colors, yielding the term



6

x

1



x

2



x

3




{\displaystyle 6x_{1}x_{2}x_{3}}


For each pair of colors, there are



2


{\displaystyle 2}

ways to color




P

3




{\displaystyle P_{3}}

yielding the terms




x

i


2



x

j




{\displaystyle x_{i}^{2}x_{j}}

and




x

i



x

j


2




{\displaystyle x_{i}x_{j}^{2}}

for



i
≠
j


{\displaystyle i\neq j}


Altogether, the chromatic symmetric function of




P

3




{\displaystyle P_{3}}

is then given by:




X


P

3




(

x

1


,

x

2


,

x

3


)
=
6

x

1



x

2



x

3


+

x

1


2



x

2


+

x

1



x

2


2


+

x

1


2



x

3


+

x

1



x

3


2


+

x

2


2



x

3


+

x

2



x

3


2


=
6

m

(
1
,
1
,
1
)


+

m

(
1
,
2
)




{\displaystyle X_{P_{3}}(x_{1},x_{2},x_{3})=6x_{1}x_{2}x_{3}+x_{1}^{2}x_{2}+x_{1}x_{2}^{2}+x_{1}^{2}x_{3}+x_{1}x_{3}^{2}+x_{2}^{2}x_{3}+x_{2}x_{3}^{2}=6m_{(1,1,1)}+m_{(1,2)}}





Properties


Let




χ

G




{\displaystyle \chi _{G}}

be the chromatic polynomial of



G


{\displaystyle G}

, so that




χ

G


(
k
)


{\displaystyle \chi _{G}(k)}

is equal to the number of proper vertex colorings of



G


{\displaystyle G}

using at most



k


{\displaystyle k}

distinct colors. The values of




χ

G




{\displaystyle \chi _{G}}

can then be computed by specializing the chromatic symmetric function, setting the first



k


{\displaystyle k}

variables




x

i




{\displaystyle x_{i}}

equal to



1


{\displaystyle 1}

and the remaining variables equal to



0


{\displaystyle 0}

:




X

G


(

1

k


)
=

X

G


(
1
,
…
,
1
,
0
,
0
,
…
)
=

χ

G


(
k
)


{\displaystyle X_{G}(1^{k})=X_{G}(1,\ldots ,1,0,0,\ldots )=\chi _{G}(k)}


If



G
⨿
H


{\displaystyle G\amalg H}

is the disjoint union of two graphs, then the chromatic symmetric function for



G
⨿
H


{\displaystyle G\amalg H}

can be written as a product of the corresponding functions for



G


{\displaystyle G}

and



H


{\displaystyle H}

:




X

G
⨿
H


=

X

G


⋅

X

H




{\displaystyle X_{G\amalg H}=X_{G}\cdot X_{H}}


A stable partition



π


{\displaystyle \pi }

of



G


{\displaystyle G}

is defined to be a set partition of vertices



V


{\displaystyle V}

such that each block of



π


{\displaystyle \pi }

is an independent set in



G


{\displaystyle G}

. The type of a stable partition




type

(
π
)


{\displaystyle {\text{type}}(\pi )}

is the partition consisting of parts equal to the sizes of the connected components of the vertex induced subgraphs. For a partition



λ
⊢
n


{\displaystyle \lambda \vdash n}

, let




z

λ




{\displaystyle z_{\lambda }}

be the number of stable partitions of



G


{\displaystyle G}

with




type

(
π
)
=
λ
=
⟨

1


r

1





2

r
2


…
⟩


{\displaystyle {\text{type}}(\pi )=\lambda =\langle 1^{r_{1}}2^{r2}\ldots \rangle }

. Then,




X

G




{\displaystyle X_{G}}

expands into the augmented monomial symmetric functions,







m
~




λ


:=

r

1


!

r

2


!
⋯

m

λ




{\displaystyle {\tilde {m}}_{\lambda }:=r_{1}!r_{2}!\cdots m_{\lambda }}

with coefficients given by the number of stable partitions of



G


{\displaystyle G}

:




X

G


=

∑

λ
⊢
n



z

λ






m
~




λ




{\displaystyle X_{G}=\sum _{\lambda \vdash n}z_{\lambda }{\tilde {m}}_{\lambda }}


Let




p

λ




{\displaystyle p_{\lambda }}

be the power-sum symmetric function associated to a partition



λ


{\displaystyle \lambda }

. For



S
⊆
E


{\displaystyle S\subseteq E}

, let



λ
(
S
)


{\displaystyle \lambda (S)}

be the partition whose parts are the vertex sizes of the connected components of the edge-induced subgraph of



G


{\displaystyle G}

specified by



S


{\displaystyle S}

. The chromatic symmetric function can be expanded in the power-sum symmetric functions via the following formula:




X

G


=

∑

S
⊆
E


(
−
1

)


|

S

|




p

λ
(
S
)




{\displaystyle X_{G}=\sum _{S\subseteq E}(-1)^{|S|}p_{\lambda (S)}}


Let




X

G


=

∑

λ
⊢
n



c

λ



e

λ




{\textstyle X_{G}=\sum _{\lambda \vdash n}c_{\lambda }e_{\lambda }}

be the expansion of




X

G




{\displaystyle X_{G}}

in the basis of elementary symmetric functions




e

λ




{\displaystyle e_{\lambda }}

. Let




sink

(
G
,
s
)


{\displaystyle {\text{sink}}(G,s)}

be the number of acyclic orientations on the graph



G


{\displaystyle G}

which contain exactly



s


{\displaystyle s}

sinks. Then we have the following formula for the number of sinks:




sink

(
G
,
s
)
=

∑



λ
⊢
n


l
(
λ
)
=
s





c

λ




{\displaystyle {\text{sink}}(G,s)=\sum _{\underset {l(\lambda )=s}{\lambda \vdash n}}c_{\lambda }}





Open problems


There are a number of outstanding questions regarding the chromatic symmetric function which have received substantial attention in the literature surrounding them.




= (3+1)-free conjecture

=
For a partition



λ


{\displaystyle \lambda }

, let




e

λ




{\displaystyle e_{\lambda }}

be the elementary symmetric function associated to



λ


{\displaystyle \lambda }

.
A partially ordered set



P


{\displaystyle P}

is called



(
3
+
1
)


{\displaystyle (3+1)}

-free if it does not contain a subposet isomorphic to the direct sum of the



3


{\displaystyle 3}

element chain and the



1


{\displaystyle 1}

element chain. The incomparability graph




inc

(
P
)


{\displaystyle {\text{inc}}(P)}

of a poset



P


{\displaystyle P}

is the graph with vertices given by the elements of



P


{\displaystyle P}

which includes an edge between two vertices if and only if their corresponding elements in



P


{\displaystyle P}

are incomparable.
Conjecture (Stanley–Stembridge) Let



G


{\displaystyle G}

be the incomparability graph of a



(
3
+
1
)


{\textstyle (3+1)}

-free poset, then




X

G




{\textstyle X_{G}}

is



e


{\displaystyle e}

-positive.
A weaker positivity result is known for the case of expansions into the basis of Schur functions.
Theorem (Gasharov) Let



G


{\displaystyle G}

be the incomparability graph of a



(
3
+
1
)


{\textstyle (3+1)}

-free poset, then




X

G




{\textstyle X_{G}}

is



s


{\displaystyle s}

-positive.
In the proof of the theorem above, there is a combinatorial formula for the coefficients of the Schur expansion given in terms of



P


{\displaystyle P}

-tableaux which are a generalization of semistandard Young tableaux instead labelled with the elements of



P


{\displaystyle P}

.




Generalizations


There are a number of generalizations of the chromatic symmetric function:

There is a categorification of the invariant into a homology theory which is called chromatic symmetric homology. This homology theory is known to be a stronger invariant than the chromatic symmetric function alone. The chromatic symmetric function can also be defined for vertex-weighted graphs, where it satisfies a deletion-contraction property analogous to that of the chromatic polynomial. If the theory of chromatic symmetric homology is generalized to vertex-weighted graphs as well, this deletion-contraction property lifts to a long exact sequence of the corresponding homology theory.
There is also a quasisymmetric refinement of the chromatic symmetric function which can be used to refine the formulae expressing




X

G




{\displaystyle X_{G}}

in terms of Gessel's basis of fundamental quasisymmetric functions and the expansion in the basis of Schur functions. Fixing an order for the set of vertices, the ascent set of a proper coloring



κ


{\displaystyle \kappa }

is defined to be




asc

(
κ
)
=
{
{
i
,
j
}
∈
E
:
i
<
j

and

κ
(
i
)
<
κ
(
j
)
}


{\displaystyle {\text{asc}}(\kappa )=\{\{i,j\}\in E:i
. The chromatic quasisymmetric function of a graph



G


{\displaystyle G}

is then defined to be:




X

G


(

x

1


,

x

2


,
…
;
t
)
:=

∑



κ
:
V
→

N


proper




t


|

a
s
c
(
κ
)

|




x

κ
(

v

1


)


⋯

x

κ
(

v

n


)




{\displaystyle X_{G}(x_{1},x_{2},\ldots ;t):=\sum _{\underset {\text{proper}}{\kappa :V\to \mathbb {N} }}t^{|asc(\kappa )|}x_{\kappa (v_{1})}\cdots x_{\kappa (v_{n})}}





See also


Chromatic polynomial
Symmetric function




References






Further reading


Blasiak, Jonah; Eriksson, Holden; Pylyavskyy, Pavlo; Siegl, Isaiah (2022). "Noncommutative Schur functions for posets". arXiv:2211.03967 [math.CO].
Chow, Timothy Y. (1999). "Descents, Quasi-Symmetric Functions, Robinson-Schensted for Posets, and the Chromatic Symmetric Function". Journal of Algebraic Combinatorics. 10 (3): 227–240. doi:10.1023/A:1018719315718.
Harada, Megumi; Precup, Martha E. (2019). "The cohomology of abelian Hessenberg varieties and the Stanley–Stembridge conjecture". Algebraic Combinatorics. 2 (6): 1059–1108. arXiv:1709.06736. doi:10.5802/alco.76.
Hwang, Byung-Hak (2024). "Chromatic quasisymmetric functions and noncommutative



P


{\displaystyle P}

-symmetric functions". Transactions of the American Mathematical Society. 377 (4): 2855–2896. arXiv:2208.09857. doi:10.1090/tran/9096.
Shareshian, John; Wachs, Michelle L. (2012). "Chromatic quasisymmetric functions and Hessenberg varieties". Configuration Spaces. pp. 433–460. arXiv:1106.4287. doi:10.1007/978-88-7642-431-1_20. ISBN 978-88-7642-430-4.

Kata Kunci Pencarian:

• Daftar masalah matematika yang belum terpecahkan
• Chromatic symmetric function
• Chromatic polynomial
• Chromatic scale
• Graph coloring
• Optical transfer function
• Function (music)
• Augmented sixth chord
• Optical aberration
• Petersen graph
• Lovász number