#Tutte symmetric functions
The Tutte symmetric functions were introduced by R. Stanley [Def. 3.1, Sta98], and generalize the chromatic symmetric functions. See also [ACSZ20] for a vertex-weighted generalization.
The Tutte symmetric functions are indexed by graphs, and defined as \[\tutte_G(\xvec;t) \coloneqq \sum_{\pi \vdash V(G)} (1+t)^{a(\pi)} \tilde{\monomial}_{\lambda(\pi)}\] 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)\) denotes 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 \[\tutte_G(\xvec;t) \coloneqq \sum_{\kappa : V(G) \to \setN} (1+t)^{m(\kappa)} x_{\kappa(1)} \dotsm x_{\kappa(n)}\] 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.\)
Example
For the graph \(K_2\) with one edge, \[\tutte_{K_2}(\xvec;t) = \tilde{\monomial}_{11} + (1+t)\tilde{\monomial}_{2}.\] At \(t=-1,\) only the proper colorings remain, giving \(\chrom_{K_2}(\xvec) = \tilde{\monomial}_{11}.\)
A quasisymmetric version of the Tutte symmetric functions was introduced in [AB16]. In [Thm. 7.15, AS19], we give the expansion of these polynomials in the quasisymmetric powersum basis.
See [CS21] for more results on the Tutte symmetric functions. L. Crew and S. Spirkl also give graph-theoretic interpretations for plethysms based on chromatic and Tutte symmetric functions [CS22]. This yields short proofs of several plethystic identities and chromatic-symmetric-function identities.
#Powersum expansion
Stanley’s powersum expansion is \[\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
A 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].
Bibliography
- [AS19]Per Alexandersson and Robin Sulzgruber. P-partitions and p-positivity. International Mathematics Research Notices, 2021(14):10848–10907, July 2019.
.bib
@article{AlexanderssonSulzgruber2019, title = {{P}-Partitions and {p}-Positivity}, volume = {2021}, ISSN = {1687-0247}, url = {http://dx.doi.org/10.1093/imrn/rnz130}, DOI = {10.1093/imrn/rnz130}, number = {14}, journal = {International Mathematics Research Notices}, publisher = {Oxford University Press (OUP)}, author = {Alexandersson, Per and Sulzgruber, Robin}, year = {2019}, month = jul, pages = {10848–10907} } - [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:2007.11042, 2020.
.bib
@article{AlistePrietoCrewSpirklZamora2020x, Author = {José Aliste-Prieto and Logan Crew and Sophie Spirkl and José Zamora}, Title = {A Vertex-Weighted {T}utte Symmetric Function, and Constructing Graphs with Equal Chromatic Symmetric Function}, Year = {2020}, Eprint = {2007.11042}, url = {https://arxiv.org/abs/2007.11042}, journal = {arXiv e-prints} } - [AB16]Jordan Awan and Olivier Bernardi. Tutte polynomials for directed graphs. arXiv:1610.01839, 2016.
.bib
@article{AwanBernardi2016, Author = {Jordan Awan and Olivier Bernardi}, Title = {Tutte polynomials for directed graphs}, Year = {2016}, Eprint = {1610.01839}, url = {https://arxiv.org/abs/1610.01839}, journal = {arXiv e-prints} } - [CS21]Logan Crew and Sophie Spirkl. A Complete Multipartite Basis for the Chromatic Symmetric Function. SIAM Journal on Discrete Mathematics, 35(4):2647–2661, 2021.
.bib
@article{CrewSpirkl2020x, author = {Crew, Logan and Spirkl, Sophie}, title = {A {C}omplete {M}ultipartite {B}asis for the {C}hromatic {S}ymmetric {F}unction}, year = {2021}, journal = {SIAM Journal on Discrete Mathematics}, volume = {35}, number = {4}, pages = {2647--2661}, publisher = {Society for Industrial \& Applied Mathematics (SIAM)}, doi = {10.1137/20m1380314}, url = {http://dx.doi.org/10.1137/20M1380314}, issn = {1095-7146} } - [CS22]Logan Crew and Sophie Spirkl. Plethysms of chromatic and Tutte symmetric functions. The Electronic Journal of Combinatorics, 29(3), 2022.
.bib
@article{CrewSpirkl2022Plethysm, author = {Logan Crew and Sophie Spirkl}, title = {Plethysms of chromatic and {T}utte symmetric functions}, year = {2022}, journal = {The Electronic Journal of Combinatorics}, volume = {29}, number = {3}, doi = {10.37236/10637}, url = {https://doi.org/10.37236/10637}, eprint = {2108.03188} } - [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.
.bib
@article{McDonaldMoffatt2012, doi = {10.1007/s10955-012-0449-2}, url2 = {https://doi.org/10.1007/s10955-012-0449-2}, year = {2012}, month = feb, publisher = {Springer Science and Business Media {LLC}}, volume = {146}, number = {6}, pages = {1288--1302}, author = {Leslie M. McDonald and Iain Moffatt}, title = {On the {P}otts Model Partition Function in an External Field}, journal = {Journal of Statistical Physics} } - [Sta98]Richard P. Stanley. Graph colorings and related symmetric functions: Ideas and applications. Discrete Mathematics, 193(1):267–286, 1998.
.bib
@article{Stanley1998, title = {Graph colorings and related symmetric functions: ideas and applications}, journal = {Discrete Mathematics}, volume = {193}, number = {1}, pages = {267--286}, year = {1998}, issn = {0012-365X}, doi = {10.1016/S0012-365X(98)00146-0}, url2 = {http://www.sciencedirect.com/science/article/pii/S0012365X98001460}, author = {Richard P. Stanley} }