Conjecture de Sidorenko — Wikipédia

La conjecture de Sidorenko est une conjecture de la théorie des graphes, formulée par Alexander Sidorenko en 1986. Elle affirme que pour tout graphe biparti ${\displaystyle H}$ et tout graphe ${\displaystyle G}$ à ${\displaystyle n}$ sommets de degré moyen ${\displaystyle pn}$, il y a au moins ${\displaystyle p^{|E(H)|}n^{|V(H)|}}$ copies de ${\displaystyle H}$ dans ${\displaystyle G}$, à un petit terme d'erreur près^[1]. Plus formellement, elle fournit une inégalité intuitive sur les densités d'homomorphismes de graphons. L'inégalité conjecturée peut être interprétée comme l'assertion selon laquelle la densité de copies de ${\displaystyle H}$ dans un graphe est asymptotiquement minimisée par un graphe aléatoire ; elle est égale à la fraction ${\displaystyle p^{|E(H)|}}$ dee sous-graphes qui sont une copie de ${\displaystyle H}$, dans le cas où chaque arête existe avec probabilité ${\displaystyle p}$ .

Un graphe ${\displaystyle H}$ est dit avoir la propriété de Sidorenko si, pour tout graphon ${\displaystyle W}$, l'inégalité

${\displaystyle t(H,W)\geq t(K_{2},W)^{|E(H)|}}$

est vérifiée, où ${\displaystyle t(H,W)}$ est la densité d'homomorphismes de ${\displaystyle H}$ dans ${\displaystyle W}$ .

La conjecture de Sidorenko, formulée en 1986^[2] et développée en 1993^[3], stipule que tout graphe biparti possède la propriété de Sidorenko.

Si le graphon ${\displaystyle W}$ est un graphe ${\displaystyle G}$, cela signifie que la probabilité qu'une fonction aléatoire uniforme de ${\displaystyle V(H)}$ sur ${\displaystyle V(G)}$ est un homomorphisme est au moins égale au produit pour chaque arête de ${\displaystyle H}$ de la probabilité que cette arête soit envoyée sur une arête dans ${\displaystyle G}$. Cela signifie grosso modo qu'un graphe choisi au hasard avec un nombre fixe de sommets et un certain degré moyen possède le nombre minimum de copies étiquetées de ${\displaystyle H}$. Ce n'est pas une conjecture surprenante puisque le membre droit de l'inégalité est la probabilité que la fonction est un homomorphisme si chaque application d'arêtes est indépendante. Il peut donc s'attendre à ce que les deux côtés soient au moins du même ordre. L'extension naturelle aux graphons découle alors de ce que chaque graphon est le point limite d'une suite de graphes.

Le fait que ${\displaystyle H}$ est biparti est nécessaire pour avoir la propriété de Sidorenko : si ${\displaystyle W}$ est un graphe biparti, alors ${\displaystyle t(K_{3},W)=0}$ puisque ${\displaystyle W}$ est sans triangle. Mais ${\displaystyle t(K_{2},W)}$ est le double du nombre d'arêtes dans ${\displaystyle W}$, donc la propriété de Sidorenko est fausse pour ${\displaystyle K_{3}}$ . Un argument similaire montre qu'aucun graphe avec un cycle de longueur impaire ne possède la propriété de Sidorenko. Puisqu'un graphe est biparti si et seulement s'il n'a pas de cycles impairs, cela implique que les seuls graphes possibles qui peuvent avoir la propriété de Sidorenko sont des graphes bipartis.

La propriété de Sidorenko équivaut à la formulation suivante:

Pour tout graphes ${\displaystyle G}$, à ${\displaystyle n}$ sommets et de degré moyen ${\displaystyle pn}$, on a ${\displaystyle t(H,G)\geq p^{|E(H)|}}$ .

Cet énoncé est équivalent au précédent car le nombre d'homomorphismes de ${\displaystyle K_{2}}$ sur ${\displaystyle G}$ est le double du nombre d'arêtes dans ${\displaystyle G}$, et l'inégalité ne doit être vérifiée que lorsque ${\displaystyle W}$ est un graphe, comme précédemment.

Dans cette formulation, puisque le nombre d'homomorphismes non injectifs de ${\displaystyle H}$ dans ${\displaystyle G}$ est au plus ${\displaystyle n^{|V(H)|-1}}$à une constante près, la propriété de Sidorenko implique qu'il y a au moins ${\displaystyle (p^{|E(H)|}-o(1))n^{|V(H)|}}$ copies de ${\displaystyle H}$ dans ${\displaystyle G}$ .

Pour prouver la propriété de Sidorenko, il suffit de démontrer l'inégalité pour les graphes ${\displaystyle G}$. Dans cette section, ${\displaystyle G}$ est un graphe à ${\displaystyle n}$ sommets, de degré moyen ${\displaystyle pn}$. L'entier ${\displaystyle \operatorname {hom} (H,G)}$ est le nombre d'homomorphismes de ${\displaystyle H}$ dans ${\displaystyle G}$. Cette quantité est égale à ${\displaystyle n^{|V(H)|}t(H,G)}$.

Des preuves élémentaires de la propriété de Sidorenko pour certains graphes découlent de l'inégalité de Cauchy-Schwarz ou de l'inégalité de Hölder. D'autres preuves utilisent la théorie spectrale des graphes, en observant que le nombre de chemins de longueur ${\displaystyle \ell }$ d'un sommet ${\displaystyle i}$ à un sommet ${\displaystyle j}$ dans ${\displaystyle G}$ est l'élément d'indice de ligne ${\displaystyle i}$ et de colonne ${\displaystyle j}$ de la matrice ${\displaystyle A^{\ell }}$, où ${\displaystyle A}$ est la matrice d'adjacence de ${\displaystyle G}$.

En fixant deux sommets ${\displaystyle u}$ et ${\displaystyle v}$ de ${\displaystyle G}$, une copie du graphe cycle ${\displaystyle C_{4}}$ de longueur 4 qui a ${\displaystyle u}$ et ${\displaystyle v}$ aux extrémités opposées peut être identifiée en choisissant deux voisins communs (pas nécessairement distincts) de ${\displaystyle u}$ et ${\displaystyle v}$. En dénotant ${\displaystyle \operatorname {codeg} (u,v)}$ le codegré de ${\displaystyle u}$ et ${\displaystyle v}$ (c'est-à-dire le nombre de voisins communs), on obtient par l'inégalité de Cauchy-Schwarz :

${\displaystyle \operatorname {hom} (C_{4},G)=\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)^{2}\geq {\frac {1}{n^{2}}}\left(\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)\right)^{2}}$

La somme compte le nombre de paires de sommets et de leurs voisins communs et est égale au nombre de sommets et de paires de leurs voisins. Donc, et à nouveau par l'inégalité de Cauchy–Schwarz :

${\displaystyle \operatorname {hom} (C_{4},G)\geq {\frac {1}{n^{2}}}\left(\sum _{x\in V(G)}\deg(x)^{2}\right)^{2}\geq {\frac {1}{n^{2}}}\left({\frac {1}{n}}\left(\sum _{x\in V(G)}\deg(x)\right)^{2}\right)^{2}={\frac {1}{n^{2}}}\left({\frac {1}{n}}(n\cdot pn)^{2}\right)^{2}=p^{4}n^{4}}$

Il en résulte que

${\displaystyle t(C_{4},G)={\frac {\operatorname {hom} (C_{4},G)}{n^{4}}}\geq p^{4}}$

comme voulu.

Bien que l'approche par Cauchy – Schwarz pour le cycle ${\displaystyle C_{4}}$ est élégante et élémentaire, elle ne se généralise pas immédiatement à tous les cycles pairs. Cependant, on peut appliquer la théorie spectrale des graphes pour prouver que tous les cycles pairs ${\displaystyle C_{2k}}$ ont la propriété de Sidorenko. Les cycles impairs ne sont pas pris en compte dans la conjecture de Sidorenko car ils ne sont pas bipartis.

En utilisant l'observation sur les chemins, il s'ensuit que ${\displaystyle \operatorname {hom} (C_{2k},G)}$ est la somme des entrées diagonales dans ${\displaystyle A^{2k}}$. Celle-ci est égale à la trace de ${\displaystyle A^{2k}}$, qui à son tour est égale à la somme des puissances d'exposant ${\displaystyle 2k}$des valeurs propres de ${\displaystyle A}$. Si ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \dots \geq \lambda _{n}}$ sont les valeurs propres de ${\displaystyle A}$, alors le théorème min-max de Courant-Fischer implique que

${\displaystyle \lambda _{1}\geq {\frac {\mathbf {1} ^{\intercal }A\mathbf {1} }{\mathbf {1} ^{\intercal }\mathbf {1} }}={\frac {1}{n}}\sum _{x\in V(G)}\deg(x)=pn,}$

où ${\displaystyle \mathbf {1} }$ est le vecteur avec ${\displaystyle n}$ composantes toutes égales à ${\displaystyle 1}$. Mais alors

${\displaystyle \operatorname {hom} (C_{2k},G)=\sum _{i=1}^{n}\lambda _{i}^{2k}\geq \lambda _{1}^{2k}\geq p^{2k}n^{2k}}$

car les valeurs propres d'une matrice symétrique réelle sont réelles. Donc

${\displaystyle t(C_{2k},G)={\frac {\operatorname {hom} (C_{2k},G)}{n^{2k}}}\geq p^{2k}}$

comme voulu.

J. L. Xiang Li et Balázs Szegedy ont introduit en 2011^[4] l'idée d'utiliser l'entropie pour prouver certains cas de la conjecture de Sidorenko. Szegedy a appliqué en 2015 ces idées pour prouver qu'une classe encore plus large de graphes bipartis possède la propriété de Sidorenko^[5]. Alors que la preuve de Szegedy est abstraite et technique, Timothy Gowers et Jason Long ont simplifié l'argument dans des cas particuliers tels que les chemins de longueur ${\displaystyle 3}$^[6]. Dans cette preuve on prend une distribution de probabilité appropriée pour le choix des sommets d'un chemin et on applique l'inégalité de Jensen (c'est-à-dire la convexité) pour en déduire l'inégalité.

Voici une liste de graphes bipartis ${\displaystyle H}$ dont il a été démontré qu'ils possédaient la propriété de Sidorenko. La bipartition de ${\displaystyle H}$ est notée ${\displaystyle A\sqcup B}$.

• Les chaînes ont la propriété de Sidorenko, comme l'ont montré Mulholland et Smith en 1959, donc même avant que Sidorenko ne formule sa conjecture^[7].
• Les arbres ont la propriété de Sidorenko, généralisant le résultat précédent pour les chaînes. Cela a été montré par Sidorenko dans un article de 1991^[8].
• Les cycles de longueur paire ont la propriété de Sidorenko comme déjà indiqué. Sidorenko l'a également démontré dans son article de 1991.
• Les graphes bipartis complets ont la propriété de Sidorenko ; également montré dans l'article de 1991 de Sidorenko.
• Les graphes bipartis avec ${\displaystyle \min\{|A|,|B|\}\leq 4}$ ont la propriété de Sidorenko ; également montré dans l'article de 1991 de Sidorenko.
• Les hypercubes (généralisations de ${\displaystyle Q_{3}}$ ) ont la propriété de Sidorenko, comme l'a montré Hatami en 2008^[9]. Plus généralement, les graphes normatifs (tels qu'introduits par Hatami) ont la propriété de Sidorenko.
• S'il existe un sommet dans ${\displaystyle A}$ qui est voisin de tout sommet dans ${\displaystyle B}$ (ou vice-versa), alors ${\displaystyle H}$ a la propriété de Sidorenko ; démontré par Conlon, Fox et Sudakov en 2010^[10]. Cette preuve utilise la méthode du choix aléatoire dépendant.
• Pour tout graphe biparti ${\displaystyle H}$, il existe un nombre entier positif ${\displaystyle p}$ tel que la ${\displaystyle p}$-explosion de ${\displaystyle B}$ possède la propriété de Sidorenko. Ici la ${\displaystyle p}$-explosion de ${\displaystyle H}$ est formée en remplaçant chaque sommet dans ${\displaystyle B}$ par ${\displaystyle p}$ copies de lui-même, chacun étant connecté à ses voisins d'origine dans ${\displaystyle A}$. Cette propriété a été montré par Conlon et Lee en 2018^[11].
• Certaines approches récursives ont été tentées, qui utilisent une collection de graphes qui ont la propriété de Sidorenko pour créer un nouveau graphe qui a la propriété de Sidorenko. Les principaux progrès dans cette direction ont été faits par Sidorenko dans son article de 1991, par Li et Szegedy en 2011^[4], et par Kim, Lee et Lee en 2013^[12]. L'article de Li et Szegedy a également utilisé des méthodes d'entropie pour prouver la propriété d'une classe de graphes appelés « arbres de réflexion ». L'article de Kim, Lee et Lee a étendu cette idée à une classe de graphes avec une sous-structure arborescente appelée «graphes arrangeables en arbre».

Cependant, il existe des graphes pour lesquels la conjecture de Sidorenko est toujours ouverte. Un exemple est le graphe « bande de Möbius » ${\displaystyle K_{5,5}\setminus C_{10}}$, formé en enlevant un ${\displaystyle 10}$-cycle du graphe biparti complet dont les parties sont de taille ${\displaystyle 5}$ .

László Lovász a prouvé une version locale de la conjecture de Sidorenko, à savoir pour des graphes qui sont "proches" de graphes aléatoires dans un sens de norme de coupe^[13].

Une suite de graphes ${\displaystyle \{G_{n}\}_{n=1}^{\infty }}$ est dite quasi-aléatoire de densité ${\displaystyle p}$ pour une certaine densité ${\displaystyle 0<p<1}$ si, pour chaque graphe ${\displaystyle H}$, on a :

${\displaystyle t(H,G_{n})=(1+o(1))p^{|E(H)|}.}$

La suite de graphes possède ainsi les propriétés du graphe aléatoire d'Erdős-Rényi ${\displaystyle G(n,p)}$. Si la densité des arêtes ${\displaystyle t(K_{2},G_{n})}$ est fixée à ${\displaystyle (1+o(1))p}$, alors la condition implique que la suite de graphes est proche du cas d'égalité dans la propriété de Sidorenko pour chaque graphe ${\displaystyle H}$.

D'après un article de Chung, Graham et Wilson de 1989^[14] sur les graphes quasi-aléatoires, il suffit que le décompte en ${\displaystyle C_{4}}$ corresponde à ce qui serait attendu d'un graphique aléatoire (c'est-à-dire que la condition est vérifiée pour ${\displaystyle H=C_{4}}$ ). L'article cherche également à décrire les graphes ${\displaystyle H}$ en dehors de ${\displaystyle C_{4}}$ qui ont cette propriété. Ces graphes sont appelés graphes forçants car leur décompte contrôle le caractère quasi aléatoire d'une séquence de graphes.

La conjecture de forçage est l'énoncé suivant :

Un graphe ${\displaystyle H}$ est forçant si et seulement s'il est biparti et non arborescente.

Il est facile de voir que si ${\displaystyle H}$ est forçant, alors il est bipartite et n'est pas un arbre. Des exemples de graphes forçants sont les cycles pairs (montré par Chung, Graham et Wilson). Skokan et Thoma^[15] ont montré que tous les graphes bipartis complets qui ne sont pas des arbres sont forçants.

La conjecture de Sidorenko pour les graphes de densité ${\displaystyle p}$ découle de la conjecture de forçage. De plus, la conjecture de forçage montrerait que les graphes qui sont proches de l'égalité dans la propriété de Sidorenko doivent satisfaire des conditions quasi-aléatoires^[16].

• Jacob Fox et Fan Wei, « On the Local Approach to Sidorenko's Conjecture », Electronic Notes in Discrete Mathematics, vol. 61,‎ 2017, p. 459–465 (DOI 10.1016/j.endm.2017.06.074)
• David Conlon, Jeong Han Kim, Choongbum Lee et Joonkyung Lee, « Some advances on Sidorenko's conjecture », Journal of the London Mathematical Society, vol. 98, n^o 3,‎ 2018, p. 593–608 (DOI 10.1112/jlms.12142).
• Ashwin Sah, Mehtaab Sawhney, David Stoner et Yufei Zhao, « A reverse Sidorenko inequality », Inventiones mathematicae, vol. 221, n^o 2,‎ 2020, p. 665–711 (DOI 10.1007/s00222-020-00956-9, arXiv 1809.09462)

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