Starting from Doeblin's observation on the Poissonian nature of occurrences of large digits in typical continued fraction expansions, I will outline some recent work on rare events in measure preserving systems (including spatiotemporal and local limit theorems) which, in particular, allows us to refine Doeblin's statement in several ways.

(Part of this is joint work with Max Auer.)

Cut-reduction procedures for classical sequent calculus are notoriously non-deterministic and non-confluent, both in the original formulation by Gentzen and in later reformulations. It is natural to ask whether those instances of non-confluence are superficial in nature, i.e. whether syntactically distinct normal forms of the same derivation are in fact correlated in a non-trivial way, as is the case in the intuitionistic and linear versions of sequent calculus. A famous counter-example by Lafont purports to show that the answer is negative, that is, every interpretation of derivations in LK that is invariant under classical cut-elimination must be a trivial one that identifies at least all proofs of the same sequent. A long-standing open question has then been whether it could be possible to work around Lafont's example by natural and non-trivial adjustments of the calculus and/or of cut-reduction steps, without resorting to symmetry-breaking techniques like polarization or embeddings into intuitionistic or linear logic.

Working within the propositional fragment of the context-sharing formulation of LK — where parallel logical rules permute freely — we show that the graph constructed by tracing the history of atomic formula occurrences through axiom and cut rules is invariant under arbitrary rule permutations in cut-free proofs, thus providing a canonical representation of normal-form proofs.

We then introduce a refinement of the notion of axiom-induced graph that allows extending the invariance result to proofs with cuts, although at the cost of a strong assumption on the shape of derivations. Because cut-reduction in this formulation of LK can be implemented entirely by logical rule permutations plus a pair of local rewriting steps that preserve the refined axiom graphs, the result yields a non-trivial invariant of cut-reduction.

The problem of reconfiguring independent sets belongs to the broader field of combinatorial reconfiguration problems. It can be formulated as follows: given a collection of tokens placed on the vertices of an independent set of a graph, is it possible to move one by one these tokens to another target independent set, such that two tokens are never neighbors throughout the transformation? After a general introduction to combinatorial reconfiguration and the independent set reconfiguration problem, we will focus on the “Token Sliding” variant. In this variant, one step of the transformation consists in moving a token from a vertex to a neighboring vertex. We will focus on the parameterized complexity of this problem in sparse classes of graphs and on the new tools we have recently designed for the development of FPT algorithms.

Dans cet exposé très informel à propos d'un travail en cours, je souhaiterais discuter de différents styles pour définir (en Coq) la sémantique d'un langage de programmation. Une de mes motivations est d'obtenir une sémantique au moins partiellement exécutable dans Coq et d'en tirer un mécanisme d'exécution symbolique qui pourrait être exploité dans un système de vérification de programmes.

Au cours de l'exposé, je présenterai deux styles de sémantique (pour un langage sans effets de bord, hormis divergence et plantage), et au-dessus de chacun d'eux, je construirai une logique de Hoare. Le premier style, “monadique jusqu'au bout”, reproduit des idées que l'on trouve dans la littérature: un premier interprète est exprimé dans une monade libre bien choisie, puis, dans un second temps, les habitants de cette monade sont traduits dans d'autres monades (monade des interaction trees; monade de spécification). Le second style, “à pas amples”, est hybride: dans une couche inférieure, on conserve le même interprète monadique, exprimé dans la monade libre; dans une couche supérieure, on raisonne à l'aide d'une sémantique opérationnelle à petits pas. J'aimerais recevoir des commentaires et suggestions du public afin de prévoir les prochaines étapes: ajout du non-déterminisme, du parallélisme, de l'état mutable, puis construction d'une logique de programmes de la famille Iris.

La combinatoire des statistiques (longueur de la plus longue sous-suite croissante, le nombre d'apparitions de motifs ou encore la structure en cycle d'un mot etc.) sur les permutations est généralement bien comprise, Cependant, lorsque l'on restreint l'étude à une classe de conjugaison, la question devient plus difficile. Par exemple, il reste difficile de comprendre le comportement de la longueur de la plus longue sous-suite croissante pour des permutations uniformément choisis parmi celles ayant n/3 cycles de longueur 3.

Dans cet exposé, je présente quelques résultats et plusieurs conjectures sur des phénomènes où seuls les petits cycles jouent un rôle asymptotiquement.

(Basé sur des travaux avec Natasha Blitvić, Mylène Maïda et Einar Steingrímsson.)

In this talk we will study different positivity notions that exist for tropical flag varieties. We will start with an introduction to tropical flag varieties and the related polyhedral subdivisions. After explaining what each notion of positivity is and how do they relate to each other, I will provide equations on the Plücker coordinates for each of them. Finally, we discuss the cases where we know that these equations are sufficient.

Topology-based geometric modeling deals with the representation of nD objects, which splits the topological description, i.e., the representation of the objects' topological cells (vertices, edges, faces, volumes, …), and the geometric information, i.e., the addition of data to the topological cells. We study the combinatorial models of generalized and oriented maps represented as attributed typed graphs subject to consistency conditions. This representation allows the study of modeling operations as graph rewriting rules. The motivation is twofold. First, we study the preservation of the model consistency through syntactic conditions statically checked on the rules. Second, we extend rules into rule schemes to abstract over the underlying topology. This formalization of modeling operations also offers guidelines for inferring operations from a representative example consisting of an initial and a target object. The inference mechanism is implemented in Jerboa, a platform for designing geometric modelers exploiting graph transformation rules.

The study of combinatorial optimization problems with a submodular objective has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. A few examples of such functions include cuts functions of graphs and hypergraphs, rank functions of matroids, and covering functions.

Let $N = {u_1, u_2, ..., u_n}$ be a ground set of elements, A function $F : 2^{\mathcal{N}} \to R_{\geq 0}$ is submodular if for every $A \subset B \subset \mathcal{N}$ and $u \in \mathcal{N} \setminus B$, $F(A\cup\{u\})−F(A) \geq F (B \cup \{u\}) − F (B)$. Since the submodular maximization problem is NP-hard, we will discuss some important approximation algorithms of the constrained versions of the problem in both monotone and non-monotone cases.