DIKUL - logo
E-resources
Peer reviewed Open access
  • Eigenfunctions and minimum ...
    Valyuzhenich, Alexandr

    Discrete mathematics, March 2021, 2021-03-00, Volume: 344, Issue: 3
    Journal Article

    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 Ui(n,q) for 0≤i≤n. In this work we study functions belonging to a direct sum Ui(n,q)⊕Ui+1(n,q)⊕⋯⊕Uj(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 Ui(n,3) for i>n2. 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).