Math-Info 2010

Towards new interactions between mathematics and computer science


Invited Seminars

Thematic month

The five weeks

Seminar On Combinatorics On Words

This seminar is organized by Anna Frid.

The seminar on 10-12 May 2010.

  • This seminar was focused on the pattern avoidance and in particular on the topics around the Dejean conjecture recently proved after more than 30 years of attempts by several groups including some of the speakers. Like the previous time, free discussions were scheduled in addition to the regular conference talks.
    • Monday, May 10, 9.30 Pascal Ochem: Repetition thresholds for trees and large graph subdivisions
      • We consider the words corresponding to the sequences of colors induced by the non-intersecting paths of a colored graph. Given a number of colors k (i.e., alphabet size), the repetition threshold of a graph is the minimum (over all k-colorings) of the maximum exponent of these words. The repetition threshold of a graph class is the maximum of the repetition threshold of the graphs in the class. Dejean's conjecture gives the repetition thresholds for the class of paths. In this talk, we give in particular the repetition thresholds for the class of trees: 7/2, 5/2, and 3/2, respectively for k=2, k=3, and k>=4.
    • Tuesday, May 11, 9.30 Michael Rao: Growth factor of Dejean words over small alphabets
      • We give lower and upper bounds on the growth factor of Dejean words, i.e. minimally repetitive words over a k-letters alphabet, for 5<=k<=10. As an consequence, we establish the exponential growth of the number of Dejean words over a k-letter alphabet, for 5<=k<=10. For k=3, 4 this fact was proved by [Ochem 2004]. (Joint work with Roman Kolpakov.)
    • Wednesday, May 12, 9.30 Elise Vaslet: 2D-repetitions in binary 2D-words
      • A 2D-word is an array {$(x_{i,j})$} of symbols over a finite alphabet. We will give a possible generalization of the standard notions of repetition and exponent. We will then focus on the case of the binary 2D-words, and discuss some of the first questions coming to mind. What is the smallest unavoidable exponent for an infinite binary 2D-word? What is the highest exponent in the 2D-word constructed from the Thue-Morse word by a summation modulo 2? Given a period, is it possible to construct a 2D-word with no arbitrarily high exponent for this period?
    • Wednesday, May 12, 11.00 Jean Philippe Labbé: Canonical representatives of Cantorian Tableaux and bi-Cantorian tableaux
      • Brlek, Mendès France, Robson and Rubey introduced the notion of Cantorian tableau as a finite interpretation of the celebrated infinite Cantor Diagonal. A convenient equivalence relation allows to generate, and is useful for getting enumeration results. Extensions to bi-Cantorian tableaux follow. Sage helped.

The seminar on 6-9 April 2010.

  • The speakers were Sébastien Ferenczi, Narad Rampersad, Kalle Saari, and Luca Zamboni.
  • The problems discussed included variations of the complexity measures for words and languages, their abelian properties and pattern avoidance. Another direction concerns relations between infinite words and infinite permutations.
  • The talks took place during the first two days of the event; the 8 and 9 of April were devoted to free discussions.


  • Tuesday, April 6
    • 9:30-10.30 Kalle Saari: Avoiding Abelian powers in binary words with bounded Abelian complexity
      • A recent application of van der Waerden's theorem shows that bounded Abelian complexity implies the existence of Abelian powers of arbitrary order in an infinite word. In this talk we discuss the possibility of avoiding Abelian powers somewhere in words with bounded Abelian complexity.
    • 11:00-12.00 Narad Rampersad: Abelian Repetitions and Related Topics
      • I will discuss first the classical results on avoiding Abelian squares and cubes and the main techniques used to prove these results. I will then discuss some results and open problems on avoiding more general patterns in the Abelian sense. I will also talk about some recent results concerning the Abelian complexity of infinite words.
    • 14:00-15.00 Sébastien Ferenczi: Substitutions as dynamical systems: An introduction
      • This lecture is supposed to help pure combinatoricians to understand the jargon, and possibly the beauties, of dynamical systems.
  • Wednesday, April 7
    • 9:30-10:30 Luca Zamboni: Some applications of infinitary Ramsey theory to words
      • We consider some applications of the infinitary version of Ramsey's theorem to combinatorics on words. In particular, we apply Ramsey's theorem to obtain a characterization of recurrent aperiodic binary words in terms of their maximal abelian pattern complexity, that is to say the abelian version of Kamae's maximal pattern complexity. We also discuss an analogous characterization of recurrent words on 3 or more symbols which are not periodic under a letter to letter projection to a binary alphabet.
    • 14:00-15.00 Sébastien Ferenczi: Substitutions on an infinite alphabet
      • By stuying several examples, the most important being the drunken man substitution, we endeavour to begin a theory of these objects, with emphasis on the associated dynmical systems.

Uploaded slides


For any technical question or comment regarding this wiki, you can contact the wemaster.