# Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G))$ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) respectively, then we have

$$\max ({n_{-}A(K_{n, m}), n_{+}(A(K_{n, m}) }) = \binom{n}{m-1}$$

The proof is meant to be in the book "C. Godsil, G. Royle, Algebraic Graph Theory, Springer, 2001." which I do have but can't find, or in the paper http://www.sciencedirect.com/science/article/pii/S0095895602000412 but they only state it as a fact and reference to "] K.N. Vander Meulen, Covers and decompositions of graphs by complete multipartite subgraphs, Ph.D. Thesis, Queen’s University, Kingston, 1995." which I can't seem to get hold of.

If anybody could direct me to the proof, or show me how it is done, I would be immensely grateful.

Many thanks!

Rodger

• as the eigenvalues and their multiplicities are known, this seems to be a straightforward exercise. – Dima Pasechnik Jun 17 '14 at 19:26

I think that formula should state that the max is ${n-1\choose m}$.
Here is a proof: Using the formulas for the multiplicities of the negative eigenvalues given on wikipedia, you have $$n_{-}(A(K_{n,m}))=\sum_{j=0}^{m^*}(-1)^{j+1}{n\choose j}=(-1)^{m^*+1}{n-1\choose m^*}$$ where $m^*=m$ if $m$ is odd and $m^*=m-1$ if $m$ is even; the identity for partial alternating sums of binomial coefficients can is on page 165 of Concrete Mathematics by Graham, Knuth, and Patashnik.
Thus if $m$ is odd there are ${n-1\choose m}$ negative eigenvalues and ${n-1\choose m-1}$ positive eigenvalues, and vice versa if $m$ is even. Since $m\geq n/2$ (otherwise $K_{n,m}$ is empty), ${n-1\choose m}$ is bigger.