Upper bound for Turán number for bipartite degenerate 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. 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^{21/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^{2c/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^{21/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), 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.

5  N. Alon, M. Krivelevich, and B. Sudakov. Turán numbers of bipartite graphs and related Ramseytype questions. Combinatorics, Probability and Computing 12 (2003), 477494.
