Superpola

Dalam studi matematis mengenai permutasi dan pola permutasi, sebuah superpola atau permutasi semesta merupakan sebuah permutasi yang berisi semua pola mengenai sebuah panjang yang diberikan. Lebih spesifiknya, sebuah superpola-${\displaystyle k}$ berisi semua pola yang mungkin mengenai panjang ${\displaystyle k}$.^[1]

Jika ${\displaystyle \pi }$ merupakan sebuah permutasi panjang ${\displaystyle n}$, diwakili sebagai sebuah barisan dari bilangan dari 1 ke ${\displaystyle n}$ dalam suatu urutan, dan ${\displaystyle s=s_{1},s_{2},\dots ,s_{k}}$ merupakan sebuah subbarisan ${\displaystyle \pi }$ dari panjang ${\displaystyle k}$, maka ${\displaystyle s}$ berpadan dengan sebuah pola tunggal, sebuah permutasi panjang ${\displaystyle k}$ yang unsur-unsurnya ada di dalam urutan yang sama sebagai ${\displaystyle s}$. Yakni, untuk setiap pasangan ${\displaystyle i}$ dan ${\displaystyle j}$ dari indeks, unsur ke-${\displaystyle i}$ dari pola untuk ${\displaystyle s}$ seharusnya menjadi lebih kecil daripada unsur ke-${\displaystyle j}$ jika dan hanya jika unsur ke-${\displaystyle i}$ dari ${\displaystyle s}$ lebih kecil dari unsur ke-${\displaystyle j}$. Dengan setara, polanya adalah isomorfik-urutan ke subbarisan. Contoh, jika ${\displaystyle \pi }$ adalah permutasi 25314, maka ini memiliki sepuluh subbarisan panjang tiga, membentuk pola berikut:

Sebuah permutasi ${\displaystyle \pi }$ disebut sebuah superpola-${\displaystyle k}$ jika pola panjang ${\displaystyle k}$ mencakup semua dari permutasi panjang-${\displaystyle k}$. Misalnya, pola panjang-3 dari 25314 mencakup semua enam dari permutasi panjang-3, jadi 25314 adalah sebuah superpola-3. Tidak ada superpola-3 dapat menjadi lebih pendek, karena suatu dua subbarisan yang membentuk dua pola 123 dan 321 dapat hanya memotong dalam sebuah posisi tunggal, jadi lima simbol diperlukan hanya untuk meliputi dua pola ini.

Arratia (1999) memperkenalkan masalah menentukan panjang dari superpola-${\displaystyle k}$ kemungkinan terkecil.^[2] Dia mengamati bahwa terdapat sebuah superpola panjang ${\displaystyle k^{2}}$ (diberikan oleh pengurutan leksikografik pada vektor koordinat mengenai titik-titik dalam sebuah kisi kuadrat) dan juga diamati bahwa, untuk sebuah superpola panjang ${\displaystyle n}$, ini harus menjadi kasus bahwa ini memiliki banyak subbarisan karena terdapat pola. Yakni, ini harus menjadi benar bahwa ${\displaystyle {\binom {n}{k}}\geq k!}$, untuk yang ini mengikuti oleh hampiran Stirling bahwa ${\displaystyle n\geq {\frac {k^{2}}{e^{2}}}}$, dimana ${\displaystyle e\approx 2.71828}$ adalah bilangan Euler. Batas bawah ini kemudian disempurnakan sangat sedikit oleh Chroman, Kwan, and Singhal (2020), yang ditingkatkan ke ${\displaystyle {\frac {1.000076k^{2}}{e^{2}}}}$,^[3] membantah konjektur Arratia bahwa batas bawah ${\displaystyle {\frac {k^{2}}{e^{2}}}}$ adalah ketat.^[2]

Batas atas ${\displaystyle k^{2}}$ mengenai panjang superpola dibuktikan oleh Arratia tidak ketat. Setelah antara penyempurnaan,^[4] Miller (2009) membuktikan bahwa terdapat sebuah superpola-${\displaystyle k}$ dari panjang setidaknya ${\displaystyle {\frac {k(k+1)}{2}}}$ untuk setiap ${\displaystyle k}$.^[5] Batas ini kemudian disempurnakan oleh Engen and Vatter (2019), yang menurunkannya ke ${\displaystyle \left\lceil {\frac {k^{2}+1}{2}}\right\rceil }$.^[6]

Eriksson dkk. menduga bahwa panjang yang benar dari superpola-${\displaystyle k}$ terpendek adalah asimtotik ke ${\displaystyle {\frac {k^{2}}{2}}}$.^[4] Namun, ini ada di dalam kontradiksi dengan sebuah konjektur Alon pada superpola acak yang dijelaskan di bawah.

Peneliti juga telah mempelajari panjang dibutuhkan untuk sebuah barisan dihasilkan oleh sebuah proses acak menjadi sebuah superpola.^[7] (Arratia 1999) mengamati bahwa, karena subbarisan meningkat terpanjang mengenai sebuah permutasi acak memiliki panjang (dengan probabilitas tinggi) kira-kira ${\displaystyle 2{\sqrt {n}}}$, ini mengikuti bahwa sebuah permutasi acak harus memiliki panjang setidaknya ${\displaystyle {\frac {k^{2}}{4}}}$ untuk memiliki probabilitas tinggi menjadi sebuah permutasi superpola-${\displaystyle k}$ yang lebih pendek daripada ini akan kemungkinan tidak berisi pola identitas.^[2] Dia menghubungkan ke Alon, konjekturnya bahwa, untuk suatu ${\displaystyle \varepsilon >0}$, dengan probabilitas tinggi, permutasi acak dari panjang ${\displaystyle {\frac {k^{2}}{4-\varepsilon }}}$ akan menjadi superpola-${\displaystyle k}$.

• Superpermutasi

1. ^ Bóna, Miklós (2012), Combinatorics of Permutations, Discrete Mathematics and Its Applications, 72 (edisi ke-2nd), CRC Press, hlm. 227, ISBN 9781439850510 .
2. ^ ^{a b c} Arratia, Richard (1999), "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics, 6: N1, doi:10.37236/1477 , MR 1710623 
3. ^ Chroman, Zachary; Kwan, Matthew; Singhal, Mihir (2020), Lower bounds for superpatterns and universal sequences, arXiv:2004.02375  
4. ^ ^{a b} Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Dense packing of patterns in a permutation", Annals of Combinatorics, 11 (3–4): 459–470, doi:10.1007/s00026-007-0329-7, MR 2376116 
5. ^ Miller, Alison (2009), "Asymptotic bounds for permutations containing many different patterns", Journal of Combinatorial Theory, Series A, 116 (1): 92–108, doi:10.1016/j.jcta.2008.04.007 
6. ^ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly, 128 (1): 4–24, doi:10.1080/00029890.2021.1835384  
7. ^ Godbole, Anant; Liendo, Martha (2013), Waiting time distribution for the emergence of superpatterns, arXiv:1302.4668 , Bibcode:2013arXiv1302.4668G .