Root multiplicities for Borcherds-Kac-Moody algebras and graph coloring[HBNI Th140]

Abstract

Borcherds-Kac-Moody algebras (Borcherds algebras in short) were introduced by R. Borcherds as a natural generalization of Kac-Moody algebras. The theory of Borcherds algebras gained much interest because of its application in Borcherds’s proof of the Conway-Nortan conjecture on the representation theory of the Monster finite simple group. The most important step in understanding the structure of these algebras is to study roots and root multiplicities; the imaginary roots being the most mysterious ones. We establish a connection between root multiplicities for Borcherds algebras and graph coloring. We show that the generalized chromatic polynomial of the graph associated to a given Borcherds algebra can be used to give a closed formula for certain root multiplicities. Using this connection we give a second interpretation, namely that the root multiplicity of a given root coincides with the number of acyclic orientations with a unique sink of a certain graph (depending on the root). We will use the closed formula and the combinatorics of Lyndon words to construct a family of bases for certain root spaces. The most interesting case arises when all simple roots are imaginary, In this case, the positive part of a Borcherds algebra is isomorphic to the free partially commutative Lie algebra associated with the graph G. Finding a basis for these types of Lie algebras is the central study in the theory of free partially commutative Lie algebras; the best known such basis is the Lyndon-Shirshov basis and Chibrikov’s right-normed basis for free Lie algebras. The right-normed basis for free partially commutative Lie algebras is not known and we give a partial answer to this question by constructing right normed basis for certain grade spaces of these algebras. Next, we study the evaluation of the generalized chromatic polynomial at any integer. We show that these numbers show up in the Hilbert series of the q-fold tensor product of the universal enveloping algebra associated to free partially commutative Lie algebras. We use this interpretation to give a simple Lie theoretic proof of Stanley’s reciprocity theorem of chromatic polynomials. Finally, we study the combinatorial properties of the linear coefficient of the chromatic polynomial. 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).