# Upper bound for Turán number for bipartite 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) \binom{n}{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) \binom{n}{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. For $$G$$ a graph, we say $$G$$ is $$r$$-degenerate if every induced subgraph of $$G$$ has a vertex of degree at most $$r$$. We have the following conjecture, proposed by Erdos and Simonovits[4] in 1984:

# Conjecture on the Turán number for bipartite degenerate graphs (\$100)

If $$G$$ is a bipartite $$r$$-degenerate graph, then the Turán number for $$G$$ satisfies $t(n, G)=O(n^{2-1/r}).$

In 2003, Alon, Krivelevich and Sudakov[5] proved that there exists a universal constant $$c$$ so that for every $$r$$-degenerate bipartite graph $$G$$, $$t(n, G)=O(n^{2-c/r})$$. Moreover, Alon, Krivelevich and Sudakov prove that if $$G$$ is a bipartite graph wherein the maximum degree in one partite set is $$r$$, then $$t(n, G)\leq cn^{2-1/r}$$ for some universal constant $$c$$.

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.

5 N. Alon, M. Krivelevich, and B. Sudakov. Turán numbers of bipartite graphs and related Ramsey-type questions. Combinatorics, Probability and Computing 12 (2003), 477-494.