Turán number for complete balanced bipartite graphs

The following problem was proposed not by Erdos but by Zarankiewicz[1] in 1951.

Problem

What is the largest integer \(m\) such that there is a graph \(G\) on \(n\) vertices and \(m\) edges which does not contain \(K_{r,r}\) as a graph?
In other words, determine \(t(n,K_{r,r})\).

This long-standing problem is also known as the problem of Zarankiewicz. Kövári, Sós and Turán [2] gave an upper bound for \( t(n,K_{r,s})\) in 1954. Namely, for \( 2 \leq r \leq s\),

\begin{equation} t(n,K_{r,s}) < c s^{1/r} n^{2-1/r} +O(n) \end{equation}

There is a footnote in the paper, mentioning that Erdos also proved this upper bound independently.

The proof of (1) is by the following counting argument:

Suppose a graph \( G\) has \( m\) edges and has degree sequence \( d_1, \ldots, d_n\). The number of copies of stars \( S_r\) in \( G\) is exactly

\(\displaystyle \displaystyle\sum_i \binom{d_i}{r} . \)

Therefore, there is at least one copy of \( K_{r,t}\) contained in \( G\) if

\begin{equation*} \frac{ \displaystyle\sum_i \binom{d_i}{r}}{\binom{n}{r}} \geq \frac{ n \binom{m/n}{r}}{\binom{n}{r}} > s \end{equation*}

which holds if \( m \geq c s^{1/r} n^{2-1/r}\) for some appropriate constant \( c\) (which depends on \( r\) but is independent of \( n\)). This implies (1).

Conjecture on the Turán number for complete bipartite graphs:

Prove that for \(r \geq 4\), \[ t(n,K_{r,r}) > c n^{2-1/r} \] where \(c\) is a constant depending on \(r\) (but independent of \(n\)).

The above conjecture is only known to be true for \( r=2\) [3]) and \( 3\) [4] and unknown for \( r \geq 4\). Here we describe the following constructions of \( C_4\)-free and \( K_{3,3}\)-free graphs.

The construction of \( C_4\)-free graphs by Erdos, Rényi and Sós [3]

Let \( G_n\) be a graph with vertices \( (x,y)\), where \( x,y \) are distinct residues modulo \( p\) for a prime \( p\). Two vertices \( (a,b)\) and \( (x,y)\) are adjacent if \( ax+by=1\). The graph \( G_n\) has \( \frac{1}{2}p(p-1)\) edges, and \( n=p^2\) vertices, since for given \( (a,b)\) there are \( p\) solutions to \( ax+by=1\). If \( G_n\) has a \( 4\)-cycle with vertices \( (a,b),(u,v),(a',b'), (u',v')\), then the system of equations

\(\displaystyle \left\{\begin{array}{l} ax+by=1 a'x+b'y=1\end{array}\right.\)

would have two solutions, which is impossible.

The construction of \( K_{3,3}\)-free graphs by W. G. Brown [4]

Let \( B_n\) be a graph where vertices are triples \( (x,y,z)\), where \( x,y,z \) are distinct residues modulo \( p\) for a prime \( p\). Two vertices \( (a,b,c)\) and \( (x,y,z)\) are adjacent if \( (a-x)^2+(b-y)^2+(c-z)^2=1\). The graph \( B_n\) has \( (\frac{1}{2}+o(1))n^{5/3}\) edges, where \( n=p^3\), since for a given triple, the edge-defining equation has \( p^2-p\) solutions. Moreover, \( B_n\) contains no \( K_{3,3}\), as there are at most two points in \( 3\)-space equidistant from three points not on a circle.

For \( t(n,K_{4,4})\), it is only known that \( t(n,K_{4,4}) \geq t(n,K_{3,3}) \geq c n^{5/3}\).

Problem

Is it true that \[ \frac{t(n,K_{4,4})}{n^{5/3}} \rightarrow \infty ?\]

The best known lower bound for \( t(n,K_{r,r})\) is of the order \( O( n^{2-2/(r+1)})\), which can be proved by the following deletion method[5] from probabilistic combinatorics.

Suppose that we consider a random subgraph \( G\) in which each edge is chosen with probability \( \rho\). The expected number of \( K_{r,r}\) in \( G\) is \( \rho^{r^2} \binom{n}{2r} \binom{2r}{r}\). For each copy of \( K_{r,r}\), we delete an edge. Then the remaining graph contains no \( K_{r,r}\) and has at least

\begin{equation*} \rho \binom{n}{2} - \rho^{r^2} \binom{n}{2r} \binom{2r}{r} > \frac{1}{2} \rho \binom{n}{2} \end{equation*}

edges if \( \rho \leq n^{-2/(r+1)}\). This implies that \( t(n,K_{r,r}) \geq c n^{2-2/(r+1)}\).

We now consider \( t(n,K_{r,s})\) where \( r\neq s\). For the case of \( r=2\), the bound in \( [2]\) implies

\(\displaystyle t(n, K_{2,t+1}) \leq \frac{1}{2} \sqrt{t} n^{3/2} + \frac{n}{4} . \)

For the lower bound , Füredi [6] extended the construction of Erdos, Rényi and Sós and proved

\(\displaystyle r(n,K_{2,t+1}) \geq \frac 1 2 \sqrt t n^{3/2} +O(n^{4/3}) \)

for \( n\) sufficiently large.

In 1996, Kollár, Rónyai and Szabó [7] showed that \( t(n,K_{r,s})> c n^{2- 1/r}\) if \( r \geq 4\) and \( s \geq r!+1\).

Recently, spectral methods have also been used to approach this problem. In 2009, Babai and Guiduli[8] proved the following theorem:

Theorem 1   Suppose \( G\) contains no subgraph isomorphic to \( K_{r, s}\). Then the spectral radius \( \lambda\) of the adjacency matrix of \( G\) satisfies \( \lambda\leq ((r-1)^{1/s}+o_n(1))n^{1-1/s}\).

As the spectral radius \( \lambda\) satisfies \( \lambda\geq 2E(G)/V(G)\), this result implies the above result of Kövári, Sós and Turán. However, the method used here is independent of the method in [2], suggesting that there one might be able to find an extension of Babai and Guiduli's work to improve the bound.

Bibliography
1 K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951), 116-131.

2 T. Kövári, V. T. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954), 50-57.

3 P. Erdös, R. Rényi and V. T. Sós, On a problem of graph theory, Studia Sci. Math. Hungar. 1 (1966), 215-235.

4 W. G. Brown. On graphs that do not contain a Thomsen graph. Canad. Math. Bull. 9 (1966), 281-285.

5 P. Erdös and J. H. Spencer, Probabilistic Methods in Combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press, New York, 1974.

6 Z. Füredi, On the number of edges of quadrilateral-free graphs, J. Comb. Theory Ser. B 68 (1996), 1-6.

7 J. Kollár, L. Rónyai and T. Szabó, Norm graphs and bipartite Turán numbers, Combinatorica 16 (1996), 399-406.

8 L. Babai and B. Guiduli. Spectral extrema for graphs: the Zarankiewicz problem. Elec. J. of Combin. 16 (2009), R123.