Conjecture d'Erdős-Hajnal

En théorie des graphes, la conjecture d'Erdős-Hajnal concerne une relation entre les sous-graphes induits et les cliques et stables.

Étant donné un graphe non orienté arbitraire ${\displaystyle H}$, on dit qu'un graphe ${\displaystyle G}$ est un « graphe sans ${\displaystyle H}$ » (${\displaystyle H}$-free graph en anglais) si ${\displaystyle G}$ n'a pas de sous-graphe induit isomorphe à ${\displaystyle H}$. Plus précisément, étant donné un graphe non orienté arbitraire ${\displaystyle H}$, soit ${\displaystyle {\mathcal {F}}_{H}}$ la famille de graphes qui n'ont pas ${\displaystyle H}$ comme sous-graphe induit, donc qui sont des graphes sans ${\displaystyle H}$ (${\displaystyle H}$-free graphs en anglais). La conjecture dit qu'il existe une constante ${\displaystyle \delta _{H}>0}$ telle que les graphes à ${\displaystyle n}$ sommets dans ${\displaystyle {\mathcal {F}}_{H}}$ possèdent soit une clique, soit un stable de taille ${\displaystyle \Omega (n^{\delta _{H}})}$.

Pour les graphes aléatoires dans le modèle Erdős-Rényi avec une probabilité 1/2 pour les arêtes, la clique maximale et le stable maximal sont beaucoup plus petits : leur taille est proportionnelle au logarithme de ${\displaystyle n}$, plutôt que de croître de manière polynomiale. Le théorème de Ramsey permet de prouver qu'aucun graphe n'a à la fois une clique maximale et un stable maximale de taille inférieure au logarithme de sa taille^[1],[2]. Le théorème de Ramsey implique également le cas particulier de la conjecture d'Erdős-Hajnal où ${\displaystyle H}$ lui-même est une clique ou un stable^[1].

Le point central de la théorie de Ramsey est le théorème d'Erdős et Szekeres^[3] des années 1930, selon lequel chaque graphe sur ${\displaystyle n}$ sommets a une clique ou un stable de taille ${\displaystyle \Omega (\log n)}$. Cet ordre de grandeur ne peut pas être amélioré, car Erdős^[4] a montré qu'il existe une infinité de graphes G avec ${\displaystyle \max(\alpha (G),\omega (G))=O(\log |G|}$, où ${\displaystyle \alpha (G)}$ et ${\displaystyle \omega (G)}$ dénotent les cardinalités des plus grands ensembles stables et des plus grandes cliques dans ${\displaystyle G}$. En effet, pour la plupart des graphes G, ${\displaystyle \alpha (G)}$ et ${\displaystyle \omega (G)}$ ont tous deux une taille logarithmique. La conjecture est due à Paul Erdős et András Hajnal, qui l'ont prouvé dans le cas où ${\displaystyle H}$ est un cographe. Ils ont également montré que, pour ${\displaystyle H}$ arbitraire, la taille de la plus grande clique ou du stable maximal croît de manière plus que logarithmique. Plus précisément, pour chaque ${\displaystyle H}$ il existe une constante ${\displaystyle c}$ tel que les graphes ${\displaystyle G}$ sans ${\displaystyle H}$ de taille ${\displaystyle n}$ vérifient

${\displaystyle \max(\alpha (G),\omega (G))\geq 2^{c{\sqrt {\log n}}}}$^[1],[5].

Les graphes ${\displaystyle H}$ pour lesquels la conjecture est vraie incluent également ceux avec au plus quatre sommets^[1],[6], et tous les graphes à cinq sommets sauf le chemin à cinq sommets et son complément^[7],[1],[8] et tout graphe qui peut être obtenu à partir de ceux-ci et des cographes par décomposition modulaire^[1],[2]. En 2021, la conjecture complète n'a pas été prouvée et reste un problème ouvert^[1],[9].

Le cas particulier où ${\displaystyle H}$ est le graphe cycle à 5 sommets a été résolue par Maria Chudnovsky, Alex Scott, Paul Seymour et Sophie Spirkl en 2021^[9]. Ils prouvent :

Les graphes sans ${\displaystyle C_{5}}$ comprennent les graphes parfaits, qui ont nécessairement soit une clique, soit un stable de taille proportionnelle à la racine carrée de leur nombre de sommets. Réciproquement, chaque clique ou stable est lui-même parfait. Ainsi, une reformulation plus maniable et symétrique de la conjecture d'Erdős-Hajnal est que pour chaque graphe ${\displaystyle H}$, les graphes sans ${\displaystyle H}$ contiennent toujours un sous-graphe parfait induit de taille polynomiale^[1].

Alon et al. ont montré que l'énoncé suivant concernant les tournois est équivalent à la conjecture d'Erdős-Hajnal^[2].

Conjecture. Pour tout tournoi ${\displaystyle T}$, il existe des nombres ${\displaystyle \varepsilon (T)>0}$ et ${\displaystyle c>0}$ tels que tout graphe ${\displaystyle G}$ sans ${\displaystyle T}$ à ${\displaystyle n}$ sommets vérifie ${\displaystyle \chi (G)\leq c\cdot n^{1-\varepsilon }}$.

Ici ${\displaystyle \chi (G)}$ dénote le nombre chromatique de ${\displaystyle G}$, qui est le plus petit ${\displaystyle k\in \mathbb {N} }$ tel qu'il existe un ${\displaystyle k}$ -coloration pour ${\displaystyle G}$. Une coloration d'un tournoi ${\displaystyle G}$ est une application ${\displaystyle \phi :V(G)\to \{1,\ldots ,k\}}$ telle que les classes de couleur ${\displaystyle \{v\in V(T):\phi (v)=i\}}$ sont transitives pour tout ${\displaystyle i=1,\ldots ,k}$.

La classe des tournois ${\displaystyle H}$ tels qu'un tournois ${\displaystyle G}$ sans ${\displaystyle H}$ satisfait l'inégalité ${\displaystyle \chi (G)\leq c(H)}$ pour une constante ${\displaystyle c(H)}$ vérifie cette conjecture équivalente (avec ${\displaystyle \varepsilon =1}$ ). De tels tournois ${\displaystyle H}$, appelés héros, ont été considérés par Berger et al.^[10]. Ils ont prouvé qu'un héros a une structure spéciale qui est la suivante :

Théorème. Un tournoi est un héros si et seulement si toutes ses composantes fortes sont des héros. Un tournoi fort avec plus d'un sommet est un héros si et seulement s'il est égal à ${\displaystyle \Delta (H,k,1)}$ ou à ${\displaystyle \Delta (H,1,k)}$ pour un héros ${\displaystyle H}$ et un nombre entier ${\displaystyle k\geq 0}$.

Dans ce énoncé, ${\displaystyle \Delta (H,k,1)}$ dénote le tournoi avec les trois composantes ${\displaystyle H}$, le tournoi transitif de taille ${\displaystyle k}$ et un seul nœud ${\displaystyle q}$. Les arcs entre les trois composants sont définis comme suit : ${\displaystyle A=\{(v,w):(v\in H\wedge w\in T_{k})\vee (v\in T_{k}\wedge w=q)\vee (v=q\wedge w\in H)\}}$. Le tournoi ${\displaystyle \Delta (H,1,k)}$ est défini de manière analogue.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős–Hajnal conjecture » (voir la liste des auteurs).

• Maria Chudnovsky et Paul Seymour, « Erdős-Hajnal for cap-free graphs », Journal of Combinatorial Theory, Series B, vol. 151,‎ novembre 2021, p. 417-434.

• La conjecture d'Erdös-Hajnal, The garden of open problems

• Portail des mathématiques
• Portail de l'informatique théorique