2025/02/20 by Alexandr Valyuzhenich, Valyuzhenich, Alexandr, Konstantin Vorob’ev +1
Mathematics · #Algorithm #Biology #Block code #Combinatorics #Combinatorics (math.CO) #Computer science #Eigenfunction #Eigenvalues and eigenvectors #FOS: Mathematics #Genetics #Hamming code #Hamming graph #Mathematics #NODAL #Physics #Quantum mechanics #Spectral Theory in Mathematical Physics
paper · pdf · doi:10.48550/arxiv.2502.14543
openalex publication_date 2025/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The Laplacian matrix of the n-dimensional hypercube has n+1 distinct eigenvalues 2i, where 0≤ i≤ n. In 2004, Bıyıkoğlu, Hordijk, Leydold, Pisanski and Stadler initiated the study of eigenfunctions of hypercubes with the minimum number of weak and strong nodal domains. In particular, they proved that for every 1≤ i≤ (n)/(2) there is an eigenfunction of the hypercube with eigenvalue 2i that have exactly two strong nodal domains. Based on computational experiments, they conjectured that the result also holds for all 1≤ i≤ n-2. In this work, we confirm their conjecture for i≤ (2)/(3)(n-(1)/(2)) if i is odd and for i≤ (2)/(3)(n-1) if i is even. We also consider this problem for the Hamming graph H(n,q), q≥ 3 (for q=2, this graph coincides with the n-dimensional hypercube), and obtain even stronger results for all q≥ 3.