One can verify that among the two asymptotic upper bounds of z(m,n;s,t) in the previous section, the first bound is better when m=o(n^{s/t}), and the second bound becomes better when m=\omega(n^{s/t}). Therefore, if one can show a lower bound for z(n^{s/t},n;s,t) that matches the upper bound up to a constant, then by a simple sampling argument (on either an n^{t/s}\times t bipartite graph or an m\times m^{s/t} bipartite graph that achieves the maximum edge number), we can show that for all m,n, one of the above two upper bounds is tight up to a constant. This leads to the following question: is it the case that for any fixed s\leq t and m\leq n^{s/t}, we have :z(m,n;s,t)=\Omega(mn^{1-1/s})? In the special case m=n, up to constant factors, z(n,n;s,t) has the same order as \text{ex}(n,K_{s,t}), the maximum number of edges in an n-vertex (not necessarily bipartite) graph that has no K_{s,t} as a subgraph. In one direction, a bipartite graph with n vertices on each side and z(n,n;s,t) edges must have a subgraph with n vertices and at least z(n,n;s,t)/4 edges; this can be seen from choosing n/2 vertices uniformly at random from each side, and taking the expectation. In the other direction, we can transform a graph with n vertices and no copy of K_{s,t} into a bipartite graph with n vertices on each side of its bipartition, twice as many edges and still no copy of K_{s,t}, by taking its
bipartite double cover. Same as above, with the convention that s\leq t, it has been conjectured that :z(n,n;s,t)=\Theta(n^{2-1/s}) for all constant values of s,t. For some specific values of s,t (e.g., for t sufficiently larger than s, or for s=2), the above statements have been proved using various algebraic and random algebraic constructions. At the same time, the answer to the general question is still unknown to us.
Incidence graphs in finite geometry gives rise to the
Heawood graph, a bipartite graph with seven vertices on each side, 21 edges, and no 4-cycles. For s=t=2, a bipartite graph with n vertices on each side, \Omega(n^{3/2}) edges, and no K_{2,2} may be obtained as the
Levi graph, or point-line incidence graph, of a
projective plane of order q, a system of q^2+q+1 points and q^2+q+1 lines in which each two points determine a unique line, and each two lines intersect at a unique point. We construct a bipartite graph associated to this projective plane that has one vertex part as its points, the other vertex part as its lines, such that a point and a line is connected if and only if they are incident in the projective plane. This leads to a K_{2,2}-free graph with q^2+q+1 vertices and (q^2+q+1)(q+1) edges. Since this lower bound matches the upper bound given by I. Reiman, we have the asymptotic :z(n;2)=(1/2+o(1))n^{3/2}. For s=t=3, bipartite graphs with n vertices on each side, \Omega(n^{5/3}) edges, and no K_{3,3} may again be constructed from finite geometry, by letting the vertices represent points and spheres (of a carefully chosen fixed radius) in a three-dimensional finite
affine space, and letting the edges represent point-sphere incidences. More generally, consider s=2 and any t. Let \mathbb F_q be the q-element finite field, and h be an element of multiplicative order t, in the sense that H=\{1,h,\dots, h^{t-1}\} form a t-element subgroup of the multiplicative group \mathbb F_q^*. We say that two nonzero elements (a,b),(a',b')\in\mathbb F_q\times \mathbb F_q are equivalent if we have a'=h^da and b'=h^db for some d. Consider a graph G on the set of all equivalence classes \langle a,b\rangle, such that \langle a,b\rangle and \langle x,y\rangle are connected if and only if ax+by\in H. One can verify that G is well-defined and free of K_{2,t+1}, and every vertex in G has degree q or q-1. Hence we have the upper bound :z(n,n;2,t+1)=(t^{1/2}+o(1))n^{3/2}.
Norm graphs and projective norm graphs For t sufficiently larger than s, the above conjecture z(n,n;s,t)=\Theta(n^{2-1/s}) was verified by Kollár, Rónyai, and Szabó and Alon, Rónyai, and Szabó using the construction of norm graphs and projective norm graphs over finite fields. For t>s!, consider the
norm graph NormGraphp,s with vertex set \mathbb F_{p^s}, such that every two vertices a,b\in\mathbb F_{p^s} are connected if and only if N(a+b)=1, where N\colon\mathbb F_{p^s}\rightarrow\mathbb F_p is the
norm map :N(x)=x\cdot x^p\cdot x^{p^2}\cdots x^{p^{s-1}}=x^{(p^s-1)/(p-1)}. It is not hard to verify that the graph has p^s vertices and at least p^{2s-1}/2 edges. To see that this graph is K_{s,s!+1}-free, observe that any common neighbor x of s vertices y_1,\ldots,y_s\in\mathbb F_{p^s} must satisfy :1=N(x+y_i)=(x+y_i)\cdot (x+y_i)^p\cdots (x+y_i)^{p^{s-1}}=(x+y_i)\cdot (x^p+y_i^p)\cdots (x^{p^{s-1}}+y_i^{p^{s-1}}) for all i=1,\ldots,s, which a system of equations that has at most s! solutions. The same result can be proved for all t>(s-1)! using the
projective norm graph, a construction slightly stronger than the above. The projective norm graph ProjNormGraphp,s is the graph on vertex set \mathbb F_{p^{s-1}}\times \mathbb F_p^\times, such that two vertices (X,x),(Y,y) are adjacent if and only if N(X+Y)=xy, where N\colon\mathbb F_{p^s}\rightarrow\mathbb F_p is the norm map defined by N(x)=x^{(p^s-1)/(p-1)}. By a similar argument to the above, one can verify that it is a K_{s,t} -free graph with \Omega(n^{2-1/s}) edges. The above norm graph approach also gives tight lower bounds on z(m,n;s,t) for certain choices of m,n. proved a tight lower bound on z(m,n;2,t) for arbitrary t: if m=(1+o(1))n^{t/2}, then we have :z(m,n;2,t)=(1+o(1))mn^{1/2}. For 2\leq t\leq n, we say that a collection of subsets A_1,\dots,A_\ell\subset[n] is a
clique partition of H\subset {[n]\choose t} if \bigcup_{i=1}^\ell{A_i\choose t} form a partition of H. Observe that for any k, if there exists some H\subset{[n]\choose t} of size (1-o(1)){n\choose t} and m=(1+o(1)){n\choose t}/{k\choose t}, such that there is a partition of H into m cliques of size k, then we have z(m,n;2,t)=km. Indeed, supposing A_1,\dots,A_m\subset[n] is a partition of H into m cliques of size k, we can let G be the m\times n bipartite graph with V_1=\{A_1,\dots,A_m\} and V_2=[n], such that A_i\sim v in G if and only if v\in A_i. Since the A_i form a clique partition, G cannot contain a copy of K_{2,t}. It remains to show that such a clique partition exists for any m=(1+o(1))n^{t/2}. To show this, let \mathbb F_q be the finite field of size q and V=\mathbb F_q\times \mathbb F_q. For every polynomial p(\cdot) of degree at most t-1 over \mathbb F_q, define C_p=\{(x,p(x)):x\in\mathbb F_q\}\subset V. Let \mathcal C be the collection of all C_p, so that |\mathcal C|=q^t=n^{t/2} and every C_p has size q=\sqrt{n}. Clearly no two members of \mathcal C can share t members. Since the only t-sets in V that do not belong to H are those that have at least two points sharing the same first coordinate, we know that almost all t-subsets of V are contained in some C_p.
Randomized algebraic constructions Alternative proofs of \text{ex}(n,K_{s,t})=\Omega(n^{2-1/s}) for t sufficiently larger than s were also given by Blagojević, Bukh and Karasev and by Bukh using the method of random algebraic constructions. The basic idea is to take a random polynomial f:\mathbb F_q^s\times \mathbb F_q^s\rightarrow \mathbb F_q and consider the graph G between two copies of \mathbb F_q^s whose edges are all those pairs (x,y) such that f(x,y) = 0. To start with, let q be a prime power and n=q^2. Let :f\in\mathbb F_q[x_1,\dots,x_s,y_1,\dots,t_s]_{\leq s^2} be a random polynomial with degree at most s^2 in X=(x_1,\dots,x_s), degree at most s^2 in Y=(y_1,\dots,y_s), and furthermore satisfying f(X,Y)=f(Y,X) for all X,Y. Let G be the associated random graph on vertex set \mathbb F_q^s, such that two vertices x and y are adjacent if and only if f(x,y)=0. To prove the asymptotic lower bound, it suffices to show that the expected number of edges in G is \Omega(q^{2s-1}). For every s-subset U\subset\mathbb F_q^s, we let Z_U denote the vertex subset of \mathbb F_q^s\setminus U that "vanishes on f(\cdot,U)": :Z_U=\{x\in \mathbb F_q^s\setminus U:f(x,u)=0\text{ for all }u\in U\}. Using the Lang-Weil bound for polynomials f(\cdot,u) in \mathbb F_q^s, we can deduce that one always has Z_U\leq C or Z_U> q/2 for some large constant C, which implies :\mathbb P(|Z_U|>C)=\mathbb P(|Z_U|>q/2). Since f is chosen randomly over \mathbb F_q, it is not hard to show that the right-hand side probability is small, so the expected number of s-subsets U with |Z_U|>C also turned out to be small. If we remove a vertex from every such U, then the resulting graph is K_{s,C+1} free, and the expected number of remaining edges is still large. This finishes the proof that \text{ex}(n,K_{s,t})=\Omega(n^{2-1/s}) for all t sufficiently large with respect to s. More recently, there have been a number of results verifying the conjecture z(m,n;s,t)=\Omega(n^{2-1/s}) for different values of s,t, using similar ideas but with more tools from algebraic geometry. ==Applications==