Nonpositive Eigenvalues of the Adjacency Matrix and Lower Bounds for Laplacian Eigenvalues

Zachary B. Charles; Miriam Farber; Charles R. Johnson; Lee Kennedy-Shaffer

paper

Nonpositive Eigenvalues of the Adjacency Matrix and Lower Bounds for Laplacian Eigenvalues

arXiv:1108.4810

Abstract

Let $N P O (k)$ be the smallest number $n$ such that the adjacency matrix of any undirected graph with $n$ vertices or more has at least $k$ nonpositive eigenvalues. We show that $N P O (k)$ is well-defined and prove that the values of $N P O (k)$ for $k = 1, 2, 3, 4, 5$ are $1, 3, 6, 10, 16$ respectively. In addition, we prove that for all $k \geq 5$ , $R (k, k + 1) \geq N P O (k) > T_{k}$ , in which $R (k, k + 1)$ is the Ramsey number for $k$ and $k + 1$ , and $T_{k}$ is the $k^{t h}$ triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the $k$ -th largest eigenvalue is bounded from below by the $N P O (k)$ -th largest degree, which generalizes some prior results.

23 pages, 12 figures