Thuejev izrek o brezkvadratnih besedah in neizogibni vzorci

slovenski

2026

letnik 13, številka 1

brezkvadratne besede   kombinatorika besed   vzorci

Univerza v Ljubljani, Fakulteta za matematiko in fiziko
(Obvezni izvod spletne publikacije)

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.

23.09.2026