النمط الفائق

في الدراسة الرياضية للتباديل وأنماطها ، يُعرف النمط الفائق أو التبديل الشامل بأنه تبديل يحتوي على جميع الأنماط ذات طول معين. وبشكل أكثر تحديدًا، يحتوي النمط الفائق من الرتبة k على جميع الأنماط الممكنة ذات الطول k . ^{[ 1 ]}

إذا كان π تبديلًا طوله n ، ممثلًا بتسلسل الأعداد من 1 إلى _{n بترتيب معين، وكانت s = s₁} , s₂ ,  ... , sₖ متتالية _جزئية من π طولها k ، فإن _s تُقابل نمطًا فريدًا ، وهو تبديل طوله k عناصره بنفس ترتيب s . أي، لكل زوج من المؤشرات i و j ، يجب أن يكون العنصر i في نمط s أصغر من العنصر j إذا وفقط إذا كان العنصر i في s أصغر من العنصر j . وبصورة مكافئة، يكون النمط متماثلًا ترتيبيًا مع المتتالية الجزئية. على سبيل المثال، إذا كان π هو التبديل 25314، فإنه يحتوي على عشر متتاليات جزئية طول كل منها ثلاثة، تُشكل الأنماط التالية: 

يُطلق على التبديل π اسم نمط فائق من الرتبة k إذا كانت أنماطه ذات الطول k تشمل جميع التبديلات ذات الطول k . على سبيل المثال، تشمل أنماط 25314 ذات الطول 3 جميع التبديلات الستة ذات الطول 3، لذا فإن 25314 هو نمط فائق من الرتبة 3. لا يمكن أن يكون أي نمط فائق من الرتبة 3 أقصر من ذلك، لأن أي سلسلتين فرعيتين تُشكلان النمطين 123 و321 لا يمكن أن تتقاطعا إلا في موضع واحد، لذا يلزم خمسة رموز لتغطية هذين النمطين فقط.

طرح أراتيا ( 1999 ) مشكلة تحديد طول أقصر نمط فائق ممكن من الرتبة k . ^{[ 2 ]} ولاحظ وجود نمط فائق بطول k² ⁽ يُحدد بالترتيب المعجمي لمتجهات إحداثيات النقاط في شبكة مربعة)، كما لاحظ أنه بالنسبة لنمط فائق بطول n ، يجب أن يحتوي على عدد من المتتاليات الفرعية يساوي على الأقل عدد الأنماط. أي أنه يجب أن يكون صحيحًا أن ${\displaystyle {\tbinom {n}{k}}\geq k!}$^{ومن ثم ،} يستنتج بتقريب ستيرلينغ أن n  ≥ k² / e² ، حيث e ≈ 2.71828 هو عدد أويلر . وقد حسّن كرومان وكوان وسينغال ( 2021 ) هذا الحد الأدنى تحسينًا طفيفًا ^، إذ رفعوه إلى 1.000076 k² / e² ^{، [ 3 ]} داحضين بذلك تخمين أراتيا بأن الحد ^{الأدنى k²} / e² ^كان دقيقًا . ^{[ 2 ]}    

إن الحد الأعلى لطول النمط الفائق k² الذي أثبته أراتيا ليس دقيقًا. بعد تحسينات وسيطة، ^{[ 4 ]} أثبت ميلر ( 2009 ) وجود نمط فائق من الرتبة k بطول لا يتجاوز k ( k + 1)/2 لكل قيمة لـ ^k . [ ^{5 ] وقد} حسّن إنجين وفاتر ( 2021 ) هذا الحد لاحقًا ^، حيث خفّضاه إلى ⌈( k² ⁺ 1 )/2⌉. ^[ 6 ^]      

افترض إريكسون وآخرون أن الطول الحقيقي لأقصر نمط فائق k يقترب من k ² /2. ^{[ 4 ]} ومع ذلك، فإن هذا يتعارض مع تخمين ألون حول الأنماط الفائقة العشوائية الموصوفة أدناه.

درس الباحثون أيضًا الطول اللازم لتسلسل مُوَلَّد بعملية عشوائية ليصبح نمطًا فائقًا. ^{[ 7 ]} لاحظ أراتيا (1999) أنه نظرًا لأن أطول تسلسل فرعي متزايد في تبديل عشوائي يبلغ طوله (باحتمالية عالية) حوالي 2√n ، فإنه يترتب على ذلك أن التبديل العشوائي يجب أن يكون طوله على الأقل k² ^/ 4 ليكون لديه احتمالية عالية لكونه نمطًا فائقًا من الرتبة k : من المرجح ألا تحتوي التبديلات الأقصر من ذلك على نمط التطابق. ^{[ 2 ]} وينسب إلى ألون التخمين القائل بأنه لأي ε > 0 ، باحتمالية عالية، ستكون التبديلات العشوائية التي يبلغ طولها k² ^/ (4 − ε) أنماطًا فائقة من الرتبة k .

• التبديل الفائق