Teorema del circuito par

En la teoría extremal de grafos , el teorema del circuito par es un resultado de Paul Erdős según el cual un grafo de n vértices que no tiene un ciclo simple de longitud 2k solo puede tener O ( n¹ ^{+ 1/ k} ) aristas. Por ejemplo, los grafos sin ciclos de 4 lados tienen O ( n³ ^/2 ) aristas, los grafos sin ciclos de 6 lados tienen O ( n⁴ ^/3 ) aristas, etc.

El resultado fue enunciado sin demostración por Erdős en 1964. ^{[ 1 ]} Bondy y Simonovits (1974) publicaron la primera demostración y reforzaron el teorema para mostrar que, para grafos de n vértices con Ω ( n ^{1 + 1/ k} ) aristas, todas las longitudes de ciclo pares entre 2 k y 2 kn ^{1/ k} ocurren. ^{[ 2 ]}

Problema sin resolver en matemáticas

¿Existen?${\displaystyle 2k}$-gráficos sin ciclos (para${\displaystyle k}$otro que${\displaystyle 2}$,${\displaystyle 3}$, o${\displaystyle 5}$) que tienen${\displaystyle \Omega (n^{1+1/k})}$¿bordes?

Más problemas sin resolver en matemáticas

La cota del teorema de Erdős es ajustada salvo factores constantes para algunos valores pequeños de k : para k = 2, 3 o 5, existen grafos con Ω ( n ^{1 + 1/ k} ) aristas que no tienen 2 k -ciclos. ^{[ 2 ] [ 3 ] [ 4 ]} 

Se desconoce si para k distinto de 2, 3 o 5 existen grafos que no tengan ciclos de 2k pero que tengan Ω ( n1 ^{+ 1/ k} ) aristas, coincidiendo con la cota superior de Erdős. ^{[ 5 ]} Solo se conoce una cota más débil, según la cual el número de aristas puede ser Ω ( n1 ^{+ 2/( 3k − 3)} ) para valores impares de k , o Ω ( n1 ^{+ 2/( 3k − 4)} ) para valores pares de k . ^{[ 4 ]}

Dado que un 4-ciclo es un grafo bipartito completo , el número máximo de aristas en un grafo libre de 4-ciclos puede considerarse un caso especial del problema de Zarankiewicz sobre grafos bipartitos completos prohibidos, y el teorema del circuito par para este caso puede considerarse un caso especial del teorema de Kővári-Sós-Turán. Más precisamente, en este caso se sabe que el número máximo de aristas en un grafo libre de 4-ciclos es

${\displaystyle n^{3/2}\left({\frac {1}{2}}+o(1)\right).}$

Erdős y Simonovits (1982) conjeturaron que, de forma más general, el número máximo de aristas en un grafo 2k -libre de ciclos es

${\displaystyle n^{1+1/k}\left({\frac {1}{2}}+o(1)\right).}$^{[ 6 ]}

Sin embargo, investigadores posteriores descubrieron que existen grafos libres de 6 ciclos y grafos libres de 10 ciclos con un número de aristas mayor por un factor constante que este límite conjeturado, refutando así la conjetura. Más precisamente, el número máximo de aristas en un grafo libre de 6 ciclos se encuentra entre los límites.

${\displaystyle 0.5338n^{4/3}\leq \operatorname {ex} (n,C_{6})\leq 0.6272n^{4/3},}$

donde ex( n , G ) denota el número máximo de aristas en un grafo de n vértices que no tiene ningún subgrafo isomorfo a G . ^{[ 3 ]} El número máximo de aristas en un grafo libre de 10 ciclos puede ser al menos ^{[ 4 ]}

${\displaystyle 4\left({\frac {n}{5}}\right)^{6/5}\approx 0.5798n^{6/5}.}$

Para valores generales de k , Pikhurko demostró la siguiente cota superior.

${\displaystyle \operatorname {ex} (n,C_{2k})\leq (k-1+o(1))n^{1+1/k}.}$^{[ 5 ]}

Bukh y Jiang posteriormente mejoraron la dependencia de k a

${\displaystyle \operatorname {ex} (n,C_{2k})\leq \left(80{\sqrt {k}}\log k+o(1)\right)n^{1+1/k}.}$^{[ 7 ]}

Este límite fue mejorado aún más por Él para

${\displaystyle \operatorname {ex} (n,C_{2k})\leq \left(16{\sqrt {5}}{\sqrt {k\log k}}+o(1)\right)n^{1+1/k}.}$^{[ 8 ]}