Strongly cospectral sets in seven-dimensional cubelike graphs

Every set of pairwise strongly cospectral vertices in a cubelike graph on $128$ vertices has at most four elements, and a connected graph attains four. Vertices are strongly cospectral if their orthogonal projections onto each adjacency eigenspace agree up to sign. This gives a negative answer to Árnadóttir and Godsil's question whether their upper bound is tight in every dimension: in dimension seven their bound gives eight. They proved the general bound, attained it in dimensions three through six, and supplied the connected construction attaining four used here. Our upper bound combines their abelian character criterion, building on Sin and Sorci's normal-Cayley criterion, with congruences, a second-moment bound and an exact finite inequality certified by linear programming duality. The universal upper bound, including the certificate checks, is formalized in Lean; exact computations also verify the attaining graph. Sin's construction gives arbitrarily large strongly cospectral classes as the dimension grows.

Computer-assisted; not yet reviewed by experts. Produced by AI models under the author's direction.