6
$\begingroup$

It is well known that the characteristic polynomial of a bipartite graph is of the form

$\sum_{k=0}^n (-1)^kc_{2k} x^{2k}$ where $c_{2k} \geq 0$.

I can prove why there cannot be any odd powered coefficients in the characteristic polynomial but cannot find a way to prove that the coefficients of the remaining terms alternate sign.

I have tried working with Sachs Theorem which states that for a graph $G$ the coefficients $a_k$ are given by

$a_k(G) = \sum_{S \in L_k} (-1)^{\omega(S)}2^{c(S)}$

where $L_k$ denotes the set of subgraphs of G composed only of cycles and disjoint edges, $\omega(S)$ is the number of connected components in S and $c(S)$ is the number of cycles.

However, counting up all of the possible graphs and their contributions (particularly with different labellings) has proved tedious and tricky and I am wondering if there is a better way to approach the proof which I have not seen yet.

Thanks!

  • 1
    One thing you could try is use the fact that if $G$ is a bipartite graph and $\lambda$ is an eigenvalue with multiplicity $m$ then $-\lambda$ is also an eigenvalue of $G$ with same multiplicity $m$ along with the fact that the $k'$th coefficient of the charpoly is just the sum of the product of all possible choices of $k$-eigenvalues from the (multi)set of all eigenvalues.2012-12-20

1 Answers 1

6

First, if the roots of a polynomial are real and positive, then its coefficients alternate in sign.

Second, if $G$ is bipartite we can write its adjacency matrix in partitioned form $ A =\begin{pmatrix}0&B^T\\ B&0 \end{pmatrix}; $ since $ \begin{pmatrix}-I&0\\0&I\end{pmatrix}\begin{pmatrix}0&B^T\\ B&0 \end{pmatrix}\begin{pmatrix}-I&0\\0&I\end{pmatrix} =\begin{pmatrix}0&-B^T\\-B&0\end{pmatrix} $ we see that $A$ and $-A$ are similar. Hence if $\lambda$ is an eigenvalue of $A$ with multiplicity $k$, so is $-\lambda$. It follows that the characteristic polynomial if a power of $x$ times a product of terms of the form $x^2-\lambda^2$.

Your statement about the coefficients of the characteristic polynomial is a consequence of the above two facts.

  • 0
    yes awesome +1...2012-12-21