Generalized chromatic polynomials of graphs from Heaps of pieces

G Arunkumar

arxiv: 1907.08864 · v1 · pith:XUJQTSRPnew · submitted 2019-07-20 · 🧮 math.CO

Generalized chromatic polynomials of graphs from Heaps of pieces

G Arunkumar This is my paper

Pith reviewed 2026-05-24 18:36 UTC · model grok-4.3

classification 🧮 math.CO

keywords generalized chromatic polynomialsheaps of piecespartially commutative Lie algebraspyramidsLyndon heapsacyclic orientationsreciprocity theorem

0 comments

The pith

The generalized k-chromatic polynomial of a graph G equals a sum of dimensions of the grade spaces of the free partially commutative Lie algebra L(G) associated to G.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an explicit formula that writes the generalized k-chromatic polynomial of any simple graph in terms of the dimensions of graded pieces of its associated Lie algebra, obtained by counting certain heaps of pieces. A sympathetic reader would care because the formula supplies an algebraic counting interpretation for chromatic polynomials and immediately yields the classical theorems that count acyclic orientations as special cases. The argument proceeds by introducing pyramids (heaps with a unique minimal piece), proving two lemmas that relate pyramid counts to Lyndon heaps, and then applying the resulting identity to labelled acyclic orientations to obtain a reciprocity statement for derivatives of the polynomial.

Core claim

Using heaps of pieces, we prove an expression for the generalized k-chromatic polynomial of G in terms of dimensions of the grade spaces of L(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 (

What carries the argument

Heaps of pieces on the graph, with pyramids (heaps possessing a unique minimal piece) acting as the counting device that matches the dimensions of the graded components of the free partially commutative Lie algebra L(G).

If this is right

The number of acyclic orientations of G equals a particular evaluation of the Lie-algebra dimension sum.
The Greene-Zaslavsky theorem counting acyclic orientations with given sink sets follows as a corollary of the same identity.
The derivatives of the chromatic polynomial satisfy a reciprocity law when evaluated via (m,λ)-labelled acyclic orientations.
The generalized k-chromatic polynomial admits an equivalent counting interpretation by multilinear heaps of Lyndon length.
The formula supplies an algebraic route to the chromatic polynomial once the graded dimensions of L(G) are known.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the heap-to-dimension map is effective, existing algorithms for computing dimensions in free partially commutative Lie algebras could be repurposed to evaluate chromatic polynomials on graphs whose Lie algebras admit compact presentations.
The two pyramid lemmas may supply similar translation mechanisms for other graph polynomials that arise from partial commutation relations.
The (m,λ)-labelling construction suggests a route to reciprocity statements for additional graph invariants built from acyclic orientations.

Load-bearing premise

The pyramid proportionality lemma and the pyramid and Lyndon heap lemma hold so that heap counts translate directly into the Lie-algebra dimensions appearing in the chromatic-polynomial formula.

What would settle it

For the triangle graph K3 and any fixed k greater than 2, compute the generalized k-chromatic polynomial by direct enumeration and compare the value to the sum of dimensions of the grade spaces of the corresponding Lie algebra L(K3); a numerical mismatch falsifies the claimed equality.

read the original abstract

Let $G$ be a simple graph and let $\mathcal{L}(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 $\textbf k$-chromatic polynomial of $G$ in terms of dimensions of the grade spaces of $\mathcal{L}(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a new heap-based formula for the generalized k-chromatic polynomial in terms of graded dimensions of the partially commutative Lie algebra L(G), recovering the classical Stanley and Greene-Zaslavsky results on acyclic orientations as checks.

read the letter

The core contribution is an explicit identity that expresses the generalized chromatic polynomial directly via dimensions of the graded pieces of L(G), obtained by counting multilinear heaps and applying two pyramid lemmas. The argument then recovers the known theorems on acyclic orientations and proves a reciprocity statement for derivatives using a new (m,λ)-labelling on orientations. That the classical corollaries fall out cleanly is a useful sanity check on the construction. The heap machinery and the connection to Lyndon heaps appear to be the genuinely new pieces here, and they sit at the intersection of combinatorial enumeration and algebraic structures in a way that could interest people working on graph polynomials or partially commutative algebras. The proofs of the pyramid proportionality lemma and the pyramid-and-Lyndon-heap lemma are the load-bearing steps; if those hold, the translation from heap counts to Lie-algebra dimensions looks direct and non-circular. The (m,λ)-labelling is presented as analogous to Stanley's compatible pairs, so that part is more of an adaptation than a fresh invention. No obvious gaps in the overall logic show up from the stated outline, and the fact that the target polynomial is not presupposed inside the equations keeps the derivation honest. This is specialized work aimed at combinatorialists already comfortable with heaps or Lie-algebraic methods on graphs. A reader looking for fresh algebraic interpretations of chromatic polynomials will find something concrete to work with. It is worth sending to a serious referee because the central claim is a clean, falsifiable identity with verifiable classical consequences, even if the proofs of the two lemmas will need careful checking.

Referee Report

0 major / 3 minor

Summary. The paper claims to derive an explicit formula for the generalized k-chromatic polynomial of a simple graph G in terms of the dimensions of the graded pieces of the free partially commutative Lie algebra L(G) associated to G. The derivation proceeds by counting multilinear heaps, invoking two new lemmas on pyramids (heaps with a unique minimal piece)—the pyramid proportionality lemma and the pyramid and Lyndon heap lemma—and recovers the classical Stanley and Greene–Zaslavsky theorems on acyclic orientations as corollaries. The final section introduces (m,λ)-labellings of acyclic orientations and applies the main theorem to obtain a reciprocity result for derivatives of the chromatic polynomial.

Significance. If the heap-to-Lie-algebra translation and the two pyramid lemmas hold, the work supplies a new combinatorial interpretation of chromatic polynomials via multilinear heaps and Lyndon lengths, together with an algebraic expression that is derived rather than fitted. Recovery of the two classical corollaries supplies an internal consistency check. The construction is free of ad-hoc parameters once the Lie algebra and heap rules are fixed.

minor comments (3)

The definition of the generalized k-chromatic polynomial is invoked in the main theorem but is not restated with its precise normalization or variable set; a short paragraph or reference to the standard definition would aid readability.
Notation for the graded dimensions dim L_n(G) and the heap-counting functions is introduced gradually; a consolidated table of symbols at the end of the introduction would reduce cross-referencing.
The (m,λ)-labelling is defined in the final section; a brief comparison table with Stanley’s λ-compatible pairs would clarify the precise generalization.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive summary, and assessment of significance. The recommendation for minor revision is noted, but the report contains no specific major comments requiring point-by-point response. We are prepared to incorporate any minor editorial or clarification changes the editor or referee may identify in a revised version.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation proceeds from the definitions of the free partially commutative Lie algebra L(G) and the combinatorial rules for heaps of pieces, through two lemmas (pyramid proportionality lemma and pyramid and Lyndon heap lemma) whose proofs are supplied internally in the manuscript, to an explicit formula for the generalized k-chromatic polynomial in terms of graded dimensions. The argument recovers the classical Stanley and Greene-Zaslavsky results on acyclic orientations as corollaries, providing an internal consistency check. No load-bearing step reduces by construction to a fitted parameter, a self-citation chain, or a renaming of the target quantity; the central claim is obtained by direct counting of multilinear heaps and Lyndon heaps without presupposing the chromatic polynomial expression.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

Review performed from abstract only; the paper relies on the standard construction of the free partially commutative Lie algebra associated to a graph and on the combinatorial theory of heaps. Two new lemmas about pyramids are introduced and proved inside the paper. No numerical free parameters are mentioned.

axioms (2)

standard math The free partially commutative Lie algebra L(G) is well-defined for any simple graph G and its graded dimensions are finite.
Invoked at the outset to state the main theorem.
domain assumption Heaps of pieces with the partial commutation rules induced by G form a combinatorial model whose enumeration yields the chromatic polynomial.
Central modeling assumption of the proof strategy.

invented entities (2)

Pyramid (heap with a unique minimal piece) no independent evidence
purpose: Key technical device used to prove the main identity via the pyramid proportionality lemma.
Defined and studied inside the paper; no independent existence claim outside the combinatorial model.
(m,λ)-labelling of acyclic orientations no independent evidence
purpose: New labelling used to prove the reciprocity theorem for derivatives of the chromatic polynomial.
Introduced in the final section as an extension of Stanley's λ-compatible pairs.

pith-pipeline@v0.9.0 · 5725 in / 1620 out tokens · 27295 ms · 2026-05-24T18:36:11.252116+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel (J-cost uniqueness) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

using heaps of pieces, we prove an expression for the generalized k-chromatic polynomial of G in terms of dimensions of the grade spaces of L(G) ... pyramid proportionality lemma, and the pyramid and Lyndon heap lemma
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.2 ... ˜π_G_k(q) = ∑_{J∈LG(k)} chrmult J q|J|

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages · 1 internal anchor

[1]

Arunkumar

G. Arunkumar. The peterson recurrence formula for the ch romatic discriminant of a graph. Indian Journal of Pure and Applied Mathematics , 49(3):581–587, Sep 2018

work page 2018
[2]

Arunkumar, Deniz Kus, and R

G. Arunkumar, Deniz Kus, and R. Venkatesh. Root multipli cities for Borcherds algebras and graph coloring. J. Algebra, 499:538–569, 2018

work page 2018
[3]

Chromatic Polynomial and Heaps of Pieces

Bishal Deb. Chromatic Polynomial and Heaps of Pieces. arXiv e-prints , page arXiv:1902.02240, Feb 2019

work page internal anchor Pith review Pith/arXiv arXiv 1902
[4]

R. M. Green. Combinatorics of minuscule representations , volume 199 of Cambridge Tracts in Mathematics . Cambridge University Press, Cambridge, 2013

work page 2013
[5]

On the interpretati on of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orie ntations of graphs

Curtis Greene and Thomas Zaslavsky. On the interpretati on of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orie ntations of graphs. Trans. Amer. Math. Soc. , 280(1):97–126, 1983. 18 G. ARUNKUMAR

work page 1983
[6]

Halld´ orsson and Guy Kortsarz

Magn´ us M. Halld´ orsson and Guy Kortsarz. Multicoloring: problems and techniques. In Mathematical foun- dations of computer science 2004 , volume 3153 of Lecture Notes in Comput. Sci. , pages 25–41. Springer, Berlin, 2004

work page 2004
[7]

Victor G. Kac. Inﬁnite-dimensional Lie algebras . Cambridge University Press, Cambridge, third edition, 1990

work page 1990
[8]

Bases de Lyndon des alg` ebres de Lie libr es partiellement commutatives

Pierre Lalonde. Bases de Lyndon des alg` ebres de Lie libr es partiellement commutatives. Theoret. Comput. Sci., 117(1-2):217–226, 1993. Conference on Formal Power Serie s and Algebraic Combinatorics (Bordeaux, 1991)

work page 1993
[9]

Lyndon heaps: an analogue of Lyndon word s in free partially commutative monoids

Pierre Lalonde. Lyndon heaps: an analogue of Lyndon word s in free partially commutative monoids. Discrete Math., 145(1-3):171–189, 1995

work page 1995
[10]

Orientations acycliques et le polynˆ ome chr omatique

Bodo Lass. Orientations acycliques et le polynˆ ome chr omatique. European J. Combin. , 22(8):1101–1123, 2001

work page 2001
[11]

Ronald C. Read. An introduction to chromatic polynomia ls. J. Combinatorial Theory , 4:52–71, 1968

work page 1968
[12]

Richard P. Stanley. Acyclic orientations of graphs. Discrete Math. , 5:171–178, 1973

work page 1973
[13]

Richard P. Stanley. Graph colorings and related symmet ric functions: ideas and applications: a description of results, interesting applications, & notable open problem s. Discrete Math. , 193(1-3):267–286, 1998. Selected papers in honor of Adriano Garsia (Taormina, 1994)

work page 1998
[14]

Venkatesh and Sankaran Viswanath

R. Venkatesh and Sankaran Viswanath. Unique factoriza tion of tensor products for Kac-Moody algebras. Adv. Math. , 231(6):3162–3171, 2012

work page 2012
[15]

Venkatesh and Sankaran Viswanath

R. Venkatesh and Sankaran Viswanath. Chromatic polyno mials of graphs from Kac-Moody algebras. J. Algebraic Combin. , 41(4):1133–1142, 2015

work page 2015
[16]

Commutations and Heaps of Piec es, Chapter 2

G´ erard Xavier Viennot. Commutations and Heaps of Piec es, Chapter 2. Lectures at IMSc, Chennai. http://www.xavierviennot.org/coursIMSc2017/Ch_2_files/cours_IMSc17_Ch2b.pdf, http://www.xavierviennot.org/coursIMSc2017/Ch_2_files/cours_IMSc17_Ch2d.pdf

work page
[17]

Commutations and heaps of piec es, chapter 5

G´ erard Xavier Viennot. Commutations and heaps of piec es, chapter 5. Lectures at IMSc, Chennai. http://www.xavierviennot.org/coursIMSc2017/Ch_5_files/cours_IMSc17_Ch5a.pdf

work page
[18]

Commutations and Heaps of Piec es, Chapter 6

G´ erard Xavier Viennot. Commutations and Heaps of Piec es, Chapter 6. Lectures at IMSc, Chennai. http://cours.xavierviennot.org/Talca_2013_14_files/Talca13%3A14_Ch6.pdf

work page
[19]

Heaps of pieces

G´ erard Xavier Viennot. Heaps of pieces. I. Basic deﬁni tions and combinatorial lemmas. In Graph theory and its applications: East and West (Jinan, 1986) , volume 576 of Ann. New York Acad. Sci. , pages 542–570. New York Acad. Sci., New York, 1989. Indian Institute of Science Education and Research, Mohali , India. E-mail address : arun.maths123@gmail.co...

work page 1986

[1] [1]

Arunkumar

G. Arunkumar. The peterson recurrence formula for the ch romatic discriminant of a graph. Indian Journal of Pure and Applied Mathematics , 49(3):581–587, Sep 2018

work page 2018

[2] [2]

Arunkumar, Deniz Kus, and R

G. Arunkumar, Deniz Kus, and R. Venkatesh. Root multipli cities for Borcherds algebras and graph coloring. J. Algebra, 499:538–569, 2018

work page 2018

[3] [3]

Chromatic Polynomial and Heaps of Pieces

Bishal Deb. Chromatic Polynomial and Heaps of Pieces. arXiv e-prints , page arXiv:1902.02240, Feb 2019

work page internal anchor Pith review Pith/arXiv arXiv 1902

[4] [4]

R. M. Green. Combinatorics of minuscule representations , volume 199 of Cambridge Tracts in Mathematics . Cambridge University Press, Cambridge, 2013

work page 2013

[5] [5]

On the interpretati on of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orie ntations of graphs

Curtis Greene and Thomas Zaslavsky. On the interpretati on of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orie ntations of graphs. Trans. Amer. Math. Soc. , 280(1):97–126, 1983. 18 G. ARUNKUMAR

work page 1983

[6] [6]

Halld´ orsson and Guy Kortsarz

Magn´ us M. Halld´ orsson and Guy Kortsarz. Multicoloring: problems and techniques. In Mathematical foun- dations of computer science 2004 , volume 3153 of Lecture Notes in Comput. Sci. , pages 25–41. Springer, Berlin, 2004

work page 2004

[7] [7]

Victor G. Kac. Inﬁnite-dimensional Lie algebras . Cambridge University Press, Cambridge, third edition, 1990

work page 1990

[8] [8]

Bases de Lyndon des alg` ebres de Lie libr es partiellement commutatives

Pierre Lalonde. Bases de Lyndon des alg` ebres de Lie libr es partiellement commutatives. Theoret. Comput. Sci., 117(1-2):217–226, 1993. Conference on Formal Power Serie s and Algebraic Combinatorics (Bordeaux, 1991)

work page 1993

[9] [9]

Lyndon heaps: an analogue of Lyndon word s in free partially commutative monoids

Pierre Lalonde. Lyndon heaps: an analogue of Lyndon word s in free partially commutative monoids. Discrete Math., 145(1-3):171–189, 1995

work page 1995

[10] [10]

Orientations acycliques et le polynˆ ome chr omatique

Bodo Lass. Orientations acycliques et le polynˆ ome chr omatique. European J. Combin. , 22(8):1101–1123, 2001

work page 2001

[11] [11]

Ronald C. Read. An introduction to chromatic polynomia ls. J. Combinatorial Theory , 4:52–71, 1968

work page 1968

[12] [12]

Richard P. Stanley. Acyclic orientations of graphs. Discrete Math. , 5:171–178, 1973

work page 1973

[13] [13]

Richard P. Stanley. Graph colorings and related symmet ric functions: ideas and applications: a description of results, interesting applications, & notable open problem s. Discrete Math. , 193(1-3):267–286, 1998. Selected papers in honor of Adriano Garsia (Taormina, 1994)

work page 1998

[14] [14]

Venkatesh and Sankaran Viswanath

R. Venkatesh and Sankaran Viswanath. Unique factoriza tion of tensor products for Kac-Moody algebras. Adv. Math. , 231(6):3162–3171, 2012

work page 2012

[15] [15]

Venkatesh and Sankaran Viswanath

R. Venkatesh and Sankaran Viswanath. Chromatic polyno mials of graphs from Kac-Moody algebras. J. Algebraic Combin. , 41(4):1133–1142, 2015

work page 2015

[16] [16]

Commutations and Heaps of Piec es, Chapter 2

G´ erard Xavier Viennot. Commutations and Heaps of Piec es, Chapter 2. Lectures at IMSc, Chennai. http://www.xavierviennot.org/coursIMSc2017/Ch_2_files/cours_IMSc17_Ch2b.pdf, http://www.xavierviennot.org/coursIMSc2017/Ch_2_files/cours_IMSc17_Ch2d.pdf

work page

[17] [17]

Commutations and heaps of piec es, chapter 5

G´ erard Xavier Viennot. Commutations and heaps of piec es, chapter 5. Lectures at IMSc, Chennai. http://www.xavierviennot.org/coursIMSc2017/Ch_5_files/cours_IMSc17_Ch5a.pdf

work page

[18] [18]

Commutations and Heaps of Piec es, Chapter 6

G´ erard Xavier Viennot. Commutations and Heaps of Piec es, Chapter 6. Lectures at IMSc, Chennai. http://cours.xavierviennot.org/Talca_2013_14_files/Talca13%3A14_Ch6.pdf

work page

[19] [19]

Heaps of pieces

G´ erard Xavier Viennot. Heaps of pieces. I. Basic deﬁni tions and combinatorial lemmas. In Graph theory and its applications: East and West (Jinan, 1986) , volume 576 of Ann. New York Acad. Sci. , pages 542–570. New York Acad. Sci., New York, 1989. Indian Institute of Science Education and Research, Mohali , India. E-mail address : arun.maths123@gmail.co...

work page 1986