{
  "id": "2009.03022",
  "version": "v1",
  "published": "2020-09-07T11:28:14.000Z",
  "updated": "2020-09-07T11:28:14.000Z",
  "title": "On the spectrum and linear programming bound for hypergraphs",
  "authors": [
    "Sebastian M. Cioabă",
    "Jack H. Koolen",
    "Masato Mimura",
    "Hiroshi Nozaki",
    "Takayuki Okuda"
  ],
  "comment": "26 pages, 3 tables",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The spectrum of a graph is closely related to many graph parameters. In particular, the spectral gap of a regular graph which is the difference between its valency and second eigenvalue, is widely seen an algebraic measure of connectivity and plays a key role in the theory of expander graphs. In this paper, we extend previous work done for graphs and bipartite graphs and present a linear programming method for obtaining an upper bound on the order of a regular uniform hypergraph with prescribed distinct eigenvalues. Furthermore, we obtain a general upper bound on the order of a regular uniform hypergraph whose second eigenvalue is bounded by a given value. Our results improve and extend previous work done by Feng--Li (1996) on Alon--Boppana theorems for regular hypergraphs and by Dinitz--Schapira--Shahaf (2020) on the Moore or degree-diameter problem. We also determine the largest order of an $r$-regular $u$-uniform hypergraph with second eigenvalue at most $\\theta$ for several parameters $(r,u,\\theta)$. In particular, orthogonal arrays give the structure of the largest hypergraphs with second eigenvalue at most $1$ for every sufficiently large $r$. Moreover, we show that a generalized Moore geometry has the largest spectral gap among all hypergraphs of that order and degree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-07T11:28:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear programming bound",
      "second eigenvalue",
      "regular uniform hypergraph",
      "largest spectral gap",
      "general upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}