2025-11-14T23:55:11.549557

Turán densities of stars in uniformly dense hypergraphs

Lin, Zhou
A $3$-uniform hypergraph (or $3$-graph) $H=(V,E)$ is $(d,μ, \text{dot})$-dense if for any subsets $X, Y, Z\subseteq V$, the number of triples $(x,y,z)\in X\times Y\times Y$ with $\{x,y,z\}$ being an edge of $H$ is at least $d|X||Y||Z|-μ|V|^3$. Similarly, we say that $H$ is $(d,μ, \text{dot-edge})$-dense if for any subset $X\subseteq V$ and every pair set $P\subseteq V\times V$, the number of pairs $(x,(y,z))\in X\times P$ with $\{x,y,z\}$ being an edge of $H$ is at least $d|X||P|-μ|V|^3$. Restricting to $\text{dot}$-dense $3$-graphs and $\text{dot-edge}$-dense $3$-graphs, determining the $\text{dot}$-uniform Turán density $π_{\text{dot}}(S_k)$ and the $\text{dot-edge}$-uniform Turán density $π_{\text{dot-edge}}(S_k)$ of the $k$-star $S_k$ for $k\ge 4$ was proposed by Schacht in ICM 2022. In particular, Reiher, Rödl and Schacht presented that $π_{\text{dot}}(S_k)\ge π_{\text{dot-edge}}(S_k)\ge \frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 3$ and $π_{\text{dot}}(S_3)= π_{\text{dot-edge}}(S_3)=1/4$. Last year, Lamaison and Wu shown that $π_{\text{dot}}(S_k)=\frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 48$. In this paper, we show that $π_{\text{dot}}(S_k)=\frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 11$. Moreover, we determine the $\text{dot-edge}$-uniform Turán density for all $S_k$ except for $k=4$.
academic

Densités de Turán des étoiles dans les hypergraphes uniformément denses

Informations de base

  • ID de l'article: 2510.12576
  • Titre: Turán densities of stars in uniformly dense hypergraphs
  • Auteurs: Hao Lin, Wenling Zhou
  • Classification: math.CO (Mathématiques combinatoires)
  • Date de publication: 14 octobre 2025 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2510.12576

Résumé

Cet article étudie le problème des densités de Turán des structures en étoile dans les hypergraphes uniformément denses. Pour les 3-hypergraphes uniformes, les auteurs définissent deux concepts de densité : (d,μ,⋅)(d,\mu,\cdot)-dense et (d,μ,⋆)(d,\mu,\star)-dense. Sous ces contraintes, la détermination de la densité de Turán ⋅\cdot-uniforme π⋅(Sk)\pi_{\cdot}(S_k) et de la densité de Turán ⋆\star-uniforme π⋆(Sk)\pi_{\star}(S_k) pour la kk-étoile SkS_k est un problème important proposé par Schacht lors de l'ICM 2022. Les principales contributions de cet article sont : la preuve que π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} pour tous les k≥11k \geq 11, et la détermination de la densité de Turán ⋆\star-uniforme pour tous les SkS_k sauf k=4k=4.

Contexte et motivation de la recherche

Contexte du problème

Le problème de Turán est l'une des questions les plus fondamentales de la combinatoire extrémale, interrogeant le seuil de densité minimal garantissant l'existence d'une sous-structure donnée. Le problème de Turán pour les hypergraphes est particulièrement difficile, car la plupart des constructions extrémales connues et conjecturées contiennent de grands ensembles indépendants.

Développement historique

  1. Problème de Turán classique: En raison de la difficulté du problème de Turán pour les hypergraphes, Erdős et Sós ont proposé dans les années 1980 une variante restreignant l'attention aux 3-graphes FF-libres uniformément denses sur de grands sous-ensembles de sommets.
  2. Progrès spécifiques:
    • Rödl (1986) a conjecturé π⋅(K4(3))=1/2\pi_{\cdot}(K_4^{(3)}) = 1/2, toujours non résolu
    • Glebov, Král' et Volec (2016) ainsi que Reiher, Rödl et Schacht (2015) ont indépendamment prouvé π⋅(K4(3)−)=1/4\pi_{\cdot}(K_4^{(3)-}) = 1/4
    • Ces derniers ont également établi des bornes générales pour les kk-étoiles : k2−5k+7(k−1)2≤π⋅(Sk)≤(k−2k−1)2\frac{k^2-5k+7}{(k-1)^2} \leq \pi_{\cdot}(S_k) \leq \left(\frac{k-2}{k-1}\right)^2

Motivation de la recherche

Schacht a formellement proposé lors de l'ICM 2022 le problème de déterminer π⋅(Sk)\pi_{\cdot}(S_k) et π⋆(Sk)\pi_{\star}(S_k). Lamaison et Wu (2024) ont prouvé que la borne inférieure est serrée pour k≥48k \geq 48, et cet article vise à généraliser ce résultat à des valeurs de kk plus petites.

Contributions principales

  1. Résultat théorique principal: Preuve que π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} pour tous les k≥11k \geq 11
  2. Résultat étendu: Détermination que π⋆(Sk)=k2−5k+7(k−1)2\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2} pour tous les k≥5k \geq 5
  3. Innovation méthodologique: Adoption du cadre de construction de palettes de Lamaison, évitant le lemme de régularité traditionnel pour les hypergraphes
  4. Percée technique: Établissement d'estimations de bornes supérieures critiques par analyse structurelle de graphes orientés auxiliaires

Explication détaillée de la méthode

Définitions principales

Définition de la kk-étoile: La kk-étoile SkS_k est un 3-hypergraphe sur (k+1)(k+1) sommets, contenant les sommets u,v1,…,vku, v_1, \ldots, v_k, tels que uvivj∈E(Sk)uv_iv_j \in E(S_k) pour tous les 1≤i<j≤k1 \leq i < j \leq k.

Concepts de densité:

  • ⋅\cdot-dense: Un 3-hypergraphe H=(V,E)H=(V,E) est (d,μ,⋅)(d,\mu,\cdot)-dense si pour tous les sous-ensembles X,Y,Z⊆VX,Y,Z \subseteq V, le nombre de triplets (x,y,z)∈X×Y×Z(x,y,z) \in X \times Y \times Z avec {x,y,z}∈E\{x,y,z\} \in E est au moins d∣X∣∣Y∣∣Z∣−μ∣V∣3d|X||Y||Z| - \mu|V|^3
  • ⋆\star-dense: Pour tous les sous-ensembles X⊆VX \subseteq V et les paires d'ensembles P⊆V×VP \subseteq V \times V, satisfaisant les conditions correspondantes

Méthode des palettes

Définition de palette: Une palette P=(C,A)P = (C,A) comprend un ensemble de couleurs fini CC et un ensemble de triplets ordonnés A⊆C×C×CA \subseteq C \times C \times C.

Propriétés clés:

  • Densité: d(P):=∣A∣/∣C∣3d(P) := |A|/|C|^3
  • Degré minimum: δ(P):=min⁡i∈[3],a∈C∣Aai∣/∣C∣2\delta(P) := \min_{i \in [3], a \in C} |A_a^i|/|C|^2

Théorème central:

  • π⋅(F)=πpal⋅(F)\pi_{\cdot}(F) = \pi_{pal}^{\cdot}(F) (Théorème 2.2)
  • π⋆(F)=πpal⋆(F)\pi_{\star}(F) = \pi_{pal}^{\star}(F) (Théorème 2.3)

Construction de graphe orienté auxiliaire

Pour une palette P=(C,A)P = (C,A), construction du graphe orienté auxiliaire DP=(V,E)D_P = (V,E):

  • Ensemble de sommets: V=C1∪C2V = C_1 \cup C_2 (deux copies disjointes de CC)
  • Règle d'arcs: Ajout d'arcs selon l'acceptabilité (i,j)(i,j) des paires de couleurs (a,b)(a,b)

Lemme clé: Si la palette PP est SkS_k-mauvaise, alors DPD_P est acyclique et TkT_k-libre (Lemme 2.4).

Configuration expérimentale

Cadre d'analyse théorique

Cet article emploie une approche d'analyse théorique pure, sans données expérimentales. Les étapes principales sont:

  1. Stratégie de réduction: Réduction du théorème principal au lemme clé (Lemme 2.6)
  2. Analyse structurelle: Analyse des propriétés des graphes orientés TkT_k-libres
  3. Estimation de borne supérieure: Établissement de bornes supérieures via une variante du théorème de Caro-Wei

Techniques de preuve

  • Théorème de Brown-Harary: Détermination du nombre maximal d'arcs dans les graphes orientés TkT_k-libres
  • Techniques d'inégalités: Utilisation d'inégalités fondamentales comme xy≤(x+y2)2xy \leq \left(\frac{x+y}{2}\right)^2
  • Analyse par cas: Discussion par cas selon la taille du minimum min⁡{e2,1(a),e2,3(a)}\min\{e_{2,1}(a), e_{2,3}(a)\}

Résultats expérimentaux

Théorèmes principaux

Théorème 1.2: π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} pour tous les k≥11k \geq 11.

Théorème 1.4: π⋆(Sk)=k2−5k+7(k−1)2\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2} pour tous les k≥5k \geq 5.

Lemmes clés

Lemme 2.6: Soit k≥5k \geq 5. Pour toute palette SkS_k-mauvaise PP satisfaisant δ(P)≥14\delta(P) \geq \frac{1}{4}, on a d(P)≤k2−5k+7(k−1)2d(P) \leq \frac{k^2-5k+7}{(k-1)^2}.

Résultats techniques

Lemme 3.2: Soit k≥4k \geq 4 et DD un graphe orienté TkT_k-libre sur nn sommets. Pour chaque sommet vv, soit m(v)=max⁡{dD+(v)/n,dD−(v)/n}m(v) = \max\{d_D^+(v)/n, d_D^-(v)/n\}, et soit V′={v∈V(D):m(v)≥2k−1}V' = \{v \in V(D) : m(v) \geq \frac{2}{k-1}\}. Alors ∑v∈V′(m(v)−12)2≤(k−3)24(k−1)2n\sum_{v \in V'} \left(m(v) - \frac{1}{2}\right)^2 \leq \frac{(k-3)^2}{4(k-1)^2}n

Travaux connexes

Développement historique

  1. Problème d'Erdős-Sós: Proposé en 1982, restreignant le problème de Turán aux hypergraphes uniformément denses
  2. Construction de Rödl: Proposée en 1986, construction quasi-aléatoire conjecturant π⋅(K4(3))=1/2\pi_{\cdot}(K_4^{(3)}) = 1/2
  3. Méthode des algèbres de drapeaux: Introduite par Razborov (2007), utilisée par Glebov et al. pour résoudre le problème K4(3)−K_4^{(3)-}
  4. Méthode de régularité pour hypergraphes: Série de travaux de Reiher, Rödl et Schacht

Progrès récents

  • Cadre de Lamaison: Introduction en 2024 de la méthode des palettes, unifiant l'étude de π⋅\pi_{\cdot} et π⋆\pi_{\star}
  • Résultat de Lamaison-Wu: Preuve de la valeur exacte pour k≥48k \geq 48
  • Aide informatique: Indiquant que la borne inférieure est probablement serrée pour k≥40k \geq 40

Conclusion et discussion

Conclusions principales

Cet article améliore significativement le résultat de Lamaison et Wu, étendant la détermination exacte de π⋅(Sk)\pi_{\cdot}(S_k) de k≥48k \geq 48 à k≥11k \geq 11, et résolvant complètement le problème de π⋆(Sk)\pi_{\star}(S_k) (sauf pour k=4k=4).

Problèmes ouverts

Les auteurs proposent deux conjectures:

  1. Conjecture 5.1: π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2} pour tous les 4≤k≤104 \leq k \leq 10
  2. Conjecture 5.2: π⋆(S4)=13\pi_{\star}(S_4) = \frac{1}{3}

Limitations techniques

  • Pour le cas k=4k=4, la condition m(v)≥2/3m(v) \geq 2/3 est requise, mais difficile à garantir dans le cadre actuel
  • Le seuil m(v)≥2/(k−1)m(v) \geq 2/(k-1) du Lemme 3.2 est optimal pour k=4k=4, nécessitant une percée technique nouvelle

Évaluation approfondie

Avantages

  1. Innovation technique: Application réussie de la méthode des palettes, évitant le lemme de régularité complexe pour les hypergraphes
  2. Résultats significatifs: Extension substantielle de la portée des résultats connus
  3. Unification méthodologique: Traitement simultané des deux problèmes π⋅\pi_{\cdot} et π⋆\pi_{\star}
  4. Clarté de la preuve: Stratégie de réduction structurée rendant le raisonnement transparent

Insuffisances

  1. Couverture incomplète: Les cas 4≤k≤104 \leq k \leq 10 restent non résolus
  2. Limitations méthodologiques: Le cas particulier k=4k=4 nécessite de nouvelles techniques
  3. Complexité computationnelle: La preuve implique des estimations d'inégalités complexes et une analyse par cas

Impact

  1. Contribution théorique: Avancement d'un problème fondamental de la combinatoire extrémale
  2. Valeur méthodologique: L'application réussie de la technique des palettes offre de nouvelles perspectives pour les problèmes connexes
  3. Recherche ultérieure: Pose les fondations pour la résolution complète du problème de Schacht

Domaines d'application

Cette méthode s'applique à:

  1. Problèmes de Turán pour sous-structures interdites dans les hypergraphes
  2. Problèmes extrémaux sous conditions de densité uniforme
  3. Problèmes d'optimisation combinatoire impliquant des estimations de densité

Références

L'article cite les références clés du domaine, notamment:

  • Erdős-Sós (1982): Formulation du problème original
  • Razborov (2007): Méthode des algèbres de drapeaux
  • Série de travaux de Reiher, Rödl et Schacht: Établissement des bornes fondamentales
  • Lamaison (2024): Cadre des palettes
  • Brown-Harary (1970): Nombres de Turán pour graphes orientés