Les grandes cliques dans les graphes avec structures semi-induites interdites

Informations de base

• ID de l'article: 2511.13073
• Titre: Large cliques in graphs with forbidden semi-induced structures
• Auteurs: Nannan Chen (Université de Shandong & IBS), Yulai Ma (Université de Nankai), Fan Yang (Université de Shandong & IBS)
• Classification: math.CO (Combinatoire)
• Date de soumission: 17 novembre 2025
• Lien de l'article: https://arxiv.org/abs/2511.13073

Résumé

Cet article étudie l'existence de grandes cliques dans les graphes avec structures semi-induites interdites. Holmsen a prouvé en 2022 que tout graphe contenant au moins $c\binom{n}{r}$ cliques $r$ mais ne contenant pas le graphe complet $r$-parti induit $K_{2,\ldots,2}$ doit contenir une clique d'ordre $Ω(c^{2^{r-1}}n)$. En interdisant les structures semi-induites liées à $K_{2,\ldots,2}$, cet article prouve que tout graphe $G$ à $n$ sommets contenant au moins $c\binom{n}{r}$ copies de $K_r$ doit contenir une clique d'ordre $Ω(cn)$. Ce résultat améliore la dépendance en $c$ dans la borne de Holmsen de $c^{2^{r-1}}$ à une dépendance linéaire en $c$, en interdisant seulement un nombre borné de structures. De plus, cette approche établit naturellement un lien avec le concept de dimension VC.

Contexte et motivation de la recherche

Contexte du problème

1. Théorie classique de Turán: Le théorème de Turán et ses généralisations (théorème d'Erdős-Stone-Simonovits) étudient les problèmes extrémaux pour les sous-graphes non induits. Pour un graphe $H$ avec nombre chromatique $χ(H) ≥ 3$, interdire $H$ comme sous-graphe rend le graphe extrêmal asymptotiquement $(χ(H)-1)$-parti, limitant ainsi le nombre de cliques par une constante.
2. Cas des sous-graphes induits: Lorsqu'on interdit les sous-graphes induits, la situation est complètement différente. Gyárfás, Hubenko et Solymosi (2002) ont prouvé que si un graphe $G$ à $n$ sommets a au moins $c\binom{n}{2}$ arêtes et ne contient pas $K_{2,2}$ induit, alors $ω(G) ≥ \frac{c^2}{10}n$.
3. Bornes optimales pour les graphes cordaux: Les graphes cordaux (interdisant les cycles induits de longueur au moins 4) atteignent une meilleure borne: $ω(G) ≥ (1-\sqrt{1-c})n$, ce qui est $Ω(cn)$ lorsque $c$ est petit.
4. Généralisation de Holmsen: Holmsen (2020) a généralisé le cas $K_{2,2}$ à la version multipartite, prouvant que les graphes interdisant $K_r[2]$ (l'expansion 2 de $K_r$) contiennent une clique d'ordre $Ω(c^{2^{r-1}}n)$.

Motivation de la recherche

Bien que le résultat de Holmsen soit linéaire en $n$, sa borne en $c$ se détériore rapidement avec $r$. La question centrale de cet article est: Peut-on, de manière similaire à l'amélioration du théorème 1.1 au théorème 1.2, améliorer la borne de Holmsen en interdisant plus de structures (mais en nombre borné)?

Importance

• Ce problème relie la théorie extrémale des graphes au théorème de Helly abstrait
• Il est fondamental pour comprendre la relation entre l'interdiction de sous-graphes induits et le nombre de cliques
• Il révèle le rôle de la dimension VC dans les structures de graphes

Contributions principales

1. Théorème principal: Preuve que pour un graphe $G$ induit $K_r^{[2]}$-libre contenant au moins $c\binom{n}{r}$ copies de $K_r$, on a $ω(G) ≥ \frac{c}{18r}n$ (théorème 1.5)
2. Amélioration de la borne: Amélioration de la borne $Ω(c^{2^{r-1}}n)$ de Holmsen à $Ω(cn)$, réalisant une dépendance linéaire en $c$
3. Structures interdites bornées: Seule l'interdiction d'au plus $2^{\binom{r}{2}}$ structures induites est nécessaire (comparé aux infinies pour les graphes cordaux)
4. Approche par dimension VC: Établissement d'un lien naturel entre les sous-graphes semi-induits et la dimension VC, généralisant la théorie existante des sous-graphes doublement induits
5. Aperçus structurels: Révélation que même en interdisant bien moins de structures que pour les graphes cordaux, on peut garantir une clique de taille linéaire

Détails de la méthode

Définition de la tâche

Entrée: Un graphe $G$ à $n$ sommets satisfaisant:

• Contient au moins $c\binom{n}{r}$ copies de $K_r$ ($c > 0$ est une constante)
• Est induit $K_r^{[2]}$-libre (ne contient aucun graphe de $K_r^{[2]}$ comme sous-graphe induit)

Sortie: Preuve que $G$ contient une clique d'ordre au moins $\frac{c}{18r}n$

Définitions clés:

• $K_r[2]$: L'expansion 2 de $K_r$, remplaçant chaque sommet par un ensemble indépendant de taille 2
• $K_r^{[2]}$: La famille des sous-graphes de $K_r[2]$ dont l'ensemble d'arêtes a la forme $(E(K_r[2])\backslash E(K_{U'})) \cup E'$, où $U' = \{u'_1, \ldots, u'_r\}$ est l'ensemble des deuxièmes sommets de chaque partie, et $E' \subseteq E(K_{U'})$

Architecture centrale

La preuve se divise en trois étapes clés:

1. Borne sur la dimension VC (Claim 2.3)

Lemme central: La famille des cliques maximales $MC(G)$ d'un graphe induit $K_r^{[2]}$-libre a dimension VC au plus $r-1$.

Esquisse de preuve:

• Supposer qu'il existe un ensemble $S = \{u_1, \ldots, u_r\}$ de taille $r$ pulvérisé par $MC(G)$
• Pour chaque $i \in [r]$, il existe une clique maximale $K_i$ telle que $K_i \cap S = S \backslash \{u_i\}$
• Par maximalité, il existe $u'_i \in K_i \backslash S$ tel que $u_i u'_i \notin E(G)$
• Alors $\{u_1, u'_1, \ldots, u_r, u'_r\}$ induit un certain graphe de $K_r^{[2]}$, contradiction

2. Application du lemme de Sauer-Shelah

Pour un système d'ensembles $\mathcal{F}$ de dimension VC $k$, tout ensemble $S$ de taille $m$ satisfait: $|\mathcal{F}|_S| \leq \sum_{i=0}^{k} \binom{m}{i}$

Pour notre cas, $k = r-1$, en choisissant $m = \lfloor\frac{9r}{c}\rfloor$, on obtient: $|MC(G)|_{S_m}| \leq \sum_{i=0}^{r-1} \binom{m}{i} < \frac{1}{4}c\binom{m}{r}$

3. Argument probabiliste

Preuve par contradiction: Supposer que $ω(G) < c'n$, où $c' = \frac{c}{18r}$

Sélection aléatoire: Choisir aléatoirement $S_r \subseteq S_m$, où $|S_r| = r$, $|S_m| = m$

Analyse probabiliste:

• La probabilité que $S_r$ induise une clique est au moins $c$
• Si $S_r$ induit une clique et est contenue dans une clique maximale $K$ de taille $< c'n$, alors la probabilité que $S_m$ contienne $S_r$ mais que $S_m \backslash S_r$ ne contienne aucun sommet de $K$ est au moins: $\frac{\binom{n-c'n}{m-r}}{\binom{n-r}{m-r}} \geq \left(\frac{n-c'n-m}{n-m}\right)^m \geq e^{-2c'm} \geq \frac{1}{4}$
• Par conséquent, la probabilité que $S_r = S_m \cap K$ est au moins $\frac{1}{4}c$
• L'espérance du nombre de $S_r$ satisfaisant les conditions est au moins $\frac{1}{4}c\binom{m}{r}$

Contradiction: Ceci contredit la borne donnée par le lemme de Sauer-Shelah.

Points d'innovation technique

1. Introduction des structures semi-induites: La famille $K_r^{[2]}$ équilibre astucieusement l'intensité des restrictions structurelles et leur nombre, assurant à la fois une force de contrainte suffisante et un nombre borné de structures interdites
2. Lien naturel avec la dimension VC: Association directe de la dimension VC du système de cliques maximales avec les sous-graphes induits du graphe, fournissant une nouvelle perspective analytique
3. Estimations probabilistes fines: Dans le cadre de sélection aléatoire, établissement de relations quantitatives entre la densité de cliques et la taille des cliques par des calculs probabilistes soignés
4. Optimisation des paramètres: Le choix $m = \lfloor\frac{9r}{c}\rfloor$ fait que la borne de Sauer-Shelah et la borne probabiliste inférieure produisent exactement une contradiction

Configuration expérimentale

Cet article est un pur article de mathématiques théoriques et n'implique pas de vérification expérimentale. Tous les résultats sont obtenus par des preuves mathématiques rigoureuses.

Vérification théorique

• Exemples extrémaux: Pour le cas $r=2$, l'article note que les graphes induits $K_2^{[2]}$-libres (interdisant $P_4$ et $K_{2,2}$ induits) forment une sous-classe des graphes cordaux
• Analyse de serrage: Bien que l'article ne fournisse pas de construction extrémale précise, la quantité de la borne est prouvée raisonnable

Résultats expérimentaux

Résultats théoriques principaux

Théorème 1.5 (Résultat principal): Soit $r ≥ 2$, $0 < c < 1$, et $G$ un graphe à $n$ sommets contenant au moins $c\binom{n}{r}$ copies de $K_r$. Si $G$ est induit $K_r^{[2]}$-libre, alors pour $n$ suffisamment grand, $ω(G) ≥ \frac{c}{18r}n$

Comparaison avec les résultats existants

Améliorations clés

1. De l'exponentiel au linéaire: La dépendance en $c$ passe de $c^{2^{r-1}}$ à $c/r$
   • Pour $r=3$: amélioration de $c^4$ à $c/3$
   • Pour $r=5$: amélioration de $c^{16}$ à $c/5$
2. Nombre de structures borné: Seule l'interdiction de $2^{\binom{r}{2}}$ structures est nécessaire
   • $r=2$: 2 structures
   • $r=3$: 8 structures
   • $r=4$: 64 structures
3. Optimalité: Pour $r=2$, le résultat de cet article est en accord quantitatif avec la borne pour les graphes cordaux (tous deux $Ω(cn)$), mais interdit moins de structures

Travaux connexes

Théorie extrémale classique des graphes

1. Théorème de Turán (1941): Détermine la valeur exacte de $ex(n, K_k)$ et le graphe extrêmal
2. Théorème d'Erdős-Stone-Simonovits (1946, 1966): $ex(n,H) = \left(1 - \frac{1}{χ(H)-1}\right)\binom{n}{2} + o(n^2)$
   • Pour les graphes non bipartis $H$, résout complètement le comportement asymptotique
   • Pour les graphes bipartis, donne seulement $ex(n,H) = o(n^2)$

Théorie extrémale des sous-graphes induits

3. Gyárfás-Hubenko-Solymosi (2002):
   • Graphes $K_{2,2}$-libres induits: $ω(G) ≥ \frac{c^2}{10}n$
   • Graphes $C_4$-libres (graphes cordaux): $ω(G) ≥ (1-\sqrt{1-c})n$
4. Abbott-Katchalski (1979): Preuve indépendante de la borne optimale pour les graphes cordaux
5. Loh et al. (2018): Généralisation aux graphes $K_{2,t}$-libres induits
6. Holmsen (2020):
   • Généralisation aux hypergraphes et versions multipartites
   • Preuve que le théorème de Helly coloré abstrait implique le théorème de Helly fractionnaire abstrait
   • Cet article améliore directement le résultat de théorie des graphes de Holmsen

Applications de la dimension VC en théorie des graphes

7. Nguyen-Scott-Seymour (2025): Établissement du lien entre la densité de sous-graphes doublement induits et la dimension VC
8. Sauer (1972), Shelah (1972): Preuve indépendante de la borne fondamentale de la dimension VC (lemme de Sauer-Shelah)

Positionnement de cet article

Cet article, basé sur le travail de Holmsen, réalise une amélioration quantitative en introduisant les structures semi-induites et la méthode de dimension VC. Le lien avec la théorie des graphes cordaux fournit une explication naturelle pour le cas $r=2$.

Conclusions et discussion

Conclusions principales

1. Amélioration quantitative: En interdisant la famille $K_r^{[2]}$ (au plus $2^{\binom{r}{2}}$ structures), amélioration de la borne inférieure pour les cliques de $Ω(c^{2^{r-1}}n)$ à $Ω(cn)$
2. Contribution méthodologique: Établissement d'un lien naturel entre les sous-graphes semi-induits et la dimension VC, généralisant le cadre théorique existant
3. Aperçus structurels: Révélation que des conditions de restriction structurelle finies suffisent à garantir une clique de taille linéaire, sans nécessiter comme pour les graphes cordaux d'interdire infiniment de structures

Limitations

1. Facteurs constants: La constante $\frac{1}{18r}$ dans la borne peut ne pas être optimale, et l'article ne discute pas de son serrage
2. Nombre de structures interdites: Bien que borné, $2^{\binom{r}{2}}$ croît exponentiellement avec $r$, restant considérable pour $r$ grand
3. Absence de construction extrémale: L'article ne fournit pas de graphe extrêmal atteignant la borne inférieure
4. Propriétés asymptotiques: Les résultats requièrent $n$ suffisamment grand, le seuil spécifique n'étant pas clarifié

Directions futures

L'article énonce explicitement dans sa conclusion les problèmes ouverts:

Question centrale: À quel moment la transition de $c^{2^{r-1}}$ à une dépendance linéaire en $c$ se produit-elle? Plus précisément, quel est le nombre minimum de structures interdites nécessaire pour forcer une borne linéaire en $c$?

Directions de recherche possibles:

1. Détermination de la famille de structures interdites minimale atteignant la borne linéaire
2. Amélioration du facteur constant $\frac{1}{18r}$
3. Construction d'exemples extrémaux ou preuve du serrage de la borne
4. Généralisation aux hypergraphes
5. Exploration d'autres conditions de restriction de structures semi-induites

Évaluation approfondie

Points forts

1. Amélioration quantitative importante:
   • L'amélioration de la dépendance exponentielle à linéaire constitue un progrès substantiel
   • Importance pour les applications (comme le théorème de Helly abstrait)
2. Techniques de preuve élégantes:
   • La méthode de dimension VC fournit un cadre d'analyse unifié
   • L'argument probabiliste est concis et puissant
   • La preuve est complètement autonome, ne dépendant que d'outils fondamentaux
3. Innovation conceptuelle:
   • La définition de la famille $K_r^{[2]}$ équilibre astucieusement l'intensité des contraintes et leur nombre
   • L'introduction des structures semi-induites est une généralisation naturelle
4. Clarté de la rédaction:
   • Motivation suffisamment explicitée
   • Détails techniques complets
   • Relations avec les travaux existants clairement établies
5. Profondeur théorique:
   • Révélation de la structure profonde de la théorie des sous-graphes induits
   • Connexion de plusieurs branches mathématiques (théorie extrémale des graphes, théorie de la dimension VC, géométrie combinatoire)

Insuffisances

1. Optimisation des constantes:
   • La constante $\frac{1}{18r}$ peut ne pas être suffisamment fine
   • Absence de discussion sur le serrage de la borne ou fourniture d'une construction supérieure correspondante
2. Dépendance du nombre de structures:
   • $2^{\binom{r}{2}}$ croît toujours rapidement avec $r$
   • Absence d'exploration quant à la possibilité d'atteindre des résultats similaires avec moins de structures interdites
3. Absence de seuils concrets:
   • "Suffisamment grand" n'est pas quantifié
   • Peut avoir un impact sur les applications pratiques
4. Discussion insuffisante de la généralisation:
   • Absence de discussion sur l'applicabilité de la méthode à d'autres structures interdites
   • Le lien avec les hypergraphes n'est mentionné que dans l'introduction
5. Spécificité insuffisante des problèmes ouverts:
   • Bien que des problèmes importants soient énoncés, aucune conjecture ou résultat partiel n'est fourni

Évaluation de l'impact

Impact théorique:

• Fournit de nouveaux outils pour la théorie extrémale des sous-graphes induits
• La méthode de dimension VC peut inspirer davantage d'applications
• Contribution directe à la recherche sur le théorème de Helly abstrait

Valeur pratique:

• Principalement de nature théorique
• Applications potentielles en théorie algorithmique des graphes et géométrie computationnelle

Reproductibilité:

• Preuve complètement vérifiable
• Aucun calcul expérimental impliqué

Valeur de citation potentielle:

• Anticipation d'une citation élevée dans le domaine de la combinatoire extrémale
• Risque de devenir une référence standard dans ce domaine

Contextes d'application

1. Recherche théorique:
   • Problèmes de sous-graphes induits interdits en théorie extrémale des graphes
   • Applications de la dimension VC dans les structures combinatoires
   • Théorème de Helly abstrait et ses généralisations
2. Problèmes connexes:
   • Étude d'autres structures semi-induites
   • Relations entre le nombre de cliques et d'autres paramètres de graphes
   • Structures de cliques dans les graphes aléatoires
3. Applications potentielles:
   • Conception d'algorithmes (exploitation des propriétés structurelles)
   • Théorie de la complexité computationnelle
   • Problèmes d'optimisation combinatoire

Références

L'article cite les références clés suivantes:

1. Abbott & Katchalski (1979): Problèmes de type Turán pour les graphes d'intervalle
2. Erdős & Simonovits (1966), Erdős & Stone (1946): Théorème ESS
3. Gyárfás, Hubenko & Solymosi (2002): Grandes cliques dans les graphes $C_4$-libres
4. Holmsen (2020): Grandes cliques pour structures interdites dans les hypergraphes (travail directement amélioré par cet article)
5. Loh et al. (2018): Nombres de Turán induits
6. Nguyen, Scott & Seymour (2025): Densité de sous-graphes induits et dimension VC
7. Sauer (1972), Shelah (1972): Bornes fondamentales de la dimension VC
8. Turán (1941): Théorème classique de Turán

Évaluation générale: Ceci est un article de haute qualité en mathématiques combinatoires, réalisant un progrès substantiel sur un problème important en théorie extrémale des graphes. En introduisant les structures semi-induites et la méthode de dimension VC, les auteurs ont amélioré avec succès la borne exponentielle de Holmsen à une borne linéaire, tout en maintenant le caractère borné du nombre de structures interdites. Les techniques de preuve sont élégantes et riches d'intuitions, fournissant de nouveaux outils de recherche au domaine. Les principales contributions sont au niveau théorique, mais les méthodes et idées peuvent avoir un impact large sur les domaines connexes.