Lower bound for Turán number for \(K_{4,4}\)
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
Please see The Turan number of \( K_{r, r}\) for additional information about this problem and its background. This is a special case of the Zarankiewicz problem[1]. The Zarankiewicz problem in general is the following:
Problem
What is the largest integer \(m\) such that there is a graph \(G\) on \(n\) vertices with \(m\) edges such that \(K_{r, r}\) is not a subgraph of \(G\)? We denote this integer \(m\) by \(t(n, K_{r, r})\)?For \( t(n,K_{4,4})\), it is only known that \( t(n,K_{4,4}) \geq t(n,K_{3,3}) \geq c n^{5/3}\).
Problem
Is it true that\[ \frac{t(n,K_{4,4})}{n^{5/3}} \rightarrow \infty ?\]The best known lower bound for \( t(n,K_{r,r})\) is of the order \( O( n^{2-2/(r+1)})\), which can be proved by the following deletion method[2] from probabilistic combinatorics.
Suppose that we consider a random subgraph \( G\) in which each edge is chosen with probability \( \rho\). The expected number of \( K_{r, r}\) in \( G\) is \( \rho^{r^2} \binom{n}{2r} \binom{2r}{r}\). For each copy of \( K_{r, r}\), we delete an edge. Then the remaining graph contains no \( K_{r, r}\) and has at least
\begin{equation*} \rho \binom{n}{2} - \rho^{r^2} \binom{n}{2r} \binom{2r}{r} > \frac 1 2 \rho \binom{n}{2} \end{equation*}edges if \( \rho \leq n^{-2/(r+1)}\). This implies that \( t(n,K_{r,r}) \geq c n^{2-2/(r+1)}\).
Bibliography | |
---|---|
1 | K. Zarankiewicz,
Problem P 101, Colloq. Math. 2 (1951), 116-131.
|
2 |
P. Erdös and J. H. Spencer, Probabilistic Methods in
Combinatorics, Probability and Mathematical Statistics, Vol. 17,
Academic Press,
New York, 1974.
|