Grid-free linear hypergraphs via Cayley-Bacharach

1. Problématique et Contexte

Le papier s'inscrit dans le domaine de la théorie des hypergraphes extrémaux et de la théorie des designs. Le problème central est la détermination de la densité maximale d'hypergraphes linéaires $r$-uniformes qui évitent une configuration locale spécifique : la grille $r \times r$ ($G_{r \times r}$).

• Définitions :

  • Un hypergraphe $r$-uniforme est linéaire si toute paire d'arêtes distinctes partage au plus un sommet.
  • La grille $G_{r \times r}$ est un hypergraphe sur $r^2$ sommets $\{v_{ij}\}$ avec $2r$ arêtes : $r$ lignes (les rangées) et $r$ colonnes.
  • On note $ex_{lin}(n, G_{r \times r})$ le nombre maximal d'arêtes d'un hypergraphe linéaire $r$-uniforme à $n$ sommets ne contenant pas de copie de $G_{r \times r}$.

• État de l'art :

  • La borne supérieure triviale pour un hypergraphe linéaire est $\Theta(n^2)$ (atteinte par les systèmes de Steiner $S(2, r, n)$).
  • Pour $r \ge 4$, F"uredi et Ruszink'o (ainsi que d'autres auteurs récents) ont montré qu'il est possible de construire des hypergraphes denses ($\Theta(n^2)$) sans grille, perdant seulement un terme d'ordre inférieur.
  • Pour $r = 3$, la situation était plus complexe. Les méthodes classiques (modèle de lignes partielles) échouaient à produire des constructions quadratiques denses. Des constructions récentes de Gishboliner-Shapira et Solymosi ont établi que $ex_{lin}(n, G_{3 \times 3}) = \Theta(n^2)$, mais avec des constantes spécifiques et des méthodes distinctes.

L'objectif du papier est de fournir une construction unifiée valable pour tout $r \ge 3$ démontrant que $ex_{lin}(n, G_{r \times r}) = \Theta_r(n^2)$, en utilisant une approche géométrique fondée sur le théorème de Cayley-Bacharach.

2. Méthodologie

L'auteur propose une construction géométrique dans le plan affine fini $AG(2, q)$(où$q$ est une puissance de nombre premier impair), exploitant les propriétés d'intersection des courbes algébriques.

A. La Construction de l'Hypergraphe $H_{r,q}$

Soit $q$ une puissance de nombre premier impair et $r \ge 3$.

1. Sommets : L'ensemble des sommets $V$ est la réunion disjointe de deux ensembles :
   • $A$ : L'union de $r-1$ droites horizontales distinctes $L_t = \{(x, \alpha_t) : x \in \mathbb{F}_q\}$, où les $\alpha_t$ sont des non-carrés distincts dans $\mathbb{F}_q$.
   • $B$ : Une conique (parabole) définie par $B = \{(x, x^2) : x \in \mathbb{F}_q\}$.
   • Propriété clé : $A \cap B = \emptyset$ car les $\alpha_t$ ne sont pas des carrés.
2. Arêtes : Pour chaque droite affine non horizontale $\ell$ qui intersecte $B$, on définit une arête $e(\ell)$ :
   • $e(\ell) = (\ell \cap A) \cup \{p(\ell)\}$, où $p(\ell)$ est un point unique choisi dans $\ell \cap B$.
   • Puisque $\ell$ n'est pas horizontal, il coupe chaque droite horizontale $L_t$ en un point unique, donc $|\ell \cap A| = r-1$. En ajoutant un point de $B$, l'arête a exactement $r$ sommets.

B. Outil Théorique : Le Théorème de Cayley-Bacharach

Le cœur de la preuve repose sur le Théorème de Cayley-Bacharach (Lemme 3.1) :

Soient $D_1$ et $D_2$ deux courbes planes de degré $r$ sans composante commune, dont l'intersection $X = D_1 \cap D_2$ contient exactement $r^2$ points distincts. Alors, toute courbe de degré $\le 2r-3$ passant par $r^2-1$ points de $X$ doit nécessairement passer par le $r^2$-ième point.

Ce théorème généralise des résultats classiques comme le théorème de Pascal ($r=3$).

3. Résultats Principaux

Théorème 1.1 : Existence d'hypergraphes sans grille

Pour tout $r \ge 3$ et $q$ suffisamment grand (puissance de nombre premier impair), il existe un hypergraphe linéaire $r$-uniforme $H_{r,q}$ tel que :

• Nombre de sommets : $|V| = rq$.
• Nombre d'arêtes : $|E| = \frac{q^2 + 2q - 1}{2} \approx \frac{1}{2r^2} n^2$.
• Propriété : $H_{r,q}$ ne contient aucune copie de la grille $r \times r$.

Preuve de la propriété "Grid-free" :
Par l'absurde, supposons l'existence d'une grille $r \times r$.

1. Les $r$ lignes et $r$ colonnes de la grille correspondent à $2r$ droites affines distinctes.
2. Ces droites forment deux courbes $D_1$ et $D_2$ (unions de $r$ droites) de degré $r$. Leur intersection $X$ contient $r^2$ points (les sommets de la grille).
3. On construit une courbe $D$ de degré $2r-3$ qui contient tous les sommets de la grille sauf un ($b_r$) :
   • $D$ contient $A$ (degré $r-1$).
   • $D$ contient les $r-1$ premiers points de $B$ via des droites les reliant ($r-2$ droites supplémentaires).
   • Le degré total est $(r-1) + (r-2) = 2r-3$.
4. Par construction, $D$ contient $r^2-1$ points de l'intersection $X$ mais pas le dernier point $b_r$ (car $b_r \notin A$ et la droite reliant les autres points de $B$ ne peut couper la conique $B$ en un troisième point distinct sans violer la linéarité).
5. Cela contredit le théorème de Cayley-Bacharach, qui impose que si une courbe de degré $\le 2r-3$ contient $r^2-1$ points de l'intersection, elle doit contenir le dernier.

Théorème 1.2 : Évitement d'intersections "percées" (Punctured Intersections)

Le papier généralise ce résultat pour éviter non seulement la grille complète, mais aussi des configurations partielles appelées intersections percées $P_r(T)$.

• Une configuration $P_r(T)$ est obtenue en retirant un ensemble $T$ d'incidences ligne-colonne de la grille et en ajoutant des sommets "privés" pour maintenir l'uniformité $r$.
• Résultat : Pour $t \le r-2$, l'hypergraphe $H^\parallel_{r,q}$ (une variante plus dense basée sur des transversales de droites parallèles) ne contient aucune copie de $P_r(T)$ pour $|T|=t$.
• La preuve utilise un "budget de degré" (Lemme 4.3) : la courbe supportant les sommets a un degré $d$ tel que $d + (t-1) \le 2r-3$, rendant impossible l'évitement d'un point par une courbe de bas degré.

4. Contributions Clés et Signification

1. Unification des constructions : C'est la première construction unifiée qui prouve que $ex_{lin}(n, G_{r \times r}) = \Theta(n^2)$ pour tous les $r \ge 3$, y compris le cas difficile $r=3$. Auparavant, les cas $r=3$ et $r \ge 4$ nécessitaient des approches très différentes.
2. Nouvelle perspective géométrique : L'article démontre la puissance du théorème de Cayley-Bacharach en combinatoire extrémale. Il transforme un problème d'évitement de sous-graphes en un problème d'intersection de courbes algébriques et de degrés de polynômes.
3. Généralisation aux motifs complexes : La méthode ne se limite pas aux grilles complètes. Elle permet d'exclure systématiquement des familles entières de configurations "presque complètes" (intersections percées), ce qui était difficile avec les méthodes probabilistes ou de packing précédentes.
4. Connexion avec la Combinatorial Nullstellensatz : La conclusion relie ces résultats au théorème d'Alon-F"uredi et à la Combinatorial Nullstellensatz, suggérant que de nombreuses bornes inférieures en théorie de Turán peuvent être vues comme des manifestations du mécanisme de "complétion" de Cayley-Bacharach.

Conclusion

Ce papier offre une avancée significative en établissant une borne quadratique optimale (à une constante près) pour l'existence d'hypergraphes linéaires denses sans grille, pour toutes les tailles d'arêtes $r \ge 3$. La force de l'approche réside dans sa simplicité conceptuelle (géométrie algébrique finie) et sa capacité à s'adapter à des motifs d'interdiction plus généraux, ouvrant la voie à de nouvelles applications en combinatoire extrémale.