Let $F$ be a graph, $k \geq 2$ be an integer, and write $\mathrm{ ex}_{ \chi \leq 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 \leq 2} ( n , F)$ has been studied by many researchers. Finding $\mathrm{ ex}_{ \chi \leq 2} (n , K_{ s,t})$ is a special case of the Zarankiewicz problem. We prove an analogue of the K\"{ o}v\'{ a}ri-S\'{ o}s-Tur\'{ a}n Theorem for 3-partite graphs by showing \[ \mathrm{ ex}_{ \chi \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 \leq s \leq 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 \geq 3$ is odd, i.e., $\mathrm{ ex}_{ \chi \leq 3} ( n , K_{ 2,2t+1} ) = \sqrt{ \frac{ t}{ 3}} n^{ 3/2} + o(n^{ 3/2})$ for $t \geq 1$. In the cases of $K_{ 2,t}$ and $K_{ 3,3}$, we use a result of Allen, Keevash, Sudakov, and Verstra\"{ e}te, to show that a similar upper bound holds for all $k \geq 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 \leq 3 } (n ,C_4)$.

Categories: math.CO

The Zarankiewicz problem in 3-partite graphs