On the spectrum and linear programming bound for hypergraphs

DOI10.1016/J.EJC.2022.103535MaRDI QIDQ2143404zbMATH OpenOpenAlexWikidataFDO

Authors Sebastian Cioaba, Jack H. Koolen, Masato Mimura, Hiroshi Nozaki, Takayuki Okuda

Publication date 31 May 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.03022

zbMATH Keywords

adjacency matrixdegree-diameter problemregular hypergraphAlon-Boppana theorem

Mathematics Subject Classification ID

Linear programming (90C05) Hypergraphs (05C65) Expander graphs (05C48)

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 $heta$ for several parameters $(r,u,heta)$. 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.

Recommendations

• Spectra of hypergraphs and applications
• Spectra of uniform hypergraphs
• Linear programming bounds for regular graphs
• Spectra of random regular hypergraphs
• Some upper bounds on the eigenvalues of uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 3878961 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3467565 (Why is no real title available?)
• scientific article; zbMATH DE number 3528270 (Why is no real title available?)
• scientific article; zbMATH DE number 3394189 (Why is no real title available?)
• A Survey on Spectra of infinite Graphs
• A generalization of Moore graphs of diameter two
• A spectral version of the Moore problem for bipartite regular graphs
• Approximate Moore graphs are good expanders
• Current research on algebraic combinatorics. Supplements to our book, Algebraic combinatorics I
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Distance-regular graphs
• Eigenvalues and expanders
• Eigenvalues of a real supersymmetric tensor
• Harmonic Analysis on Symmetric Spaces—Higher Rank Spaces, Positive Definite Matrix Space and Generalizations
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Laplacian eigenvalues and partition problems in hypergraphs
• Linear programming bounds for regular graphs
• Maximizing the order of a regular graph of given valency and second eigenvalue
• Mixing rates of random walks with little backtracking
• On Moore Graphs with Diameters 2 and 3
• On the Maximum Diameter of a Class of Distance-Regular Graphs
• On the existence of certain distance-regular graphs
• On the second eigenvalue of hypergraphs
• Quantum probability and spectral analysis of graphs. With a foreword by Professor Luigi Accardi.
• Ramanujan Type Buildings
• Ramanujan hypergraphs
• Shifted simplicial complexes are Laplacian integral
• Simplicial complexes: spectrum, homology and random walks
• Some Ramanujan hypergraphs associated to GL\((n,\mathbb{F}_q)\)
• Spectra of combinatorial Laplace operators on simplicial complexes
• Spectra of graphs
• Spectra of hypergraphs and applications
• Spectra of regular graphs and hypergraphs and orthogonal polynomials
• Spectra of uniform hypergraphs
• The finite upper half space and related hypergraphs
• The theta number of simplicial complexes
• Transversals in Latin Squares
• Turán problems and shadows. I: Paths and cycles
• Universally optimal distribution of points on spheres
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(5)

• (Nearly-)tight bounds on the contiguity and linearity of cographs
• Linear programming bounds for regular graphs
• Spectra of random regular hypergraphs
• Spectral extremal results for hypergraphs
• A Spectral Moore Bound for Bipartite Semiregular Graphs

This page was built for publication: On the spectrum and linear programming bound for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2143404)