0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ as the eigenvalues and their multiplicities are known, this seems to be a straightforward exercise. $\endgroup$ Jun 17, 2014 at 19:26

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\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$ Jun 19, 2014 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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