Isomorphic substructures in words and permutations

Tematem pracy są izomorficzne podstruktury w strukturach kombinatorycznych, które w skrócie nazywać będziemybliźniakami. Interesuje nas problem znajdowania maksymalnych dwóch rozłącznych podstruktur w danej strukturze, które są izomorficzne. Problem ten był szeroko omawiany dla grafów. Praca skupia się na rozważaniu analogicznego problemu dla słów oraz permutacji. Rozdział pierwszy dotyczy problemu bliźniaków w słowach, zarówno z teoretycznego jak i algorytmicznego punktu widzenia. Główne wyniki tego rozdziału pochodzą z pracy Axenovich, Persona i Puzyniny . Pokazano między innymi zaskakującetwierdzenie , że w słowie długości znajdziemy bliźniaki długości n/2-o(n). Dowód twierdzenia zapewnia algorytm znajdujący bliźniaki tej długości, w rozdziale załączono implementację tego algorytmu. Rozdział drugi poświęcony jest problemowi bliźniaków w permutacjach. Podano dolne i górne ograniczenia na długość bliźniakóww dowolnej permutacji zbioru n-elementowego. Głównymi narzędziami w dowodzie są twierdzenie Erdosa-Szekeresa, lemat lokalnyLovasza oraz metoda probabilistyczna. Zaimplementowane zostały również algorytmy wyszukujące bliźniaki w permutacjach.

The main topic of the thesis are isomorphic substructures in words and permutations. We call them twins. We are interested infinding two maximal disjoint substructures in given structure. This problem has a long history for graphs. We investigate thisproblem for words and permutations.In Chapter one we consider twins in words form both theoretical and algorithmic point of view. The main results of this chapterare theorems of Axenovich, Person and Puzynina. They showed surprising theorem about maximal twins in word of lenth n. Moreprecisely they showed that in each word of lenth n there are twins of length at least n/2-o(n). Proof of this theorem gives an algorithm for finding such twins. We have implemented this algorithm.In Second Chapter we consider twins in permutations. We give lower and upper bound on length of twins in permutations of theset 1,2,...,n. The main tools which we used are Erdos-Szekeres theorem, Lovasz local lemma and probabilistic method. We alsoimplemented some algorithms which finds twins in permutations.