Invited Seminars
Thematic month
The five weeks

Seminar On Combinatorics On Words
This seminar is organized by Anna Frid.
The seminar on 1012 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 nonintersecting 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 kcolorings) 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 kletters alphabet, for 5<=k<=10. As an consequence, we establish the exponential growth of the number of Dejean words over a kletter 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: 2Drepetitions in binary 2Dwords
 A 2Dword 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 2Dwords, and discuss some of the first questions coming to mind. What is the smallest unavoidable exponent for an infinite binary 2Dword? What is the highest exponent in the 2Dword constructed from the ThueMorse word by a summation modulo 2? Given a period, is it possible to construct a 2Dword with no arbitrarily high exponent for this period?
 Wednesday, May 12, 11.00 Jean Philippe Labbé: Canonical representatives of Cantorian Tableaux and biCantorian 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 biCantorian tableaux follow. Sage helped.
The seminar on 69 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.
Programme
 Tuesday, April 6
 9:3010.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:0012.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:0015.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:3010: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:0015.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
