Minimum supports of functions on the Hamming graphs with spectral constraints

Alexandr Valyuzhenich, Konstantin Vorob'ev

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)1351-1360
Number of pages10
JournalDiscrete Mathematics
Volume342
Issue number5
DOIs
Publication statusPublished - 1 May 2019

Keywords

  • Eigenfunction
  • Hamming graph
  • Support
  • CARDINALITY
  • EIGENFUNCTIONS

Fingerprint Dive into the research topics of 'Minimum supports of functions on the Hamming graphs with spectral constraints'. Together they form a unique fingerprint.

Cite this