Eigenvalues and eigenfunctions of a Hamming ball

This survey will appear as a chapter in the forthcoming "Proceedings of the HDP VIII Conference".

Let $G$ be a graph and let $g, f$ be nonnegative integer-valued functions defined on $V(G)$ such that $g(v) \le f(v)$ and $g(v) \equiv f(v) \pmod{2}$ for all $v \in V(G)$. A $(g,f)$-parity factor of $G$ is a spanning subgraph $H$ such that for each vertex $v \in V(G)$, $g(v) \le d_H(v) \le f(v)$ and $f(v)\equiv d_H(v) \pmod{2}$. We prove sharp upper bounds for certain eigenvalues in an $h$-edge-connected graph $G$ with given minimum degree to guarantee the existence of a $(g,...

We give a delocalization estimate for eigenfunctions of the discrete Laplacian on large $d+1$-regular graphs, showing that any subset of the graph supporting $\epsilon$ of the $L^2$ mass of an eigenfunction must be large. For graphs satisfying a mild girth-like condition, this bound will be exponential in the size of the graph.

We survey recent results related to the concentration of eigenfunctions. We also prove some new results concerning ball-concentration, as well as showing that eigenfunctions saturating lower bounds for $L^1$-norms must also, in a measure theoretical sense, have extreme concentration near a geodesic.

The width of a poset is the size of its largest antichain. Sperner's theorem states that $(2^{[n]},\subset)$ is a poset whose width equals the size of its largest layer. We show that Hamming ball posets also have this property. This extends earlier work that proves this in the case of small radii. Our proof is inspired by (and corrects) a result of Harper.

We introduce a new notion of error-correcting codes on $[q]^n$ where a code is a set of proper $q$-colorings of some fixed $n$-vertex graph $G$. For a pair of proper $q$-colorings $X, Y$ of $G$, we define their distance as the minimum Hamming distance between $X$ and $\sigma(Y)$ over all $\sigma \in S_q$. We then say that a set of proper $q$-colorings of $G$ is $\delta$-distinct if any pair of colorings in the set have distance at least $\delta n$. We investigate how one-si...

In this note, we improve the lower bounds for the maximum size of the $k$th largest eigenvalue of the adjacency matrix of a graph for several values of $k$. In particular, we show that closed blowups of the icosahedral graph improve the lower bound for the maximum size of the fourth largest eigenvalue of a graph, answering a question of Nikiforov.

In this paper we investigate the behavior of the eigenvalues of the Dirichlet Laplacian on sets in $\mathbb{R}^N$ whose first eigenvalue is close to the one of the ball with the same volume. In particular in our main Theorem we prove that, for all $k\in\mathbb{N}$, there is a positive constant $C=C(k,N)$ such that for every open set $\Omega\subseteq \mathbb{R}^N$ with unit measure and with $\lambda_1(\Omega)$ not excessively large one has \begin{align*} |\lambda_k(\Omega)-\la...

We present sharp inequalities relating the number of vertices, edges, and triangles of a graph to the smallest eigenvalue of its adjacency matrix and the largest eigenvalue of its Laplacian.

In this paper, we give some bounds for principal eigenvector and spectral radius of connected uniform hypergraphs in terms of vertex degrees, the diameter, and the number of vertices and edges.