{
  "id": "1108.4810",
  "version": "v3",
  "published": "2011-08-24T11:06:55.000Z",
  "updated": "2012-05-26T21:45:45.000Z",
  "title": "Nonpositive Eigenvalues of the Adjacency Matrix and Lower Bounds for Laplacian Eigenvalues",
  "authors": [
    "Zachary B. Charles",
    "Miriam Farber",
    "Charles R. Johnson",
    "Lee Kennedy-Shaffer"
  ],
  "comment": "23 pages, 12 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $NPO(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 $NPO(k)$ is well-defined and prove that the values of $NPO(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) \\ge NPO(k) > T_k$, in which $R(k,k+1)$ is the Ramsey number for $k$ and $k+1$, and $T_k$ is the $k^{th}$ triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the $k$-th largest eigenvalue is bounded from below by the $NPO(k)$-th largest degree, which generalizes some prior results.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2012-05-26T21:45:45.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "adjacency matrix",
      "lower bounds",
      "nonpositive eigenvalues",
      "laplacian eigenvalues",
      "th largest degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1108.4810C"
    }
  }
}