Bounds on Characteristic Polynomials

Authors Suijie Wang, Yeong-Nan Yeh, Fengwei Zhou

Publication date 24 September 2012

Abstract: Suppose

G

is a simple graph with

n

vertices,

m

edges, and rank

r

. Let

c h i_{G} (t) = a_{0} t^{n} - a_{1} t^{n - 1} + c d o t s + (- 1)^{r} a_{r} t^{n - r}

be the chromatic polynomial of

G

. For

q, k i n B b b Z

and

0 l e k l e q + r + 1

, we obtain a sharp two-side bound for the partial binomial sum of the coefficient sequence, that is, [ {r+qchoose k}le sum_{i=0}^{k}{qchoose k-i}a_{i}le {m+qchoose k}. ] Indeed, this bound holds for the characteristic polynomial of hyperplane arrangements and matroids, and its weak version can be generalized to the characteristic polynomial of toric arrangements and arithmetic matroids. We also propose a problem on the geometric interpretation of the above bound.

This page was built for publication: Bounds on Characteristic Polynomials

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