Rappelons tout d’abord les deux concepts centraux introduits précédemment. Un graphe $G$ est un ensemble de points, appelés nœuds, et de traits appelés arêtes, reliant ces points. Les graphes que nous considérons ici sont dit simples, c’est à dire qu’il n’y a pas d’arête reliant un nœud directement à lui même ; que deux nœuds ne sont reliés que par au plus une arête ; et que toute arête peut être parcourue dans n’importe quel sens. Nous supposerons également que $G$ est connexe, c’est à dire en un seul morceau : on peut aller de n’importe quel nœud à n’importe quel autre en empruntant une ou plusieurs arêtes à la suite.

Dans ce contexte, un chemin est une trajectoire empruntant une succession d’arêtes contigües sur le graphe $G$. Dans la première partie, nous avions vu comment compter tous les chemins allant d’un nœud $n$ à un nœud $n'$ sur un graphe $G$ en empruntant exactement $\ell$ arêtes. Notez que le nœud $n'$ pourrait être le même que $n$ . Néanmoins, notre méthode était récursive et peu explicite. Revoyons la ici en considérant à nouveau le graphe de la première partie :

Nous avons donné des noms aux nœuds—ces noms étant simplement des entiers—afin de pouvoir parler plus précisément de chemins sur ce graphe. Considérons par exemple un chemin $w$ de longueur $\ell=5$ allant du nœud $1$ au nœud $3$, en écrivant $w$ comme la succession des nœuds qu’il visite, $w=132453$, ce qui donne :

Illustration du chemin $w$ sur le graphe. En rouge, les noms des nœuds, en noire une indication de l’ordre dans lequel les arêtes sont parcourues par $w$.

Notre observation était qu’après $\ell-1=4$ arêtes, le chemin arrive sur le nœud $5$ qui est un voisin du nœud $3$ dans le graphe. Clairement, ceci se généralise très bien : pour aller d’un nœud $n$ à un nœud $n'$ en empruntant exactement $\ell$ arêtes, il faut aller de $n$ à un voisin de $n'$ en exactement $\ell-1$ arêtes, la dernière arête étant forcément utilisée pour finir en $n'$. Ce choix est non-ambigu car le graphe $G$ est simple. De plus, n’importe quel chemin qui va de $n$ à un voisin de $n'$ en $\ell-1$ étapes, donne naissance à exactement un et un seul chemin allant de $n$ à $n'$ en $\ell$ étapes.

Il suit que le nombre total $\mathcal{N}_{n\to n'}(\ell)$ de chemins de $n$ à $n'$ empruntant exactement $\ell$ arêtes est égal à la somme totale du nombre de chemins allant de $n$ à n’importe quel voisin de $n'$ en exactement $\ell-1$ étapes. Mathématiquement, ceci s’exprime comme suit :
\[ \mathcal{N}_{n\to n'}(\ell)=\sum_{m:\,\text{voisin de }n'}\mathcal{N}_{n\to m}(\ell-1) \]
De la même manière, nous pouvons exprimer les quantités $\mathcal{N}_{n\to m}(\ell-1)$ en termes de chemins de longueur $\ell-2$ allant de $n$ aux voisins de $m$. En continuant ainsi nous pouvons remonter jusqu’aux chemins de longueur 1, qui sont les arêtes, et que nous savons compter (puisqu’il y en a soit une soit zéro entre deux nœuds) !

Mathématiquement, nous pouvons faire bien mieux en encodant le graphe dans un tableau de chiffres, appelé matrice. L’idée est la suivante : donnons des noms d’entiers de 1 à $N$, aux nœuds du graphe comme dans le dessin plus haut. Créons maintenant un tableau à $N$ lignes et $N$ colonnes, autant que le nombre de nœuds dans le graphe. Dans la cellule du tableau qui se trouve à la ligne $i$, colonne $j$, nous mettons « 1 » si il y a une arête entre le nœud $i$ et le nœud $j$ et sinon nous mettons 0. Voici un exemple de ce que nous obtenons :

Le tableau $A_G$ à droite est appelé matrice d’adjacence du graphe $G$, à gauche. La cellule du tableau qui se trouve à la ligne $i$ colonne $j$ est désignée $(A_G)_{ij}$, par exemple ici $(A_G)_{12}=1$ et $(A_G)_{36}=0$. Cette matrice encode toute l’information sur le graphe $G$, comme en témoigne le fait que l’on peut aisément redessiner $G$ à partir de $A_G$. Vous pouvez essayer vous-même ! Par exemple, quel est le graphe qui correspond à la matrice d’adjacence $A_{G'}$ donnée ci dessous ?

Le nombre $\mathcal{N}_{i\to j}(\ell)$ de chemins de longueur $\ell$ d’un nœud $i$ à un nœud $j$ sur $G$ est maintenant facilement accessible de manière rigoureuse. Mais avant, rappelons la définition du produit entre matrices :

Ceci signifie que la cellule située à la ligne $i$, colonne $j$ de la matrice produit $A.B$ est égale à la somme sur $k$ allant de 1 à $N$ des produits des entrées $A_{ik}$ par $B_{kj}$. Avec le produit matriciel vient également la notion de puissance : par exemple, $A^1=A$, $A^2:=A\cdot A$, $A^3=A\cdot A\cdot A$ et ainsi de suite.

Avec ces définitions nous avons :

C’est un résultat qui est quand même beau ! Grâce à celui-ci, nous passons des graphes à un domaine des mathématiques appelé l’algèbre linéaire, qui étudie les matrices et leurs propriétés. Les algébristes ont développé de nombreuses techniques pour évaluer les puissances d’une matrice, de sorte que $A_G^\ell$ est tout à fait accessible. Plus précisément, il est possible de calculer $A_G^\ell$ en faisant un nombre d’opérations basiques (multiplications et additions entre nombres) de l’ordre de $N^3$ [1]. Nous savons donc compter les chemins et ce à la fois théoriquement (avec la formule) et concrètement du moment que $N$ n’est pas trop grand ! D’ailleurs, avant de passer à la preuve du théorème, vous pouvez vous amuser à compter des chemins de cette manière en reprenant par exemple la matrice d’adjacence présentée plus haut et en calculant ses puissances en ligne, comme ici.

Forts de ce théorème et de l’arsenal mathématique offert par l’algèbre linéaire, nous pouvons faire de nombreuses choses jusqu’ici impossible. Par exemple nous pouvons estimer le nombre de chemins de longueur $\ell$ lorsque $\ell$ tend vers l’infini, ce que nous dénoterons $\ell\to\infty$. En effet, un résultat dit (sous certaines conditions que l’on suppose ici satisfaites) que pour une matrice $A$, les quantités $(A^k)_{ij}$ sont de l’ordre de $c_{ij}\lambda^k$ lorsque $k$ tend vers l’infini. Ici les $c_{ij}$ sont des constantes positives et $\lambda$ est un nombre réel que l’on peux calculer aisément, appelé plus grande valeur propre de la matrice $A$. Puisque notre théorème ci-dessus relie le nombre de chemins sur $G$ et les puissances de sa matrice d’adjacence, nous obtenons ainsi l’estimation suivante lorsque $\ell\to\infty$
\[ \mathcal{N}_{i\to j}(\ell)\sim c_{ij}\lambda_G^\ell, \]
avec $\lambda_G$ la plus grande valeur propre de la matrice d’adjacence $A_G$. À votre avis quelle information est portée par les constantes $c_{ij}$ ?

Retour en force des problèmes

Les chemins nous donnent de nombreux outils pour analyser les graphes et l’algèbre linéaire fournit le contexte mathématique des calculs. Par exemple, dans un graphe simple, le degré d’un nœud $n$ est égal au nombre de cycles de longueur 2 partant de $n$ puisque ces cycles sont chacun un aller-retour sur une arête. Nous retrouvons donc immédiatement l’information du nœud qui a le plus grand nombre de voisins en regardant les entrées $(A_G^2)_{ii}$. De même, dans un graphe simple, nous avions vu dans la deuxième partie que le nombre de triangles auxquels un nœud $n$ participe est égal au nombre de cycles de longueur 3 divisé par 2. Avec la notation matricielle, ceci est $ \frac{1}{2}(A_G^3)_{nn}, $

Quant au nombre total de triangles dans le graphe, il est égal à la somme sur tous les nœuds du nombre de triangles auxquels chaque nœud participe, divisé par 3. Cette division par 3 intervient puisqu’il y a 3 nœuds dans un triangle et donc un seul et même triangle est compté trois fois dans cette somme ! Ces observations nous donnent ainsi, en notation matricielle,
\[ \mathcal{N}_{\text{Triangles}} = \frac{1}{6} \sum_{n:\,\text{noeud}} (A_G^3)_{nn} \]
La somme ci-dessus est la somme des cellules sur la diagonale de la matrice $A_G^3$. On appel ceci la trace de $A_G^3$ et l’on note $\sum_{n:\,\text{noeud}} (A_G^3)_{nn}=\text{Tr}(A_G^3)$. On peut donc donner le résultat suivant, de plus en plus élégant :
\[ \mathcal{N}_\text{Triangles} = \frac{1}{6} \text{Tr}(A_G^3). \]
Et si on reprend le graphe :

nous calculons qu’il comporte $\mathcal{N}_{\text{triangles}}=9$ triangles sans même le regarder, ce qui est quand même puissant !

Continuons ! Par exemple, pour compter les quadrilatères dans un graphe, considérons les cycles de longueur 4. Parmi ceux qui peuvent exister, il y a des quadrilatères comme $1\to 7\to 4\to 5\to 1$ mais aussi des aller-retours comme $1\to 3\to 1 \to 3\to 1$ et $1\to 3\to 5\to 3\to 1$. Pour dénombrer les quadrilatères, il nous faut donc enlever ces aller-retours du décompte de tous les cycles de longueur 4. Puisqu’un ’double’ aller-retour comme $1\to 3\to 1 \to 3\to 1$ emprunte deux fois la même arête, il y a autant de tels cycles que d’arêtes.
Pour l’aller-retour $1\to 3\to 5\to 3\to 1$, observons qu’il passe par deux arêtes distinctes qui se touchent, ce qui, sur le graphe, correspond à la configuration de noeuds $\bullet\!—\!\bullet\!— \!\bullet$. Il y a donc autant de tels cycles que de telles configurations. À partir de maintenant, nous dénoterons par $\mathcal{N}_{\bullet\!—\!\bullet\!—\!\bullet}$ le nombre de ces configurations.

Ceci nous conduit à un autre joli résultat :
\[ \mathcal{N}_{\text{Carrés}}=\frac{1}{8}\mathrm{Tr}(A^4)- \frac{1}{2}\mathcal{N}_{\bullet\!—\!\bullet\!— \!\bullet}-\frac{1}{4}\mathcal{N}_{\text{arêtes}} \]
Ici, le premier terme compte tous les cycles de longueur 4 et les deux suivants enlèvent les aller-retours, laissant ainsi uniquement les carrés.
Les facteurs $1/8$, $1/2$ et $1/4$ prennent en compte les orientations et le nombre de points de départ possibles pour chaque type de cycle. Par exemple, un cycle comme $1\to 7\to 4\to 5\to 1$ correspond au même carré que le cycle $1\to 5\to 4\to 7\to 1$, il faut donc diviser le nombre de cycles par 2 pour prendre en compte notre indifférence quant au sens de parcours du cycle. De plus, il nous faut encore diviser par 4 puisque nous sommes aussi indifférents au point de départ, $1\to 7\to 4\to 5\to 1$ et $7\to 4\to 5\to 1 \to 7$ correspondant bien au même carré.

Comme expliqué dans la deuxième partie de ce trio d’articles, la formule devient donc un peu plus compliquée que pour les triangles mais reste tout à fait calculable puisque nous avons trois termes, chacun étant accessible via l’algèbre linéaire. Malheureusement nos nouvelles armes mathématiques—bien que très utiles et permettant des calculs concrets sur ordinateurs—ne changent rien à l’observation fondamentale de la partie 2 selon laquelle compter les cycles auto-évitants (triangles, carrés, pentagones, hexagones...) de longueur $\ell$ est de plus en plus difficile lorsque la longueur considérée augmente.

Deux conjectures

Afin d’éluder cette difficulté, nous avions tenté d’ajouter des contraintes sur le graphe $G$ dans l’espoir que celle-ci s’estompe dans un cadre plus restreint. Pour cela, nous proposions de considérer uniquement les graphes pour lesquels tous les nœuds sont identiques, c’est à dire indistinguables (ils ont donc tous le même degré, le même nombre de second voisins, participent au même nombre de triangles etc., toutes les quantités auxquelles nous pourrions penser sont identiques). En outre, dans l’espoir de simplifier encore les choses, nous demandions à ce que ce graphe soit planaire, c’est à dire que nous pouvons le dessiner sur une feuille sans qu’aucune arête ne se croise. Voici ce que nous obtenons :

Malgré toutes ces simplifications, aucune formule n’a été trouvée dénombrant exactement les polygones auto-évitants (c’est à dire les cycles dont tous les nœuds sont distincts hormis à la dernière étape lorsque le cycle revient sur son point de départ). Il n’est possible de les compter qu’en les trouvant par ordinateur. Redonnons ici quelques résultats obtenus de cette manière, en prenant pour exemple le réseau carré :

Nombre de polygones auto-évitants sur le réseau carré.

Illustration des 8 polygones auto-évitants de longueur 4 sur le réseau carré. Le nœud de départ fixé est ici illustré en rouge. Tout comme le tableau de dénombrement plus haut, ici nous avons gardé le facteur d’orientation, c’est à dire que par exemple les carrés $1\to2\to3\to4\to1$ et $1\to4\to3\to2\to1$ comptent comme deux polygones différents. Divisez les nombres par 2 pour enlever ce facteur.

Puisque trouver une formule comptant exactement les polygones auto-évitants dans le cadre restreint des réseaux planaires est pour le moment impossible, essayons simplement d’estimer le nombre de tels polygones de longueur $\ell$ lorsque $\ell$ tend vers l’infini. L’espoir est qu’une telle estimation doit être plus simple à obtenir qu’un dénombrement exact. En outre, nous avons déjà répondu à la question équivalente sur les chemins à l’aide de la plus grande valeur propre de la matrice d’adjacence du graphe. Peut-être pouvons-nous obtenir un résultat similaire pour les polygones auto-évitants ? Pour avoir une idée de ce qu’il faudrait démontrer, regardons de plus près les nombres produits par ordinateur. Ceux-ci nous mènent à la conjecture suivante :

La constante $\mu$, appelée constante de connectivité, dépend du réseau mais on sait uniquement prouver que cette constante existe. En effet, en dehors du seul cas du réseau hexagonal où $\mu_{\text{Hexagonal}}=\sqrt{2+\sqrt{2}}$ est connue [2], la valeur exacte de $\mu$ sur les autres réseaux nous échappe encore. Voici quelques évaluations numériques obtenues par ordinateur :
\[ \mu_{\text{Triangulaire}}=4.15079(4),\quad\mu_{\text{Kagomé}}=2,5606(2),\quad\mu_{\text{Carré}}=2,63815853034(10), \]
Les chiffres entre parenthèses sont incertains. Le mystère s’épaissit encore un peu plus en observant que $1/\mu_{\text{Carré}}\simeq 0,14368062927(1)$ est indistinguable d’une des solutions de l’équation polynomiale d’inconnue $x$ :
\[ 581x^4 + 7x^2 − 13 = 0. \]

Notons tout de même qu’une étude récente porte un doute sur cette observation, sans toutefois l’invalider complètement. Peut-être que les deux nombres sont non-identiques mais très proches par hasard ? [3] En tout cas, la Conjecture 1 ci-dessus est ouverte depuis environ 70 ans...

Peut-être pourrions-nous mieux comprendre ce qui se passe en posant la même question mais pour les chemins auto-évitants plutôt que pour les polygones (rappelons qu’un chemin auto-évitant ne repasse jamais par le même nœud et ne revient pas non plus à son point de départ). Dans ce cas, nous fixons encore un nœud de départ et nous comptons tous les chemins de longueur $\ell$ partant de ce nœud et qui ne repassent jamais deux fois par le même nœud. On arrive alors à la conjecture suivante :

Ici, la constante $\mu$ est la même que dans la conjecture précédente, un résultat loin d’être évident. Mais dans les deux conjectures, ce sont surtout les exposants $-5/2$ et $11/32$ qui sont intrigants, car ceux-ci ne dépendent pas du réseau : si les conjectures disent vraies ces exposants sont universels.

Des expériences numériques et des résultats théoriques montrent que ces exposants dépendent au moins de la dimension du réseau, c’est à dire ici du fait que nous avons pu tracer le graphe sur un plan sans jamais croiser deux arêtes. Mais la preuve que tous les réseaux planaires donnent bien les mêmes exposants et que ceux-ci sont $-5/2$ et $11/32$ nous échappe encore. Aucun nom particulier n’est attaché aux deux conjectures ci-dessus qui n’ont émergé que progressivement à partir des travaux du chimiste W. Orr qui, en 1947, a le premier attiré l’attention sur les polygones auto-évitants des réseaux planaires. Le domaine de recherche est toujours actif, les travaux des médaillés Fields Stanislav Smirnov, Wendelin Werner et du prix Wolf 2019 Gregory Lawler ayant porté directement ou indirectement sur les deux conjectures ci-dessus.

P.S :
Je remercie Shalom Eliahou et Bruno Martin qui m’ont proposé d’écrire un article dans Images des mathématiques et m’ont aidé lors de sa rédaction. Merci également aux relecteurs Cidrolin, Victoria Cantoral et Mathieu Mourichoux pour leurs observations et questions et à Clément Caubel pour son aide éditoriale.