UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Binomial Inequalities of Chromatic, Flow, and Ehrhart Polynomials

Algebra & Discrete Mathematics

Speaker: Prof. Matthias Beck, San Francisco State Univ.
Location: 1147 Math. Science Building
Start time: Mon, May 20 2019, 12:10PM

A famous and wide-open problem, going back to at least the early 1970's, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one

may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute one such set of inequalities when a chromatic polynomial $\chi_G(n) = \chi^*_0

\binom {n+d} d + \chi^*_1 \binom {n+d-1} d + \dots + \chi^*_d \binom n d$ is written in terms of a binomial-coefficient basis. More precisely, we prove that $\chi^*_{d-2}+\chi^*_{d-3}+\dots+\chi^*_{d-j-1} \ \ge \ \chi^*_2+\chi^*_3+\dots+\chi^*_{j+1} $, for $1 \le j \le \lfloor \frac{ d }{ 2 } \rfloor - 1$. A similar result holds for flow polynomials enumerating either modular or integral nowhere-zero flows of a graph. Our theorems follow from connections among chromatic, flow, order, and Ehrhart polynomials, and the fact that the latter satisfy a decomposition formula into symmetric polynomials due to


This is joint work with Emerson Le\'on.