Chemin auto-évitant
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Self_avoiding_walk.svg/200px-Self_avoiding_walk.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/a/a9/Chemin_auto-%C3%A9vitant.gif)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Autoevitant_hexag.gif/220px-Autoevitant_hexag.gif)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/93/%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg/220px-%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg)
En mathématiques, un chemin auto-évitant (CAE), ou marche auto-évitante, est un chemin dans un réseau ne passant jamais par le même sommet ; lorsqu'il est fermé, on parle de polygone auto-évitant (PAE). Pour le graphe infini associé au réseau, les notions de CAE et de PAE correspondent à celles de chaînes et de cycles.
Les CAE ont été introduits en 1948 par le chimiste prix Nobel Paul Flory[1] dans le but de modéliser le comportement des polymères plongés dans un solvant. Depuis cette introduction, des physico-chimistes ont proposé de nombreuses conjectures qui ont été confirmées par des simulations numériques, mais peu d'entre elles ont été démontrées mathématiquement.
Un CAE de longueur infinie a une structure fractale[2],[3]. On démontre qu'il a une dimension fractale égale à 4/3 dans le cas plan, 5/3 en dimension 3, et 2 en dimension . Cette dimension est la limite supérieure de la dimension critique au-dessus de laquelle le volume exclu est négligeable. Un CAE qui ne satisfait pas la condition de volume exclu a été récemment étudié pour modéliser explicitement la géométrie de surface résultant de l'expansion d'un CAE[4].
Les propriétés des CAE ne pouvant pas être obtenues analytiquement, on utilise des simulations numériques. L'algorithme du pivot, méthode classique concernant les simulations de chaîne de Markov, est utilisé pour la mesure uniforme des CAE de longueur n. Il consiste à prendre un CAE, à choisir au hasard un point sur ce chemin, puis à appliquer une opération de symétrie (rotation ou/et réflexion) sur la partie du chemin située après ce point pour créer un nouveau chemin et à continuer jusqu'à ce que le chemin obtenu soit auto-évitant.
Propriétés combinatoires
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 de CAE de longueur 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 | Référencement dans l'OEIS | Encadrement simple prouvé |
---|---|---|---|---|
Réseau carré | suite A001411 de l'OEIS | |||
Réseau carré orienté, type "Manhattan" | ![]() | suite A117633 de l'OEIS | ||
Réseau carré orienté "en L" | ![]() | suite A322419 de l'OEIS | ||
Réseau hexagonal (ou "en nid d'abeilles") | suite A001668 de l'OEIS | |||
Réseau triangulaire | suite A001334 de l'OEIS | |||
Réseau triangulaire orienté | ![]() | suite A272265 de l'OEIS | ||
Réseau cubique | suite A001412 de l'OEIS | |||
Réseau cubique centré | suite A001666 de l'OEIS |
Comme les CAE à nœuds peuvent être décomposés en deux CAE à et nœuds mis bout à bout, on a l'inégalité d'où la sous-additivité de la suite , et en utilisant le lemme sous-additif on est assuré de l'existence du nombre , appelé constante de connectivité du réseau, ainsi que de l'inégalité (théorème de John_Hammersley).
La valeur exacte (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 avec pour tous les réseaux plans réguliers (propriété d'universalité). Le nombre est associé à la probabilité que deux CAE mis bout à bout donne un CAE, probabilité valant .
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 cn est conjecturé être un problème NP-difficile[réf. nécessaire].
Le nombre 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 ( pour n impair dans ce cas).
Sur les réseaux
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].
Limites
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.
Références
- (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).
- ↑ P. Flory, Principles of Polymer Chemistry, Cornell University Press, , 672 p. (ISBN 978-0-8014-0134-3, lire en ligne)
- ↑ S. Havlin, D. Ben-Avraham, « New approach to self-avoiding walks as a critical phenomenon », J. Phys. A, vol. 15, , p. 321 (DOI 10.1088/0305-4470/15/6/013, Bibcode 1982JPhA...15L.321H, lire en ligne)
- ↑ S. Havlin, D. Ben-Avraham, « Theoretical and numerical study of fractal dimensionality in self-avoiding walks », Phys. Rev. A, vol. 26, no 3, , p. 1728 (DOI 10.1103/PhysRevA.26.1728, Bibcode 1982PhRvA..26.1728H, lire en ligne)
- ↑ A. Bucksch, G. Turk, J.S. Weitz, « The Fiber Walk: A Model of Tip-Driven Growth with Lateral Expansion », PLOS ONE, vol. 9, no 1, , e85585 (PMID 24465607, PMCID 3899046, DOI 10.1371/journal.pone.0085585, Bibcode 2014PLoSO...985585B, arXiv 1304.3521, lire en ligne)
- ↑ Hayes B, « How to Avoid Yourself », American Scientist, vol. 86, no 4, jul–aug 1998, p. 314 (DOI 10.1511/1998.31.3301, lire en ligne)
- ↑ Liśkiewicz M, Ogihara M et Toda S, « The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes », Theoretical Computer Science, vol. 304, nos 1–3, , p. 129–56 (DOI 10.1016/S0304-3975(03)00080-X, lire en ligne)
- ↑ Hugo Duminil-Copin et Stanislav Smirnov, « The connective constant of the honeycomb lattice equals sqrt(2+sqrt 2) », Annals of Mathematics, vol. 175, no 3, , p. 1653–1665 (DOI 10.4007/annals.2012.175.3.14, arXiv 1007.0575)
- ↑ Carlos P. Herrero, « Self-avoiding walks on scale-free networks », Phys. Rev. E, vol. 71, no 3, , p. 1728 (DOI 10.1103/PhysRevE.71.016103, Bibcode 2005PhRvE..71a6103H, arXiv cond-mat/0412658, lire en ligne)
- ↑ I. Tishby, O. Biham et E. Katzav, « The distribution of path lengths of self avoiding walks on Erdős–Rényi networks », Journal of Physics A: Mathematical and Theoretical, vol. 49, no 28, , p. 285002 (DOI 10.1088/1751-8113/49/28/285002, Bibcode 2016JPhA...49B5002T, arXiv 1603.06613)
Liens externes
- 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
Portail de la géométrie
Portail de la chimie