Que sait-on compter sur un graphe ? Partie 3

Matrices et chemins

Pista negra El 21 diciembre 2020  - Escrito por  Pierre-Louis Giscard Ver los comentarios

Dans les deux premiers articles de ce trio sur les chemins dans les graphes, nous avons vu qu’il est possible de compter tous les chemins selon leur longueur. De plus, le problème, en apparence plus simple, du dénombrement des chemins ne repassant jamais par le même point s’est avéré beaucoup plus difficile à résoudre. Dans cette dernière partie nous revenons sur nos résultats avec des armes mathématiques, ce qui nous amènera à deux célèbres conjectures portant sur les chemins ne repassant jamais par le même point.

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 ?

Cliquez pour voir le graphe $G'$.


Graphe $G'$ dont la matrice d’adjacence est $A_{G'}$.

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:

Definition 2 : Soit $N\geq 1$ un entier. Soit deux matrices $A$ et $B$ ayant chacune $N$ lignes et $N$ colonnes. Posons que ces matrices se multiplient entre elles comme ceci: \[ \begin{equation} (A\cdot B)_{ij} =\sum_{k=1}^N A_{ik}\times B_{kj}. \label{prodmat} \end{equation} \]

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:

Théorème 1 : Soir $G$ un graphe comportant $N\geq 1$ nœuds, que nous nommons par des entiers de 1 à N. Soit $A_G$ la matrice d’adjacence de $G$. Alors le nombre $\mathcal{N}_{i\to j}(\ell)$ de chemins de longueur $\ell$ allant du nœud $i$ au nœud $j$ sur $G$ est l’entrée en ligne $i$ colonne $j$ de la matrice $A_G$ à la puissance $\ell$: \[ \mathcal{N}_{i\to j}(\ell)=(A_G^\ell)_{ij}, \]

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.

Cliquez pour voir la preuve de ce résultat.

Revenons sur notre résultat précédent:
\[ \mathcal{N}_{i\to j}(\ell)=\sum_{k_1:\,\text{voisin de }j}\mathcal{N}_{i\to k_1}(\ell-1). \]
Puisque $(A_G)_{ij}=1$ si $i$ et $j$ sont voisins et 0 sinon, nous pouvons réécrire ceci comme une simple somme sur tous les nœuds du graphe,
\[ \mathcal{N}_{i\to j}(\ell)=\sum_{k_1:\,\text{nœud}}\mathcal{N}_{i\to k_1}(\ell-1)\times(A_G)_{k_1j}. \]
Si l’on recommence pour $\mathcal{N}_{i\to k_1}(\ell-1)$, il vient
\[ \mathcal{N}_{i\to j}(\ell)=\sum_{k_1:\,\text{nœud}}\sum_{k_2:\,\text{nœud}}\mathcal{N}_{i\to k_2}(\ell-2)\times(A_G)_{k_2k_1}\times(A_G)_{k_1j}, \]
Simplifions maintenant notre notation: comme les nœuds sont numérotés de 1 à N, une somme sur les nœuds $k_1$ est une somme où $k_1$ va de 1 à $N$. Comme c’est aussi le cas pour $k_2$, nous écrivons
\[ \mathcal{N}_{i\to j}(\ell)= \sum_{k_1, k_2=1}^N\mathcal{N}_{i\to k_2}(\ell-2)\times(A_G)_{k_2k_1}\times(A_G)_{k_1j}. \]
Maintenant, continuons notre raisonnement comme ci-dessus jusqu’à arriver aux chemins de longueur 1 partant de $i$, qui sont juste les arêtes attachées à $i$
\[ \begin{equation} \mathcal{N}_{i\to j}(\ell)=\sum_{k_1, k_2, \cdots, k_{\ell-1}=1}^N(A_G)_{ik_{\ell-1}}\times \cdots\times(A_G)_{k_3k_2} \times(A_G)_{k_2k_1}\times(A_G)_{k_1j}. \label{NL} \end{equation} \]
Par exemple, les chemins de longueur $\ell= 2$ sont comptés par
\[ \mathcal{N}_{i\to j}(2)=\sum_{k_1=1}^N(A_G)_{ik_1}\times(A_G)_{k_1j}, \]
et pour les chemins de longueur $\ell=3$,
\[ \mathcal{N}_{i\to j}(3)=\sum_{k_1, k_2=1}^N(A_G)_{ik_2}\times(A_G)_{k_2k_1}\times (A_G)_{k_1j}. \]

C’est un bon début: les formules ci-dessus ont l’avantage de ne plus faire appel qu’à des sommes sur tous les nœuds du graphe, de sorte que nous n’avons plus besoin de surveiller qui est voisin de qui. Mais nous pouvons rendre ces résultats encore bien plus concis, en faisant appel à la multiplication entre matrices.

Avec la définition $\ref{prodmat}$ du produit matriciel, nous observons en particulier que la matrice d’adjacence multipliée avec elle-même donne:
\[ (A_G^2)_{ij}=(A_G\cdot A_G)_{ij} = \sum_{k_1=1}^N(A_G)_{ik_1}(A_G)_{k_1j}, \]
et
\[ (A_G^3)_{ij}=(A_G\cdot A_G\cdot A_G)_{ij} = \sum_{k=1}^N\sum_{k_2=1}^N (A_G)_{ik_1}(A_G)_{k_1k_2}(A_G)_{k_2j}. \]
À y regarder de plus près, ceci correspond exactement à nos formules donnant $\mathcal{N}_{i\to j}(2)$ et $\mathcal{N}_{i\to j}(3)$. De même, si l’on regarde maintenant $A_G^\ell$, nous obtenons exactement la formule $\ref{NL}$ donnant $\mathcal{N}_{i\to j}(\ell)$. Plus précisément, $\mathcal{N}_{i\to j}(\ell)$ est égal à l’entrée en ligne $i$, colonne $j$ du produit de $A_G$ avec elle-même $\ell$ fois.

Pour ceux qui ont suivit la preuve jusqu’au bout, félicitations! Sachez aussi qu’il existe une approche plus concise pour prouver notre résultat. Cette approche, vue en terminale ou première année de licence scientifique, s’appelle la preuve par récurrence.

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}$ ?

Cliquez ici pour voir la réponse. Indice: pensez Partie 1 - PageRank !

Dans la première partie de ce trio d’articles, nous avions vu qu’il est intéressant de classer les nœuds d’un graphe selon le nombre de cycles de grandes longueurs partant de chaque nœud. C’est même l’idée fondamentale du classement effectué par l’algorithme PageRank de Google sur le graphe formé par les sites internet et leurs liens hypertextes.
Or, nous savons maintenant que le nombre de cycles partant d’un nœud $i$ est estimé par
\[ \mathcal{N}_{i\to i}(\ell) \sim c_{ij}\lambda_G^\ell, \]
lorsque $\ell$ tend vers l’infini. En particulier, cela signifie que $\mathcal{N}_{i\to i}(\ell)/\lambda_G^\ell$ tend vers $c_{ij}$ lorsque $\ell$ tend vers l’infini. En comparant, puis en classant les constantes positives $c_{ij}$, on peut donc concrètement classer les nœuds du graphe $G$ comme le ferait PageRank !

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.

Cliquez pour voir une formule explicite donnant $\mathcal{N}_{\bullet\!—\!\bullet\!—\!\bullet}$

Le nombre $\mathcal{N}_{\bullet\!—\!\bullet\!—\!\bullet}$ est aussi donné par une formule explicite. En effet, si l’on se place sur le nœud du milieu dans la configuration $\bullet\!—\!\bullet\!—\!\bullet$, on voit que l’on peut former autant de telles configurations qu’il y a de façons de choisir deux arêtes parmi toutes celles touchant le nœud. Le nombre de telles arêtes étant le degré $d$ du nœud, il vient que le nombre de configurations $\bullet\!—\!\bullet\!—\!\bullet$ auxquelles un noeud $i$ de degré $d_i$ participe est $\binom{d_i}{2}$. Et ainsi \[\mathcal{N}_{\bullet\!—\!\bullet\!—\!\bullet}=\sum_{i:\, \text{nœud}}\binom{d_i}{2}.\]
Rappelons qu’en outre $d_i=(A_G^2)_{ii}$ est facilement accessible.

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é:

Longueur $\ell$ $\ell=4$ $\ell=6$ $\ell=8$ $\ell=10$ $\ell=12$ $\ell=14$ $\ell=16$
$\mathcal{N}(\ell)$ 8 24 112 560 2976 16464 94016
Longueur $\ell$ $\ell=18$ $\ell=20$ $\ell=22$ $\ell=24$ $\ell=26$ $\ell=28$ $\ell=30$
$\mathcal{N}(\ell)$ 549648 3273040 19781168 121020960 748039552 4664263744 29303071680

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:

Conjecture 1 : Le nombre de polygones auto-évitants de longueur $\ell$ sur un réseau comme décrit ci-dessus grandit comme $\mathcal{N}(\ell)\sim \mu^\ell \ell^{-5/2}$ lorsque $\ell\to\infty$.

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:

Conjecture 2 : Le nombre de chemins auto-évitants de longueur $\ell$ sur un réseau comme décrit ci-dessus grandit comme $\mathcal{N}(\ell)\sim \mu^\ell \ell^{11/32}$ lorsque $\ell\to\infty$.

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.

Article édité par Shalom Eliahou

Notas

[1Ceci ne dépend pas de $\ell$ car nous considérons ici la situation où $N$ est grand et $\ell$ est bien plus petit que $N^2$. Pour aboutir à ce résultat, il faut utiliser la décomposition spectrale de $A_G$, une technique d’algèbre linéaire permettant de calculer $A_G^\ell$ sans faire les $\ell-1$ produits de la matrice $A_G$ avec elle-même explicitement. Plus précisément, il est suffisant de prendre les puissances $\ell$ de $N$ nombres complexes $\lambda_1,\cdots, \lambda_N$, appelés valeurs propres de $A_G$, ce qui nécessite $N\ell$ opérations basiques. En comparaison, la décomposition spectrale de $A_G$ requiert de l’ordre de $N^3$ opération basiques. Pour $N$ grand, $N^3$ est bien plus grand que $N\ell$ tant que $\ell$ n’est pas de l’ordre de $N^2$, et nous avons bien un coût de calcul total $N^3+N\ell\sim N^3$ indépendant de $\ell$.

[2Nous devons ce résultat à H. Duminil-Copin et S. Smirnov, voyez cette vidéo pour une présentation de ce résultat par Duminil-Copin lui même. Malheureusement la technique de preuve utilisée est très spécifique au réseau hexagonal et ne peut s’étendre aux autres cas.

[3Le polynôme $581x^4 + 7x^2 − 13$ n’a aucune justification connue. Il a été trouvé par ordinateur en essayant tous les polynômes de faible degré à coefficient entiers relativement petits dont $1/\mu$ serait une racine. La motivation derrière une telle recherche provient de problèmes similaires mais beaucoup plus simples pour lesquels nous savons que de tels polynômes fournissent des solutions.

Comparte este artículo

Para citar este artículo:

Pierre-Louis Giscard — «Que sait-on compter sur un graphe ? Partie 3» — Images des Mathématiques, CNRS, 2020

Comentario sobre el artículo

Dejar un comentario

Foro sólo para inscritos

Para participar en este foro, debe registrarte previamente. Gracias por indicar a continuación el identificador personal que se le ha suministrado. Si no está inscrito/a, debe inscribirse.

Conexióninscribirse¿contraseña olvidada?

La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.