Circular Super patterns and Zigzag constructions

तकनीकी सारांश: सर्कुलर सुपरपैटर्न और जिगज़ैग निर्माण (Circular Superpatterns and Zigzag Constructions)

लेखक: एम. हरिप्रसाद और राइसा डिसौज़ा (चाणक्य विश्वविद्यालय, बेंगलुरु)

1. समस्या विवरण

यह शोध पत्र कॉम्बिनेटरियल पैटर्न कंटेनमेंट (combinatorial pattern containment) के एक मौलिक प्रश्न को संबोधित करता है: एक ऐसा न्यूनतम लंबाई वाला क्रमपरिवर्तन (permutation) क्या है जिसमें लंबाई $k$ के सभी संभावित पैटर्न समाहित हों? ऐसा क्रमपरिवर्तन एक $k$-सुपरपैटर्न के रूप में जाना जाता है।

जबकि इस समस्या का रैखिक (linear) संस्करण सुव्यवस्थित है (स्थापित ऊपरी सीमाओं जैसे $L(k) \leq \frac{k(k+1)}{2}$ और एसिम्प्टोटिक विकास के संबंध में अनुमानों के साथ), यह शोध पत्र एक नया रूपांतर प्रस्तुत करता है और उसका अन्वेषण करता है: सर्कुलर $k$-सुपरपैटर्न (Circular $k$-superpatterns)। इस सेटिंग में, क्रमपरिवर्तनों को एक वृत्त पर व्यवस्थित माना जाता है, जिसका अर्थ है कि पैटर्न तब समान माने जाते हैं जब उन्हें रोटेशन (चक्रीय समतुल्यता) के माध्यम से प्राप्त किया जा सके। लक्ष्य $L_{circ}(k)$ की न्यूनतम लंबाई निर्धारित करना है जो रोटेशन तक सभी $k$-लंबाई वाले पैटर्न को समाहित करने के लिए आवश्यक है।

2. कार्यप्रणाली (Methodology)

लेखक इस समस्या से निपटने के लिए तीन प्राथमिक गणितीय दृष्टिकोणों का उपयोग करते हैं:

• पुनरावर्ती निर्माण (Recursive Construction): वे मौजूदा रैखिक सुपरपैटर्न के ज्ञान का लाभ उठाकर सर्कुलर सुपरपैटर्न बनाने का प्रयास करते हैं।
• जिगज़ैग फ्रेमवर्क अनुकूलन (Zigzag Framework Adaptation): वे मूल रूप से एंगेन और वेटर द्वारा प्रस्तावित "जिगज़ैग वर्ड" फ्रेमवर्क का उपयोग और सरलीकरण करते हैं। इसमें पैटर्न को एम्बेड करने के लिए पैरिटी (सम/विषम) के आधार पर "रन्स" (runs) के अनुक्रमों का निर्माण शामिल है।
• स्कोर फंक्शन विश्लेषण (Score Function Analysis): लेखक "लोकल कॉस्ट्स" पर आधारित एक "सर्कुलर स्कोर फंक्शन" विकसित करते हैं। यह फंक्शन एक विशिष्ट क्रमपरिवर्तन को एम्बेड करने के लिए आवश्यक अतिरिक्त जिगज़ैग रन्स की संख्या को मापता है। इन स्कोर की पैरिटी (parity) का विश्लेषण करके, वे एक परिमित जिगज़ैग शब्द के भीतर एम्बेडिंग की व्यवहार्यता निर्धारित करते हैं।

3. मुख्य योगदान और परिणाम

A. सामान्य ऊपरी सीमा (General Upper Bound)
लेखक सिद्ध करते हैं कि एक सर्कुलर $k$-सुपरपैटर्न को एक रैखिक $(k-1)$-सुपरपैटर्न से बनाया जा सकता है।

• प्रमेय (Theorem): यदि $\pi$ एक रैखिक $(k-1)$-सुपरपैटर्न है, तो क्रमपरिवर्तन $\gamma = (L+1, \pi_1, \dots, \pi_L)$ एक सर्कुलर $k$-सुपरपैटन है।
• परिणाम: यह ऊपरी सीमा स्थापित करता है: $L_{circ}(k) \leq L(k-1) + 1$।

B. सर्कुलर स्कोर फंक्शन और पैरिटी गुण (Circular Score Function and Parity Properties)
लेखक एंगेन-वेटर स्कोर फंक्शन को सर्कुलर सेटिंग में विस्तारित करते हैं।

• सर्कुलर लिफ्ट आइडेंटिटी (Circular Lift Identity): वे सिद्ध करते हैं कि किसी भी क्रमपरिवर्तन $\sigma$ के लिए, $\sigma$ का सर्कुलर स्कोर और उसके इंक्रीमेंटेड वर्जन $\sigma^+$ का स्कोर $S_c(\sigma) + S_c(\sigma^+) = 0$ होता है।
• पैरिटी बाधा (Parity Constraint): विषम $k$ के लिए, वे सिद्ध करते हैं कि $S_c(\sigma) \neq 0$ है। यह गैर-शून्य गुण महत्वपूर्ण है क्योंकि यह गारंटी देता है कि किसी भी पैटर्न के लिए, या तो वह पैटर्न स्वयं या उसका इंक्रीमेंटेड वर्जन कम संख्या में जिगज़ैग रन्स में एम्बेड करने के लिए पर्याप्त कम स्कोर रखेगा।

C. विषम $k$ के लिए जिगज़ैग निर्माण (Zigzag Construction for Odd $k$)
यह शोध पत्र एक संशोधित जिगज़ैग शब्द $zzc(k)$का उपयोग करके विषम$k$ के लिए एक विशिष्ट निर्माण प्रस्तावित करता है।

• निर्माण: वे जिगज़ैग शब्द $zz(k-1, k-1)$लेते हैं, टर्मिनल तत्वों$(2, 1)$को$(k, k-1)$ से बदलते हैं, और शब्द को क्रमपरिवर्तन में बदलने के लिए "ब्रेकिंग टाइज़" (breaking ties) पद्धति लागू करते हैं।
• अनुमान/दावा (Conjecture/Claim): वे एक विस्तृत प्रमाण रूपरेखा (दावा 1) प्रदान करते हैं जो सुझाव देती है कि यह निर्माण $\gamma_k$ विषम $k$ के लिए एक सर्कुलर $k$-सुपरपैटर्न प्रदान करता है।

4. परिणामों का सारांश (तालिका 1)

शोध पत्र विभिन्न संदर्भों के लिए स्पष्ट ऊपरी सीमाएं प्रदान करता है:

संदर्भ (Context)	लंबाई सीमा (Length Bound)
वर्णमाला $[k+1]$ पर	$(k-1)(k+1)/2$
क्रमपरिवर्तनों पर	$\lfloor \frac{k^2+1}{2} \rfloor + 1$
रैखिक $(k-1)$ सुपरपैटर्न का उपयोग करके	$L(k-1) + 1$

5. महत्व

यह कार्य महत्वपूर्ण है क्योंकि यह पैटर्न कंटेनमेंट थ्योरी के डोमेन को रैखिक संरचनाओं से चक्रीय संरचनाओं तक विस्तारित करता है। सर्कुलर स्कोर फंक्शन को पेश करके और विषम $k$ के लिए एम्बेडिंग की पैरिटी-आधारित उपस्थिति को सिद्ध करके, लेखक कुशल सुपरपैटर्न बनाने के लिए एक सैद्धांतिक आधार प्रदान करते हैं। इसका जैव सूचना विज्ञान (जैसे गोलाकार डीएनए अनुक्रम) और नेटवर्क टोपोलॉजी जैसे क्षेत्रों में संभावित अनुप्रयोग है जहाँ चक्रीय समरूपता अंतर्निहित होती है।