New Turán exponents for two extremal hypergraph problems

Abstract

An $r$-uniform hypergraph is called $t$-cancellative if for any $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 any 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)$ (resp. $U_t(n,r)$) denote the maximum number of edges of a $t$-cancellative (resp. $t$-union-free) $r$-uniform hypergraph on $n$ vertices. Among other results, we show that for fixed $r\ge 3,t\ge 3$ and $n\to \infty$ $$\Omega (n^{\lfloor \frac{2r}{t+2}\rfloor +\frac{2r(\mathrm{mod}t+2)}{t+1}})=C_t(n,r)=O(n^{\lceil \frac{r}{\lfloor t/2\rfloor +1}\rceil })\text{ and }\Omega (n^{\frac{r}{t-1}})=U_t(n,r)=O(n^{\lceil \frac{r}{t-1}\rceil }),$$ thereby significantly narrowing the gap between the previously known lower and upper bounds. In particular, we determine the Turán exponent of $C_t(n,r)$ when $2\mid t\text{ and }(t/2+1)\mid r$, and of $U_t(n,r)$ when $(t-1)\mid r$. The main tool used in proving the two lower bounds is a novel connection between these problems and sparse hypergraphs.

8 pages, SIAM Journal on Discrete Mathematics, to appear