On the spectrum and linear programming bound for hypergraphs
arXiv:2009.03022 · doi:10.1016/j.ejc.2022.103535
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 -regular -uniform hypergraph with second eigenvalue at most for several parameters . In particular, orthogonal arrays give the structure of the largest hypergraphs with second eigenvalue at most for every sufficiently large . Moreover, we show that a generalized Moore geometry has the largest spectral gap among all hypergraphs of that order and degree.
arXiv commentreferences updated, fixed some typos, added explanation describing the differences between the graphs and hypergraphs results, 27 pages, 3 tables, European Journal of Combinatorics, accepted for publication
References in corpus (6)
- Universally optimal distribution of points on spheres
- Distance-regular graphs
- Simplicial complexes: spectrum, homology and random walks
- A spectral version of the Moore problem for bipartite regular graphs
- Eigenvalues of graphs and spectral Moore theorems
- Mixing Rates of Random Walks with Little Backtracking