¿Estimaciones de densidad de borde de tipo Teorema de Erdős-piedra para grafos bipartidos?

Question

El Erdős–Piedra teorema de la teoría dice que la más densa gráfico no contiene una gráfica de H (que ha cromática número r) tiene el número de bordes de igual a $(r-2)/(r-1) {n \choose 2}$ asintóticamente.

Sin embargo, esto no dice mucho, por bipartito gráficos (ya que r=2). Quería saber cuáles son los mejores resultados conocidos para el más denso de los gráficos no contiene un gráfico bipartito H. supongo que este problema sigue abierto y no ha sido completamente resuelto.

Este problema es fácil si H es un bosque, ya que cada gráfico con $|E| > k|V|$ contiene todos los bosques de k vértices como un subgrafo. Incluso para los ciclos, sé que no es 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$$[k, n^{1/k}]$."

Así que puede que alguien me señale a los mejores resultados conocidos ahora por bipartito gráficos cíclicos?

Answer 1

Deje $ex(n, H)$ indicar el número máximo de aristas de un grafo en $n$ vértices no contiene una copia de $H$. Los exactos límites son difíciles ya si prohíbes completa grafos 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}.$$

De acuerdo a la clásica Kövári-Sós-Frigyes Teorema de (1954), $$ex(n,K_{t,s}) \leq c_{s,t} n^{2-\frac{1}{t}}$$ for $s\geq t\geq 2$, mientras que un azar de la construcción da el límite inferior $$ex(n,K_{t,s})\geq cn^{2-\frac{s+t-2}{st-1}}.$$

Brown (1966) mostraron Kövári-Sós-Frigyes es apretado para $s=t=3$: $$ex(n,K_{3,3}) \geq cn^{2-\frac{1}{3}},$$ and Füredi (1996) proved that the constant in Brown's construction is optimal, giving $$ex(n,K_{3,3}) \sim \frac{1}{2}n^{2-\frac{1}{3}}.$$

Alon, Kollár, Rónyai, Szabó (1995, 1999) mostró que, para cada una de las $t\geq 2$ existe $c_t>0$ tal que para todos los $s\geq(t-1)!+1$, $$ex(n,K_{t,s}) \geq c_tn^{2-\frac{1}{t}},$$ mus coincidencia Kövári-Sós-Frigyes asintóticamente.

No estoy seguro de si la construcción de la coincidencia de Kövári-Sós-Frigyes se ha encontrado para el caso de $K_{4,4}$. También debe de ser más conocido de lo que se menciona aquí. Pero como se puede ver, algo más que solo se conoce un poco más, a pesar de las lagunas en nuestros conocimientos son todavía enorme aquí.

Answer 2

Para agregar a Konrad respuesta:

Ningún tipo de construcción es conocida por $K_{4,4}$. Tampoco es una construcción de $C_{2k}$ k otra que 2,3,5. Hay una construcción por Lazebnik y Woldar que late el probabilístico para $C_{2k}$, sin embargo. Hay algunos que no trivial límites superiores en grafos bipartitos de limitada grado y (en general) de la acotada la degeneración. Estos límites superiores (y algunas referencias) pueden ser encontrados en la encuesta sobre la dependiente de una elección al azar por Fox y Sudakov.

Answer 3

El artículo de wikipedia dice que para grafos bipartidos generalizados teorema H Erdos-piedra produce ex(n,H) = o(n^2) "y para general bipartito gráficos poco más se sabe" ver

http://en.wikipedia.org/wiki/ERD%C5%91S%E2%80%93Stone_theorem

así que como puedo ver tienes razón que este problema está todavía abierto.