2025-11-25T13:16:17.951447

On the quadratic 8-edge case of the Brown-Erdős-Sós problem

Pikhurko, Sun
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 1973 that the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ exists for all $k$. Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity $r\ge 4$: the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(r)}(n;rk-2k+2,k)$ exists for all $r\ge 3$ and $k\ge 2$. The value of the limit is currently known for $k\in \{2,3,4,5,6,7\}$ due to various results authored by Glock, Joos, Kim, Kühn, Lichev, Pikhurko, Rödl and Sun. In this paper we consider the case $k=8$, determining the value of the limit for each $r\ge 4$ and presenting a lower bound for $k=3$ that we conjecture to be sharp.
academic

Sur le cas quadratique des 8 arêtes du problème de Brown-Erdős-Sós

Informations fondamentales

  • ID de l'article: 2506.01739
  • Titre: On the quadratic 8-edge case of the Brown-Erdős-Sós problem
  • Auteurs: Oleg Pikhurko, Shumin Sun (Université de Warwick)
  • Classification: math.CO (Mathématiques combinatoires)
  • Date de publication: 16 octobre 2025 (version 2 sur arXiv)
  • Lien de l'article: https://arxiv.org/abs/2506.01739

Résumé

Cet article étudie le cas quadratique des 8 arêtes du problème de Brown-Erdős-Sós. Soit f(r)(n;s,k)f^{(r)}(n;s,k) le nombre maximal d'arêtes dans un hypergraphe rr-uniforme sur nn sommets ne contenant pas kk arêtes couvrant au plus ss sommets. Brown, Erdős et Sós ont conjecturé en 1973 que pour tous les kk, la limite lim⁡n→∞n−2f(3)(n;k+2,k)\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k) existe. Récemment, Delcourt et Postle ont résolu cette conjecture, et Shangguan l'a généralisée à toutes les uniformités r≥4r\ge 4. Cet article considère le cas k=8k=8, détermine la valeur de la limite pour chaque r≥4r\ge 4, et fournit une borne inférieure pour r=3r=3.

Contexte et motivation de la recherche

  1. Problème fondamental: Le problème de Brown-Erdős-Sós étudie les nombres de Turán des hypergraphes rr-uniformes, c'est-à-dire le nombre maximal d'arêtes qu'un hypergraphe sur nn sommets peut contenir en évitant un sous-graphe interdit spécifique.
  2. Importance du problème: C'est l'un des problèmes fondamentaux de la combinatoire extrémale, étroitement lié aux domaines centraux tels que la théorie de Ramsey et la théorie de Turán. La résolution de ce problème est cruciale pour comprendre les propriétés structurelles des hypergraphes.
  3. Progrès existants:
    • Brown, Erdős et Sós ont prouvé que f(r)(n;s,k)=Θ(nt)f^{(r)}(n;s,k) = \Theta(n^t), où t=(rk−s)/(k−1)t = (rk-s)/(k-1)
    • Lorsque t=2t=2 (c'est-à-dire s=rk−2k+2s = rk-2k+2), l'existence de la limite π(r,k):=lim⁡n→∞n−2f(r)(n;rk−2k+2,k)\pi(r,k) := \lim_{n\to\infty} n^{-2}f^{(r)}(n;rk-2k+2,k) a été établie
    • Pour k∈{2,3,4,5,6,7}k \in \{2,3,4,5,6,7\}, les valeurs limites sont connues
  4. Motivation de la recherche: k=8k=8 est l'objectif naturel suivant, et ce cas présente une nouvelle complexité, particulièrement dans les comportements différents entre r=3r=3 et r≥4r\ge 4.

Contributions principales

  1. Théorème principal: Pour tous les r≥4r \geq 4, on détermine π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}
  2. Résultats de borne inférieure: On prouve que π(3,8)≥316\pi(3,8) \geq \frac{3}{16} et on conjecture que cette borne est optimale
  3. Méthodes de construction: On fournit des constructions explicites atteignant les bornes, basées sur les graphes d'incidence des plans projectifs
  4. Analyse structurelle: Analyse approfondie de la structure des hypergraphes G8(r)G^{(r)}_8-libres, en particulier la classification des 2-clusters
  5. Applications: Établissement de connexions avec les nombres de Ramsey généralisés, obtenant lim⁡n→∞GR(n,18,146)n2=512\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12}

Détails des méthodes

Définition de la tâche

Étudier le comportement asymptotique de la fonction f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k) lorsque k=8k=8, c'est-à-dire déterminer la valeur de la limite π(r,8)=lim⁡n→∞n−2f(r)(n;8r−14,8)\pi(r,8) = \lim_{n\to\infty} n^{-2}f^{(r)}(n; 8r-14, 8).

Méthodes de construction de borne inférieure

Unités de construction fondamentales

  • Graphes R: Définition d'un 3-graphe RR à 5 sommets et 3 arêtes, composé d'une arête abcabc et d'un losange {buv,cuv}\{buv, cuv\}
  • Familles de chemins: Utilisation de plans projectifs Desarguésiens pour construire des familles de 2-chemins PP satisfaisant des conditions spécifiques de parcimonie et de connectivité

Méthode de suppression probabiliste

  1. Commencer par le graphe d'incidence du plan projectif, construire un graphe biparti G′G'
  2. Sélectionner aléatoirement des 2-chemins avec probabilité (logm)/m1/2(log m)/m^{1/2}
  3. Utiliser la méthode de suppression probabiliste pour éliminer les chemins formant des configurations denses
  4. Placer des copies du graphe RR sur chaque 2-chemin

Lemme clé

Lemme 3.2: Pour tout nombre premier puissance qq suffisamment grand, il existe une famille de 2-chemins PP satisfaisant:

  • ∣P∣=Ω(m3/2log⁡m)|P| = \Omega(m^{3/2} \log m)
  • L'union ⋃P∈PP\bigcup_{P\in P} P a O(m3/2)O(m^{3/2}) arêtes
  • L'union est sans triangles, sans 4-cycles et sans 5-cycles
  • Pour tout i∈[8]i \in [8], chaque ii-sous-ensemble de sommets a au moins i+2i+2 sommets

Méthodes de preuve de borne supérieure

Stratégie de fusion

  1. Fusion 1: Partitionner l'ensemble des arêtes en 1-clusters connexes (en fait des arbres)
  2. Fusion 2: Fusionner davantage pour obtenir des 2-clusters, via la condition de fusibilité {1}∣{2}\{1\}|\{2\}

Analyse structurelle

Lemme 4.7: Pour tout 2-cluster FF avec ∣F∣≥9|F| \geq 9, FF appartient à l'une des familles suivantes:

  • AA: 2-cluster à 9 arêtes avec combinaison (5,2,2)(5,2,2)
  • BB: 2-cluster à 9 arêtes avec combinaison (1,2,4,2)(1,2,4,2)
  • C1,C2C_1, C_2: 2-clusters avec différentes combinaisons
  • E,FE, F: 2-clusters avec structures spéciales
  • SiS_i: 2-clusters composés d'1 arbre 1 et de ii losanges, avec (2i+1)(2i+1) arêtes

Attribution de poids

Pour r≥5r \geq 5 et r=4r = 4, on utilise différentes fonctions de poids:

Pour r≥5r \geq 5:

1 & \text{si } 1 \in C_F(uv) \\ 1/3 & \text{si } 2 \in C_F(uv) \text{ et } 1 \notin C_F(uv) \\ 0 & \text{sinon} \end{cases}$$ **Pour $r = 4$**: Utiliser le maximum de 5 fonctions auxiliaires $h_i^F$ comme poids. ## Configuration expérimentale Cet article est une recherche purement théorique sans expériences informatiques. Tous les résultats sont obtenus par des preuves mathématiques rigoureuses. ### Vérification des preuves - Les bornes inférieures sont vérifiées par construction explicite - Les bornes supérieures sont prouvées par analyse exhaustive des cas et méthodes d'attribution de poids - Tous les lemmes clés ont des preuves mathématiques complètes ## Résultats expérimentaux ### Résultats principaux **Théorème 1.1**: Pour chaque $r \geq 4$, on a $\pi(r,8) = \frac{1}{r^2-r}$. **Théorème 1.2**: $\pi(3,8) \geq \frac{3}{16}$. **Conjecture 1.3**: $\pi(3,8) = \frac{3}{16}$. ### Comparaison avec les résultats connus - $\pi(r,2) = \frac{1}{r^2-r}$ (Rödl) - $\pi(r,4) = \frac{1}{r^2-r}$ (Glock et al.) - $\pi(r,6) = \frac{1}{r^2-r}$ pour $r \geq 4$ (Glock et al.) - $\pi(3,6) = \frac{61}{330}$ (cas particulier) ### Découvertes nouvelles 1. **Phénomène de seuil**: $r=4$ est l'uniformité minimale pour laquelle $\pi(r,8) = \frac{1}{r^2-r}$ est vérifiée 2. **Complexité structurelle**: Le cas $k=8$ révèle une structure de 2-clusters plus complexe que les valeurs de $k$ précédemment étudiées 3. **Connexion Ramsey**: Établissement de nouvelles connexions avec les nombres de Ramsey généralisés ## Travaux connexes ### Développement historique 1. **Brown-Erdős-Sós (1973)**: Proposition de la conjecture originale et bornes fondamentales 2. **Rödl (1985)**: Résolution du cas $k=2$ 3. **Glock (2019)**: Résolution du cas $k=3$ 4. **Delcourt-Postle (2024)**: Preuve de l'existence de la limite 5. **Shangguan (2023)**: Généralisation à toutes les uniformités ### Développement technique - **Théorie des appariements sans conflit**: Technique clé développée par Delcourt-Postle et Glock et al. - **Méthode d'attribution de poids**: Technique de borne supérieure développée sur la base des travaux de Glock et al. - **Construction probabiliste**: Méthode probabiliste basée sur des structures de géométrie algébrique ## Conclusions et discussion ### Conclusions principales 1. Détermination complète de la valeur de $\pi(r,8)$ pour $r \geq 4$ 2. Fourniture de bornes possiblement optimales pour le cas $r=3$ 3. Établissement de nouvelles connexions avec les nombres de Ramsey généralisés ### Limitations 1. **Cas $r=3$**: Seule une borne inférieure est obtenue, la correspondance de la borne supérieure reste un problème ouvert 2. **Complexité de la construction**: La construction de borne inférieure est assez technique, il peut exister des constructions plus simples 3. **Généralisation**: L'applicabilité de la méthode aux valeurs plus grandes de $k$ n'est pas claire ### Directions futures 1. Prouver la conjecture $\pi(3,8) = \frac{3}{16}$ 2. Étudier les cas $k \geq 9$ 3. Chercher des techniques de construction et de borne supérieure plus générales 4. Explorer les connexions avec d'autres problèmes extrémaux ## Évaluation approfondie ### Avantages 1. **Innovation technique**: Développement de nouvelles techniques de classification des 2-clusters et d'attribution de poids 2. **Construction ingénieuse**: La construction basée sur les plans projectifs révèle des intuitions géométriques profondes 3. **Complétude**: Fourniture d'une solution complète pour $r \geq 4$ 4. **Clarté de la rédaction**: Les détails techniques sont bien organisés et faciles à comprendre ### Insuffisances 1. **Incomplétude pour $r=3$**: Le principal problème ouvert reste non résolu 2. **Spécificité de la méthode**: Les techniques sont hautement adaptées à $k=8$, avec une généralité limitée 3. **Complexité computationnelle**: Certaines preuves sont assez longues et techniques ### Impact 1. **Contribution théorique**: Avancement de la recherche sur le problème de Brown-Erdős-Sós 2. **Méthodologie**: Fourniture de nouveaux outils techniques pour des problèmes similaires 3. **Valeur applicative**: Les connexions avec la théorie de Ramsey ouvrent de nouvelles directions de recherche ### Scénarios applicables Cette méthode s'applique à: 1. L'étude des problèmes extrémaux sur les hypergraphes 2. Les problèmes de type Turán avec sous-graphes interdits 3. L'analyse structurelle en optimisation combinatoire 4. Les applications de la combinatoire algébrique ## Références L'article cite les travaux fondamentaux du domaine, incluant: - Les travaux originaux de Brown, Erdős et Sós - Les résultats révolutionnaires de Delcourt-Postle - La série de travaux de Glock et al. - Les résultats de généralisation de Shangguan - Les travaux de Bennett et al. sur les nombres de Ramsey généralisés --- **Évaluation générale**: Cet article est une contribution théorique de haute qualité en combinatoire, réalisant des progrès importants dans l'étude du problème de Brown-Erdős-Sós. Bien que le principal problème ouvert (le cas $r=3$) reste partiellement non résolu, les contributions techniques et les innovations méthodologiques de l'article jettent des bases solides pour les recherches futures dans ce domaine.