Lower bound for Turán number for bipartite nondegenerate graphs
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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 ErdosSimonovitsStone Theorem [1] can be used to determine \( t(n, G)\) asymptotically:
This result was further strengthened by Bollobás, Erdos, and Simonovits[2], and Chvátal and Szemerédi [3] as follows:
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^{21/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), 5157.

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, 219224.

3  V. Chvátal and E. Szemerédi. On the ErdosStone theorem. Journal of London Math. Soc. Ser. 2, 23 (1981), 207214.

4 
P. Erdös and M. Simonovits,
Cubesupersaturated graphs and related problems, Progress in graph theory (Waterloo, Ont., 1982), 203218,
Academic Press, Toronto, 1984.
