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 Erdos-Simonovits-Stone 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^{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.
|