Sparse hypergraphs: From theory to applications
Shangguan Chong, Gennian Ge · Scientia Sinica Mathematica · 2022
For fixed integers $r$, $e$ and $v$, an $r$-uniform hypergraph is said to be $(v,e)$-free or $(v,e)$-sparse if the union of any $e$ distinct edges of it contains at least $v+1$ vertices. The notion of sparse hypergraphs was initially introduced by Brown, ErdHos and Sós in the 1970s. Since then, determining the upper and lower bounds on the maximum number of edges that can be contained in a sparse hypergraph with a given number of vertices has become one of the central problems in extremal combinatorics. A number of powerful methods from several disciplines, including combinatorics, probability theory, algebra, and number theory, have been applied to the study of sparse hypergraphs. In this paper, we introduce the recent developments on two important conjectures of Brown, ErdHos and Sós on sparse hypergraphs, and discuss some of the applications of sparse hypergraphs to extremal combinatorics and information sciences. We also provide new constructions for perfect Hash matrices and union-free hypergraphs under certain parameters. Our constructions improve the previously best-known lower bounds for these problems.