Sharp asymptotic bounds for uniform union-free hypergraphs

Abstract

An $r$-uniform hypergraph is called $t$-union-free if any two distinct subsets of at most $t$ edges have distinct union. The study of union-free hypergraphs has multiple origins and a long history, dating back to the works of Kautz and Singleton (1964) in coding theory, Bollobás and Erdős (1976) in combinatorics, and Hwang and Sós (1987) in group testing. Let $U_t(n,r)$ denote the maximum number of edges in an $n$-vertex $t$-union-free $r$-uniform hypergraph. In this paper, we determine the asymptotic behavior of $U_t(n,r)$, up to a lower order term, for almost all $t\ge 3$ and $r\ge 3$. This significantly advances the understanding of this extremal function, as previously, only the asymptotics of $U_2(n,3)$ and $U_2(n,4)$ were known. As a key ingredient of our proof, we establish the existence of near-optimal locally sparse induced hypergraph packings, which is of independent interest.

This work overlaps with arXiv:2411.07908, which was split into two papers after substantially expanding the results