TY - JOUR

T1 - Minimum supports of functions on the Hamming graphs with spectral constraints

AU - Valyuzhenich, Alexandr

AU - Vorob'ev, Konstantin

N1 - Publisher Copyright: © 2019 Elsevier B.V.

PY - 2019/5/1

Y1 - 2019/5/1

N2 - We study functions defined on the vertices of the Hamming graphs H(n,q). 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 consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum Ui(n,q)⊕Ui+1(n,q)⊕⋯⊕Uj(n,q) for 0≤i≤j≤n. For the case i+j≤n and q≥3 we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case i+j>n and q≥4 we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for i=j, i>[Formula presented] and q≥5. In particular, we characterize eigenfunctions from the eigenspace Ui(n,q) with the minimum cardinality of the support for cases i≤[Formula presented], q≥3 and i>[Formula presented], q≥5.

AB - We study functions defined on the vertices of the Hamming graphs H(n,q). 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 consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum Ui(n,q)⊕Ui+1(n,q)⊕⋯⊕Uj(n,q) for 0≤i≤j≤n. For the case i+j≤n and q≥3 we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case i+j>n and q≥4 we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for i=j, i>[Formula presented] and q≥5. In particular, we characterize eigenfunctions from the eigenspace Ui(n,q) with the minimum cardinality of the support for cases i≤[Formula presented], q≥3 and i>[Formula presented], q≥5.

KW - Eigenfunction

KW - Hamming graph

KW - Support

KW - CARDINALITY

KW - EIGENFUNCTIONS

UR - http://www.scopus.com/inward/record.url?scp=85061211835&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2019.01.015

DO - 10.1016/j.disc.2019.01.015

M3 - Article

AN - SCOPUS:85061211835

VL - 342

SP - 1351

EP - 1360

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 5

ER -