Generalised chromatic polynomials of graphs from heaps of pieces

DOI10.1007/S00026-022-00571-WMaRDI QIDQ2155545zbMATH OpenOpenAlexFDO

Authors G. Arunkumar

Publication date 15 July 2022

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.08864

zbMATH Keywords

acyclic orientationschromatic polynomialschromatic reciprocity theoremfree partially commutative Lie algebrasheaps of piecesLyndon heapspyramid proportionality lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Combinatorial aspects of groups and algebras (05E16) Identities, free Lie (super)algebras (17B01) Kac-Moody (super)algebras; extended affine Lie algebras; toroidal Lie algebras (17B67)

Abstract: Let $G$ be a simple graph and let $mathcalL(G)$ be the free partially commutative Lie algebra associated to $G$. In this paper, using heaps of pieces, we prove an expression for the generalized $extbfk$-chromatic polynomial of $G$ in terms of dimensions of the grade spaces of $mathcalL(G)$. This will give us a new interpretation for the chromatic polynomials in terms of multilinear heaps and Lyndon length. The classical results of Stanley, and Greene and Zaslavsky regarding the acyclic orientations of $G$ are obtained as corollaries. A heap with a unique minimal piece is said to be a pyramid and our main theorem is proved using the properties of pyramids. For this reason, we prove two important properties of pyramids namely the pyramid proportionality lemma, and the pyramid and Lyndon heap lemma. In the last section, we will introduce the $(m,lambda)$-labelling on acyclic orientations which is similar to Stanley's $lambda$-compatible pairs. As an application of our main theorem, using this $(m,lambda)$-labelled acyclic orientations, we will prove the reciprocity theorem for the derivatives of the chromatic polynomials.

Recommendations

• Chromatic polynomials of graphs from Kac-Moody algebras
• Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
• A symmetric function generalization of the chromatic polynomial of a graph
• Acyclic orientations and the chromatic polynomial
• Acyclic heaps of pieces. I.

Cites work

• A logical expansion in mathematics
• A symmetric function generalization of the chromatic polynomial of a graph
• Acyclic orientations and the chromatic polynomial
• Acyclic orientations of graphs
• An introduction to chromatic polynomials
• Chromatic polynomials of graphs from Kac-Moody algebras
• Chromatic symmetric function of graphs from Borcherds algebras
• Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
• Combinatorics of minuscule representations
• Expansions of Chromatic Polynomials and Log-Concavity
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• scientific article; zbMATH DE number 194085 (Why is no real title available?)
• scientific article; zbMATH DE number 568838 (Why is no real title available?)
• Lattice animals and heaps of dimers
• Lyndon bases of free partially commutative Lie algebras
• Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids
• Mathematical Foundations of Computer Science 2004
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Root multiplicities for Borcherds algebras and graph coloring
• Unique factorization of tensor products for Kac-Moody algebras

Cited in

(1)

• A study on free roots of Borcherds-Kac-Moody Lie superalgebras

This page was built for publication: Generalised chromatic polynomials of graphs from heaps of pieces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155545)