On the $(k+2,k)$-problem of Brown, Erd\H{o}s and Sós for even integers $k$

Cet article détermine la valeur exacte de la limite $\lim_{n\to\infty} n^{-2} f^{(r)}(n;rk-2k+2,k)$ pour tout entier pair $k \geq 4$ et toute uniformité $r \geq 2+\sqrt{\frac{3}{2}k-4}$, en démontrant qu'elle est égale à $\frac{1}{r^2-r}$.

L'essentiel

Imaginez que vous êtes un architecte chargé de construire des gratte-ciels avec des règles très strictes. C'est un peu ce que font les mathématiciens dans ce papier, mais au lieu de briques, ils utilisent des points et des liens (des arêtes) pour créer des structures appelées hypergraphes.

Voici l'histoire de leur découverte, racontée simplement :

1. Le Problème : Construire sans s'effondrer

Imaginons que vous ayez une immense boîte de Lego (vos points). Vous voulez assembler le plus grand nombre de blocs possibles (vos liens) sans jamais créer une structure interdite.

• La règle interdite : Vous ne pouvez pas assembler $k$ blocs de manière à ce qu'ils ne touchent que $s$ points au total. C'est comme dire : "Si vous prenez 5 pièces de Lego, elles doivent occuper au moins 10 emplacements différents, sinon c'est interdit."
• L'objectif : Trouver le nombre maximum de blocs que vous pouvez mettre dans votre ville de Lego avant de violer cette règle.

Les mathématiciens s'intéressent à un cas très précis : quand le nombre de blocs ($k$) est un nombre pair (comme 4, 6, 8...) et que la règle est ajustée de manière très fine. Ils se demandent : "Quelle est la densité maximale de notre ville de Lego ?"

2. Le Défi : La "Conjecture" des Anciens

Depuis 1973, des mathématiciens célèbres (Brown, Erdős et Sós) ont soupçonné une chose : si on prend une ville de Lego infiniment grande, la densité de blocs finit par se stabiliser à une valeur précise, comme si l'eau dans une baignoire atteignait un niveau constant.

Pour certains petits nombres ($k=2, 3, 4...$), on a déjà trouvé la réponse exacte. Mais pour les grands nombres pairs ($k=6, 8, 10...$), c'était un mystère total. On savait que la réponse existait, mais pas quelle était la formule magique.

3. La Solution : Le "Miroir" et le "Poids"

Dans ce papier, Yan Wang et Jiasheng Zeng ont réussi à résoudre ce mystère pour tous les nombres pairs $k$ (à partir de 4), à condition que la taille des blocs ($r$) soit assez grande.

Voici leur astuce, expliquée avec une analogie :

L'Analogie du "Poids des Voisins" :
Imaginez que chaque paire de points dans votre ville de Lego est un couple de voisins.

• Les auteurs inventent un système de poids. Ils disent : "Si deux voisins sont connectés par une petite structure simple, ils portent un poids de 1. Si c'est une structure un peu plus complexe, ils portent un poids de 2 divisé par un grand nombre."
• Ensuite, ils appliquent une règle de fusion : si deux structures peuvent se coller ensemble sans créer de "monstre interdit", elles fusionnent.
• Le génie de l'astuce : Ils prouvent que, peu importe comment vous construisez votre ville (tant que vous respectez la règle), la somme totale des poids de tous les voisins ne peut jamais dépasser 1 par paire.

C'est comme si vous disiez : "Chaque couple de voisins a un budget de 1 euro. Si vous dépassez ce budget en construisant trop de liens, vous créez automatiquement la structure interdite."

4. Le Résultat : La Formule Magique

Grâce à cette méthode de "poids", ils ont démontré que la densité maximale de votre ville de Lego est exactement :

$$\frac{1}{r^2 - r}$$

Où $r$ est la taille de vos blocs de base.

Pourquoi est-ce important ?
Avant, on pensait qu'il fallait des conditions très complexes et des nombres gigantesques pour que cette formule fonctionne. Wang et Zeng ont montré qu'il suffit que la taille des blocs ($r$) soit un peu plus grande que la racine carrée de $k$ (environ $\sqrt{1.5k}$). C'est une amélioration énorme par rapport aux travaux précédents qui demandaient des nombres beaucoup plus grands.

En Résumé

C'est comme si on avait dit : "Pour construire une ville de Lego géante sans effondrement, il faut respecter une densité précise. Nous avons prouvé que cette densité est toujours la même, quelle que soit la taille de la ville, tant que vos briques sont assez grosses."

Ils ont trouvé la clé pour ouvrir la porte de ce problème vieux de 50 ans pour une grande famille de nombres (les pairs), en utilisant une méthode élégante de "poids" qui évite de devoir analyser chaque détail compliqué de la structure. C'est une victoire de l'intuition et de la logique pure sur la complexité brute.

Résumé technique

1. Contexte et Problématique

Le papier s'inscrit dans le domaine de la combinatoire extrémale, plus précisément dans l'étude des nombres de Turán pour les hypergraphes.

• Définitions de base : Soit $r \ge 2$. Un $r$-graphe (ou hypergraphe $r$-uniforme) $H$ est un ensemble de sommets et d'arêtes, chaque arête contenant exactement $r$ sommets.
• Fonction $f^{(r)}(n; s, k)$ : Ce nombre représente le nombre maximal d'arêtes dans un $r$-graphe à $n$ sommets tel que toute sous-structure de $k$ arêtes englobe strictement plus de $s$ sommets. Autrement dit, le graphe est libre de toute configuration de $k$ arêtes ayant au plus $s$ sommets.
• La conjecture de Brown, Erdős et Sós (1973) : Les auteurs ont conjecturé que pour $r=3$, la limite $\lim_{n \to \infty} n^{-2} f^{(3)}(n; k+2, k)$ existe. Cette conjecture a été résolue récemment par Delcourt et Postle (2023) pour $r=3$, puis généralisée par Shangguan pour tout $r \ge 4$.
• Le cas spécifique étudié : Le papier se concentre sur le cas où $s = (r-2)k + 2$. Dans ce régime, le nombre d'arêtes est de l'ordre de $\Theta(n^2)$. La question centrale est de déterminer la valeur exacte de la limite :
  $$\pi(r, k) := \lim_{n \to \infty} n^{-2} f^{(r)}((r-2)k + 2, k)$$
  Pour les petits $k$, ces valeurs ont été déterminées (ex: $\pi(3,2)=1/6$, $\pi(3,3)=1/5$). Pour les entiers pairs $k$, Letzter et Sgueglia ont montré que $\pi(r, k) = \frac{1}{r^2-r}$ pour des uniformités $r$ suffisamment grandes ($r \ge \sqrt{2k^{3/2}} + 2$).

L'objectif du papier : Améliorer la borne inférieure sur l'uniformité $r$ à partir de laquelle la formule $\pi(r, k) = \frac{1}{r^2-r}$ est valable pour tout entier pair $k \ge 4$.

2. Résultats Principaux

Le résultat central est le Théorème 1.2 :

Pour tout entier pair $k \ge 4$ et tout entier $r \ge \sqrt{\frac{3}{2}k} - 4 + 2$, on a :
$$\pi(r, k) = \frac{1}{r^2 - r}$$

Comparaison avec les travaux antérieurs :

• Letzter et Sgueglia (2024) : Prouvaient le résultat pour $r \ge \sqrt{2k^{3/2}} + 2$.
• Wang et Zeng : Améliorent considérablement cette condition en réduisant la dépendance en $k$ de $O(k^{3/2})$ à $O(k^{1/2})$. La nouvelle borne est $r_0(k) \approx \sqrt{1.5k}$.

3. Méthodologie et Preuve

La preuve repose sur une combinaison de bornes inférieures (constructions) et de bornes supérieures (analyse structurelle par poids), s'inspirant des travaux récents de Glock, Joos, Kim, K"uhn, Lichev, Pikhurko et Sun.

A. Bornes Inférieures

La borne inférieure $\pi(r, k) \ge \frac{1}{r^2-r}$ est obtenue en utilisant un $r$-graphe constitué d'une seule arête comme graphe interdit, ou plus généralement via des systèmes de Steiner approximatifs (résultat connu de Rödl). Cela montre que la limite ne peut pas être plus petite que cette valeur.

B. Bornes Supérieures (Le cœur de la preuve)

Pour prouver que $\pi(r, k) \le \frac{1}{r^2-r}$, les auteurs doivent montrer que tout $r$-graphe $G$ sans configuration interdite (libre de $\mathcal{G}^{(r)}_k$) a un nombre d'arêtes borné par $\frac{1}{r^2-r} n^2$.

La stratégie utilise une méthode de fusion (merging) et d'assignation de poids :

1. Définition des configurations : On définit $\mathcal{G}^{(r)}_k$ comme la famille des configurations de $k$ arêtes avec au plus $(r-2)k+2$ sommets. Le graphe $G$ est supposé $\mathcal{G}^{(r)}_k$-libre.
2. Processus de fusion (Merging) :
   • On partitionne d'abord les arêtes de $G$ en composantes connexes maximales (1-clusters).
   • On applique ensuite des règles de fusion itératives pour combiner ces clusters en des "2-clusters" (notés $M_2$). La fusion est basée sur la notion de "mergeabilité" : deux sous-graphes peuvent être fusionnés s'ils partagent des paires de sommets spécifiques qui sont "revendiquées" (claimed) par un certain nombre d'arêtes.
   • La propriété de liberté de $G$ impose des contraintes structurelles strictes sur ces clusters finaux.
3. Structure des clusters ($M_2$) :
   • Les auteurs analysent la structure des clusters dans $M_2$. Ils introduisent la notion de diamant flexible (deux arêtes intersectant en exactement deux sommets).
   • Ils démontrent que si un cluster satisfait une propriété spécifique (Propriété P), il possède une structure très rigide : il est composé d'un noyau initial et de blocs ajoutés de taille 2.
   • Le Théorème 3.7 établit une relation linéaire entre le nombre d'arêtes $|F|$ d'un cluster et son nombre de fusion $m(F)$ : $|F| \ge 2m(F) - k + 3$.
4. Assignation de poids (Weighting Scheme) :
   • Pour chaque paire de sommets $xy$ dans un cluster $F$, on assigne un poids $w_F(xy)$ basé sur le nombre d'arêtes "revendiquant" cette paire (1-claim ou 2-claim).
   • La fonction de poids est définie comme suit :
     • $1$ si la paire est 1-claimée.
     • $\frac{2}{k-2}$ si la paire est 2-claimée mais pas 1-claimée.
     • $0$ sinon.
   • Lemme 3.13 : La somme des poids sur toutes les paires d'un cluster ne dépasse pas 1 par paire de sommets globale.
   • Lemme 3.14 (Clé) : Pour tout cluster $F \in M_2$, le poids total $w(F)$ est inférieur ou égal à $\binom{r}{2} |F|$.
   • La preuve de ce lemme repose sur l'inégalité $r \ge \sqrt{\frac{3}{2}k} - 4$. Cette condition assure que le terme dominant dans le calcul du poids (lié aux intersections de taille 2) compense suffisamment les termes négatifs liés à la structure du graphe.

En sommant sur tous les clusters, on obtient $|G| \le \binom{r}{2}^{-1} \binom{n}{2} \approx \frac{1}{r^2-r} n^2$.

4. Contributions Clés

1. Amélioration de la borne de $r$ : La contribution majeure est la réduction de la condition sur $r$ de $O(k^{3/2})$ à $O(k^{1/2})$. Cela signifie que la formule asymptotique exacte est valable pour des uniformités beaucoup plus faibles, se rapprochant de la borne optimale conjecturée (qui est probablement $r=4$ pour $k \ge 6$).
2. Raffinement de l'analyse structurelle : L'article affine l'analyse des clusters obtenus par fusion, en particulier la gestion des "diamants flexibles" et la preuve que les clusters satisfaisant la Propriété P ont une croissance contrôlée.
3. Optimisation de l'assignation de poids : La définition des poids et la preuve que leur somme est bornée par la taille du graphe sont optimisées pour fonctionner avec la nouvelle borne sur $r$.

5. Signification et Perspectives

• Résolution partielle du problème de Brown-Erdős-Sós : Ce travail résout le problème pour une large classe de paramètres ($k$ pair, $r$ grand) avec une précision asymptotique parfaite.
• Impact théorique : La réduction de la dépendance en $k$ suggère que la structure des hypergraphes extrémaux devient "simple" (proche des systèmes de Steiner) beaucoup plus tôt que prévu.
• Problèmes ouverts : Les auteurs soulignent que pour $k \in \{6, 8\}$, leur borne donne $r_0(k) \le 5$, alors que la conjecture est que $r_0(k)=4$. Atteindre $r=4$ pour tous les $k$ pairs nécessiterait probablement une assignation de poids encore plus délicate, comme mentionné dans les remarques conclusives.

En résumé, ce papier représente une avancée significative dans la compréhension fine des limites de Turán pour les hypergraphes, en repoussant les frontières de validité des formules asymptotiques connues grâce à une analyse combinatoire rigoureuse et une optimisation des méthodes de poids.