Chemin auto-évitant

Considérant ici des chemins dans des graphes sommets-transitifs, on définit la longueur d'un CAE comme le nombre de sommets rencontrés (départ excepté).

Le calcul du nombre ${\displaystyle c_{n}}$ de CAE de longueur ${\displaystyle n}$ dans réseau donné et partant d'un nœud donné est un problème informatique classique, mais on ne connaît actuellement aucune formule exacte l'exprimant [5] - [6].

Voici quelques exemples :

Type de réseau	Schémas	Premières valeurs de ${\displaystyle c_{n}}$	Référencement dans l'OEIS	Encadrement simple prouvé
Réseau carré		${\displaystyle 1,4,12=4\times 3,36=12\times 3,}$${\displaystyle 100=3\times 36-8,284,...}$	suite A001411 de l'OEIS	${\displaystyle 2^{n}\leqslant c_{n}\leqslant 4.3^{n-1}}$
Réseau carré orienté, type "Manhattan"		${\displaystyle 1,2,4=2\times 2,8=4\times 2,14,26,48,88,...}$	suite A117633 de l'OEIS	${\displaystyle ({\sqrt {2}})^{n}\leqslant c_{n}\leqslant 2^{n}}$
Réseau carré orienté "en L"		${\displaystyle 1,2,4=2\times 2,8=4\times 2,12,20,32,52,...}$	suite A322419 de l'OEIS	${\displaystyle ({\sqrt {2}})^{n}\leqslant c_{n}\leqslant 2^{n}}$
Réseau hexagonal (ou "en nid d'abeilles")		${\displaystyle 1,3,6=3\times 2,12=6\times 2,24=12\times 2,}$${\displaystyle 48=24\times 2,90=48\times 2-8,174,...}$	suite A001668 de l'OEIS	${\displaystyle ({\sqrt {2}})^{n}\leqslant c_{n}\leqslant 3.2^{n-1}}$
Réseau triangulaire		${\displaystyle 1,6,30=6\times 5,138=30\times 5-12,}$${\displaystyle 618,2730,...}$	suite A001334 de l'OEIS	${\displaystyle 2^{n}\leqslant c_{n}\leqslant 6.5^{n-1}}$
Réseau triangulaire orienté		${\displaystyle 1,3,9=3\times 3,21=9\times 3-6,51,123,...}$	suite A272265 de l'OEIS	${\displaystyle ({\sqrt {2}})^{n}\leqslant c_{n}\leqslant 3^{n}}$
Réseau cubique		${\displaystyle 1,6,30=6\times 5,150=30\times 5,}$${\displaystyle 726=150\times 5-24,3534,16926,...}$	suite A001412 de l'OEIS	${\displaystyle 3^{n}\leqslant c_{n}\leqslant 6.5^{n-1}}$
Réseau cubique centré		${\displaystyle 1,8,56=8\times 7,392=56\times 7,2648,...}$	suite A001666 de l'OEIS	${\displaystyle 4^{n}\leqslant c_{n}\leqslant 8.7^{n-1}}$

Comme les CAE à ${\displaystyle n+m}$ nœuds peuvent être décomposés en deux CAE à ${\displaystyle n}$ et ${\displaystyle m}$ nœuds mis bout à bout, on a l'inégalité ${\displaystyle c_{n+m}\leqslant c_{n}c_{m}}$ d'où la sous-additivité de la suite ${\displaystyle (\ln c_{n})}$, et en utilisant le lemme sous-additif on est assuré de l'existence du nombre ${\displaystyle \mu =\lim _{n\to \infty }c_{n}^{\frac {1}{n}}}$, appelé constante de connectivité du réseau, ainsi que de l'inégalité ${\displaystyle c_{n}\geqslant \mu ^{n}}$ (théorème de John_Hammersley).

La valeur exacte ${\displaystyle \mu ={\sqrt {2+{\sqrt {2}}}}\approx 1,847759}$ (cf. suite A179260 de l'OEIS ) n'est connue que pour le réseau hexagonal (résultat dû aux mathématiciens français et russe Hugo Duminil-Copin et Stanislav Smirnov, Médaille Fields 2010)[7]. On conjecture de plus que ${\displaystyle c_{n}\sim c\mu ^{n}n^{\gamma }}$ avec ${\displaystyle \gamma ={\frac {11}{32}}}$ pour tous les réseaux plans réguliers (propriété d'universalité). Le nombre ${\displaystyle \gamma }$ est associé à la probabilité que deux CAE mis bout à bout donne un CAE, probabilité valant ${\displaystyle {\frac {c_{2n}}{c_{n}^{2}}}\sim {\frac {c'}{n^{\gamma }}}}$.

Pour les réseaux carré et triangulaire, on ne connait que des approximations de la constante μ, et on pense même qu'elle n'est pas algébrique.

De plus, déterminer le nombre c_n est conjecturé être un problème NP-difficile.

Le nombre ${\displaystyle p_{n}}$ de polygones auto-évitants ne possède lui-aussi pas de formule simple. Dans le cas du réseau carré, voir la suite A010566 de l'OEIS (${\displaystyle p_{n}=0}$ pour n impair dans ce cas).

Les chemins auto-évitants ont également été étudiés dans le contexte de la théorie des réseaux[8]. Il est alors d'usage de traiter le CAE comme un processus dynamique (à chaque étape un marcheur aléatoire saute d'un nœud à un nœud voisin). La marche se termine lorsque le marcheur atteint un cul-de-sac. Il a été récemment constaté que sur les réseaux d'Erdős–Rényi, la distribution des longueurs de tels CAE croissant dynamiquement peut être calculée analytiquement : elle suit la loi de probabilité de Gompertz[9].

Considérons le système de mesure uniforme des CAE de longueur n dans le plan tout entier. On ne sait pas actuellement si la limite de la mesure uniforme quand n → ∞ induit une mesure sur le plan. Cependant, Harry Kesten a démontré qu'une telle mesure existe pour les CAE dans le demi-plan. Une question importante impliquant les CAE est l'existence et l'invariance conforme de la limite d'échelle, c'est-à-dire la limite quand la longueur du chemin tend vers l'infini et le maillage du réseau tend vers zéro. La limite d'échelle du CAE est conjecturée être décrite par l'évolution de Schramm–Loewner avec le paramètre κ = 8/3.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Self-avoiding walk » (voir la liste des auteurs).

• Conférence de Hugo Duminil-Copin.
• Article de Vincent Beffara.
• Page d'Alain Esculier avec tracé des chemins et programme maple correspondant.
• Weisstein, Eric W. "Self-avoiding walk". MathWorld.
• Texte en anglais avec Applet Java.
• Programme python pour simuler les CAE