Maximum number of edges in a bipartite graph without $K_{s,t}$

Question

I want to prove the lower and upper bound

2ex(n,$K_{s,t}$) $\le$ z(n,s,t) $\le$ ex(2n,$K_{s,t}$)

of the maximum number of edges in a bipartite graph that does not contain a $K_{s,t}$.

I have found out that this is called the Zarankiewicz problem and but I have no idea how I can prove these boundaries. Can anybody help?

Answer 1

By definition

• $z(n;s,t)$ is the maximum number of edges in a $K_{s,t}$-free subgraph of $K_{n,n}$;
• $\text{ex}(n,K_{s,t})$ is the maximum number of edges in a $K_{s,t}$-free graph on $n$ vertices.

For the upper bound: a $K_{s,t}$-free subgraph of $K_{n,n}$ is in particular a $K_{s,t}$-free graph on $2n$ vertices. So it has at most $\text{ex}(2n, K_{s,t})$ edges.

For the lower bound: given any $K_{s,t}$-free graph $G$ on $n$ vertices, let $H$ be its bipartite double cover. That is, if $G$ has vertices $\{v_1, \dots, v_n\}$, then $H$ has vertices $\{u_1, \dots, u_n, w_1, \dots, w_n\}$, with two edges $u_iw_j$ and $u_j w_i$ for every edge $v_iv_j$ in $G$.

Then $H$ is a subgraph of $K_{n,n}$ (all its edges join $\{u_1, \dots, u_n\}$ to $\{w_1, \dots, w_n\}$) and $K_{s,t}$-free: if vertices $\{u_{i_1}, \dots, u_{i_s}, w_{j_1}, \dots, w_{j_t}\}$ form a $K_{s,t}$ in $H$, then vertices $\{v_{i_1}, \dots, v_{i_s}, v_{j_1}, \dots, v_{j_t}\}$ form a $K_{s,t}$ in $G$. We conclude that $|E(H)| \le z(n;s,t)$.

But $|E(G)| = \frac12|E(H)|$, so $|E(G)| \le \frac12 z(n;s,t)$. Since this is true for any $K_{s,t}$-free graph $G$ on $n$ vertices, we conclude $\text{ex}(n,K_{s,t}) \le \frac12 z(n;s,t)$, giving us the lower bound.