De tout temps, femmes et hommes ont aspiré à des nano-colifichets en ADN. Depuis les années 1990, dans la suite des travaux séminaux de Reif, Adleman, Winfree, puis Rothemund et tant d'autres, ils et elles sont exaucés: par une conception astucieuse de mots sur l'alphabet {A, C, T, G}, il est possible d'obtenir des séquences d'ADN dont les interactions ressemblent à de petites tuiles flottant sur un plan discret. Ces tuiles portent des couleurs sur leurs quatre côtés —des séquences d'ADN. Telles des coraux sur un récif, leurs concrétions s'agrègent autour d'une graine: chaque fois qu'une tuile passe à proximité d'une position du bord dont le voisinage est propice, elle se fixe au motif.

Année après année, la sophistication des motifs obtenus par ce procédé d'auto-assemblage s'est accrue, donnant naissance aux «self-assembly studies», avec la question des liens entre possibilité de calcul et géométrie de l'objet à assembler. Je présenterai l'énoncé de la caractérisation des fractales auto-assemblables (nec plus ultra du domaine), et l'outil central pour la borne inférieur: le théorème de l'espalier.

Ce lemme de pompage établit une relation entre largeur arborescente bornée et limitation du calcul plutôt attendue, mais subtile à caractériser précisément. De plus, sa preuve nous emmènera à la découverte d'outils et de raffinements liés à l'asynchronisme inhérent aux systèmes d'auto-assemblage:

- la largeur arborescente connexe qui permet de contrôler la décomposition d'un graphe y compris quand certaines parties sont nettement plus arborescentes que d'autres, et d'obtenir une décomposition qui ne crée pas de distortion trop importante de ce graphe

- les séquences d'assemblage ordinales pour dompter la concurrence entre plusieurs séquence potentiellement infinies de transitions et définir un ordre de priorité entre elles,

- la généralisation des assemblages à des graphes qui ne soient pas des sous-graphes du plan euclidien discret pour éviter les collisions, couplée à une mesure de l'effervescence (la propension à créer des trous) pour se ramener au cas de Z^2.