New bounds for a hypergraph Bipartite Turán problem

Abstract

Let $t$ be an integer such that $t\ge 2$. Let $K_{2,t}^{(3)}$ denote the triple system consisting of the $2t$ triples $\{a,x_i,y_i\}$, $\{b,x_i,y_i\}$ for $1\le i\le t$, where the elements $a,b,x_1,x_2,\dots ,x_t,$ $y_1,y_2,\dots ,y_t$ are all distinct. Let $ex(n,K_{2,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2,t}^{(3)}$. This function was studied by Mubayi and Verstraëte, where the special case $t=2$ was a problem of Erdős that was studied by various authors. Mubayi and Verstraëte proved that $ex(n,K_{2,t}^{(3)})<t^4\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and that for infinitely many $n$, $ex(n,K_{2,t}^{(3)})\ge \frac{2t-1}{3}\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. These bounds together with a standard argument show that $g(t):={\lim }_{n\to \infty }ex(n,K_{2,t}^{(3)})/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ exists and that \[\frac{2t-1}{3}\leq g(t)\leq t^4.\] Addressing the question of Mubayi and Verstraëte on the growth rate of $g(t)$, we prove that as $t\to \infty$, \[g(t) = Θ(t^{1+o(1)}).\]

17 pages