The Peterson recurrence formula for the chromatic discriminant of a graph
Tóm tắt
The absolute value of the coefficient of q in the chromatic polynomial of a graph G is known as the chromatic discriminant of G and is denoted α(G). There is a well known recurrence formula for α(G) that comes from the deletion-contraction rule for the chromatic polynomial. In this paper we prove another recurrence formula for α(G) that comes from the theory of Kac- Moody Lie algebras. We start with a brief survey on many interesting algebraic and combinatorial interpretations of α(G). We use two of these interpretations (in terms of acyclic orientations and spanning trees) to give two bijective proofs for our recurrence formula of α(G).
Tài liệu tham khảo
G. Arunkumar, Deniz Kus and R. Venkatesh, Root multiplicities for Borcherds algebras and graph coloring, J. Algebra, 499 (2018), 538–569.
Brian Benson, Deeparnab Chakrabarty and Prasad Tetali, G-parking functions, acyclic orientations and spanning trees, Discrete Math., 310(8) (2010), 1340–1353.
Andreas Blass and Bruce Eli Sagan, Bijective proofs of two broken circuit theorems, J. Graph Theory, 10(1) (1986), 15–21.
Henrik Eriksson and Kimmo Eriksson, Conjugacy of Coxeter elements, Electron. J. Combin., 16(2), Special volume in honor of Anders Björner, 4(7), 2009.
David D. Gebhard and Bruce E. Sagan, Sinks in acyclic orientations of graphs, J. Combin. Theory Ser. B, 80(1) (2000), 130–146.
Chris Godsil and Gordon Royle, Algebraic graph theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001.
Curtis Greene and Thomas Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Amer. Math. Soc., 280(1) (1983), 97–126.
V. G. Kac, Infinite dimensional Lie algebras, Cambridge University Press, third edition, 1990.
Pierre Lalonde, Bases de Lyndon des algèbres de Lie libres partiellement commutatives, Theoret. Comput. Sci., 117(1-2) (1993), 217–226, Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991).
Pierre Lalonde, Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids, Discrete Math., 145(1-3) (1995), 171–189.
BodoˆLass, Orientations acycliques et le polynôme chromatique, European J. Combin., 22(8) (2001), 1101–1123.
Matthew Macauley and Henning S. Mortveit, On enumeration of conjugacy classes of Coxeter elements, Proc. Amer. Math. Soc., 136(12) (2008), 4157–4165.
Jian-yi Shi, Conjugacy relation on Coxeter elements, Adv. Math., 161(1) (2001), 1–19.
Y. Shi, M. Dehmer, X. Li and I. Gutman, Graph polynomials, Discrete Mathematics and its applications, CRC Press, 2016.
R. Venkatesh and Sankaran Viswanath, Chromatic polynomials of graphs from Kac-Moody algebras, J. Algebraic Combin., 41(4) (2015), 1133–1142.
Gérard Xavier Viennot, Commutations and heaps of pieces, chapter 5, Lectures at IMSc, Chennai, www.xavierviennot.org/coursIMSc2017/ Ch 5 files/cours IMSc17 Ch5a.pdf.