Wokół twierdzenia Morse’a – Hedlunda

Tematem przewodnim pracy jest twierdzenie Morse’a – Hedlunda.Przedstawione w pracy rozumowania dotyczą głównie nieskończonych szachownic jednowymiarowych pokolorowanych na skończenie wiele kolorów, czyli ciągów dwustronnie nieskończonych nad alfabetem skończonym. W pracy uogólniłam twierdzenia Morse’a – Hedlunda, nie korzystając przy tym z żadnej literatury. Na podstawie twierdzenia Morse’a – Hedlunda, ciągów Sturma oraz hipotezy Nivata starałam się pokazać, jak bardzo zróżnicowana jest funkcja złożoności Pη. Kolorując ciągi sprawdzałam, ile różnych prostokątów o danej długości można zobaczyć w takim ciągu. Twierdzenie Morse’a – Hedlunda dotyczy nieskończenie długich szachownic jednowymiarowych okresowych. Szachownica jest okresowa (istnieje takie k, że wybrany wzór szachownicy powtarza się, jak przesuniemy ją o k) wtedy i tylko wtedy, gdy istnieje takie n, że widzimy co najwyżej n różnych prostokątów o długości n. Natomiast hipoteza Nivata związana jest z szachownicami dwuwymiarowymi. Bardzo interesujący jest fakt, że hipoteza Nivata pochodzi z 1997 roku, a jednak w dalszym ciągu jeszcze nikt nie był w stanie jej udowodnić ani obalić. Znane są jedynie jej wyniki częściowe. Ciągi Sturma, którymi również się zajmowałam, związane są z szachownicami nieokresowymi. W pracy starałam się samodzielnie sprawdzić, jakie wartości może przyjmować funkcja złożoności ciągów. Kolorowałam szachownice na różne sposoby i sprawdzałam, kiedy można stwierdzić, że jest ona okresowa bądź nieokresowa. Aby tego dokonać, korzystałam z twierdzenia Morse’a – Hedlunda.

Gabriela Pietras
Termin: 
09/22/2018 - Od 12:15 do 12:40
Sala: 
D-227