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!


  • 1
    $\begingroup$ as the eigenvalues and their multiplicities are known, this seems to be a straightforward exercise. $\endgroup$ – 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.

  • $\begingroup$ It would be interesting to see a proof that didn't use that identity since it would give a combinatorial proof of the identity. The proof in Concrete Mathematics is formal, using binomial coefficients with negative indices. $\endgroup$ – Brendan Murphy Jun 19 '14 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.