$K_{2, t+1}$-free graphs containing an optimal number of $K_{t, t}$'s

तकनीकी सारांश: इष्टतम संख्या में $K_{t,t}$ वाले $K_{2,t+1}$-मुक्त ग्राफ

समस्या विवरण
यह शोध पत्र सामान्यीकृत टुरान संख्या (generalized Turán number) को संबोधित करता है, जिसे $\text{ex}(n, H, F)$ द्वारा दर्शाया गया है, जो $n$ शीर्षों वाले एक $F$-मुक्त ग्राफ में मौजूद $H$ की प्रतियों की अधिकतम संख्या को दर्शाता है। विशेष रूप से, लेखक $H = K_{t,t}$ और $F = K_{2,t+1}$ के मामले की जांच करते हैं। लक्ष्य $\text{ex}(n, K_{t,t}, K_{2,t+1})$ के स्पर्शोन्मुख व्यवहार (asymptotic behavior) को निर्धारित करना है।

जबकि पोहाटा, टिडोर और यू के हालिया कार्य ने यह स्थापित किया कि सभी पूर्णांक $t \ge 3$ के लिए $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ है, उनका प्रमाण संभाव्य विधियों (probabilistic methods) और सबस्पेस-इवेसिव सेट्स पर निर्भर था, जिससे एक ऐसा निचला स्तर (lower bound) प्राप्त हुआ जिसका गुणांक आवश्यक रूप से इष्टतम नहीं था। यह शोध पत्र एक स्पष्ट निर्माण (explicit construction) का उपयोग करके विशिष्ट $n$ और $t$ के मानों के लिए एक सटीक स्पर्शोन्मुख सूत्र प्रदान करने का प्रयास करता है।

कार्यप्रणाली (Methodology)
लेखक परिमित क्षेत्रों (finite fields) और रैखिकीकृत बहुपदों (linearized polynomials) पर आधारित ग्राफों का एक नियतात्मक, बीजगणितीय निर्माण (deterministic, algebraic construction) नियोजित करते हैं।

1. ग्राफ निर्माण ($\Gamma_{t,e}$):

   • $t$ को एक अभाज्य घात (prime power) और $e > 1$ को एक पूर्णांक मान लें। $q = t^e$ को परिभाषित करें।
   • $\mathbb{F}_q[x]$ पर एक $\mathbb{F}_t$-रैखिकीकृत बहुपद $L$ को इस प्रकार परिभाषित करें कि इसके कर्नेल (kernel) का आयाम 1 हो। इमेज स्पेस $R_L$ का आकार $t^{e-1}$ है।
   • शीर्षों का सेट $V = \mathbb{F}_q \times R_L$ है, जिसके परिणामस्वरूप $n = q \cdot t^{e-1} = t^{2e-1}$ शीर्ष प्राप्त होते हैं।
   • दो भिन्न शीर्ष $(v_1, v_2)$ और $(w_1, w_2)$ तभी आसन्न (adjacent) हैं यदि $v_2 + w_2 = L(v_1 w_1)$ हो। एक सरल ग्राफ सुनिश्चित करने के लिए समीकरण द्वारा निहित स्व-लूप (self-loops) को हटा दिया जाता है।

2. ऊपरी सीमा का व्युत्पत्ति (Upper Bound Derivation):

   • लेखक पहले $\text{ex}(n, K_{t,t}, K_{2,t+1})$ के लिए एक सटीक ऊपरी सीमा स्थापित करते हैं।
   • तर्क इस तथ्य पर आधारित है कि किसी भी $K_{2,t+1}$-मुक्त ग्राफ में, किन्हीं भी दो शीर्षों के उभयनिष्ठ पड़ोसी (common neighbors) अधिकतम $t$ होते हैं।
   • शीर्षों के युग्मों को गिनकर और यह विश्लेषण करके कि उनके घटक युग्मों के माध्यम से एक $K_{t,t}$ कितनी बार गिना जाता है, वे यह सीमा प्राप्त करते हैं:
     $$\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$$

3. निर्माण का संरचनात्मक विश्लेषण (Structural Analysis of the Construction):

   • $K_{2,t+1}$-फ्रीनेस: लेखक सिद्ध करते हैं कि $\Gamma_{t,e}$ में कोई $K_{2,t+1}$ नहीं है। किन्हीं भी दो शीर्षों के लिए, उभयनिष्ठ पड़ोसियों की संख्या $L$ से संबंधित एक रैखिक समीकरण के समाधानों की संख्या द्वारा निर्धारित होती है। चूंकि $L$ एक $t$-से-1 मैपिंग है, इसलिए अधिकतम $t$ उभयनिष्ठ पड़ोसी होते हैं।
   • $K_{t,t}$ का निर्माण: प्रमाण का मुख्य भाग गैर-आसन्न शीर्षों के विश्लेषण में निहित है। लेखक दिखाते हैं कि किन्हीं भी दो गैर-आसन्न शीर्षों, जिनके प्रथम निर्देशांक भिन्न हैं, वे अद्वितीय रूप से दो सेट, $M$ और $N$, को परिभाषित करते हैं जिनकी कार्डिनैलिटी (cardinality) $t$ है।
     • $N$ उभयनिष्ठ पड़ोसियों का सेट है ($\mathbb{F}_t$-लाइन)।
     • $M$ वह $\mathbb{F}_t$-लाइन है जिसमें दोनों शीर्ष शामिल हैं।
     • $M$ का प्रत्येक शीर्ष $N$ के प्रत्येक शीर्ष के बीजगणितीय रूप से आसन्न है।
   • यदि $M \cap N = \emptyset$ है, तो $M \cup N$ द्वारा प्रेरित उपग्राफ (induced subgraph) एक $K_{t,t}$ है। यदि $|M \cap N| = 1$ है, तो संरचना एक त्रिपक्षीय पूर्ण ग्राफ (tripartite complete graph) $K_{1, t-1, t-1}$ बनाती है।

मुख्य योगदान और परिणाम
प्राथमिक योगदान ग्राफ परिवार का एक स्पष्ट निर्माण प्रदान करना है जो $n$ के एक अनंत सेट के लिए, निम्न-क्रम के पदों (lower-order terms) को छोड़कर, $K_{t,t}$ प्रतियों के सैद्धांतिक ऊपरी स्तर को प्राप्त करता है।

• प्रमेय 1.1: यदि $t$ एक अभाज्य घात है और $n = t^{2e-1}$ (जहाँ $e > 1$ एक पूर्णांक है), तो सामान्यीकृत टुरान संख्या निम्नलिखित है:
  $$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
• पिछले बंधों के साथ तुलना: शोध पत्र नोट करता है कि [5] से प्राप्त पिछला सर्वोत्तम निचला स्तर $(1-o(1)) \frac{n^2}{4t^2 t!}$ के रूप में था। नया परिणाम $t > 5$ के लिए अभाज्य घातों हेतु इस गुणांक में महत्वपूर्ण सुधार करता है।
• गैर-इष्टतम मामलों की उपेक्षा: लेखक प्रदर्शित करते हैं कि $K_{1, t-1, t-1}$ (जहाँ $|M \cap N| = 1$) से उत्पन्न होने वाली विन्यासों (configurations) की संख्या $K_{t,t}$ की कुल गणना ($O(n^2)$) की तुलना में नगण्य ($O(n)$) है, जो $K_{t,t}$ की गणना के स्पर्शोन्मुख प्रभुत्व को सुनिश्चित करती है।

महत्ता और दावे
शोध पत्र का दावा है कि यह $n$ के एक अनंत, हालांकि विरल (sparse), सेट के लिए एक "सरल और पूरी तरह से स्पष्ट निर्माण" प्रदान करता है, जो पहले उपलब्ध संभाव्य अस्तित्व प्रमाणों के विपरीत है। यह निर्माण उन ग्राफों के समरूप (isomorphic) है जिनका अध्ययन लाज़ेबज़िक और मुबाई ने मल्टीकलर रामसे नंबरों के संदर्भ में किया था, हालांकि यह शोध पत्र उन्हें विशेष रूप से सामान्यीकृत टुरान समस्या के लिए लागू करता है।

लेखक यह अनुमान लगाते हुए निष्कर्ष निकालते हैं कि प्राप्त ऊपरी स्तर सभी $n$ के लिए, न कि केवल विशिष्ट अभाज्य घात मामलों के लिए, सटीक है:
$$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$$
यह कार्य द्विभाजी (bipartite) ग्राफों के लिए सामान्यीकृत टुरान संख्याओं की वृद्धि दर की समझ को परिष्कृत करने का कार्य करता है, जो कोटि-व्यवस्था (order-of-magnitude) अनुमानों से विशिष्ट व्यवस्थाओं के लिए सटीक स्पर्शोन्मुख स्थिरांकों (asymptotic constants) की ओर बढ़ता है।