String attractor, a relatively new combinatorial notion, is closely related to measuring the complexity of words and offers a unified approach to the repetitiveness measures induced by dictionary compressors. However, attractors have been only little studied in the context of combinatorics on words, particularly for classes of low complexity, including complementary-symmetric Rote sequences. In this talk, we work with pseudopalindromic closures as a useful way to generate these sequences, and then show the form of minimal attractors of their pseudopalindromic prefixes.[-]

I recently introduced a new proof technique based on a simple counting argument that I applied to many problems from combinatorics. In this talk, I will illustrate this counting argument with a proof that the Thue choice number is at most 4. Suppose we have to construct a square-free word (ie, no non-empty factors is of the form uu) by chosing the letter of each position of the word from an alphabet specific to the position. The Thue choice number is the smallest k such that, if all these alphabets have size at least k, then we can build an infinite square-free word.
I will then present how it can be pushed further in the context of combinatorics on words.[-]

Les Acides RiboNucléiques (ARN) sont des biopolymères linéaires omniprésents dans notre organisme, pouvant être codés comme des séquences sur un alphabet A,C,G,U. Ces molécules se replient sur elles-mêmes, établissant des liaisons hydrogènes d'où découlent l'appariement de certaines des positions, selon des règles de compatibilité des lettres n'autorisant que les paires dans l'ensemble A,U,C,G,G,U. De ce mécanisme d'appariements résulte l'adoption d'une ou plusieurs conformations, appelées structures secondaires, au passage bijectif avec les mots de Motzkin sans-pic. De nombreuses applications, en nanotechnologie, médecine, ou biostatistique, nécessitent de compter, ou encore engendrer aléatoirement, des séquences d'ARN simultanément compatibles avec un ensemble donné de structures secondaires. Un algorithme exponentiel, basé sur une décomposition (ear decomposition) du graphe de dépendance induit par l'union des paires, a ainsi été proposé par Höner zu Siederdissen et al [A]. Cet algorithme utilise la méthode récursive/programmation dynamique pour précalculer les nombres d'affectations compatibles avant/après chacun des choix locaux. Une phase de génération utilise ensuite ces nombres pour garantir l'uniformité de la génération. Cependant, cet algorithme ne permettait pas la prise en compte de critères énergétiques plus complexes, nécessitant l'utilisation d'un formalisme plus expressif que les graphes de dépendance (hypergraphes). De plus, la complexité de l'algorithme, théoriquement exponentielle sur un paramètre non-borné et parfois élevée en pratique, soulevait la question de la complexité du problème de comptage.
Dans un travail récent avec Hammer, Wang et Will [B], nous établissons la #P complétude, et la complexité d'approximation, du problème de comptage des séquences compatibles. Notre preuve repose sur une bijection simple entre les séquences compatibles et les stables du graphes de dépendance. Nous proposons une approche alternative, basée sur la décomposition arborescente, pour contrôler de façon probabiliste [C] l'énergie moyenne des séquences pour les différentes structures, ou la composition en les différentes lettres. Ces résultats fournissent un cadre flexible et expressif pour le design d'ARN, et soulèvent des questions sur l'utilisation de stratégies alternatives (génération de Boltzmann, simulation parfaite) pour la génération aléatoire, ainsi sur le concept d'analyse en moyenne dans un contexte où la donnée en entrée est plus complexe que la taille de l'objet engendré.[-]

Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large combinatorial sets. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they abruptly change from being efficient to inefficient as some parameter of the system is modified. Generating functions can offer an alternative approach to sampling and they play a role in showing when certain Markov chains are efficient or not. We will explore the interplay between Markov chains, generating functions, and phase transitions for a variety of combinatorial problems, including graded posets, Boltzmann sampling, and 3-colorings on $Z^{2}$.[-]

Let A be a commutative ring. Does it have a maximal ideal? Classically, Zorn's lemma would allow us to concoct such an ideal. Constructively, no such ideal needs to exist. However, even though no maximal ideal might exist in the standard domain of discourse, a maximal ideal always exists *somewhere*. This is because every ring is countable *somewhere*, and *everywhere*, countable rings have maximal ideals. Concrete computational consequences follow from this phantomic variant of existence.
The talk will introduce the modal operators 'somewhere' and 'everywhere', referring to the multiverse of parametrized mathematics, the multitude of computational forcing extensions. Just like the well-known double negation operator, they are (mostly) trivial from a classical point of view. Their purpose is to (a) put established results in constructive algebra and constructive combinatorics into perspective, (b) construct an origin story for certain inductive definitions and (c) form a unified framework for certain techniques for extracting programs from classical proofs.
Our proposal is inspired by the study of the set-theoretic multiverse, but focuses less on exploring the range of set/topos-theoretic possibility and more on concrete applications in constructive mathematics. As guiding examples, we will examine algebraic closures of fields, Noetherian conditions on rings and the foundations of well-quasi orders such as Dickson's Lemma.
(joint work with Alexander Oldenziel)[-]