Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph
Konstantin Vorob’ev, Denis S. Krotov · Journal of Applied and Industrial Mathematics · 2015
We improve the available upper and lower bounds for the minimal size of the support of an eigenfunction of the Hamming graph H(n, q), where q > 2. In particular, the size of a minimal 1-perfect bitrade in H(n, q) is estimated. We show that the size of such a bitrade is at least 2 n−(n−1)/q (q − 2)(n−1)/q for q ≥ 4 and 3 n/2(1 − O(1/n)) for q = 3. Moreover, for n ≡ 1 mod q, where q is a prime power, we propose a construction of bitrades of size q (q−2)(n−1)/q 2(n−1)/q+1.