Rigidité et percolation

Piste rouge 17 octobre 2014  - Ecrit par  Julien Barré Voir les commentaires (2)

Cet article a été écrit en partenariat avec La Gazette des Mathématiciens

IdM en partenariat avec la Société Mathématique de France et son journal la Gazette des mathématiciens, donne la parole à des lauréats des prix thématiques de l’Académie des Sciences.
Deux textes sur le même sujet sont publiés conjointement par l’auteur, l’un à la gazette des mathématiciens, l’autre sur Images des Mathématiques. Aujourd’hui, « Rigidité et percolation », par Julien Barré (publié sous le titre Percolation de la rigidité dans la gazette).

L’ article présente d’abord la théorie mathématique de la rigidité des structures formées de pivots et de barres, puis le phénomène de percolation associé, lorsque les structures considérées sont de grandes tailles et contiennent une part aléatoire.

Un jeu de construction

Peut-être connaissez-vous ces jeux de constructions constitués de boules et de barres aimantées, que l’on peut assembler. Dans leurs versions les plus simples, ils sont destinés aux enfants à partir de 1 an. Ils vont pourtant nous guider sur le chemin d’une belle théorie mathématique.

Commençons par l’assemblage ci-dessous, qui comprend 5 boules et 7 barres. Peut-on le déformer, sans la casser ? Attention, on est pour l’instant en deux dimensions : les boules doivent rester sur le plan de la table. Et bien sûr, on n’a pas le droit de détacher les barres des boules.

JPEG - 319.6 ko

On voit assez vite qu’on peut déplacer la figure, ou la tourner, mais pas la déformer.

Regardons maintenant cet autre assemblage :

JPEG - 360.9 ko

Il est déformable, et la photo ci-dessous en montre une déformation :

JPEG - 292.2 ko

Un autre exemple, avec un assemblage un peu plus grand :

JPEG - 271.5 ko

Ce n’est pas si facile de voir s’il est déformable, ou rigide !

La réponse

Cet assemblage est rigide...

On peut faire l’expérience, mais on aimerait avoir une méthode plus pratique, applicable à de plus grands assemblages...

Compter les degrés de liberté

Il existe pour cela une recette simple mais ingénieuse, en général attribuée à J. C. Maxwell. Chaque boule peut se déplacer dans un plan : on peut donc fixer librement ses deux coordonnées ; on dit qu’elle a deux degrés de liberté. Chaque barre introduit une contrainte : elle fixe une distance entre deux boules et retire donc un degré de liberté. Si on note $B$ le nombre de boules et $A$ le nombre d’arêtes, la recette de Maxwell prédit que l’assemblage a $2B-A$ degrés de liberté. Or un assemblage ne peut jamais avoir moins de trois degrés de liberté : on peut toujours au moins le faire tourner sur lui-même (un degré de liberté) ou le déplacer sur le plan en conservant son orientation (deux degrés de liberté) ; il est rigide s’il n’a pas d’autre degré de liberté que ces trois-là.

On en conclut que pour être rigide, un assemblage contenant $B$ boules doit contenir au moins $A=2B-3$ arêtes. De plus, si $A<2B-3$, $2B-A-3$ est le nombre de déformations possibles de la structure. Vous pouvez tester cette formule avec le jeu de construction, sur les photos ci-dessus, ou sur l’exemple ci-dessous :

JPEG - 12.1 ko

Avec $B=5$ boules et $A=6$ barres, $2B-A=4$ ; cet assemblage n’est pas rigide. En effet, on peut déformer le quadrilatère du bas de la figure.

Contraintes redondantes

On a vu que si $A<2B-3$, un assemblage est déformable. On aimerait pouvoir dire que si $A\geq 2B-3$, l’assemblage est rigide. Malheureusement, ce n’est pas vrai. L’assemblage ci-dessous a $B=6$ boules, $A=9$ barres, et pourtant il n’est pas rigide. Il a quatre degrés de liberté : en plus des trois degrés de liberté d’un assemblage rigide sur le plan, la boule reliée au reste par une seule barre peut pivoter librement. Que s’est-il passé ?

JPEG - 28.4 ko

Regardons la sous-structure en rouge : elle a $5$ boules et $8$ barres ; d’après la recette de Maxwell, elle devrait donc avoir $2\times 5-8 = 2$ degrés de liberté, ce qui est impossible, puisqu’un assemblage en a toujours au moins $3$. Cette sous-structure a trop de barres : on peut d’ailleurs lui enlever une barre rouge (n’importe laquelle), elle restera rigide ; on dit qu’elle possède une contrainte « redondante ». Recommençons donc le comptage de Maxwell en enlevant cette contrainte redondante : notre assemblage a alors $2\times 6-(9-1) = 4$ degrés de liberté. C’est la bonne réponse !

Théorème de Laman

Nous avons maintenant notre recette générale :

  • On identifie les sous structures qui ont des contraintes redondantes : ce sont celles qui ont $B$ boules et strictement plus de $2B-3$ barres.
  • On retire les contraintes redondantes.
  • On utilise le comptage de Maxwell.

Si l’on excepte certains assemblages particuliers (dits « non génériques »), cette recette est exacte ! C’est ce que dit le théorème de Laman, démontré en 1970, un siècle après Maxwell.

Pour en savoir un peu plus sur ce que veut dire « générique »

JPEG - 34.5 ko

L’assemblage sur cette figure a 10 boules et 17 barres ; il n’a pas de contrainte redondante. Le théorème de Laman nous dit donc qu’il doit être rigide. Pourtant, la figure indique une déformation possible : l’assemblage n’est pas rigide... Le théorème de Laman ne s’applique pas en raison de la présence de trois barres parallèles, marquées en rouge.

JPEG - 19.9 ko

Regardons maintenant ce nouvel assemblage. Il ressemble au précédent ; en particulier, le graphe associé est le même, mais les 3 barres rouges ne sont pas parallèles : cet assemblage est rigide, en conformité avec le théorème de Laman. Un assemblage est dit générique s’il ne possède pas de propriétés géométriques particulières comme des boules alignées, des barres parallèles,...(on peut bien sûr définir précisément cette notion de généricité). Le théorème de Laman s’applique uniquement à ces assemblages génériques.

Essayons d’expliquer pourquoi ce théorème est remarquable. On a besoin pour cela de la notion de graphe.

Définition :
Un graphe est un ensemble d’objets, appelés sommets ; certaines paires de sommets sont reliées par des liens, appelés arêtes.
Donnons un exemple : Ensemble des sommets = $A,B,C,D$ ; ensemble des arêtes = $AB,AC,AD,BC$.
La figure ci-dessous donne deux représentations de ce graphe ; les positions des sommets, les longueurs des arêtes et autres caractéristiques géométriques sont différentes sur les deux représentations, mais il s’agit du même graphe.

JPEG - 15.2 ko

En résumé, un graphe contient les informations comme « tel objet est connecté avec tel autre », mais ne dit rien sur la nature des liens, ou sur la position des objets dans l’espace.

Au départ, la question de la rigidité est géométrique : elle est liée aux distances entre boules et aux déplacements sur le plan. Or le théorème de Laman dit que l’on peut étudier la rigidité en comptant des boules et des barres, et que l’on peut oublier les longueurs des barres, ainsi que les positions des boules dans le plan. Autrement dit, le problème de géométrie du départ a été transformé en un problème de théorie des graphes ! Appliquons par exemple la recette donnée par le théorème à la deuxième structure magnétique photographiée ci-dessus. Le graphe correspondant est représenté ci-dessous :

JPEG - 19.2 ko

On cherche une sous structure (on dit un sous graphe) qui contient $B$ sommets et strictement plus de $2B-3$ arêtes (pour contenir une arête, un sous graphe doit contenir les deux sommets qu’elle joint). Dans cet exemple, il n’y a pas de tel sous-graphe, donc il n’y a pas de contrainte redondante. Le nombre de degrés de liberté est donc $2\times 9-15=3$, et la structure est rigide.

Notons que reformulé en termes de théorie des graphes, le problème est très facile à traiter avec un ordinateur, contrairement au problème de départ...

Percolation

On va considérer maintenant de très grosses structures. Prenons par exemple $B=1000$ sommets, ou $B=10^6$ (à ce niveau, on peut utiliser l’ordinateur), ou $B=10^{20}$ (la structure est alors beaucoup trop grosse pour être analysée par ordinateur) ; tirons au hasard $A$ paires de sommets, et joignons chaque paire par une arête. On autorise les croisements entre arêtes : en général, une telle structure ne sera donc pas réalisable avec le jeu de construction, puisque les barres aimantées ne peuvent bien sûr pas se traverser. Que se passe-t-il quand le nombre d’arêtes $A$ augmente ? Etudions un exemple.

JPEG - 22.4 ko

Sur cette figure, $B=7$, et le nombre d’arêtes augmente de gauche à droite :
$A=2, 7, 10$. La structure rigide la plus grande est indiquée en bleu dans chaque cas. Dans cet exemple, avec $A=2$, il y a deux structures rigides de taille 2 ; avec $A=7$, la plus grande structure rigide est de taille 3 ; avec $A=10$, la plus grande structure rigide est de taille 6.

C’est aussi ce qui se passe pour des graphes beaucoup plus grands : lorsqu’il y a peu d’arêtes, elles forment surtout des structures rigides de taille 2 ; et plus il y a d’arêtes, plus il est probable que des structures rigides de plus en plus grandes apparaissent. Ce qui est remarquable, c’est que l’apparition de ces structures rigides plus grandes se fait très brutalement. Notons $x=A/B$, le rapport nombre d’arêtes sur nombre de boules ; alors

  • si $x<1.794...$, avec grande probabilité il n’y a pas de structure rigide plus grande qu’un triangle.
  • si $x>1.794...$, avec grande probabilité il y a une structure rigide géante, qui comprend plus de 70% des boules !

Avec grande probabilité a un sens précis : cela signifie avec une probabilité qui tend vers 1 quand $B$ tend vers l’infini et que $A$ est un entier proche de $xB$. La valeur critique $x_c=1.794...$ est obtenue comme solution d’une équation ; on peut la calculer avec autant de précision que nécessaire.

L’apparition brutale d’une structure rigide géante pour une valeur bien déterminée de $x$ est appelée percolation de la rigidité. Cet effet a été étudié par des physiciens (P. Duxbury, C. Moukarzel, D. Jacobs, M. Thorpe) à la fin des années 90, et le résultat ci-dessus a été démontré récemment par S.P. Kasiviswanathan C. Moore et L. Théran. Ce phénomène doit vous faire penser aux transitions de phase, qui correspondent à un changement brutal des propriétés d’un système lorsqu’un paramètre de contrôle varie : par exemple, à pression atmosphérique, pour une température $T<100^o$C, l’eau est liquide, pour $T>100^o$C, elle est sous forme de vapeur.

Placer les arêtes entièrement au hasard comme nous l’avons fait n’est pas une façon très réaliste de modéliser des structures réelles, comme des assemblages d’atomes. Il se trouve que c’est aussi une grande simplification du problème. Comprendre la transition de phase pour des distributions plus réalistes des arêtes est une question largement ouverte à laquelle je consacre une partie de ma recherche, et pour laquelle il existe surtout des approches numériques. Récemment, j’ai introduit une méthode qui permet d’étudier cette transition pour une nouvelle classe de structures [1], mais qui reste loin de résoudre complètement le problème !

Quizz !

Jusqu’ici, on a cherché à déformer les structures en restant dans un plan. Naturellement, la même question se pose dans l’espace.

JPEG - 263.2 ko

Cette structure est-elle déformable ? Pouvez-vous imaginer ce que devient le comptage des contraintes pour une figure de boules et de barres en 3D ?

Réponse

Chaque boule est repérée par trois coordonnées, et a donc trois degrés de liberté. Chaque arête fixe une distance, et retire donc un degré de liberté. En trois dimensions, une structure solide a six degrés de liberté : trois déplacements dans l’espace sans modifier l’orientation, et trois degrés de liberté liés à l’orientation de la structure. Le comptage des contraintes dit donc qu’une structure avec $B$ boules doit avoir au moins $3B-6$ barres pour être rigide. La structure de la photo contient $B=8$ boules et $17$ barres ; elle est donc déformable.

Une structure avec strictement plus que $3B-6$ barres contiendra une ou plusieurs contraintes redondantes. Mais une structure peut contenir une contrainte redondante même si toutes ses sous structures avec $B'$ boules contiennent moins que $3B'-6$ barres ! La figure ci-dessous donne un exemple : le célèbre graphe en « double banane ».

JPEG - 27.6 ko

Cette structure a $B=8$ boules et $18=3B-6$ barres. De plus, aucune
sous-structure avec $B'$ boules n’a plus de $3B'-6$ barres. Si l’analogue naturel du théorème de Laman était vrai, cette structure serait rigide. Or les 2 « bananes » peuvent tourner indépendamment l’une de l’autre autour de l’axe marqué en rouge : la structure est donc déformable.

L’analogue du théor\ème de Laman est donc faux ; c’est une différence fondamentale avec le cas du plan. L’identification des contraintes redondantes par une recette du type de celle donnée par le théorème de Laman est une question ouverte en trois dimensions.

Un peu plus difficile : on considère un jeu de « meccano », en deux dimensions : des barres sont reliées entre elles par des pivots, autour desquels elles peuvent tourner. Les pivots ne sont pas nécessairement placés aux extrémités des barres.
Ce type de modèle a été utilisé pour décrire des matériaux fibreux, comme le papier.

PNG - 33.7 ko

La structure ci-dessus est-elle rigide ? Que devient le comptage des contraintes ?

Réponse

Cette fois-ci, ce sont les barres qui fournissent les degrés de liberté. Une barre dans un plan a trois degrés de liberté : deux pour sa position, et un pour son orientation. Lorsque deux barres se croisent et forment un pivot, cela retire deux degrés de liberté. Par exemple, deux barres et un pivot ont $3+3-2=4$ degrés de liberté : deux pour la position du pivot, et un pour l’orientation de chaque barre autour du pivot. Le comptage des contraintes dit donc qu’une structure avec $B$ barres et $P$ pivots ne peut pas être rigide si $3B-2P>3$. Pour ce problème, contrairement aux structures de boules et de barres dans l’espace, on sait identifier les contraintes redondantes par une recette similaire à celle du théorème de Laman. La structure représentée a $B=5$ barres et $P=6$ pivots ; $3B-2P=3$, et il n’y a pas de contrainte redondante, donc elle est rigide.

Pour avoir des informations supplémentaires :

  • Page web du groupe de recherche d’Ileana Streinu (University of Massachusetts) http://linkage.cs.umass.edu/
    La page web contient des vidéos d’explications.
  • S. P. Kasiviswanathan, C. Moore and L. Theran SODA ’11 Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, p. 1237-1252
    (2011).
Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Nathanael Jeune, toufou, Claire Burrin, Thierry Barbot et Pierre Lescanne.

Article édité par Jérôme Buzzi

Notes

[1J. Barré Hierarchical models of rigidity percolation, Phys. Rev. E 80, 061108 (2009) ; Combinatorial models of rigidity and renormalization, J. Stat. Phys. 146, 359-377 (2012).

Partager cet article

Pour citer cet article :

Julien Barré — «Rigidité et percolation» — Images des Mathématiques, CNRS, 2014

Commentaire sur l'article

  • Rigidité et percolation

    le 17 octobre 2014 à 21:52, par Creux

    Une petite coquille a échappé à la vigilance des relecteurs :

    Or le théorème de Laman dit que l’on peut étudier la rigidité en comptant des boules et des barres, et que l’on peut oublier les longueurs des barres, ainsi que les positionS des boules dans le plan.

    Article très intéressant en tout cas.

    Répondre à ce message
  • Rigidité et percolation

    le 18 octobre 2014 à 10:54, par Maï Huong Pham-Sauvageot

    Merci de votre intérêt pour cet article et de votre commentaire.
    La coquille a été en principe corrigée.

    Maï Sauvageot et Carole Gaboriau
    Secrétariat de rédaction IdM

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM