Rank-Coloring Conjecture and Folded 7-cube

Question

Rank-Coloring Conjecture is conjecture by C. van Nuffelen that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. But N. Alon and P. D. Seymour give a counterexample, with chromatic number 32 and with an adjacency matrix of rank 29. [p.50 1]

Whis counterexample is Folded 7-cube, this is distance-regular graph with Intersection arrays $\{7, 6, 5; 1, 2, 3\}$, it is easy to count the spectum $7^1, 3^{21}, (-1)^{35}, {-5}^7$, but this implies that the adjacency matrix is ​​not degenerate and its rank is equal to $64$. What I do not understand in this problem?

1. Spectra of Graphs Authors: Brouwer, Andries E., Haemers, Willem H.

Answer 1

The counterexample is the complement of the folded 7-cube: it is the graph on vertex set $\{0,1\}^6$ whose vertices are adjacent if they differ in $2$, $3$, $4$, or $5$ coordinates.

The eigenvectors of $0$ come in two types:

• We can assign to each vertex $(x_1,x_2,x_3,x_4,x_5,x_6)$ the value $(-1)^{x_a+x_b+x_c}$ for some $\{a,b,c\} \subset \{1,2,3,4,5,6\}$, for $\binom 63$ independent eigenvectors.
• We can assign to each vertex $(x_1,x_2,x_3,x_4,x_5,x_6)$ the value $(-1)^{x_a+x_b+x_c+x_d}$ for some $\{a,b,c,d\} \subset \{1,2,3,4,5,6\}$, for $\binom 64$ independent eigenvectors.

To check that these are eigenvectors, check that for the $8$ non-neighbors of a vertex, including the vertex itself, $4$ have value $+1$ and $4$ have the value $-1$. (So the $56$ neighbors are also split evenly.)

This gives a co-rank at least $\binom63 + \binom 64 = 35$, so the rank is at most $29$ (and in fact it is exactly $29$).