February 20, 2025
The Laplacian matrix of the $n$-dimensional hypercube has $n+1$ distinct eigenvalues $2i$, where $0\leq i\leq n$. In 2004, B\i y\i ko\u{g}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\leq i\leq \frac{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\leq i\leq n-2$. In this work, we confirm their conjecture for $i\leq \frac{2}{3}(n-\frac{1}{2})$ if $i$ is odd and for $i\leq \frac{2}{3}(n-1)$ if $i$ is even. We also consider this problem for the Hamming graph $H(n,q)$, $q\geq 3$ (for $q=2$, this graph coincides with the $n$-dimensional hypercube), and obtain even stronger results for all $q\geq 3$.
Similar papers 1
March 3, 2020
The Hamming graph $H(n,q)$ is the graph whose vertices are the words of length $n$ over the alphabet $\{0,1,\ldots,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\cdot i$ with corresponding eigenspaces $U_{i}(n,q)$ for $0\leq i\leq n$. In this work we study functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus\ldots\oplus U_j(n,q)$ for $0\leq i\leq j\le...
July 24, 2018
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\cdot i$ with corresponding eigenspaces $U_{i}(n,q)$ for $0\leq i\leq 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 $U_i(n,q)\oplus U_{i+1}(n,q)\oplus\ldots\oplus U_j(n,q)$ for $0\leq i\leq j\leq n$. For the case $n\geq i+j$ and $q\...
December 8, 2015
We find minimal supports of eigenfunctions of Hamming graphs for eigenvalue n(q-1)-q and describe eigenfunctions with minimal support.
November 21, 2024
We describe the eigenvalues and the eigenspaces of the adjacency matrices of subgraphs of the Hamming cube induced by Hamming balls, and more generally, by a union of adjacent concentric Hamming spheres. As a corollary, we extend the range of cardinalities of subsets of the Hamming cube for which Hamming balls have essentially the largest maximal eigenvalue (among all subsets of the same size). We show that this holds even when the sets in question are large, with cardinali...
July 23, 2008
We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known about the corresponding eigenvectors. Our main focus in this paper is on the nodal domains associated with the different eigenfunctions. In the analogous realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred ...
A neutral network is a subgraph of a Hamming graph, and its principal eigenvalue determines its robustness: the ability of a population evolving on it to withstand errors. Here we consider the most robust small neutral networks: the graphs that interpolate pointwise between hypercube graphs of consecutive dimension (the point, line, line and point in the square, square, square and point in the cube, and so on). We prove that the principal eigenvalue of the adjacency matrix of...
July 4, 2022
In 2001, Davies, Gladwell, Leydold, and Stadler proved discrete nodal domain theorems for eigenfunctions of generalized Laplacians. In 2019, Jost and Mulas generalized the normalized combinatorial Laplace operator of graphs to signed hypergraphs. In this paper, we establish nodal domain theorems for the normalized combinatorial Laplace operator in signed hypergraphs. We also obtain a lower bound estimates for the number of strong nodal domains.
January 1, 2022
In 2001, Davies, Gladwell, Leydold, and Stadler proved discrete nodal domain theorems for eigenfunctions of generalized Laplacians, i.e., symmetric matrices with non-positive off-diagonal entries. In this paper, we establish nodal domain theorems for arbitrary symmetric matrices by exploring the induced signed graph structure. Our concepts of nodal domains for any function on a signed graph are switching invariant. When the induced signed graph is balanced, our definitions an...
January 4, 2022
Inspired by the linear Schr\"odinger operator, we consider a generalized $p$-Laplacian operator on discrete graphs and present new results that characterize several spectral properties of this operator with particular attention to the nodal domain count of its eigenfunctions. Just like the one-dimensional continuous $p$-Laplacian, we prove that the variational spectrum of the discrete generalized $p$-Laplacian on forests is the entire spectrum. Moreover, we show how to transf...
March 15, 2023
Urschel introduced a notion of nodal partitioning to prove an upper bound on the number of nodal decomposition of discrete Laplacian eigenvectors. The result is an analogue to the well-known Courant's nodal domain theorem on continuous Laplacian. In this article, using the same notion of partitioning, we discuss the lower bound (or lack thereof) on the number of nodal decomposition of eigenvectors in the class of all graphs with a fixed number of vertices (however large). Thi...