Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph

2020/03/03 by Alexandr Valyuzhenich, Valyuzhenich, Alexandr
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.2003.01571

14 pages, 4 figures

arxiv created 2020/03/03 · arxiv updated 2020/03/04

Abstract

The Hamming graph H(n,q) is the graph whose vertices are the words of length n over the alphabet \0,1,…,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⋅ i with corresponding eigenspaces U_i(n,q) for 0≤ i≤ n. In this work we study functions belonging to a direct sum U_i(n,q)⊕ U_i+1(n,q)⊕…⊕ U_j(n,q) for 0≤ i≤ j≤ 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>(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).

Related

• Minimal supports of eigenfunctions of Hamming graphs
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• On strong nodal domains for eigenfunctions of Hamming graphs
• Low-degree functions without non-essential arguments
• On existence of perfect bitrades in Hamming graphs