Eigenvalues and eigenfunctions of a Hamming ball

Under study are eigenfunctions of $q$-ary $n$-dimensional hypercube. Given all values of an eigenfunction in the sphere we develop methods to reconstruct the function in full or in part. First, we obtain that all values of the function in the corresponding ball are uniquely determined under some supplementary conditions. Secondly, if the radius is equal to the eigenvalue number we obtain that all values of the eigenfunction are uniquiely determined under some supplementary co...

Let a \neq b be two positive scalars. A Euclidean representation of a simple graph G in R^r is a mapping of the nodes of G into points in R^r such that the squared Euclidean distance between any two points is a if the corresponding nodes are adjacent and b otherwise. A Euclidean representation is spherical if the points lie on an (r-1)-sphere, and is J-spherical if this sphere has radius 1 and a=2 < b. Let dim_E(G), dim_S(G) and dim_J(G) denote, respectively, the smallest dim...

Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random.

Let $N_{\alpha,\beta}(d)$ denote the maximum size of a spherical two-distance set in $\mathbb{R}^d$ such that the inner products of distinct vectors only take $\alpha$ and $\beta$. By considering the correspondence between spherical two-distance sets and graphs with specific spectral properties, we determine $N_{\alpha,\beta}(d)$ for fixed $-1\leq\beta<0\leq\alpha<1$ and sufficiently large $d$, which extends the work in [Equiangular lines with a fixed angle, Ann. Math. 194 (2...

The operator that first truncates to a neighborhood of the origin in the spectral domain then truncates to a neighborhood of the origin in the spatial domain is investigated in the case of Boolean cubes. This operator is self adjoint on a space of bandlimited signals. The eigenspaces of this iterated projection operator are studied and are shown to depend fundamentally on the neighborhood structure of the cube when regarded as a metric graph with path distance equal to Hammin...

Let $D$ denote the distance matrix for an $n+1$ point metric space $(X,d)$. In the case that $X$ is an unweighted metric tree, the sum of the entries in $D^{-1}$ is always equal to $2/n$. Such trees can be considered as affinely independent subsets of the Hamming cube $H_n$, and it was conjectured that the value $2/n$ was minimal among all such subsets. In this paper we confirm this conjecture and give a geometric interpretation of our result which applies to any subset of $H...

A celebrated theorem of Kleitman in extremal combinatorics states that a collection of binary vectors in $\{0, 1\}^n$ with diameter $d$ has cardinality at most that of a Hamming ball of radius $d/2$. In this paper, we give an algebraic proof of Kleitman's Theorem, by carefully choosing a pseudo-adjacency matrix for certain Hamming graphs, and applying the Cvetkovi\'c bound on independence numbers. This method also allows us to prove several extensions and generalizations of K...

We study a family of graphs related to the $n$-cube. The middle cube graph of parameter $k$ is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine th...

In this paper we find new maximal cliques of size $\frac{q+1}{2}$ or $\frac{q+3}{2}$, accordingly as $q\equiv 1(4)$ or $q\equiv 3(4)$, in Paley graphs of order $q^2$, where $q$ is an odd prime power. After that we use new cliques to define a family of eigenfunctions corresponding to both non-principal eigenvalues and having the cardinality of support $q+1$, which is the minimum by the weight-distribution bound.

The $n$-dimensional hypercube has $n+1$ distinct eigenvalues $n-2i$, $0\leq i\leq n$, with corresponding eigenspaces $U_i(n)$. In 2021 it was proved by the author that if a function with non-empty support belongs to the direct sum $U_i(n)\oplus U_{i+1}(n)\oplus\ldots\oplus U_j(n)$, where $0\leq i\leq j\leq n$, then it has at least $\max(2^i,2^{n-j})$ non-zeros. In this work we give a characterization of functions achieving this bound.