The symmetric functions catalog

An overview of symmetric functions and related topics

2021-03-04

Tutte symmetric functions

The Tutte symmetric functions were introduced by R. Stanley [Def. 3.1, Sta98], and generalize the chromatic symmetric functions.

The Tutte symmetric functions are indexed by graphs, and defined as

\begin{equation} \tutte_G(\xvec;t) \coloneqq \sum_{\pi \vdash V(G)} (1+t)^{a(\pi)} \tilde{\monomial}_{\lambda(\pi)} \end{equation}

where the $\tilde{\monomial}$ denote augmented monomial symmetric functions, and the sum is taken over all set-partitions of the vertex set of $G.$ Here, $a(\pi)$ denote the number of attacking edges — edges where both endpoints are in the same block of $\pi.$

Alternatively, for a graph on $n$ vertices, we have

\begin{equation} \tutte_G(\xvec;t) \coloneqq \sum_{\kappa : V(G) \to \setN} (1+t)^{m(\kappa)} x_{\kappa(1)} \dotsm x_{\kappa(n)} \end{equation}

where the sum is over all vertex colorings of $G,$ and $m(\kappa)$ counts the number of monochromatic edges in the coloring.

Note that $\tutte_G(\xvec; -1) = \chrom_G(\xvec),$ that is, we recover the chromatic symmetric function at $t=-1.$

A quasisymmetric version of the Tutte symmetric functions were introduced in [AB16]. In [Thm. 7.15, AS19b], we give the expansion of these polynomials in the quasisymmetric powersum basis.

See [CS20] for more results on the Tutte symmetric functions.

Powersum expansion

We have that (see [Sta98])

\[ \tutte_G(\xvec;t) = \sum_{S \subseteq E(G)} t^{|S|} \powerSum_{\lambda(S)}(\xvec) \]

where $\lambda(S)$ denotes the sizes of the connected components induced by $S.$

Spanning tree expansion

Formula for computing $\tutte_G(\xvec;t)$ using spanning trees and spanning forests is given in [MM12]. This generalizes the classical formula for computing Tutte polynomials using spanning trees. A vertex-weighted version is stated in [Eq. (15), ACSZ20].

References