On the spectrum and linear programming bound for hypergraphs

DOI10.1016/J.EJC.2022.103535zbMATH Open1490.05193arXiv2009.03022OpenAlexW3083511639WikidataQ114184725 ScholiaQ114184725MaRDI QIDQ2143404FDOQ2143404

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)

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.

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

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

zbMATH Keywords

adjacency matrixdegree-diameter problemregular hypergraphAlon-Boppana theorem

Mathematics Subject Classification ID

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

Cites Work

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

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)