Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is probably well-known, but... Define the $n$-dimensional hypercube graph $H_n$ as having for vertices the integers between 0 and $2^n-1$, and edges between integers differing by a power of 2. The characteristic polynomial of $H_n$ is then $\prod_{k=0}^n(x-n+2k)^{\frac {n!}{k!(n-k)!}}$, i.e. $(x-3)(x-1)^3(x+1)^3(x+3)$ for a cube, $(x-4)(x-2)^4x^6(x+2)^4(x+4)$ for a tesseract, etc. Is there a graph-theoretic proof of this result?

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

View the vertices as elements of $\mathbb{Z}^n$. If $a\in\mathbb{Z}^n$, define a function $f_a$ on the vertices by $$ f_a(x) = (-1)^{a^Tx}. $$ This function is an eigenvectors and if $a$ has weight $w$, the eigenvalue is $n-2w$. I can make this look more combinatorial by viewing vertices (and $a$) as subsets of $\{1,\ldots,n\}$ and noting that $f_a(x)$ is determined by the parity of $a \cap x$ (abusing notation). Different choices of $a$ give linearly independent eigenvectors, so we get the multiplicities as well as the eigenvalues.

The actual difficulty with this question is in deciding what you mean by a "graph theoretical proof". From where I write, linear algebra is a standard and fundamental tool in graph theory.

Comment response: (too long for a comment box). OK. The $n$-cube is the Cartesian product of $n$ copies of $K_2$. The eigenvalues of the Cartesian product of two graphs $G$ and $H$ are the sums of the eigenvalues of $G$ with the eigenvalues of $H$. (The simplest way to see this is to note that the eigenvectors of the product are the Kronecker products of the eigenvectors of the factors.) Applying this $n$ times to $K_2$ gives the desired result.

There are formulas for the effect on the characteristic polynomial adding edges or vertices, but they are not all simple, and I cannot see how to use them to get the eigenvalues of the $n$-cube.

share|improve this answer
    
Well, actually, I am looking for things like calculations of the characteristic polynomial by manipulations of the graph (addig edges or vertices, product of graphes, ans so on), and trying to get some intuition by using well-known families of graphs. But I may be completely on the wrong track –  Feldmann Denis Nov 10 '12 at 22:34
    
My comment to this was a bit too long, so I've added it to my answer. –  Chris Godsil Nov 10 '12 at 22:48
    
A related remark: since $H_n$ is regular, an explicit formula for the number of trees follows from knowing the eigenvalues of the adjacency matrix. It was an open problem to find a combinatorial proof of this formula. Such a proof was recently given by Olivier Bernardi, front.math.ucdavis.edu/1207.0896. –  Richard Stanley Nov 11 '12 at 2:23
add comment

The hypercube graph is a Cayley graph. The Hamming graph $H(n,r)$ is the Cayley graph $Cay(\Bbb Z_r^n,S)$ where $S$ is the set of all elements of $\Bbb Z_r^n$ with exactly one nozero coordinate. In particular, the Hamming graph $H(n,2)$ is the familiar $n$-dimensional hypercube.

Since $\Bbb Z_r^n$ is abelian, $\sum_{s\in S}\chi(s)$ where $\chi$ is an irreducible representation of $\Bbb Z_r^n$ is an eigenvalue of $H(n,r)$. The eigenvectors of the adjacency matrix $A$ of $H(n,r)$ are the vectors $\{u_x\}$, $x\in\Bbb Z_r^n$, where its $y$th coordinate is $\omega_r^{-\sum_{i=1}^nx_iy_i}$, $y\in\Bbb Z_r^n$ and $\omega_r=e^{\frac{2\pi i}{r}}$. Let $\lambda_x$ be the corresponding eigenvalue of $u_x$. If we dnote by $\omega_H(x)$ the number of nonzero coordinates in $x$, we have $\lambda_x=(r-1)n-r\omega_H(x)$. Now it is enough to put $r=2$. For more details on the spectrum of Cayley graphs see "Spectra of Cayley graphs, L. Babai, Journal of Combinatorial Theory, Series B 27, (1979) 180-189.

share|improve this answer
add comment

It is interesting, worthwhile, and not very difficult to understand the situation for the Cartesian product of two or more arbitrary graphs. However here is a simplified answer which applies to this case: Let $G$ be a graph with $n$ vertices and $H$ the $2n$ vertex graph made by taking two copies of $G$ and joining corresponding vertices with an edge. If the (possibly not distinct) eigenvelaues of $G$ are $\theta_1,\theta_2,\cdots,\theta_n$ then the $2n$ eigenvalues of $H$ are $\theta_1\pm 1,\theta_2\pm 1,\cdots,\theta_n\pm 1.$ (Note that $H$ is just the Cartesian product $G \times K_2$.) Here is why: Let $A$ be the adjacency matrix of $G$ and $\mathbf{x}_1,\cdots,\mathbf{x}_n$ a basis of eigenvectors with $A\mathbf{x}_i=\theta_i\mathbf{x}_i.$ Then the $2n \times 2n$ adjacency matrix of $H$ is $\left( \begin{array}{cc} A & I \\\ I & A \\\ \end{array}\right)$ and it is easy to confirm that $\left( \begin{array}{c}\mathbf{x}_i \\\ \mathbf{x}_i \\\ \end{array}\right)$ and $\left( \begin{array}{c}\mathbf{x}_i \\\ -\mathbf{x}_i \\\ \end{array}\right)$ are eigenvectors for $\theta_i+1$ and $\theta_i-1.$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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