Tag: combinatorics
Language-theoretic methods in semigroup theory
Language-theoretic methods in combinatorial group theory go back to the fundamental work by Anisimov in the 1970s. Since then, the area has exploded, including such deep theorems as the Muller-Schupp theorem: a group has context-free word problem if and only if it is virtually free. In this talk, I will ...
The Domino Snake Problem
summary: Deep within the swamp of undecidability lies the elusive domino snake. This species, first discovered in the 1970s by Myers, was originally introduced as an a priori simpler problem than the now celebrated Domino Problem. In this talk we will take a tour through what is known about this ...
The fixed-point construction in tilings
summary: Consider a tileset, i.e. a finite set of colors along with some adjacency constraints between them. It defines the set of colorings of the infinite grid that respects these adjacency constraints. Such a coloring is called a tiling. Given a tileset as input, a question naturally arises: does ...
Lattice properties of acyclic pipe dreams
summary: Pipe dreams were introduced by Bergeron and Billey in order to study Schubert polynomials and encode the algebraic structure of the symmetric group. In particular, with well-chosen parameters, they have the combinatorial structure of the Tamari lattice, a well-known quotient of the weak order on permutations. In this presentation ...
Séries génératrices et preuves d'intrinsèque ambiguïté
Cet exposé porte sur la connexion entre l'intrinsèque ambiguïté en théorie des langages formels, et les propriétés des séries génératrices des langages associés. Il est bien connu que les langages réguliers ont des séries génératrices rationnelles et que les séries génératrices des langages algébriques non ambigus sont algébriques. Dans ...
Associaèdres cycliques et degrés intrinsèques des arborescences non-croisées
Le polytope de pivot d'un polytope P est une généralisation de son polytope des chemins monotones qui vise a capturer le comportement de la "shadow vertex rule" (une règle de pivot importante en optimisation linéaire et dans le domaine des polytopes de fibre). Il a récemment été montré que ...
Walking On A Line: finding S-adic walks in an ω-automaton
summary: At the heart of symbolic dynamics lies the study of languages, infinite words and the dynamical structures associated. We focus on two classical methods to generate such structures. The first one relies on substitutions, which are morphisms on words, by iterating one on an initial letter, and considering the ...
Séminaire ouvert
Lors d'un séminaire ouvert, le thème n'est pas décidé à l'avance. Tous les membres du séminaires sont invités à participer et peuvent proposer le jour même des interventions plus ou moins longues, des démos ou des questions ouvertes au reste de l'équipe.
Realizing Geometrically s-Permutahedra via Flow Polytopes
summary: In 2020, Ceballos and Pons defined s-decreasing trees with s being a weak composition. They described an order on these objects called the s-weak order which gives them the order structure of a lattice. They further conjectured that this structure could be realized geometrically as the 1-skeleton of a ...
A realization of poset associahedra as sections of graph associahedra
Poset associahedra are a family of convex polytopes introduced by Pavel Galashin in 2021, each one associated to a partially ordered set, that generalize the classical associahedron. Galashin describes the combinatorial structure of poset associahedra, and he realizes them as convex polytopes. However, his construction is not completely satisfactory. In ...