The absolute values of the coefficients of the chromatic polynomial form a log-concave sequence

Algebra, Combinatorics 1 Minute

You need to know: Graph, proper colouring of vertices of a graph, polynomial.

Background: A sequence x_0, x_1, \dots, x_n of real numbers is called log-concave if x_{i-1}x_{i+1} \leq x_i^2 for all 0<i<n. For a finite graph G and integer q>0, let \chi_G(q) be the number of proper colouring of vertices of G with q colours. It is known that \chi_G(q) is in fact a polynomial \chi_G(q)=\sum\limits_{k=0}^n (-1)^{n-k}a_k q^k, where a_0, a_1 \dots, a_n are non-negative integers.

The Theorem: On 27th August 2010, June Huh submitted to arxiv a paper in which he proved that if \chi_G(q)=\sum\limits_{k=0}^n (-1)^{n-k}a_k q^k is the chromatic polynomial of a graph G, then the sequence a_0, a_1 \dots, a_n is log-concave.

Short context: The chromatic polynomial was introduced by Birkhoff in 1912, and is one of the most beautiful objects of study in graph theory. In 1968, Read conjectured that the sequence of the absolute values of the coefficients of the chromatic polynomial is unimodal (that is, a_0 \leq a_1 \leq \dots \leq a_{i-1} \leq a_i \geq a_{i+1} \geq \dots \geq a_n for some 0 \leq i \leq n).  In 1971, Rota conjectured that this sequence is in fact log-concave and observed that this would imply the Read’s conjecture. The Theorem confirms this prediction. In fact, Rota conjectured an even more general statement, which was also proved in a later work.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

One thought on “The absolute values of the coefficients of the chromatic polynomial form a log-concave sequence”

  1. Pingback: Rota’s and Mason’s log-concavity conjectures are true for all matroids – Theorems of the 21st century

Leave a comment