Asymptotics of the Hypergraph Bipartite Turán Problem

Abstract

For positive integers s, t, r, let Ks,t(r)$$K_{s,t}^{(r)}$$ denote the r-uniform hypergraph whose vertex set is the union of pairwise disjoint sets X,Y1,⋯,Yt$$X,Y_1,\dots ,Y_t$$, where |X|=s$$|X| = s$$ and |Y1|=⋯=|Yt|=r-1$$|Y_1| = \dots = |Y_t| = r-1$$, and whose edge set is {{x}∪Yi:x∈X,1≤i≤t}$${{x} \cup Y_i: x \in X, 1\le i\le t}$$. The study of the Turán function of Ks,t(r)$$K_{s,t}^{(r)}$$ received considerable interest in recent years. Our main results are as follows. First, we show that 1exn,Ks,t(r)=Os,rt1s-1nr-1s-1$$\begin{aligned} \textrm{ex}\left( n,K_{s,t}^{(r)}\right) = O_{s,r}\left( t^{\frac{1}{s-1}}n^{r - \frac{1}{s-1}}\right) \end{aligned}$$for all s,t≥2$$s,t\ge 2$$ and r≥3$$r\ge 3$$, improving the power of n in the previously best bound and resolving a question of Mubayi and Verstraëte about the dependence of ex(n,K2,t(3))$$\textrm{ex}(n,K_{2,t}^{(3)})$$ on t. Second, we show that (1) is tight when r is even and t≫s$$t \gg s$$. This disproves a conjecture of Xu, Zhang and Ge. Third, we show that (1) is not tight for r=3$$r = 3$$, namely that ex(n,Ks,t(3))=Os,t(n3-1s-1-εs)$$\textrm{ex}(n,K_{s,t}^{(3)}) = O_{s,t}(n^{3 - \frac{1}{s-1} - \varepsilon s})$$ (for all s≥3$$s\ge 3$$). This indicates that the behaviour of ex(n,Ks,t(r))$$\textrm{ex}(n,K{s,t}^{(r)})$$ might depend on the parity of r. Lastly, we prove a conjecture of Ergemlidze, Jiang and Methuku on the hypergraph analogue of the bipartite Turán problem for graphs with bounded degrees on one side. Our tools include a novel twist on the dependent random choice method as well as a variant of the celebrated norm graphs constructed by Kollár, Rónyai and Szabó.