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

Resumo Técnico: Grafos $K_{2,t+1}$-livres que Contêm um Número Ótimo de $K_{t,t}$s

Enunciado do Problema
O artigo aborda o número de Turán generalizado, denotado por $\text{ex}(n, H, F)$, que representa o número máximo de cópias de um grafo $H$ que podem existir em um grafo livre de $F$ com $n$ vértices. Especificamente, os autores investigam o caso onde $H = K_{t,t}$ e $F = K_{2,t+1}$. O objetivo é determinar o comportamento assintótico de $\text{ex}(n, K_{t,t}, K_{2,t+1})$.

Embora o trabalho recente de Pohoata, Tidor e Yu tenha estabelecido que $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ para todos os inteiros $t \ge 3$, sua prova baseou-se em métodos probabilísticos e conjuntos evasivos de subespaços, produzindo um limite inferior com um coeficiente que não era necessariamente ótimo. Este artigo busca fornecer uma fórmula assintótica precisa para valores específicos de $n$ e $t$ usando uma construção explícita.

Metodologia
Os autores empregam uma construção determinística e algébrica de grafos baseada em corpos finitos e polinômios linearizados.

1. Construção do Grafo ($\Gamma_{t,e}$):

   • Seja $t$ uma potência de primo e $e > 1$ um inteiro. Defina $q = t^e$.
   • Seja $L$ um polinômio $\mathbb{F}_t$-linearizado sobre $\mathbb{F}_q[x]$ tal que a dimensão de seu núcleo seja 1. O espaço imagem $R_L$ tem tamanho $t^{e-1}$.
   • O conjunto de vértices é definido como $V = \mathbb{F}_q \times R_L$, resultando em $n = q \cdot t^{e-1} = t^{2e-1}$ vértices.
   • Dois vértices distintos $(v_1, v_2)$ e $(w_1, w_2)$ são adjacentes se, e somente se, $v_2 + w_2 = L(v_1 w_1)$. Laços implícitos pela equação são removidos para garantir um grafo simples.

2. Derivação do Limite Superior:

   • Os autores primeiro estabelecem um limite superior preciso para $\text{ex}(n, K_{t,t}, K_{2,t+1})$.
   • O argumento baseia-se no fato de que, em um grafo livre de $K_{2,t+1}$, quaisquer dois vértices compartilham no máximo $t$ vizinhos comuns.
   • Ao contar pares de vértices e analisar quantas vezes um $K_{t,t}$ é contado via seus pares constituintes, eles derivam o limite:
     $$\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$$

3. Análise Estrutural da Construção:

   • $K_{2,t+1}$-livre: Os autores provam que $\Gamma_{t,e}$ não contém um $K_{2,t+1}$. Para quaisquer dois vértices, o número de vizinhos comuns é determinado pelo número de soluções de uma equação linear envolvendo $L$. Como $L$ é um mapeamento $t$-para-1, existem no máximo $t$ vizinhos comuns.
   • Formação de $K_{t,t}$: O cerne da prova envolve a análise de vértices não adjacentes. Os autores mostram que quaisquer dois vértices não adjacentes com coordenadas de primeira ordem distintas definem unicamente dois conjuntos, $M$ e $N$, de cardinalidade $t$.
     • $N$ é o conjunto de vizinhos comuns (uma reta $\mathbb{F}_t$).
     • $M$ é a reta $\mathbb{F}_t$ contendo os dois vértices.
     • Todo vértice em $M$ é algebricamente adjacente a todo vértice em $N$.
   • Se $M \cap N = \emptyset$, o subgrafo induzido por $M \cup N$ é um $K_{t,t}$. Se $|M \cap N| = 1$, a estrutura forma um grafo completo tripartido $K_{1, t-1, t-1}$.

Contribuições Principais e Resultados
A principal contribuição é a construção explícita de uma família de grafos que atinge o limite superior teórico para o número de cópias de $K_{t,t}$, módulo termos de ordem inferior, para um conjunto infinito de $n$.

• Teorema 1.1: Para $t$ sendo uma potência de primo e $n = t^{2e-1}$ (onde $e > 1$ é um inteiro), o número de Turán generalizado satisfaz:
  $$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
• Comparação com Limites Anteriores: O artigo observa que o melhor limite inferior anterior de [5] era da forma $(1-o(1)) \frac{n^2}{4t^2 t!}$. O novo resultado melhora significativamente este coeficiente para potências de primo $t > 5$.
• Negligibilidade de Casos Não Ótimos: Os autores demonstram que o número de configurações resultantes em $K_{1, t-1, t-1}$ (onde $|M \cap N| = 1$) é negligível ($O(n)$) comparado à contagem total de $K_{t,t}$s ($O(n^2)$), garantindo a dominância assintótica da contagem de $K_{t,t}$.

Significância e Alegações
O artigo afirma fornecer uma "construção simples e completamente explícita" para um conjunto infinito, embora esparso, de $n$'s, contrastando com as provas de existência probabilísticas anteriormente disponíveis. A construção é isomórfica a grafos estudados anteriormente por Lazebnik e Mubayi no contexto de números de Ramsey multicolor, embora este artigo os aplique especificamente ao problema de Turán generalizado.

Os autores concluem conjecturando que o limite superior derivado é justo para todos os $n$, não apenas para os casos específicos de potências de primo construídos:
$$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
O trabalho serve para refinar a compreensão da taxa de crescimento dos números de Turán generalizados para grafos bipartidos, passando de estimativas de ordem de magnitude para constantes assintóticas precisas para regimes específicos.