Page locked

This page is currently locked for editing by another user. You have to wait until this user finishes editing or the lock expires.
Currently locked by: 138.226.21.230
Lock expires at: 2025/12/11 14:29 (15 min)
This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
Here are the talks of [[start|One World Combinatorics on Words Seminar]] dated 2020.

**14 December 2020: [[http://www.slabbe.org|Sébastien Labbé]]** //A characterization of Sturmian sequences by indistinguishable asymptotic pairs//

{{seminar2020:slides20201214labbe.pdf|slides}}

{{ seminar2020:20201214labbe.mp4 |Video of the talk}}


We give a new characterization of Sturmian configurations in terms of indistinguishable asymptotic pairs. Two asymptotic configurations on a full $\mathbb{Z}$-shift are indistinguishable if the sets of occurrences of every pattern in each configuration coincide up to a finitely supported permutation. This characterization can be seen as an extension to biinfinite sequences of Pirillo's theorem which characterizes Christoffel words. Furthermore, we provide a full characterization of indistinguishable asymptotic pairs on arbitrary alphabets using substitutions and characteristic Sturmian sequences. The proof is based on the well-known notion of derived sequences.

This is joint work with Sebastián Barbieri and Štěpán Starosta. Preprint is available at https://arxiv.org/abs/2011.08112


**7 December 2020: [[https://sites.google.com/view/marielejeune|Marie Lejeune]]** //Reconstructing words from right-bounded-block words//


{{ seminar2020:slides20201207lejeune.pdf |slides}}

{{ seminar2020:20201207lejeune.mp4 |Video of the talk}}

In this joint work with P. Fleischmann, F. Manea, D. Nowotka, and M. Rigo, we study a variation of the famous reconstruction problem over words. It has been studied since $1973$. A survey of the different results will be held in the talk.

We study a variation of this problem.
Let $\mathcal{A}$ be a given alphabet and $n$ a natural number. We want to reconstruct a hidden word $w \in \mathcal{A}^n$. To that aim, we are allowed to pick a word $u_i$ and ask questions of the type "What is the multiplicity of $u_i$ as subword of $w$?". Based on the answers to questions related to words $u_1, \ldots, u_i$, we can decide which will be the next question (i.e. decide which word will be $u_{i+1}$). We want to have the shortest sequence $(u_1, \ldots, u_k)$ uniquely determining $w$.

We naturally look for a value of $k$ less than the upper known bound for $k$-reconstructibility.

We will show how to reconstruct a binary word $w$ from $m+1$ questions, where $m$ is the minimum number of occurrences of '' a'' and ''b'' in the word. We then reduce the problem for arbitrary finite alphabets to the binary case. We compare our bounds to the best known one for the classical reconstruction problem.



**23 November 2020: [[http://www.discmath.ulg.ac.be/charlier/|Émilie Charlier]]** //Regular sequences in abstract numeration systems//

{{ seminar2020:slides20201123charlier.pdf |slides}}

{{ seminar2020:20201123charlier.mp4 |Video of the talk}}

An abstract numeration system $S$ is given by a regular language $L$ over a totally ordered alphabet $(A,<)$. The numeration language $L$ is ordered thanks to the radix (or genealogical) order induced by $<$. A natural number $n$ is then represented by the $n$-th word of the language (where we start counting from $n=0$). Integer bases $b$ and numeration systems based on a linear base sequence $U$ with a regular numeration language are examples of abstract numeration systems. The notion of $b$-regular sequences was extended to abstract numeration systems by Maes and Rigo. Their definition is based on a notion of $S$-kernel that extends that of $b$-kernel. However, this definition does not allow us to generalize all of the many characterizations of $b$-regular sequences. In this talk, I will present an alternative definition of $S$-kernel, and hence an alternative definition of $S$-regular sequences, that permits us to use recognizable formal series in order to generalize most (if not all) known characterizations of $b$-regular sequences. I will also show that an extra characterization can be obtained in the case of Pisot numeration systems. Finally, I will consider the special cases of $S$-automatic and $S$-synchronized sequences. In particular, we will see that the factor complexity of an $S$-automatic sequence defines an $S$-regular sequence. This is a joint work with Célia Cisternino and Manon Stipulanti.


**9 November 2020: [[https://ericrowland.github.io/|Eric Rowland]]** //Avoiding fractional powers on an infinite alphabet//

{{ seminar2020:slides20201109rowland.pdf |slides}}

{{ seminar2020:20201109rowland.mp4 |Video of the talk}}

Questions concerning avoidability of patterns have been central to combinatorics on words since the work of Thue. In 2009, Guay-Paquet and Shallit gave several results about pattern avoidance of words on the alphabet of natural numbers. Most patterns are avoidable on this alphabet, but it is interesting to ask about the lexicographically least word that avoids a pattern. For fractional powers, often this word is generated by a relatively simple morphism. In recent work with Manon Stipulanti, we discovered the structure of the lexicographically least $5/4$-power-free word on the natural numbers. In a surprising departure from previously studied words, the morphism generating this word does not preserve $5/4$-power-freeness.


**26 October 2020: [[http://pageperso.lif.univ-mrs.fr/~matthieu.rosenfeld/Research.html|Matthieu Rosenfeld]]** //A simple proof technique to study avoidability of repetitions//

{{ seminar2020:slides20201026rosenfeld.pdf |slides}}

{{ seminar2020:20201026rosenfeld.mp4 |Video of the talk}}

I recently described a new proof technique that I used to study nonrepetitive colorings of graphs. This technique is in fact more general and seems to be as powerful as the Lovász local lemma or the entropy compression method.  For instance, it has since been used by D.R. Wood and I.M. Wanless in the context  of boolean satisfiability problem and of hypergraph colorings. In the particular context of combinatorics on words similar approaches had already been used by different authors, but were never extended to graphs or other structures.

In this talk, I will first present some simple applications of the method to combinatorics on words and I will then explain how to extend this approach to nonrepetitive colorings of graphs of bounded degree.

**19 October 2020: [[http://dutiosc.twi.tudelft.nl/~dekking/|Michel Dekking]]** //The structure of Zeckendorf representations and base $\varphi$ expansions//

{{ seminar2020:slides20201019dekking.pdf|slides}}

{{ seminar2020:20201019dekking.mp4 |Video of the talk}}

In the Zeckendorf numeration system natural numbers are represented as sums of Fibonacci numbers. In base $\varphi$ natural numbers are represented as sums of powers of the golden mean $\varphi$. Both representations have digits 0 and 1, where the word 11 is not allowed. We know that the Fibonacci numbers, and the powers of $\varphi$ are closely related, as, for example, in the relation $\varphi^n=F_{n-1}+F_n\varphi$. In fact, Frougny and Sakarovitch have shown that Zeckendorf representations can be transformed to base $\varphi$ expansions by a 2-tape automaton. I will take a direct approach: what are the words that can occur in the Zeckendorf representations, and what are those that occur in base $\varphi$ expansions?  In which representations/expansions, of which natural numbers do they occur?

**5 October 2020: [[https://www.tcs.uj.edu.pl/en_GB/Grytczuk|Jarosław Grytczuk]]** //Graph Coloring and Combinatorics on Words//

{{ seminar2020:slides20201005grytczuk.pdf|slides}}

 {{ seminar2020:20201005grytczuk.mp4 |Video of the talk}}

I will present a few problems inspired mutually by various issues studied in the two disciplines of the title. For instance, given any sequence of 3-letter alphabets, is it possible to pick a letter from each alphabet so that the resulting word is //square-free//? The case of equal alphabets is covered by the famous result of Thue, but intuition tells us that this should be the hardest case (the more different letters in the play, the easier to avoid repeated factors). While more than one has attacked the problem, the question remains unanswered, which is especially frustrating as it has a positive answer with 4-letter alphabets.
The above question was originally motivated by the //list coloring// problem, a very popular topic in graph coloring. However, the opposite direction of inspiration also leads to intriguing matters. For example, how many letters are needed to label the vertices of a //planar graph// so that any word occurring along a simple path is square-free? It has been recently proved that 768 letters suffice, but for a long time it was not known if any finite alphabet will do. Perhaps results of that type could be applied back to some pattern avoidability issues...?



**28 September 2020: [[https://www.utu.fi/en/people/jarkko-peltomaki|Jarkko Peltomäki]]** //Avoiding abelian powers cyclically//

{{ seminar2020:slides20200928peltomaki.pdf|slides}}

//Sorry, the video of the talk was not recorded//

A finite word $w$ avoids abelian $N$-powers cyclically if for each
abelian $N$-power of period $m$, we have $m \geq |w|$. This notion
generalizes circular avoidance of $N$-powers in two ways. Firstly
"power" is replaced by "abelian power" and secondly circular avoidance
concerns only the conjugacy class of a word, but here we require even
more. Let $\mathcal{A}(k)$ be the least integer $N$ such that for all
$n$ there exists a word of length $n$ over a $k$-letter alphabet that
avoids abelian $N$-powers cyclically. Let $\mathcal{A}_\infty(k)$ be the
least integer $N$ such that there exist arbitrarily long words over a
$k$-letter alphabet that avoid abelian $N$-powers cyclically.

I will sketch the proofs of the following results: 1) $5 \leq
\mathcal{A}(2) \leq 8$, $3 \leq \mathcal{A}(3) \leq 4$, $2 \leq
\mathcal{A}(4) \leq 3$, $\mathcal{A}(k) = 2$ for $k \geq 5$; 2)
$\mathcal{A}_\infty(2) = 4$, $\mathcal{A}_\infty(3) = 3$, and
$\mathcal{A}_\infty(4) = 2$. If time permits, I will discuss an
application to the growth rates of exponents of abelian powers occurring
in infinite binary words.

**14 September 2020: [[http://www.open.ac.uk/people/ry652|Reem Yassawi]]** //The Ellis semigroup of bijective substitution shifts// {{ seminar2020:abstract20200914yassawi.pdf|abstract}}

{{ seminar2020:slides20200914yassawi.pdf|slides}}

 {{ seminar2020:20200914yassawi.mp4 |Video of the talk}}

**27 July 2020 - [[https://www.uwinnipeg.ca/mathstats/faculty/james-currie.html|James Currie]]**, //Remarks on Pansiot encodings//

{{ seminar2020:slides20200727currie.pdf|slides}}

 {{ seminar2020:20200727currie.mp4 |Video of the talk}}

Pansiot encodings were an essential ingredient in the solution of Dejean's conjecture. We discuss these encodings, and the related group theoretic notions, in a way perhaps more natural to combinatorics on words, namely, in terms of De Bruijn graphs. We discuss variations on Pansiot encodings, with applications to circular words, and to the undirected threshold problem.  



**20 July 2020 - [[https://www.lama.univ-savoie.fr/pagesmembres/vuillon/indexang.html|Laurent Vuillon]]**, //Combinatorics on words for Markoff numbers// (joint work with Christophe Reutenauer) [[https://math.boku.ac.at/udt/vol12/no2/03ReutVuill.pdf|paper]]


{{ seminar2020:slides20200720vuillon.pdf|slides}}

 {{ seminar2020:20200720vuillon.mp4 |Video of the talk}}



Markoff numbers are fascinating integers related to number
theory, Diophantine equation, hyperbolic geometry, continued fractions
and Christoffel words. Many great mathematicians have worked on these
numbers and the $100$ years famous uniqueness conjecture by Frobenius is
still unsolved. In this talk, we state a new formula to compute the
Markoff numbers using iterated palindromic closure and the Thue-Morse
substitution. The main theorem shows that for each Markoff number $m$,
there exists a word $v\in \{a,b\}^*$ such that $m−2$ is equal to the length of the iterated palindromic
closure of the iterated antipalindromic closure of the word $av$. This
construction gives a new recursive construction of the Markoff numbers
by the lengths of the words involved in the palindromic closure.



**13 July 2020 - [[http://www.math.ulg.ac.be/rigo/|Michel Rigo]]** //Binomial$^3$ : coefficients, equivalence, complexity...//

 {{ seminar2020:slides20200713rigo.pdf |slides}}

 {{ seminar2020:20200713rigo.mp4 |Video of the talk}}

The binomial coefficient $x \choose y$ of the words $x$ and $y$ is the number of times $y$ appears as a (scattered) subword of $x$. This concept has received a lot of attention, e.g., Simon's congruence, Parikh matrices, reconstruction problem, ... A few years ago, we introduced the $k$-binomial equivalence: Two words $u$ and $v$ are $k$-binomially equivalent if the binomial coefficients $u \choose x$ and $v \choose x$ agree for all words $x$ of length up to $k$. This is a refinement of the usual abelian equivalence.

First, I will review several results (joint work with P. Salimov, M. Lejeune, J. Leroy, M. Rosenfeld) related to $k$-binomial complexity (where factors of length $n$ are counted up to $k$-binomial equivalence) for Sturmian words, Thue-Morse word and Tribonacci word. Then I will concentrate on $k$-binomial equivalence classes for finite words. In particular, I will discuss the fact that the submonoid generated by the generators of the free nil-$2$ group on $m$ generators is isomorphic to the quotient of the free monoid $\{1,...,m\}^∗$ by the $2$-binomial equivalence (joint work with M. Lejeune, M. Rosenfeld).


**29 June 2020 - [[http://ion.uwinnipeg.ca/~lmol/|Lucas Mol]]**, //Extremal Square-Free Words and Variations// (joint work with Narad Rampersad and Jeffrey Shallit)

 {{ seminar2020:slides20200629mol.pdf |slides}}

 {{ seminar2020:20200629mol.mp4 |Video of the talk}}

A square-free word $w$ over a fixed alphabet $\Sigma$ is //extremal// if every word obtained from $w$ by inserting a single letter from $\Sigma$ (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word, and demonstrated that there are arbitrarily long extremal square-free words over a ternary alphabet. One can define extremal overlap-free words, and more generally, extremal $\beta$-free words, analogously. We characterize the lengths of extremal square-free ternary words, and the lengths of extremal overlap-free binary words. We also establish that there are arbitrarily long extremal $\beta$-free binary words for every $2 < \beta \leq 8/3$. We include a variety of interesting conjectures and open questions.