We show how to construct 'simple' symbolic dynamical systems in terms of renormalisation schemes associated with multidimensional continued fractions. Continued fractions are used here to generate infinite words thanks to the iteration of infinite sequences of substitutions. Simple means that these symbolic systems have a linear number of factors of a given length, or that they have pure discrete spectrum, or else, that they have a low symbolic discrepancy. We also discuss the relation between these notions.[-]

We consider the assignment (or bipartite matching) problem between $n$ source points and $n$ target points on the real line, where the assignment cost is a concave power of the distance, i.e. |x − y|p, for 0 < p < 1. It is known that, differently from the convex case (p > 1) where the solution is rigid, i.e. it does not depend on p, in the concave case it may varies with p and exhibit interesting long-range connections, making it more appropriate to model realistic situations, e.g. in economics and biology. In the random version of the problem, the points are samples of i.i.d. random variables, and one is interested in typical properties as the sample size n grows. Barthe and Bordenave in 2013 proved asymptotic upper and lower bounds in the range 0 < p < 1/2, which they conjectured to be sharp. Bobkov and Ledoux, in 2020, using optimal transport and Fourier-analytic tools, determined explicit upper bounds for the average assignment cost in the full range 0 < p < 1, naturally yielding to the conjecture that a “phase transition” occurs at p = 1/2. We settle affirmatively both conjectures. The novel mathematical tool that we develop, and may be of independent interest, is a formulation of Kantorovich problem based on Young integration theory, where the difference between two measures is replaced by the weak derivative of a function with finite q-variation.
Joint work with M. Goldman (arXiv:2305.09234).[-]

Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for participants to get some hands-on training on how to use Walnut.[-]

Walnut is computer software, written in Java, that implements an algorithm to decide the truth of first-order logic statements in an extension of Presburger arithmetic known as Buchi arithmetic. It can be used to prove a wide variety of results in combinatorics on words and number theory. In this course we will give an introduction to the theory behind Walnut, examples of the types of results that can be proved with it, and exercises for participants to get some hands-on training on how to use Walnut.[-]

Wang's tiles were introduced in the 1960s and have been an inexhaustible source of undecidable problems ever since. They are unit square tiles with colored edges and fixed orientation, which can be placed together provided they share the same color on their common edge. Many decision problems involving Wang tiles follow the same global structure: given a finite set of Wang tiles, is there an algorithm to determine if they tile a particular shape or subset of the infinite grid? If we look for a tiling of the whole grid, this is the domino problem which is known to be undecidable for Z2 and many other groups. In this talk we focus on infinite snake tilings. Originally the infinite snake problem asks is there exists a tiling of a self-avoiding bi-infinite path on the grid Z2. In this talk I present how to expand the scope of domino snake problems to finitely generated groups to understand how the underlying structure affects computability. This is joint work with Nicolás Bitar.[-]

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.[-]