Upcoming

Past

• Nicolas Schabanel (LIP, Lyon), 2025-01-23
  
  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)
• David Doty (University of California, USA), 2025-01-15
  
  Title: Execution bounded chemical reaction networks
  Abstract:

  Chemical reaction networks (CRNs) model systems where molecules or agents interact according to a finite set of reactions such as A + B → C, representing that if a molecule of A and B collide, they disappear and a molecule of C is produced. Although traditionally used to model natural chemical systems, CRNs are also studied as a programming language for describing the desired behavior of synthetic chemical systems. Synthetic CRNs can compute Boolean-valued predicates φ : ℕ^d → {0,1} and integer-valued functions f : ℕ^d → ℕ; for instance X₁ + X₂ → Ycan be thought to compute the function min(x₁, x₂).

  We study the computational power of execution bounded CRNs, in which only a finite number of reactions can occur from the initial configuration (e.g., ruling out reversible reactions such as A ⇌ B). Our main negative results, showing limitations on the computational power of execution bounded CRNs, are based on characterizing execution bounded CRNs as precisely those that have a "linear potential function": a nonnegative linear function of the network's state, which every reaction strictly decreases. This equivalence is proved using a variant of Farkas' Lemma and may be of independent interest.

  Joint work with Ben Heckmann.
• Corentin Lunel (Inria, Montepellier), 2025-01-14
  
  Title: Some knot theory results inspired by graph theory
  Abstract:

  Graph theory and knot theory are two famous mathematical fields with profound interactions. I'm going to present some algorithmic results in knot theory, inspired by results and methods from graph theory.

  The first problem we address concerns the decidability of a knot invariant. The genus of a knot is a classical knot invariant: it is the minimal genus of an embedded orientable surface in the 3-dimensional space admitting the knot as its boundary. It is now fairly well understood from a computational perspective. On the contrary, no algorithm is known for its 4 dimensional variants, both in the smooth and in the topological locally flat category. We investigate a class of knots and links called Hopf arborescent links, which are obtained as the boundaries of surfaces constructed by iterated plumbings of Hopf bands. We show that for such links, computing the genus defects, which measure how much the four-dimensional genera differ from the classical genus, is decidable. Our proof is non-constructive and is obtained by proving that a containment relation on surfaces associated to Hopf arborescent links forms a well-quasi-order.

  The second problem we tackle is motivated by the existence of efficient algorithms to compute many knot invariants and properties on diagrams of low treewidth. It was recently proved that there exist knots which do not admit any diagram of low treewidth, and the proof relied on intricate low-dimensional topology techniques. We initiate here a thorough investigation of tree decompositions of knot diagrams (or more generally, diagrams of spatial graphs) using ideas from structural graph theory. We define an obstruction on spatial embeddings that forbids low treewidth diagrams, and we prove that it is optimal with respect to a related width invariant. We then show the existence of this obstruction whenever an embedding into a surface with high compression-representativity exists, which is the case for torus knots. Thus, we provide a new and self-contained proof that those do not admit diagrams of low treewidth.

• 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.

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