Abstract
We prove that the generating function for the symmetric chromatic polynomial of all simple graphs is (after an appropriate scaling change of variables) a linear combination of one-part Schur polynomials. This statement immediately implies that it is also a \(\tau \)-function of the Kadomtsev–Petviashvili integrable hierarchy of mathematical physics. Moreover, we describe a large family of polynomial graph invariants leading to the same \(\tau \)-function. In particular, we introduce the Abel polynomial for graphs and show this for its generating function. The key point here is a Hopf algebra structure on the space spanned by graphs and the behavior of the invariants on its primitive space.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abel, N.H.: Beweis eines Ausdruckes, von welchem die Binomialformel ein einzelner Fall ist. Journal für die reine und angewandte Mathematik 1, 159–160 (1826)
Aguiar, M., Bergeron, N., Sottile, F.: Combinatorial Hopf algebras and generalized Dehn–Sommerville relations. Compos. Math. 142, 1–30 (2006)
Billey, S., McNamara, P.: The contributions of Stanley to the fabric of symmetric and quasisymmetric functions. In: Herch, P., Lam, T., Pylyavskyy, P., Reiner, V. (eds.) The Mathematical Legacy of Richard P. Stanley, pp. 83–104. AMS, Providence (2016)
Chebotarev, P., Shamis, E.: Matrix-Forest Theorems. arXiv:math/0602575 [math.CO]
Chmutov, S., Duzhin, S., Lando, S.: Vassiliev knot invariants III. Forest algebra and weighted graphs. Adv. Sov. Math. 21, 135–145 (1994)
Goulden, I.P., Jackson, D.M.: The KP hierarchy, branched covers, and triangulations. Adv. Math. 219(3), 932–951 (2008)
Joni, S., Rota, G.-C.: Coalgebras and bialgebras in combinatorics. Stud. Appl. Math. 61(2), 93–139 (1979)
Kadomtsev, B.B., Petviashvili, V.I.: On the stability of solitary waves in weakly dispersive media. Sov. Phys. Dokl. 15, 539–541 (1970)
Kazarian, M., Lando, S.: Combinatorial solutions to integrable hierarchies. Russ. Math. Surv. 70(3), 453–482 (2015)
Kelmans, A.K., Chelnokov, V.N.: A certain polynomial of a graph and graphs with an extremal number of trees. J. Comb. Theory Ser. B 16, 197–214 (1974)
Knill, O.: Counting rooted forests in a network. arXiv:1307.3810 [math.SP]
Krasilnikov, E.: Invariants of framed graphs and the Kadomtsev–Petviashvili hierarchy. Funct. Anal. Appl. 53, 14–26 (2019)
Lando, S. K.: On primitive elements in the bialgebra of chord diagrams. In: Topics in Singularity Theory. American Mathematical Society Translations: Series 2, 180, Adv. Math. Sci., vol. 34, pp. 167–174. American Mathematical Society, Providence (1997)
Lando, S.K.: On a Hopf algebra in graph theory. J. Comb. Theory Ser. B 80, 104–121 (2000)
Noble, S., Welsh, D.: A weighted graph polynomial from chromatic invariants of knots. Annales de l’institut Fourier 49(3), 1057–1087 (1999)
Okounkov, A.: Toda equations for Hurwitz numbers. Math. Res. Lett. 7(4), 447–453 (2000)
Pitman, J.: Forest volume decompositions and Abel–Cayley–Hurwitz multinomial expansions. J. Comb. Theory Ser. A 98(1), 175–191 (2002)
Roman, S., Rota, G.-C.: The umbral calculus. Adv. Math. 27, 95–188 (1978)
Rota, G.-C., Shen, J., Taylor, B.: All polynomials of binomial type are represented by Abel polynomials. Annali della Scuola Normale Superiore di Pisa Classe di Scienze, Série 4 25(3–4), 731–738 (1997)
Sato, M., Sato, Y.: Soliton equations as dynamical systems on infinite dimensional Grassmann manifolds. In: Nonlinear Partial Differential Equations in Applied Science (Tokyo 1982), Norrth-Holland Mathematics Studies, vol. 81, pp. 259–271. North-Holland, Amsterdam (1983)
Schmitt, W.R.: Incidence Hopf algebras. J. Pure Appl. Algebra 96, 299–330 (1994)
Schmitt, W.R.: Hopf algebra methods in graph theory. J. Pure Appl. Algebra 101(1), 77–90 (1995)
Stanley, R.: A symmetric function generalization of the chromatic polynomial of a graph. Adv. Math. 111(1), 166–194 (1995)
The On-Line Encyclopedia of Integer Sequences. http://oeis.org/A134531
Acknowledgements
The work on this paper started during the third author’s visit to the Ohio State University, to which he expresses his gratitude. The second author appreciates the support of RSF Grant, Project 16-11-10316 dated 11.05.2016.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
