Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph

Abstract

The Hamming graph $H(n,q)$ is the graph whose vertices are the words of length $n$ over the alphabet $\{0,1,\dots ,q-1\}$, where two vertices are adjacent if they differ in exactly one coordinate. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_i(n,q)$ for $0\le i\le n$. In this work we study functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus \dots \oplus U_j(n,q)$ for $0\le i\le j\le n$. We find the minimum cardinality of the support of such functions for $q=2$ and for $q=3$, $i+j>n$. In particular, we find the minimum cardinality of the support of eigenfunctions from the eigenspace $U_i(n,3)$ for $i>\frac{n}{2}$. Using the correspondence between $1$-perfect bitrades and eigenfunctions with eigenvalue $-1$, we find the minimum size of a $1$-perfect bitrade in the Hamming graph $H(n,3)$.

14 pages, 4 figures