$K_{2, t+1}$-free graphs containing an optimal number of $K_{t, t}$'s

Resumen Técnico: Grafos libres de $K_{2,t+1}$ que contienen un número óptimo de $K_{t,t}$

Planteamiento del Problema
El artículo aborda el número de Turán generalizado, denotado como $\text{ex}(n, H, F)$, que representa el número máximo de copias de un grafo $H$ que pueden existir en un grafo libre de $F$ con $n$ vértices. Específicamente, los autores investigan el caso donde $H = K_{t,t}$ y $F = K_{2,t+1}$. El objetivo es determinar el comportamiento asintótico de $\text{ex}(n, K_{t,t}, K_{2,t+1})$.

Si bien el trabajo reciente de Pohoata, Tidor y Yu estableció que $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ para todos los enteros $t \ge 3$, su prueba dependía de métodos probabilísticos y conjuntos evasivos de subespacios, produciendo una cota inferior con un coeficiente que no era necesariamente óptimo. Este artículo busca proporcionar una fórmula asintótica precisa para valores específicos de $n$ y $t$ utilizando una construcción explícita.

Metodología
Los autores emplean una construcción determinista y algebraica de grafos basada en cuerpos finitos y polinomios linealizados.

1. Construcción del Grafo ($\Gamma_{t,e}$):

   • Sea $t$ una potencia de un primo y $e > 1$ un entero. Defina $q = t^e$.
   • Sea $L$ un polinomio $\mathbb{F}_t$-linealizado sobre $\mathbb{F}_q[x]$ tal que la dimensión de su núcleo es 1. El espacio de la imagen $R_L$ tiene tamaño $t^{e-1}$.
   • El conjunto de vértices se define como $V = \mathbb{F}_q \times R_L$, lo que resulta en $n = q \cdot t^{e-1} = t^{2e-1}$ vértices.
   • Dos vértices distintos $(v_1, v_2)$ y $(w_1, w_2)$ son adyacentes si y solo si $v_2 + w_2 = L(v_1 w_1)$. Los bucles propios implicados por la ecuación se eliminan para asegurar un grafo simple.

2. Derivación de la Cota Superior:

   • Los autores primero establecen una cota superior precisa para $\text{ex}(n, K_{t,t}, K_{2,t+1})$.
   • El argumento se basa en el hecho de que en un grafo libre de $K_{2,t+1}$, cualquier par de vértices comparte como máximo $t$ vecinos comunes.
   • Al contar pares de vértices y analizar cuántas veces se cuenta un $K_{t,t}$ a través de sus pares constituyentes, derivan la cota:
     $$\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$$

3. Análisis Estructural de la Construcción:

   • Libertad de $K_{2,t+1}$: Los autores demuestran que $\Gamma_{t,e}$ no contiene un $K_{2,t+1}$. Para cualquier par de vértices, el número de vecinos comunes está determinado por el número de soluciones a una ecuación lineal involucrando a $L$. Dado que $L$ es un mapeo $t$-a-1, hay como máximo $t$ vecinos comunes.
   • Formación de $K_{t,t}$: El núcleo de la prueba implica analizar vértices no adyacentes. Los autores muestran que cualquier par de vértices no adyacentes con distintas primeras coordenadas define unánimemente dos conjuntos, $M$ y $N$, de cardinalidad $t$.
     • $N$ es el conjunto de vecinos comunes (una línea $\mathbb{F}_t$).
     • $M$ es la línea $\mathbb{F}_t$ que contiene a los dos vértices.
     • Cada vértice en $M$ es algebraicamente adyacente a cada vértice en $N$.
   • Si $M \cap N = \emptyset$, el subgrafo inducido por $M \cup N$ es un $K_{t,t}$. Si $|M \cap N| = 1$, la estructura forma un grafo completo tripartito $K_{1, t-1, t-1}$.

Contribuciones Principales y Resultados
La contribución principal es la construcción explícita de una familia de grafos que alcanza la cota superior teórica para el número de copias de $K_{t,t}$, módulo términos de orden inferior, para un conjunto infinito de $n$.

• Teorema 1.1: Para $t$ siendo una potencia de un primo y $n = t^{2e-1}$ (donde $e > 1$ es un entero), el número de Turán generalizado satisface:
  $$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
• Comparación con Cotes Previas: El artículo señala que la mejor cota inferior previa de [5] era de la forma $(1-o(1)) \frac{n^2}{4t^2 t!}$. El nuevo resultado mejora este coeficiente significativamente para potencias de primos $t > 5$.
• Negligibilidad de Casos No Óptimos: Los autores demuestran que el número de configuraciones que resultan en $K_{1, t-1, t-1}$ (donde $|M \cap N| = 1$) es despreciable ($O(n)$) comparado con el conteo total de $K_{t,t}$ ($O(n^2)$), asegurando la dominancia asintótica del conteo de $K_{t,t}$.

Significancia y Reivindicaciones
El artículo afirma proporcionar una "construcción simple y completamente explícita" para un conjunto infinito, aunque disperso, de $n$'s, contrastando con las pruebas de existencia probabilísticas previamente disponibles. La construcción es isomórfica a los grafos estudiados previamente por Lazebnik y Mubayi en el contexto de números de Ramsey multicolores, aunque este artículo los aplica específicamente al problema de Turán generalizado.

Los autores concluyen conjeturando que la cota superior derivada es ajustada para todo $n$, no solo para los casos específicos de potencias de primos construidos:
$$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
El trabajo sirve para refinar la comprensión de la tasa de crecimiento de los números de Turán generalizados para grafos bipartitos, pasando de estimaciones de orden de magnitud a constantes asintóticas precisas para regímenes específicos.