The Zarankiewicz problem in 3-partite graphs

Abstract

Let $F$ be a graph, $k\ge 2$ be an integer, and write ${\mathrm{ex}}_{\chi \le k}(n,F)$ for the maximum number of edges in an $n$-vertex graph that is $k$-partite and has no subgraph isomorphic to $F$. The function ${\mathrm{ex}}_{\chi \le 2}(n,F)$ has been studied by many researchers. Finding ${\mathrm{ex}}_{\chi \le 2}(n,K_{s,t})$ is a special case of the Zarankiewicz problem. We prove an analogue of the Kövári-Sós-Turán Theorem for 3-partite graphs by showing \[ \mathrm{ex}_{ χ\leq 3} (n , K_{s,t} ) \leq \left( \frac{1}{3} \right)^{1 - 1/s} \left( \frac{ t - 1}{2} + o(1) \right)^{1/s} n^{2 - 1/s} \] for $2\le s\le t$. Using Sidon sets constructed by Bose and Chowla, we prove that this upper bound is asymptotically best possible in the case that $s=2$ and $t\ge 3$ is odd, i.e., ${\mathrm{ex}}_{\chi \le 3}(n,K_{2,2t+1})=\sqrt{\frac{t}{3}}{n}^{3/2}+o(n^{3/2})$ for $t\ge 1$. In the cases of $K_{2,t}$ and $K_{3,3}$, we use a result of Allen, Keevash, Sudakov, and Verstraëte, to show that a similar upper bound holds for all $k\ge 3$, and gives a better constant when $s=t=3$. Lastly, we point out an interesting connection between difference families from design theory and ${\mathrm{ex}}_{\chi \le 3}(n,C_4)$.

arXiv commentTo appear in Journal of Combinatorial Designs