Asymptotically sharp bounds for cancellative and union-free hypergraphs

Abstract

An $r$-graph is called $t$-cancellative if for arbitrary $t+2$ distinct edges $A_1,\dots ,A_t,B,C$, it holds that $({\cup }_{i=1}^t{A}_i)\cup B\ne ({\cup }_{i=1}^t{A}_i)\cup C$; it is called $t$-union-free if for arbitrary two distinct subsets $\mathcal{A},\mathcal{B}$, each consisting of at most $t$ edges, it holds that ${\cup }_{A\in \mathcal{A}}A\ne {\cup }_{B\in \mathcal{B}}B$. Let $C_t(n,r)$ and $U_t(n,r)$ denote the maximum number of edges that can be contained in an $n$-vertex $t$-cancellative and $t$-union-free $r$-graph, respectively. The study of $C_t(n,r)$ and $U_t(n,r)$ has a long history, dating back to the classic works of Erdős and Katona, and Erdős and Moser in the 1970s. In 2020, Shangguan and Tamo showed that $C_{2(t-1)}(n,tk)=\hat{I}˜(n^k)$ and $U_{t+1}(n,tk)=\hat{I}˜(n^k)$ for all $t\ge 2$ and $k\ge 2$. In this paper, we determine the asymptotics of these two functions up to a lower order term, by showing that for all $t\ge 2$ and $k\ge 2$, \begin{align*} \text{${\lim }_{n\to \infty }\frac{C_{2(t-1)}(n,tk)}{n^k}={\lim }_{n\to \infty }\frac{U_{t+1}(n,tk)}{n^k}=\frac{1}{k!}\cdot \frac{1}{\left(\genfrac{}{}{0ex}{}{tk-1}{k-1}\right)}$.} \end{align*} Previously, it was only known by a result of Füredi in 2012 that ${\lim }_{n\to \infty }\frac{C_2(n,4)}{n^2}=\frac{1}{6}$. To prove the lower bounds of the limits, we utilize a powerful framework developed recently by Delcourt and Postle, and independently by Glock, Joos, Kim, Kühn, and Lichev, which shows the existence of near-optimal hypergraph packings avoiding certain small configurations, and to prove the upper bounds, we apply a novel counting argument that connects $C_{2(t-1)}(n,tk)$ to a classic result of Kleitman and Frankl on a special case of the famous Erdős Matching Conjecture.

21 pages