Superwzór
W matematycznym badaniu permutacji i wzorców permutacji superwzorzec lub permutacja uniwersalna to permutacja zawierająca wszystkie wzorce o danej długości . Mówiąc dokładniej, k -superwzorzec zawiera wszystkie możliwe wzorce o długości k .
Definicje i przykład
Jeśli π jest permutacją o długości n , reprezentowaną jako ciąg liczb od 1 do n w pewnym porządku, a s = s 1 , s 2 , ..., s k jest podciągiem π o długości k , to s odpowiada unikalnemu wzorowi , permutacji o długości k , której elementy są w tej samej kolejności co s . Oznacza to, że dla każdej pary i oraz j indeksów, i element wzorca dla s powinien być mniejszy niż element j wtedy i tylko wtedy, gdy i- ty element s jest mniejszy niż element j . Równoważnie, wzór jest izomorficzny rzędu z podsekwencją. Na przykład, jeśli π jest permutacją 25314, to ma dziesięć podciągów o długości trzy, tworzących następujące wzory:
| Podsekwencja | Wzór |
|---|---|
| 253 | 132 |
| 251 | 231 |
| 254 | 132 |
| 231 | 231 |
| 234 | 123 |
| 214 | 213 |
| 531 | 321 |
| 534 | 312 |
| 514 | 312 |
| 314 | 213 |
Permutacja π nazywana jest k -superwzorem, jeśli jej wzorce o długości k obejmują wszystkie permutacje o długości k . Na przykład wzorce długości 3 25314 obejmują wszystkie sześć permutacji długości 3, więc 25314 jest superwzorem 3. Żaden 3-superwzorzec nie może być krótszy, ponieważ dowolne dwa podsekwencje, które tworzą dwa wzorce 123 i 321, mogą przecinać się tylko w jednej pozycji, więc pięć symboli jest potrzebnych tylko do pokrycia tych dwóch wzorców.
Granice długości
Arratia ( 1999 ) wprowadził problem wyznaczania długości najkrótszego k -superwzorca. Zaobserwował, że istnieje superwzorzec o długości k 2 (dany przez uporządkowanie leksykograficzne wektorów współrzędnych punktów w siatce kwadratowej), a także zauważył, że dla superwzorca o długości n musi być tak, że ma co najmniej tyle podsekwencji, ile jest wzorców. Oznacza to, że musi być prawdą, że , z czego wynika przez przybliżenie Stirlinga, że n ≥ k 2 / mi 2 , gdzie mi ≈ 2,71828 jest liczbą Eulera . Ta dolna granica została później bardzo nieznacznie poprawiona przez Chromana, Kwana i Singhala ( 2021 ), którzy zwiększyli ją do 1,000076 k 2 / e 2 , obalając przypuszczenie Arratii , że k 2 / e 2 dolna granica była ciasna.
Górna granica k 2 na długości superwzorca udowodniona przez Arratię nie jest ścisła. Po pośrednich ulepszeniach Miller ( 2009 ) udowodnił, że istnieje k -superwzorzec o długości co najwyżej k ( k + 1)/2 dla każdego k . Ta granica została później poprawiona przez Engena i Vattera ( 2021 ), którzy obniżyli ją do ⌈( k 2 + 1)/2⌉.
Eriksson i in. przypuszczał, że rzeczywista długość najkrótszego k -superwzorca jest asymptotyczna do k 2 /2. Jest to jednak sprzeczne z przypuszczeniami Alona na temat losowych superwzorców opisanych poniżej.
Losowe superwzorce
Naukowcy zbadali również długość potrzebną do tego, aby sekwencja wygenerowana w wyniku losowego procesu stała się superwzorem. Arratia (1999) zauważa, że ponieważ najdłuższy rosnący podsekw permutacji losowej ma długość (z dużym prawdopodobieństwem) w przybliżeniu 2√ n , wynika z tego, że losowa permutacja musi mieć długość co najmniej k 2 /4, aby mieć duże prawdopodobieństwo bycia k -superpattern: permutacje krótsze niż to prawdopodobnie nie będą zawierały wzorca tożsamości. Przypisuje Alonowi przypuszczenie, że dla każdego ε > 0 , z dużym prawdopodobieństwem losowe permutacje o długości k 2 /(4 − ε) będą k -superwzorcami.