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- berisi semua pola yang mungkin mengenai panjang .

Definisi dan contoh 
Jika  merupakan sebuah permutasi panjang , diwakili sebagai sebuah barisan dari bilangan dari 1 ke  dalam suatu urutan, dan  merupakan sebuah subbarisan  dari panjang , maka  berpadan dengan sebuah pola tunggal, sebuah permutasi panjang  yang unsur-unsurnya ada di dalam urutan yang sama sebagai . Yakni, untuk setiap pasangan  dan  dari indeks, unsur ke- dari pola untuk  seharusnya menjadi lebih kecil daripada unsur ke- jika dan hanya jika unsur ke- dari  lebih kecil dari unsur ke-. Dengan setara, polanya adalah isomorfik-urutan ke subbarisan. Contoh, jika  adalah permutasi 25314, maka ini memiliki sepuluh subbarisan panjang tiga, membentuk pola berikut:

Sebuah permutasi  disebut sebuah superpola- jika pola panjang  mencakup semua dari permutasi panjang-. 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.

Batas panjang 
 memperkenalkan masalah menentukan panjang dari superpola- kemungkinan terkecil. Dia mengamati bahwa terdapat sebuah superpola panjang  (diberikan oleh pengurutan leksikografik pada vektor koordinat mengenai titik-titik dalam sebuah kisi kuadrat) dan juga diamati bahwa, untuk sebuah superpola panjang , ini harus menjadi kasus bahwa ini memiliki banyak subbarisan karena terdapat pola. Yakni, ini harus menjadi benar bahwa , untuk yang ini mengikuti oleh hampiran Stirling bahwa , dimana  adalah bilangan Euler. Batas bawah ini kemudian disempurnakan sangat sedikit oleh , yang ditingkatkan ke , membantah konjektur Arratia bahwa batas bawah  adalah ketat.

Batas atas  mengenai panjang superpola dibuktikan oleh Arratia tidak ketat. Setelah antara penyempurnaan,  membuktikan bahwa terdapat sebuah superpola- dari panjang setidaknya  untuk setiap . Batas ini kemudian disempurnakan oleh , yang menurunkannya ke .

Eriksson dkk. menduga bahwa panjang yang benar dari superpola- terpendek adalah asimtotik ke . Namun, ini ada di dalam kontradiksi dengan sebuah konjektur Alon pada superpola acak yang dijelaskan di bawah.

Superpola acak 
Peneliti juga telah mempelajari panjang dibutuhkan untuk sebuah barisan dihasilkan oleh sebuah proses acak menjadi sebuah superpola.  mengamati bahwa, karena subbarisan meningkat terpanjang mengenai sebuah permutasi acak memiliki panjang (dengan probabilitas tinggi) kira-kira , ini mengikuti bahwa sebuah permutasi acak harus memiliki panjang setidaknya  untuk memiliki probabilitas tinggi menjadi sebuah permutasi superpola- yang lebih pendek daripada ini akan kemungkinan tidak berisi pola identitas. Dia menghubungkan ke Alon, konjekturnya bahwa, untuk suatu , dengan probabilitas tinggi, permutasi acak dari panjang  akan menjadi superpola-.

Lihat pula 

 Superpermutasi

Referensi 

Pola permutasi