2022-12-28
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
- [AB16] Jordan Awan and Olivier Bernardi. Tutte polynomials for directed graphs. arXiv e-prints, 2016.
- [ACSZ20] José Aliste-Prieto, Logan Crew, Sophie Spirkl and José Zamora. A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function. arXiv e-prints, 2020.
- [AS19b] Per Alexandersson and Robin Sulzgruber. P-partitions and P-positivity. International Mathematics Research Notices, July 2019.
- [CS20] Logan Crew and Sophie Spirkl. A complete multipartite basis for the chromatic symmetric function. arXiv e-prints, 2020.
- [MM12] Leslie M. McDonald and Iain Moffatt. On the Potts model partition function in an external field. Journal of Statistical Physics, 146(6):1288–1302, February 2012.
- [Sta98] Richard P. Stanley. Graph colorings and related symmetric functions: ideas and applications. Discrete Mathematics, 193(1):267–286, 1998.