Estimaciones de densidad de aristas del tipo del teorema de Erdős-Stone para grafos bipartitos?

Question

La teoría del teorema de Erdos-Stone dice que el grafo más denso que no contiene un grafo H (que tiene número cromático r) tiene un número de aristas igual a $(r-2)/(r-1) {n \choose 2}$ asintóticamente.

Sin embargo, esto no dice mucho para los grafos bipartitos (ya que r=2). Quería saber cuáles son los mejores resultados conocidos para los grafos más densos que no contienen un determinado grafo bipartito H. Supongo que este problema sigue abierto y no se ha resuelto del todo.

Este problema es fácil si H es un bosque, ya que todo gráfico con $|E| > k|V|$ contiene cada bosque en k vértices como un subgrafo. Para los ciclos pares, sé que hay un resultado de Bondy y Simonovits que dice:

"si $|E| \geq 100k|V|^{1+1/k}$ entonces G contiene un $C_{2l}$ por cada $l$ en $[k, n^{1/k}]$ ."

Entonces, ¿alguien puede indicarme los resultados más conocidos ahora para los grafos cíclicos bipartitos?

Answer 1

Dejemos que $ex(n, H)$ denotan el número máximo de aristas de un gráfico en $n$ vértices que no contienen una copia de $H$ . Los límites exactos ya son difíciles si se prohíbe completa gráficos bipartitos $K_{m,n}$ .

Erdös, Rényi, Sós (1954) demostraron que $$ex(n,K_{2,2}) \sim \frac{1}{2}n^{3/2}.$$

Según el clásico Teorema de Kövári-Sós-Turán (1954), $$ex(n,K_{t,s}) \leq c_{s,t} n^{2-\frac{1}{t}}$$ para $s\geq t\geq 2$ , mientras que una construcción aleatoria da el límite inferior $$ex(n,K_{t,s})\geq cn^{2-\frac{s+t-2}{st-1}}.$$

Brown (1966) demostró que Kövári-Sós-Turán es ajustado para $s=t=3$ : $$ex(n,K_{3,3}) \geq cn^{2-\frac{1}{3}},$$ y Füredi (1996) demostraron que la constante en la construcción de Brown es óptima, dando $$ex(n,K_{3,3}) \sim \frac{1}{2}n^{2-\frac{1}{3}}.$$

Alon, Kollár, Rónyai, Szabó (1995, 1999) demostraron que para cada $t\geq 2$ existe $c_t>0$ tal que para todo $s\geq(t-1)!+1$ , $$ex(n,K_{t,s}) \geq c_tn^{2-\frac{1}{t}},$$ coincidiendo así con Kövári-Sós-Turán asintóticamente.

No estoy seguro de que se haya encontrado una construcción que coincida con Kövári-Sós-Turán para el caso $K_{4,4}$ . También deben conocerse más cosas de las que se mencionan aquí. Pero como se puede ver, se sabe algo más que un poco más, aunque las lagunas en nuestro conocimiento siguen siendo enormes aquí.

Answer 2

Para añadir a la respuesta de Konrad:

No se conoce ninguna construcción para $K_{4,4}$ . Tampoco hay una construcción para $C_{2k}$ para k distintos de 2,3,5. Existe una construcción de Lazebnik y Woldar que supera el probabilístico para $C_{2k}$ Sin embargo. Existen algunos límites superiores no triviales en grafos bipartitos de grado acotado y (más generalmente) de degeneración acotada. Estos límites superiores (y algunas referencias) se pueden encontrar en el encuesta sobre la elección aleatoria dependiente por Fox y Sudakov.

Answer 3

El artículo de la wikipedia dice que Para grafos bipartitos generalizados H el teorema de Erdos-Stone da ex(n,H) = o(n^2) "y para grafos bipartitos generales poco más se sabe" ver

http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem

así que por lo que veo tienes razón en que este problema sigue abierto.