Bounds on Characteristic Polynomials

arXiv1209.5185MaRDI QIDQ6235871FDOQ6235871

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.

Mathematics Subject Classification ID

Graph polynomials (05C31)

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)