On the spectrum and linear programming bound for hypergraphs
On the spectrum and linear programming bound for hypergraphs
复制标题
DOI：
10.1016/j.ejc.2022.103535
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
S. Cioabă;J. Koolen;M. Mimura;Hiroshi Nozaki;T. Okuda
中科院分区：
文献类型：
--
作者：
S. Cioabă;J. Koolen;M. Mimura;Hiroshi Nozaki;T. Okuda
图的谱与许多图的参数密切相关。特别地，正则图的谱隙是其价与第二特征值之间的差，被广泛认为是连通性的代数度量，并且在扩展图理论中起着关键作用。在本文中，我们扩展了以前的工作，图和二部图，并提出了一个线性规划的方法获得的阶的规则一致超图规定的不同的特征值的上界。此外，我们还得到了第二特征值受给定值限制的正则一致超图的阶的一般上界。我们的结果改进和推广了Feng和Li（1996）关于正则超图的Alon-Boppana定理和Dinitz等人的工作。（2020）关于摩尔或度直径问题。对于多个参数（r，u，θ），确定了第二特征值至多为θ的r-正则u-一致超图的最大阶.特别地，正交表给出了对每一个充分大的r，第二特征值至多为1的最大超图的结构。此外，我们还证明了广义摩尔几何在该阶和度的超图中具有最大的谱隙。
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 as 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 and Li (1996) on Alon–Boppana theorems for regular hypergraphs and by Dinitz et al.(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.