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

Résumé Technique : Graphes sans $K_{2,t+1}$ contenant un nombre optimal de $K_{t,t}$

Énoncé du Problème
Le papier traite du nombre de Turán généralisé, noté $\text{ex}(n, H, F)$, qui représente le nombre maximal de copies d'un graphe $H$ pouvant exister dans un graphe sans $F$ sur $n$ sommets. Plus précisément, les auteurs étudient le cas où $H = K_{t,t}$ et $F = K_{2,t+1}$. L'objectif est de déterminer le comportement asymptotique de $\text{ex}(n, K_{t,t}, K_{2,t+1})$.

Alors que les travaux récents de Pohoata, Tidor et Yu ont établi que $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ pour tous les entiers $t \ge 3$, leur preuve reposait sur des méthodes probabilistes et des ensembles évasifs de sous-espaces, produisant une borne inférieure avec un coefficient qui n'était pas nécessairement optimal. Ce papier cherche à fournir une formule asymptotique précise pour des valeurs spécifiques de $n$ et $t$ en utilisant une construction explicite.

Méthodologie
Les auteurs emploient une construction déterministe et algébrique de graphes basés sur des corps finis et des polynômes linéarisés.

1. Construction du Graphe ($\Gamma_{t,e}$) :

   • Soit $t$ une puissance de nombre premier et $e > 1$ un entier. Définir $q = t^e$.
   • Soit $L$ un polynôme $\mathbb{F}_t$-linéarisé sur $\mathbb{F}_q[x]$ tel que la dimension de son noyau est 1. L'espace image $R_L$ a pour taille $t^{e-1}$.
   • L'ensemble des sommets est défini par $V = \mathbb{F}_q \times R_L$, ce qui donne $n = q \cdot t^{e-1} = t^{2e-1}$ sommets.
   • Deux sommets distincts $(v_1, v_2)$ et $(w_1, w_2)$ sont adjacents si et seulement si $v_2 + w_2 = L(v_1 w_1)$. Les auto-boucles impliquées par l'équation sont supprimées pour garantir un graphe simple.

2. Dérivation de la Borne Supérieure :

   • Les auteurs établissent d'abord une borne supérieure précise pour $\text{ex}(n, K_{t,t}, K_{2,t+1})$.
   • L'argument repose sur le fait que dans un graphe sans $K_{2,t+1}$, deux sommets quelconques partagent au plus $t$ voisins communs.
   • En comptant les paires de sommets et en analysant combien de fois un $K_{t,t}$ est compté via ses paires constituantes, ils dérivent la borne :
     $$\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$$

3. Analyse Structurelle de la Construction :

   • Absence de $K_{2,t+1}$ : Les auteurs prouvent que $\Gamma_{t,e}$ ne contient aucun $K_{2,t+1}$. Pour deux sommets quelconques, le nombre de voisins communs est déterminé par le nombre de solutions d'une équation linéaire impliquant $L$. Puisque $L$ est une application $t$-vers-1, il y a au plus $t$ voisins communs.
   • Formation de $K_{t,t}$ : Le cœur de la preuve implique l'analyse des sommets non adjacents. Les auteurs montrent que deux sommets non adjacents ayant des premières coordonnées distinctes définissent de manière unique deux ensembles, $M$ et $N$, de cardinalité $t$.
     • $N$ est l'ensemble des voisins communs (une droite $\mathbb{F}_t$).
     • $M$ est la droite $\mathbb{F}_t$ contenant les deux sommets.
     • Chaque sommet de $M$ est algébriquement adjacent à chaque sommet de $N$.
   • Si $M \cap N = \emptyset$, le sous-graphe induit par $M \cup N$ est un $K_{t,t}$. Si $|M \cap N| = 1$, la structure forme un graphe complet tripartite $K_{1, t-1, t-1}$.

Contributions Principales et Résultats
La principale contribution est la construction explicite d'une famille de graphes qui atteint la borne supérieure théorique pour le nombre de copies de $K_{t,t}$, modulo les termes d'ordre inférieur, pour un ensemble infini de $n$.

• Théorème 1.1 : Pour $t$ étant une puissance de nombre premier et $n = t^{2e-1}$ (où $e > 1$ est un entier), le nombre de Turán généralisé satisfait :
  $$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
• Comparaison avec les Bornes Précédentes : Le papier note que la meilleure borne inférieure précédente de [5] était de la forme $(1-o(1)) \frac{n^2}{4t^2 t!}$. Le nouveau résultat améliore considérablement ce coefficient pour les puissances de nombres premiers $t > 5$.
• Négligeabilité des Cas Non-Optimaux : Les auteurs démontrent que le nombre de configurations résultant en un $K_{1, t-1, t-1}$ (où $|M \cap N| = 1$) est négligeable ($O(n)$) par rapport au compte total de $K_{t,t}$ ($O(n^2)$), assurant la dominance asymptotique du compte de $K_{t,t}$.

Signification et Revendications
Le papier prétend fournir une « construction simple et complètement explicite » pour un ensemble infini, bien que creux, de $n$, contrastant avec les preuves d'existence probabilistes précédemment disponibles. La construction est isomorphe aux graphes précédemment étudiés par Lazebnik et Mubayi dans le contexte des nombres de Ramsey multicolores, bien que ce papier les applique spécifiquement au problème de Turán généralisé.

Les auteurs concluent en conjecturant que la borne supérieure dérivée est serrée pour tous les $n$, et pas seulement pour les cas spécifiques de puissances de nombres premiers construits :
$$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
Le travail sert à affiner la compréhension du taux de croissance des nombres de Turán généralisés pour les graphes bipartis, passant des estimations d'ordre de grandeur à des constantes asymptotiques précises pour des régimes spécifiques.