Responsible : Malory Marin

malory.marin[at]ens-lyon.fr

Labratoire d'Informatique et du Parallélisme
École Normale Supérieure de Lyon
46 Allée d'Italie
69364 Lyon Cedex 7
France

Upcoming

• Nicolas Schabanel (LIP, Lyon), 2025-01-09
  
  Title: How do we make DNA origami and what are the challenges we tackle.
  Abstract: Curved shapes are ubiquitous in both natural and engineered structures contributing to their intricate functionalities and mechanical resilience. Replicating these shapes at the nanoscale using DNA nanotechnology poses significant challenges due to the inherent constraints of DNA geometry. Here, we introduce a geometric model for curved DNA helices and an algorithm for automatic routing of DNA helices along non-planar trajectories to fold predefined 3D DNA origami nanostructures. We provide an automated design process that enables the self-assembly of curved DNA helix bundles, hollow shapes, nested spheres, and biomimetic structures such as vault-like cages, using a novel spiral-based paradigm. This process, integrated in ENSnano software, revisites DNA origami principles to go beyond current structural confinements and opens opportunities for creating general 3D spatial configurations with advanced programmability for enhanced functional integration.
  L'exposé sera spécialement conçu pour des personnes qui ne connaissent rien du tout à l'ADN ni au origami ADN.
  Joint work with: Nicolas Levy (LIP), Julie Finkel (CBS), Allan Mills (CBS), Pierre Marcus (LIP), Octave Hazard (LIP), Daria Pchelina (LIP), Joris Picot (LIP) and Gaëtan Bellot (CBS)
• Corentin Lunel (Inria, Montepellier), 2025-01-...
  
  Title: De la topologie algorithmique inspirée de théorie structurelle des graphes
  Abstract: La théorie des graphes et la théorie des nœuds sont deux célèbres domaines mathématiques qui présentent de profondes interactions. Cette présentation se concentre sur l'étude de certains problèmes de théorie des nœuds d'un point de vue algorithmique en s'inspirant de résultats et méthodes issus de théorie structurelle des graphes. Le premier problème que nous abordons concerne la décidabilité d'un invariant de nœud sur une classe de nœuds que nous définissons. Notre preuve est non constructive et est obtenue en exhibant un bel ordre sur les surfaces associées à nos nœuds. Le genre d'un nœud est un invariant classique : c'est le genre minimal d'une surface orientable plongée dans l'espace de dimension 3 qui est bordée par le nœud. De nos jours, il est assez bien compris d'un point de vue algorithmique. En revanche, aucun algorithme n'est connu pour ses variantes en dimension 4, à la fois dans la catégorie des variétés lisses et dans celle des variétés localement plates. Nous étudions une classe de nœuds et d'entrelacs appelés entrelacs arborescents de Hopf, qui sont obtenus comme bords de surfaces construites par des plombages itérés de bandes de Hopf. Nous montrons que sur ces entrelacs, le calcul des défauts de genre, qui mesurent à quel point les genres quadridimensionnels diffèrent du genre classique, est décidable. Le deuxième problème que nous attaquons est motivé par l'existence d'algorithmes efficaces (FPT) pour calculer de nombreux invariants et propriétés de nœuds sur des diagrammes de faible largeur arborescente (treewidth). Il a été récemment prouvé, par de complexes résultats de topologie en basse dimension, qu'il existe des nœuds qui n'admettent pas de diagrammes de faible largeur arborescente. Nous entamons ici une étude approfondie des décompositions arborescentes des diagrammes de nœuds, ou plus généralement des diagrammes de graphes spatiaux, en utilisant des idées de la théorie structurelle des graphes. Nous définissons une obstruction sur les plongements dans l'espace qui s'oppose à des diagrammes de faible largeur arborescente. Nous prouvons de plus que cette obstruction est optimale vis-à-vis d'un invariant de largeur que nous définissons. Nous montrons ensuite l'existence d'une telle obstruction dès qu'il existe un plongement dans une surface avec haute représentativité. Cette dernière partie est toujours vérifiée sur les nœuds toriques: nous fournissons ainsi une nouvelle preuve que ces nœuds n'admettent aucun diagramme de faible largeur arborescente. Pour finir, nous nous concentrons sur la complexité des diagrammes de nœuds sous l'action de mouvements de Reidemeister. Reconnaître le nœud trivial est un problème fondamental de théorie des nœuds. Une façon naturelle de l'attaquer est d'appliquer des mouvements de Reidemeister sur un diagramme du nœud de manière exhaustive ou aléatoire jusqu'à ce que le diagramme corresponde à un cercle. Il s'avère que le nombre de croisements de certains diagrammes du nœud trivial doit nécessairement augmenter pendant l'exécution de cet algorithme. De plus, on ne connaît pas de borne inférieure meilleure que constante sur le nombre de croisements qui doivent être ajoutés pendant l'exécution d'algorithmes similaires. Cet algorithme peut aussi être appliqué au problème de décider si un entrelacs est séparé, c'est-à-dire, s'il existe une sphère qui sépare deux de ses composantes. Il présente le même problème de devoir ajouter des croisements à un diagramme pendant son exécution. Nous prouvons qu'il existe des diagrammes d'entrelacs qui nécessitent un nombre arbitrairement grand de croisements à ajouter pour être séparés en utilisant cet algorithme en utilisant l'obstruction développée au dessus.



Past

• Pascal Koiran (LIP, Lyon), 2024-12-12
  
  Title: An efficient uniqueness theorem for overcomplete tensor decomposition .
  Abstract: We give a new, constructive uniqueness theorem for tensor decomposition. It applies to order 3 tensors of format n×n×p and can prove uniqueness of decomposition for generic tensors up to rank r=4n/3 as soon as p≥4. One major advantage over Kruskal's uniqueness theorem is that our theorem has an algorithmic proof, and the resulting algorithm is efficient. Like the uniqueness theorem, it applies in the range n≤r≤4n/3. As a result, we obtain the first efficient algorithm for overcomplete decomposition of generic tensors of order 3. For instance, prior to this work it was not known how to efficiently decompose generic tensors of format n×n×n and rank r=1.01n (or rank r≤(1+ε)n, for some constant ε>0). Efficient overcomplete decomposition of generic tensors of format n×n×3 remains an open problem. Our results are based on the method of commuting extensions pioneered by Strassen for the proof of his 3n/2 lower bound on tensor rank and border rank. In particular, we rely on an algorithm for the computation of commuting extensions recently proposed in a companion paper, and on the classical diagonalization-based "Jennrich algorithm" for undercomplete tensor decomposition.
• Florent Becker (University of Orléans), 2024-11-28
  
  Title: Le théorème de l'espalier pour l'auto-assemblage ou l'affaire du pompage arborescent.
  Abstract: 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 carrées flottant sur un plan discret. Ces tuiles, qui représentent abstraitement les dits complexes d'ADN, portent des couleurs sur leurs quatre côtés —les 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 et l'agrandit. Année après année, la sophistication des motifs obtenus par ce procédé d'auto-assemblage s'est sans cesse accrue, donnant naissance aux «self-assembly studies». Je présenterai un principe de pompage pour l'auto-assemblage, c'est à dire que je montrerai que, sous certaines conditions, les systèmes d'auto-assemblage se comportent de manière ultimement périodique. C'est une condition de largeur arborescente qui s'avère déterminante: que la taille des carrés que notre système entoure soit bornée. Par égard pour le libre arbitre des shadoks, le pompage se fera dans une direction arbitraire, pour peu que le système s'avance suffisamment dans cette direction. L'existence d'une relation entre largeur arborescente bornée et limitation du calcul est plutôt attendue, mais l'établissement de son énoncé permet de la caractériser précisément. De plus, sa preuve recèle d'outils et de subtilités liées à 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.
• Octave Hazard (LIP, Lyon), 2024-11-27
  
  Title: Understanding and controlling DNA origami co-folding.
  Abstract: DNA origami is a particularly robust technique for designing DNA structures, often on the order of hundreds of nanometers. It relies on the controlled folding of a long scaffold DNA strand, using a set of carefully chosen shorter synthetic strands acting as staples. It is particularly well-suited for designing complex structures in two or three dimensions. My PhD thesis work involves several aspects: 1) exploring algorithmic and geometrical techniques for designing DNA origamis with multiple scaffolds; 2) the experimental implementations associated with these techniques; and 3) modeling the folding and assembly process.
• Jonh Sylvester (University of Liverpool), 2024-03-12
  
  Title: Tangled Paths: a new random graph model from Mallows permutations.
  Abstract: We introduce a new random graph model, the tangled path, which results from taking the union of two paths where the vertices of one have been relabelled according to a (non-uniform) random permutation sampled from the Mallows distribution with real parameter 0 < q(n) < 1. Roughly speaking, increasing the parameter q in the Mallows distribution increases the number of inverted pairs of elements in the permutation. This has the following effect on the resulting graph: if q is close to 0 the tangled path bears resemblance to a path (if q<1 is fixed then the diameter is linear) and as q tends to 1 it becomes an expander, the question is what happens in between. In order to further understand the effect of the parameter q on the structure we obtain bounds on the treewidth in terms of q. We also give a sharp threshold for the property of having a balanced separator of size one. The talk is based on joint work with Jessica Enright, Kitty Meeks and William Pettersson.
• Clément Legrand-Duchesne (LABRI, Bordeaux), 2023-12-04
  
  Title:Random embeddings of bounded degree trees with optimal spread.
  Abstract: A seminal result of Komlos, Sarkozy and Szemeredi proves that for any \Delta, any graph G with minimum degree (1/2+\alpha)n and large enough n contains all n-vertex trees of maximum degree \Delta. Given two graphs H and G, recent advances on the Kahn-Kalai conjecture connect the existence of spread measures on the space of embeddings of H in G, with the probabilistic threshold above which a random subgraph of G, obtained by sampling the edges at a fixed rate, still contains H with good probability. Spread distributions also give a lower bound on the number of embeddings of H in G. In 2023 Pham, Sah , Sawhney and Simkin designed a spread measure on the embeddings of bounded degree trees in graphs of minimum degree (1/2+alpha)n, by following the proof of Komlos, et al. We give a regularity free proof of this result. As a result, we obtain much better constants, with a more flexible framework and unlike the proof of Phan et al., our construction generalises to hypergraphs and digraphs painlessly. This is joint work with Paul Bastide and Alp Müyesser.