Lower bound for Turán number for bipartite non-degenerate graphs

Let \( G\) be a graph. We define the Turán number \( t(n, G)\) to be the minimum integer \( m\) so that there exists a graph on \( n\) vertices with \( m\) edges without \( G\) as a subgraph.

For a general graph \( G\) with chromatic number \( \chi(G)\geq 3\), the Erdos-Simonovits-Stone Theorem [1] can be used to determine \( t(n, G)\) asymptotically:

Theorem 1 (The Erdos-Simonovits-Stone Theorem)   For a graph \( G\) with chromatic number \( \chi(G)\geq 3\), the Turán number \( t(n, G)\) satisfies

\(\displaystyle t(n,G) \geq \left(1- \frac{1}{\chi(G) -1}\right) {n\choose 2} + o(n^2) \)

This result was further strengthened by Bollobás, Erdos, and Simonovits[2], and Chvátal and Szemerédi [3] as follows:

Theorem 2   For any \( \epsilon >0\), a graph with

\(\displaystyle \left(1-\frac{1}{p}+\epsilon\right) {n\choose 2} \)

edges must contain a complete \( (p+1)\)-partite graph with each part consisting of \( m\) vertices where

\(\displaystyle m > c \frac{\log n}{ \log 1/\epsilon}. \)

The only case that has eluded the power of the above theorems is the case where \( \chi(G)=2\), that is when \( G\) is a bipartite graph. The following problem was proposed in [4].

Conjecture

If a bipartite graph \(G\) contains a subgraph \(H\) with minimum degree at least \(r+1\), then there exists \(\epsilon>0\) and \(c>0\), such that \[t(n, G)\geq cn^{2-1/r+\epsilon}.\]

We note that this problem is similar to Erdos and Simonovits' conjecture on the Turán number for bipartite degenerate graphs[4]. Little to no progress has been made on addressing the Turán number of these nondegenerate bipartite graphs since the problem was posed, despite some progress on the degenerate case.

Bibliography
1 P. Erdos and M. Simonovits. A limit theorem in graph theory. Studia Sci. Math. Hungar. 1 (1966), 51-57.

2 B. Bollobás, P. Erdos and M. Simonovits. On the structure of edge graphs, II. J. London Math. Soc. (2) 12 (1975/76) no.2, 219-224.

3 V. Chvátal and E. Szemerédi. On the Erdos-Stone theorem. Journal of London Math. Soc. Ser. 2, 23 (1981), 207-214.

4 P. Erdös and M. Simonovits, Cube-supersaturated graphs and related problems, Progress in graph theory (Waterloo, Ont., 1982), 203-218, Academic Press, Toronto, 1984.