Bounds on Characteristic Polynomials
Suppose $G$ is a simple graph with $n$ vertices, $m$ edges, and rank $r$. Let $\chi_G(t)=a_0t^n-a_1t^{n-1}+\cdots +(-1)^ra_rt^{n-r}$ be the chromatic polynomial of $G$. For $q,k\in \Bbb{Z}$ and $0\le k\le q+r+1$, we obtain a sharp two-side bound for the partial binomial sum of the coefficient sequence, that is, \[ {r+q\choose k}\le \sum_{i=0}^{k}{q\choose k-i}a_{i}\le {m+q\choose 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.
\section{Introduction}
We start with some notations in graph theory. Let $G=(VG, EG)$ be a simple graph (no loops and multi-edges) with the vertex set $VG$ and the edge set $EG$. Let $n=|VG|$, $m=|EG|$, and $c$ the number of connected components of $G$. Then the rank of $G$ is $r=n-c$. First appeared in \cite{Birkhoff}, the chromatic polynomial $\chi_G(t)$ counts the number of proper colorings of the graph $G$ with $t$ colors, which can be written as follows,
\[\chi_G(t)=a_0t^n-a_1t^{n-1}+\cdots +(-1)^ra_rt^{n-r}.\]

The chromatic polynomial is one of the most central topics in graph theory, whose coefficients are mysterious and have caught many mathematicians' interests. In 1932, Whitney \cite{Whitney2} showed that the coefficient sequence is sign-alternating, i.e., $a_i>0$. Moreover, he \cite{Whitney1} gave a combinatorial interpretation to each coefficient $a_i$, which is equal to the number of those $i$-subsets of $EG$ that contain no broken circuits, known as the \emph{no broken circuit} theorem. In 1968, Read \cite{Read} asked which polynomial is the chromatic polynomial of some graph and conjectured that the sequence $a_0,a_1,\ldots,a_r$ is unimodal. In general, it looks impossible to give all properties of the coefficient sequence. Fortunately, Read's conjecture has been positively answered by Huh \cite{Huh} presently. It turns out that the coefficient sequence $a_0,a_1,\ldots,a_r$ is logconcave. All above results are relatively big steps in the way investigating the properties of the coefficient sequence. Few results have been obtained for the coefficient sequence. After searching from the web, the next is the only general result founded on the bounds of the coefficient sequence which, in fact, can be regarded as a consequence of Whitney's combinatorial interpretation. In 1970, G.H.J. Meredith \cite{Meredith} gave an upper bound for each coefficient, which is $|a_i|\le {m\choose i}$.  In this paper, we shall introduce a new bound which will generalize Whitney's sign-alternating result and Meredith's upper bound result.

Next is the statement of our main result. If $q,k\in \Bbb{Z}$ with $0\le k\le q+r+1$, we have
\[
{r+q\choose k}\le \sum_{i=0}^{k}{q\choose k-i}a_{i}\le {m+q\choose k}.
\]
We can see that Whitney's sign-alternating theorem and Meredith's upper bound theorem are direct consequences of the above inequality. When $q=0$, we have
 \[
{r\choose k}\le a_{k}\le {m\choose k},\sp \If 0\le k\le r.
\]
If $q=-1$, we obtain that
\[
{r-1\choose k}\le (-1)^k\sum_{i=0}^{k}(-1)^ia_{i}\le {m-1\choose k}, \sp\If 0\le k\le r.
\]
So the first $r-1$ partial sums of the coefficient sequence of the chromatic polynomial are still sign-alternating.

Indeed, all above results hold for a more generalized object, the characteristic polynomial of hyperplane arrangements. Hence, we shall practise our proof on hyperplane arrangements in the next section.


\section{Main Results}
An $n$-dimensional arrangement $\mathcal{A}$ of hyperplanes is a finite collection of codimension one subspaces in an $n$-dimensional vector space $V$. Equipped with the partial order defined by the inverse of set inclusion, the set of all nonempty intersections of hyperplanes in $\mathcal{A}$ including the ambient space $V:=\cap_{H\in \emptyset} H$ forms a semi-lattice $L(\mathcal{A})$, called the intersection semi-lattice, i.e.,
\[
L(\mathcal{A})=\{\cap_{H\in \mathcal{B}}H\mid \mathcal{B}\subseteq \mathcal{A}\},
\]
Note that the minimal element of $L(\mathcal{A})$ is $V$. The maximal rank of the semi-lattice $L(\mathcal{A})$ is called the \emph{rank} of hyperplane arrangement $\mathcal{A}$, denoted by $r(\mathcal{A})$. In another viewpoint, the rank $r(\mathcal{A})$ is the dimension of the vector space spanned by those normal vectors of hyperplanes in $\mathcal{A}$.  The \emph{characteristic polynomial} $\chi(\mathcal{A},t)\in \Bbb{C}[t]$ of $\mathcal{A}$ is defined to be
\[
\chi(\mathcal{A};t):=\sum_{X\in L(\mathcal{A})}\mu(\hat{0},X)\,t^{{\small\dim(X)}}.
\]
where $\mu$ is the {\emph M\"{o}bius function} of $L(\mathcal{A})$.
Let $G=(VG,EG)$ be a simple graph with the vertex set $VG=[n]$ and the edge set $EG\subseteq [n]\times [n]$. The \emph{graphic arrangement} $\mathcal{A}_G$ of $G$ is an $n$-dimensional arrangement of $|EG|$ hyperplanes whose members are given by
\[
H_{ij}: x_i=x_j,\sp \For (i,j)\in EG.
\]
With these definitions, we have, see Theorem 2.7 in \cite{Stanley2},
\[
\chi(\mathcal{A}_G;t)=\chi_G(t).
\]
It follows that the rank of the graph $G$ is indeed the same as the rank of the graphic arrangement $\mathcal{A}_G$.

It is well known that the characteristic polynomial satisfies the \emph{deletion-contraction} recurrence
\[\chi(\mathcal{A};t)=\chi(\mathcal{A}\setminus H_0;t)-\chi(\mathcal{A}/H_0;t),\]
where $H_0\in \mathcal{A}$ is a fixed hyperplane, $\mathcal{A}\setminus H_0$ is an $n$-dimensional subarrangement of hyperplanes in $V$ obtained by removing $H_0$ from $\mathcal{A}$, and $\mathcal{A}/H_0$ is an $(n-1)$-dimensional hyperplane arrangement in $H_0$ whose members are those restrictions of all hyperplanes of $\mathcal{A}\setminus H_0$ on $H_0$, i.e.,
\[
\mathcal{A}\setminus H_0=\mathcal{A}\setminus\{H_0\}, \sp \mathcal{A}/H_0=\{H\cap H_0\mid H\in \mathcal{A}\setminus H_0\}.
\]



A hyperplane arrangement is called \emph{central} if $\cap_{H\in \mathcal{A}}H\neq \emptyset$. We have $r(\mathcal{A})\le |\mathcal{A}|$ in general and call $\mathcal{A}$ \emph{boolean} when $r(\mathcal{A})=|\mathcal{A}|$. It is easy to show that the boolean hyperplane arrangement is central and its intersection semi-lattice is isomorphic to the boolean lattice $(2^\mathcal{A},\subseteq)$. Hence the characteristic polynomial of an $n$-dimensional boolean arrangement $\mathcal{A}$ of $m$ hyperplanes is
\begin{equation}\label{boolean-formula}
\chi(\mathcal{A};t)=t^{n-m}(t-1)^m=\sum_{i=0}^m(-1)^i{m\choose i}t^{n-i}.
\end{equation}
The graphic arrangement $\mathcal{A}_G$ is boolean if and only if the graph $G$ is a forest. Note that a subset $\mathcal{B}$ of $\mathcal{A}$ naturally defines a subarrangement of hyperplanes in the same ambient space as $\mathcal{A}$, still denoted $\mathcal{B}$ by abuse of notations. A hyperplane arrangement $\mathcal{A}$ of rank $r$ is called \emph{in general position} if the subarrangement $\mathcal{B}$ of $\mathcal{A}$ is boolean whenever $|\mathcal{B}|\le r$, or not central otherwise. If a central hyperplane arrangement is in general position if and only if it is boolean. From \cite[Proposition 2.4]{Stanley2}, the characteristic polynomial of an $n$-dimensional arrangement $\mathcal{A}$ of $m$ hyperplanes in general position is
\begin{equation}\label{formula-general-position}
\chi(\mathcal{A};t)=t^n-mt^{n-1}+{m\choose 2}t^{n-2}+\cdots+(-1)^r{m\choose r}t^{n-r}.
\end{equation}
Later, we shall prove in Proposition \ref{proposition-general-position} that the converse of the above statement is still true by using no broken circuit theorem. First we need some preparations to state no broken circuit theorem. A subset $\mathcal{B}$ of the hyperplane arrangement $\mathcal{A}$ is called \emph{dependent} if $\cap_{H\in\mathcal{B}}H\neq \emptyset$ and $r(\cap_{H\in\mathcal{B}}H)<|\mathcal{B}|$, i.e., the subarrangement $\mathcal{B}$ is central but not boolean. Let $\mathcal{A}$ be totally ordered under a given order $\prec$. A subset of $\mathcal{A}$ is called a \emph{circuit} if it is a minimal dependent subset of $\mathcal{A}$. It is obvious that each dependent subset of $\mathcal{A}$ contains at least a circuit. A \emph{broken circuit} is a subset of $\mathcal{A}$ obtained by removing the maximal element from a circuit of $\mathcal{A}$. A subset $\mathcal{B}$ of $\mathcal{A}$ is called \emph{$\chi$-independent} if $\cap_{H\in\mathcal{B}}H\neq \emptyset$ and $\mathcal{B}$ contains no broken circuits.



\begin{theorem}[{\bf No Broken Circuit Theorem} \cite{Orlik}]\label{theorem-BC}
Let $\mathcal{A}$ be an $n$-dimensional hyperplane arrangement of rank $r$ and its
characteristic polynomial
\[
\chi(\mathcal{A};t)=a_0t^n-a_1t^{n-1}+\cdots +(-1)^ra_rt^{n-r}.
\]
Then for $0\le k\le r$, $a_k$ is equal to the number of $\chi$-indenpendent $k$-subsets of $\mathcal{A}$.
\end{theorem}


\begin{proposition}\label{proposition-general-position}Let $\mathcal{A}$ be an $n$-dimensional arrangement of $m$ hyperplanes and $r(\mathcal{A})=r$. Then $\mathcal{A}$ is in general position if and only if its characteristic polynomial is exactly the same as $(\ref{formula-general-position})$.
\end{proposition}
\begin{proof}Note that no subset of $\mathcal{A}$ is a circuit if $\mathcal{A}$ is in general position. Then every $k$-subset of $\mathcal{A}$ is $\chi$-independent for all $k\le r$. By Theorem \ref{theorem-BC}, we have $a_i={m\choose i}$.  Conversely, for $0\le k \le r$, $a_k={m\choose k}$  implies that all $k$-subsets of $\mathcal{A}$ are $\chi$-independent. It follows from the definition that if $\mathcal{B}\subseteq \mathcal{A}$ and $|\mathcal{B}|\le r$, $\mathcal{B}$ contains no broken circuits and $\cap_{H\in\mathcal{B}}H\neq \emptyset$. So the subarrangement $\mathcal{B}$ is boolean if $|\mathcal{B}|\le r$. When $k> r$, we have $a_k=0$,  which implies $\cap_{H\in\mathcal{B}}H=\emptyset$ if $|\mathcal{B}|\ge r$.
\end{proof}


To prove our main result, we introduce a combinatorial identity first, that is,
\begin{equation}\label{formula-combinatorial-identity}
\sum_{i=0}^{k}{x\choose i}{y\choose k-i}={x+y\choose k},\sp \If~~ x,y\in \Bbb{C}, ~~ k\in \Bbb{Z}_{\ge 0},
\end{equation}
where ${x\choose i}=\frac{1}{i!}x(x-1)\cdots(x-i+1)$.
Indeed, in the case that $x\in \Bbb{C}$ is fixed and $y$ is an arbitrary nonnegative integer, we present a brief proof for $(\ref{formula-combinatorial-identity})$ by induction on $y\in\Bbb{Z}_{\ge 0}$. First, the induction basis $y=0$ is trivial. With the induction hypothesis, we have,
\begin{eqnarray*}
\sum_{i=0}^{k}{x\choose i}{y+1\choose k-i}&=&\sum_{i=0}^{k}{x\choose i}{y\choose k-i}+\sum_{i=0}^{k-1}{x\choose i}{y\choose k-1-i}\\
&=&{x+y\choose k}+{x+y\choose k-1}={x+y+1\choose k},
\end{eqnarray*}
Notice that $(\ref{formula-combinatorial-identity})$ can be viewed as a polynomial equation in $y$ whenever $x$ is fixed. Then each $y\in \Bbb{Z}_{\ge 0}$ is a root of this polynomial equation. By the fundamental theorem of algebra,  $(\ref{formula-combinatorial-identity})$ holds for all $y\in \Bbb{C}$ whenever $x\in \Bbb{C}$ is fixed.

\begin{theorem}\label{theorem-main}
Let $\mathcal{A}$ be an $n$-dimensional arrangement of $m$ hyperplanes and its characteristic polynomial
\[
\chi(\mathcal{A};t)=a_0t^n-a_1t^{n-1}+a_2t^{n-2}+\cdots+(-1)^ra_rt^{n-r},
\]
where $r=r(\mathcal{A})$. If $q,k\in \Bbb{Z}$ satisfies $0\le k\le q+r+1$, then
\begin{equation}\label{formula-main}
{r+q\choose k}\le \sum_{i=0}^{k}{q\choose k-i}a_{i}\le {m+q\choose k}.
\end{equation}
\end{theorem}
\begin{proof}First if $\mathcal{A}$ is boolean, then $r=m$. From (\ref{boolean-formula}) and (\ref{formula-combinatorial-identity}), we have
\begin{equation}\label{boolean-case}
\sum_{i=0}^{k}{q\choose k-i}a_{i}=\sum_{i=0}^{k}{q\choose k-i}{m\choose i}={m+q\choose k}={r+q\choose k}.
\end{equation}
So if $\mathcal{A}$ is boolean, (\ref{formula-main}) holds for any $q,k\in \Bbb{Z}$. In general, we shall use induction on $|\mathcal{A}|$ to prove (\ref{formula-main}). Note that if $|\mathcal{A}|=0$ or $1$, $\mathcal{A}$ is a boolean arrangement. Suppose the result holds for $|\mathcal{A}|\le m$. Since (\ref{formula-main}) holds for any boolean hyperplane arrangement, it is enough to prove the result for the case that $|\mathcal{A}|=m+1$ and $\mathcal{A}$ is not boolean. In this case, we have $r=r(\mathcal{A})< |\mathcal{A}|=m+1$, that is to say, the space spanned by the $m+1$ normal vectors of hyperplanes in $\mathcal{A}$ has dimension $r<m+1$. So at least one of these $m+1$ normals can be removed without changing the spanning space. In another word, there is a hyperplane $H_0\in \mathcal{A}$ such that $r(\mathcal{A}\setminus H_0)=r(\mathcal{A})=r$. Then we can write
\[
\chi(\mathcal{A}\setminus H_0;t)=b_0t^n-b_1t^{n-1}+b_2t^{n-2}+\cdots+(-1)^rb_rt^{n-r}.
\]
Notice that each maximal element in the intersection semi-lattice $L(\mathcal{A}/H_0)$ is a maximal element of the intersection semi-lattice $L(\mathcal{A})$. Since all maximal elements of $L(\mathcal{A})$ have the same rank $r$, it follows that the rank of $\mathcal{A}/H_0$ is $r-1$, i.e., $r(\mathcal{A}/H_0)=r-1$. Then we can write
\[
\chi(\mathcal{A}/H_0;t)=c_0t^{n-1}-c_1t^{n-2}+c_2t^{n-3}+
\cdots+(-1)^{r-1}c_{r-1}t^{n-r}.
\]
Since $|\mathcal{A}\setminus H_0|= m$ and $r(\mathcal{A}\setminus H_0)= r$, the induction hypothesis implies that, if $0\le k\le q+r+1$,
\begin{equation}\label{deletion-case}
{r+q\choose k}~\le ~\sum_{i=0}^{k}{q\choose k-i}b_{i}~\le~{m+q\choose k}.
\end{equation}
Since  $|\mathcal{A}/H_0|\le m$ and $r(\mathcal{A}/ H_0)= r-1$, the induction hypothesis implies that, if $0\le k-1\le q+r$, i.e., $1\le k\le q+r+1$,
\begin{equation}\label{restriction-case}
{r-1+q\choose k-1}~\le ~\sum_{i=0}^{k-1}{q\choose k-1-i}c_{i}=\sum_{i=1}^{k}{q\choose k-i}c_{i-1} ~\le~ {|\mathcal{A}/H_0|+q\choose k-1}.
\end{equation}
Using the deletion-contraction recurrence $\chi(\mathcal{A};t)=\chi(\mathcal{A}\setminus H_0;t)-\chi(\mathcal{A}/H_0;t)$, we have
\[
a_0=b_0=1,\sp a_i=b_i+c_{i-1} ~\If~ 1\le i\le r.
\]
It then follows by combining with (\ref{deletion-case}) and (\ref{restriction-case}) that if $1\le k\le r+q+1$
\begin{equation}\label{combining}
{r+q\choose k}+{r-1+q\choose k-1}~\le ~\sum_{i=0}^{k}{q\choose k-i}a_{i}~\le~{m+q\choose k}+{|\mathcal{A}/H_0|+q\choose k-1}.
\end{equation}
Since (\ref{formula-main}) is obviously true when $k=0$, it remains to show that, if $1\le k\le r+q+1$,
\begin{eqnarray}
{r+q\choose k}+{r-1+q\choose k-1}&\ge& {r+q\choose k},\label{inequality-r}\\
{m+q\choose k}+{|\mathcal{A}/H_0|+q\choose k-1}&\le& {m+q+1\choose k}\label{inequality-m}.
\end{eqnarray}
Note that ${r-1+q\choose k-1}\ge 0$ if $r-1+q\ge 0$. However if $r-1+q< 0$, then $1\le k \le r+q+1<2$ implies $k=1$ and ${r-1+q\choose k-1}=1\ge 0$. It completes (\ref{inequality-r}). Since ${m+q\choose k}+{m+q\choose k-1}= {m+q+1\choose k}$ and $|\mathcal{A}/H_0|\le m$, (\ref{inequality-m}) is obvious when $|\mathcal{A}/H_0|+q\ge 0$. Now consider the case $|\mathcal{A}/H_0|+q<0$. Since $r(\mathcal{A}/H_0)=r-1$, then we have $|\mathcal{A}/H_0|\ge r-1$. Combining with $1\le k\le r+q+1$, we obtain that $k=1$. So ${|\mathcal{A}/H_0|+q\choose k-1}={m+q\choose k-1}$ if $|\mathcal{A}/H_0|+q<0$, which completes (\ref{inequality-m}).
\end{proof}




By taking $q=0$ in (\ref{formula-main}), Whitney's sign-alternating theorem and Meredith's upper bound theorem become direct consequences of Theorem \ref{theorem-main}.
\begin{corollary}\label{corollary-3}
Under assumptions of {\rm Theorem \ref{theorem-main}}, we have
\[{r\choose k}\le a_{k}\le {m\choose k}\sp ~\If~ 0\le k \le r.\]
\end{corollary}
Since ${-1 \choose k-i}=(-1)^{k-i}$, after taking $q=-1$ in (\ref{formula-main}), we shall obtain two-side bounds for the partial sums of the coefficient sequence.
\begin{corollary}\label{corollary-4}
Under assumptions of {\rm Theorem \ref{theorem-main}}, we have
\[{r-1\choose k}\le (-1)^k\sum_{i=0}^{k}(-1)^ia_{i}\le {m-1\choose k}\sp ~\If~ 0\le k \le r.\]
\end{corollary}
When $k\le r-1$, we have $(-1)^k\sum_{i=0}^{k}(-1)^ia_{i}\ge {r-1\choose k}\ge 1$, that is to say, the first $r-1$ partial sums of the coefficient sequence form a sign-alternating sequence.
\begin{corollary}\label{corollary-5}
Under assumptions of {\rm Theorem \ref{theorem-main}}, we have
\begin{equation}\label{formula-new}
(-1)^k\sum_{i=0}^{k}(-1)^i{r-i\choose k-i}a_{i}\ge 0\sp .
\end{equation}
In particular,
\begin{equation}\label{bound-new}
a_2\ge {r\choose 2}+(m-r)(r-1)\sp \And \sp a_3\ge {r\choose 3}+(m-r){r-1\choose 2}.
\end{equation}
\end{corollary}


\begin{proof}Taking $q=k-r-1$ in (\ref{formula-main}), we have
\[\sum_{i=0}^{k}{k-r-1\choose k-i}a_{i}\ge {k-1\choose k}=0.\]
Notice that ${k-r-1\choose k-i}=(-1)^{k-i}{r-i\choose k-i}$ Then (\ref{formula-new}) is obvious. It is well known from the definition of the characteristic polynomial that $a_1=|\mathcal{A}|=m$. Applying $k=2$ to (\ref{formula-new}), we have
\[
{r\choose 2}-(r-1)m+a_2\ge 0,
\]
which gives the lower bound ${r\choose 2}+(m-r)(r-1)$ of $a_2$ as above. Applying $k=3$ to (\ref{formula-new}), we have
\[
-{r\choose 3}+{r-1\choose 2}m-(r-2)a_2+a_3\ge 0.
\]
Since $a_2\ge {r\choose 2}+(m-r)(r-1)$, it follows that
\begin{eqnarray*}
a_3&\ge& {r\choose 3}-{r-1\choose 2}m-(r-2)(m-\frac{r}{2})(r-1)\\
&=&{r\choose 3}+(m-r){r-1\choose 2}.
\end{eqnarray*}
\end{proof}
Since the chromatic polynomial $\chi_G(t)$ of a graph $G$ is the characteristic polynomial of the graphic arrangement $\mathcal{A}_G$, the two-side bound $(\ref{formula-main})$ holds for the coefficient sequence of $\chi_G(t)$.
\begin{theorem}\label{theorem-chromatic}
Let $\chi_G(t)=t^n-a_1t^{n-1}+\cdots+(-1)^ra_rt^{n-r}$ be the chromatic polynomial of a graph $G$ with $n$ vertices, $m$ edges, and rank $r$. Then the following three statements are equivalent,
\begin{enumerate}[label={\rm (\roman*)}]
\item\label{theorem-i}  $a_k={m\choose k}$ for all $k$ with $1\le k\le r;$
\item\label{theorem-ii} $a_k={r\choose k}$ for all $k$ with $1\le k\le r;$
\item\label{theorem-iii} $G$ is a forest, i.e., $m=r$.
\end{enumerate}
\end{theorem}
\begin{proof}$\ref{theorem-iii}\Rightarrow\ref{theorem-i}$ and $\ref{theorem-iii}\Rightarrow\ref{theorem-ii}$ are easy consequences of Corollary \ref{corollary-3}. Recall $a_1=|EG|=m$, then $\ref{theorem-ii}\Rightarrow\ref{theorem-iii}$ becomes obvious. From Proposition \ref{proposition-general-position}, $a_k={m\choose k}$ if and only if the graphic arrangement $\mathcal{A}_G$ is in general position. Note that the graphic arrangement $\mathcal{A}_G$ is a central hyperplane arrangement. Then $\mathcal{A}_G$ contains no subset of size larger than $r$. Hence we have $|\mathcal{A}_G|=|EG|=m=r$ which proves $\ref{theorem-i}\Rightarrow\ref{theorem-iii}$.
\end{proof}
\section{Discussions and Problems}
Let $\mathcal{A}$ be an $n$-dimensional arrangement of $m$ hyperplanes and rank $r$. If all hyperplanes of $\mathcal{A}$ are restricted onto the $r$-dimensional subspace spanned by their normal vectors, we shall obtain an $r$-dimensional arrangement of $m$ hyperplanes and rank $r$, whose characteristic polynomial has the same coefficient sequence as $\chi(\mathcal{A};t)$. Under this restriction, the characteristic polynomial becomes $t$-free, i.e, containing no $t$ as a factor. Next we always assume the characteristic polynomial of $\mathcal{A}$ is
\begin{equation}\label{formula-chi}
\chi(\mathcal{A};t)=a_0t^r-a_1t^{r-1}+\cdots+(-1)^ra_r.
\end{equation}
Recall the no broken circuit Theorem \ref{theorem-BC} that $a_k$ counts the number of $\chi$-independent $k$-subsets of $\mathcal{A}$. It is then obvious that $a_k\le {m\choose k}$. On the other hand, $a_r\ne 0$ implies that there exists at least one $\chi$-independent $r$-subset $\mathcal{B}$ of $\mathcal{A}$. Note the fact from the definition that any subset of a $\chi$-independent set is still $\chi$-independent. Then all subsets of $\mathcal{B}$ are $\chi$-independent, which implies $a_k\ge {r\choose k}$ by the no broken circuit Theorem \ref{theorem-BC}. In this sense, the inequality ${r\choose k}\le a_k\le {m\choose k}$ of Corollary \ref{corollary-3} can be easily obtained from the no broken circuit theorem. Since theorem \ref{theorem-main} can be regarded as a generalization of Corollary \ref{corollary-3}, a natural problem is as follows,
\begin{itemize}
\item Can (\ref{formula-main}) be interpreted by the no broken circuit theorem?
\end{itemize}
Define an operation $\D$ of the characteristic polynomial $\chi(\mathcal{A};t)$ to be
\[\D \chi(\mathcal{A};t)=\frac{\chi(\mathcal{A};t)-\chi(\mathcal{A};1)}{t-1}.\]
Denote $\D^0$ the identity map and $\D^i \chi(\mathcal{A};t)=\underbrace{\D\circ\cdots\circ\D}_i \chi(\mathcal{A};t)$ for $i\in \Bbb{N}$. Note that
\begin{eqnarray*}
\chi(\mathcal{A};t)-\chi(\mathcal{A};1)&=&a_0(t^r-1)-a_1(t^{r-1}-1)+\cdots+(-1)^{r-1}a_{r-1}(t-1)\\
&=&(t-1)\left(\sum_{k=0}^{r-1}t^{r-1-k}\sum_{i=0}^{k}(-1)^ia_i\right)
\end{eqnarray*}
Then we have
\begin{eqnarray*}
\D \chi(\mathcal{A};t)=\sum_{k=0}^{r-1}\left(\sum_{i=0}^{k}(-1)^ia_i\right)t^{r-1-k}
\end{eqnarray*}
In general, for any non-positive integer $q$, we have
\begin{eqnarray*}
\D^{-q} \chi(\mathcal{A};t)&=&\sum_{k=0}^{r+q}(-1)^k\left(\sum_{i=0}^{k}{q\choose k-i}a_{i}\right)t^{r+q-k}.
\end{eqnarray*}
If $\D^q \chi(\mathcal{A};t)$ can be geometrically realized as the characteristic polynomial of an arrangement of $m-q$ hyperplanes and rank $r-q$, from discussions at the beginning of this section, the inequality (\ref{formula-main}) can be easily interpreted by the no broken circuit theorem, which answers the previous question. So our question is reduced to a geometric realization of $\D^{-q} \chi(\mathcal{A};t)$ as the characteristic polynomial of an arrangement of hyperplanes for all $q\in \Bbb{Z}_{\le 0}$. Moreover, it can be further reduced as follows
\begin{itemize}
\item Is there an arrangement of hyperplanes whose characteristic polynomial is $\D\chi(\mathcal{A};t)$?
\end{itemize}
Indeed, suppose we can find a geometric realization to $\D \chi(\mathcal{A};t)$ for any $\mathcal{A}$, i.e., $\D\chi(\mathcal{A};t)=\chi(\mathcal{A}_1;t)$ for some hyperplane arrangement $\mathcal{A}_1$. Similarly, we shall have a hyperplane arrangement $\mathcal{A}_2$ such that $\D\chi(\mathcal{A}_1;t)=\chi(\mathcal{A}_2;t)$. Continuing this process, the geometric realization of $\D^q\chi(\mathcal{A};t)$ can be obtained reductively for all $q\in \Bbb{Z}_{\ge 0}$. Hence, the positive answer of the above question combining with the no broken circuit theorem will provide an intuitive interpretation to the inequality (\ref{formula-main}).

Fortunately, when $\mathcal{A}$ is central, we can assume all hyperplanes in $\mathcal{A}$ pass through the origin. In this case, we can construct an affine hyperplane arrangement $\d\mathcal{A}$ such that $\chi(\d\mathcal{A};t)=\D\chi(\mathcal{A};t)$. Suppose $\mathcal{A}$ is a linear arrangement of $m+1$ hyperplanes in $\Bbb{R}^n$. Given $K_0\in \mathcal{A}$ with the defining equation $K_0: \sum_{i=1}^n\alpha_ix_i=0$, the \emph{deconing} $\d\mathcal{A}$ of $\mathcal{A}$ is an arrangement of $m$ hyperplanes in the affine space $K_1:\sum_{i=1}^n\alpha_ix_i=1$, which is defined by
\[\d\mathcal{A}=\{H\cap K_1\mid H\in \mathcal{A}, H\neq K_0\}.\]
Since $\chi(\mathcal{A},1)=0$ when $\mathcal{A}$ is linear, we have
\[\chi(\d\mathcal{A};t)=\D\chi(\mathcal{A};t),\]
Namely, the deconing construction can geometrically realize $\D\chi(\mathcal{A};t)$ as the characteristic polynomial of the hyperplane arrangement $\d\mathcal{A}$ for the linear hyperplane arrangement $\mathcal{A}$. However, this construction can not be applied directly to affine cases. Hence, to answer the above question, we need to extend the deconing construction an affine hyperplane arrangement $\mathcal{A}$ such that $\chi(\d\mathcal{A};t)=\D\chi(\mathcal{A};t)$.





2014-02-27T02:09:46.000
1209
1209.5185
en
https://arxiv.org/abs/1209.5185
Suppose $G$ is a simple graph with $n$ vertices, $m$ edges, and rank $r$. Let $\chi_G(t)=a_0t^n-a_1t^{n-1}+\cdots +(-1)^ra_rt^{n-r}$ be the chromatic polynomial of $G$. For $q,k\in \Bbb{Z}$ and $0\le k\le q+r+1$, we obtain a sharp two-side bound for the partial binomial sum of the coefficient sequence, that is, \[ {r+q\choose k}\le \sum_{i=0}^{k}{q\choose k-i}a_{i}\le {m+q\choose 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.
Combinatorics (math.CO)
Bounds on Characteristic Polynomials
Qwen/Qwen-72B
1. YES
2. YES