Turán number for bipartite graphs is a rational power of n
Home
Search
Subjects
About Erdös
About This Site
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:
Theorem 1 (The ErdosSimonovitsStone 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 problems were proposed in [4].
Conjecture
For all rationals \(1<\frac{p}{q}<2\), there exists a bipartite graph \(G\) such that \(t(n, G)=\Theta(n^{p/q})\).
Problem
Given a bipartite graph \(G\), does there exist a rational exponent \(r=r(G)\) such that \(t(n, G)=\Theta(n^r)\)?
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.
