Thuejev izrek o brezkvadratnih besedah in neizogibni vzorci

Predstavljena je kombinatorika besed in vzorci v besedah. Najprej so podane osnovne definicije. Pomembni pojmi so beseda, faktor in vzorec. Povedano je, kaj je vzorec, kdaj ga beseda vsebuje in kdaj se mu izogne. Posebej zanimiv je vzorec, ki se imenuje kvadrat. Formuliran in dokazan je Thuejev izrek, ki pove, da nad abecedo iz treh črk, obstajajo poljubno dolge besede, ki ne vsebujejo kvadrata. Nato je prikazana konstrukcija neskončne brezkvadratne besede nad abecedo iz treh črk. Nato je podana definicija brezprekrivnih besed. Primer takšne besede je Thue-Morseova beseda. Nato je predstavljen pojem (ne)izogibnosti vzorcev v besedah. Predstavljene so besede Zimina, ki določajo neizogibne vzorce. S pomočjo Ziminovega algoritma in pojma ireducibilnosti so karakterizirani neizogibni vzorci. Za neizogibne vzorce se poraja vprašanje, kako dolga mora biti beseda, da se vzorec gotovo pojavi. Na to vprašanje delno odgovorijo stolpične ocene, ki so obravnavane na koncu.

Thue's theorem about square-free words and unavoidable patterns

Combinatorics of words and patterns in words are briefly presented. Basic definitions are given at the beginning. Important terms are word, factor, and pattern. The definition of patterns is given next. It is explained when a word either contains or avoids a pattern. A pattern called a square is of particular interest. Thue's theorem, which says that there exist words of arbitrary length containing only three letters that do not contain a square, is formulated and proven. A construction of an infinite square-free word over a three-element alphabet follows next. Overlap-free words are defined. An example of such a word is the Thue-Morse word. Then the (un)avoidability of patterns in words is explained. Zimin words are presented and it is demonstrated that Zimin words determine unavoidable patterns. With the help of the Zimin algorithm and a notion of irreducibility, unavoidable patterns are characterised. For unavoidable patterns, one can ask, what is the minimum length of the word such that a given pattern certainly appears in a given word. A partial answer to this question is given by tower-type bounds, which are considered at the end.