Apparaît dans la collection : Combinatorics on words / Combinatoire des mots - Week 5

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.