On the spectrum and linear programming bound for hypergraphs
share
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 θ for several parameters (r,u,θ). 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.
READ FULL TEXT