🔢 mathematics

Exact Zarankiewicz Values On Two Finite Frontier Slices

यह शोध पत्र एक संयुक्त, प्रमाण-आधारित कंप्यूटर-सहायता प्राप्त प्रमाण प्रस्तुत करता है जो विशिष्ट परिमित स्लाइस और Z(m,n,3,3) समस्या के एक पड़ोसी फ्रंटियर के लिए सटीक ज़ारंकेविच संख्याओं (Zarankiewicz numbers) को स्थापित करता है, जिसमें मानों जैसे कि Z(12,n,3,3)=6n (18≤n≤22 के लिए) और Z(13,22,3,3)=137 की पुष्टि करने के लिए ऑर्बिट प्रमाणपत्रों, विलोपन लेम्मा (deletion lemmas) और कठोर अंकगणितीय सत्यापन का उपयोग किया गया है।

मूल लेखक: Koyar Afrasyab

प्रकाशित 2026-08-11

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Koyar Afrasyab

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक शहर के योजनाकार हैं जो संभवतः सबसे कुशल सड़क नेटवर्क बनाने की कोशिश कर रहे हैं। आपके पास दो प्रकार के स्थानों का समूह है: एक तरफ "हब्स" (Hubs) का एक सेट और दूसरी तरफ "डेस्टिनेशन" (Destinations) का एक सेट। आपका लक्ष्य उनके बीच अधिक से अधिक सड़कें (कनेक्शन) बनाना है ताकि यातायात सुचारू रूप से चलता रहे। हालाँकि, एक सख्त ज़ोनिंग कानून है: आपको एक विशिष्ट, अव्यवस्थित इंटरसेक्शन पैटर्न बनाने से रोका गया है। गणितीय भाषा में, यह वर्जित पैटर्न एक "पूर्ण द्विपक्षीय उपग्राफ" (complete bipartite subgraph) है, या सरल शब्दों में, आप ऐसी स्थिति नहीं बना सकते जहाँ तीन हब्स एक ही तीन डेस्टिनेशन्स से जुड़े हों। यदि आप ऐसा करते हैं, तो आपने नियम तोड़ दिया है।

यह पहेली ज़ारनकेविच समस्या (Zarankiewicz problem) के रूप में जानी जाती है। यह कॉम्बिनेटोरिक्स (combinatorics) के क्षेत्र में एक क्लासिक दिमागी कसरत है, जो गणना, व्यवस्था और संगठन के विज्ञान को समर्पित गणित की एक शाखा है। जबकि गणितज्ञों ने विशाल, सैद्धांतिक शहरों के लिए इसे हल करने के तरीके खोज लिए हैं, वास्तविक चुनौती इन "मध्यम आकार" के कस्बों के लिए आती है। इन विशिष्ट आकारों के लिए, संभावित रोड मैप्स की संख्या इतनी बड़ी है कि आप उन्हें हाथ से नहीं देख सकते, लेकिन वे सरल सूत्रों द्वारा हल करने के लिए बहुत जटिल भी हैं। यह कठिनाई का एक 'गोल्डिलॉक्स ज़ोन' (Goldilocks zone) है: कागज़-और-पेंसिल वाले प्रमाण के लिए बहुत बड़ा, लेकिन अनंत शहरों के लिए काम करने वाले "एसिम्प्टोटिक" (asymptotic) शॉर्टकट्स के लिए बहुत छोटा। इन सटीक संख्याओं को हल करना महत्वपूर्ण है क्योंकि वे नेटवर्क की दक्षता की छिपी हुई सीमाओं को प्रकट करते हैं, जैसे कि कंप्यूटर चिप्स या सोशल मीडिया कनेक्शन में।

यहाँ प्रवेश होता है कोयार अफ्रस्याब (Koyar Afrasyab) का, एक शोधकर्ता जिन्होंने हाल ही में इन मध्यम आकार की पहेलियों के एक विशेष कठिन सेट को सुलझा लिया है। इस समस्या को एक ग्रिड पर बिना उस वर्जित "तीन-बाय-तीन" ट्रैफिक जाम बनाए अधिकतम कितनी सड़कें बनाई जा सकती हैं, इसे खोजने के रूप में समझें। अफ्रस्याब ने केवल अनुमान नहीं लगाया; उन्होंने उत्तर खोजने के लिए एक डिजिटल जासूसी एजेंसी बनाई। यह शोध पत्र इस समस्या के दो विशिष्ट "स्लाइस" पर केंद्रित है: 12 पंक्तियों वाले ग्रिड और 13 पंक्तियों वाले ग्रिड, जो विभिन्न कॉलम की संख्या के साथ जोड़े गए हैं।

मुख्य खोज इन ग्रिडों के लिए सटीक "स्पीड लिमिट" की एक सूची है। 18 से 22 कॉलम के साथ 12 पंक्तियों वाले ग्रिड के लिए, बिना नियम तोड़े आपके पास अधिकतम सड़कों (edges) की संख्या ठीक $6n$ (जहाँ $n$ कॉलम की संख्या है) है। उदाहरण के लिए, एक 12-बाय-18 ग्रिड में ठीक 108 सड़कें हो सकती हैं, और एक 12-बाय-22 ग्रिड में ठीक 132 सड़कें हो सकती हैं। यह पत्र यह दिखाकर इसे सिद्ध करता है कि यदि आप इन ग्रिडों में केवल एक और सड़क जोड़ने का प्रयास करते हैं, तो आप अनिवार्य रूप से वह वर्जित ट्रैफिक जाम बना देंगे।

इस कहानी का सबसे नाटकीय हिस्सा 13-बाय-22 ग्रिड से संबंधित है। पिछले अनुमानों ने सुझाव दिया था कि सीमा 140 सड़कों तक उच्च हो सकती है। अफ्रस्याब का कंप्यूटर-सहायता प्राप्त प्रमाण एक छलनी की तरह काम करता है, जो हर एक असंभव व्यवस्था को छान देता है। उन्होंने यह मानकर शुरुआत की कि कोई व्यक्ति नियमों को तोड़े बिना 138 सड़कों वाला ग्रिड बना सकता है। उन्मूलन की एक चतुर प्रक्रिया के माध्यम से—यह जाँचते हुए कि प्रत्येक बिंदु से कितनी सड़कें जुड़ती हैं (प्रोफाइल)—उन्होंने सिद्ध किया कि 138 असंभव है। उन्होंने तब तक संकुचन किया जब तक कि उन्हें वास्तविक सीमा नहीं मिल गई: 137 सड़कें। उन्होंने 137 सड़कों का एक विशिष्ट, सत्यापित मैप भी प्रदान किया जो काम करता है, जिससे यह सिद्ध होता है कि आप उस संख्या तक पहुँच सकते हैं लेकिन उससे ऊपर नहीं जा सकते।

यह पत्र कई पड़ोसी ग्रिडों के लिए भी मानचित्र को ठीक करता है, जो 13-बाय-18, 14-बाय-17 और 15-बाय-18 जैसे आकारों के लिए सटीक सीमाएँ निर्धारित करता है। एक पेचीदा मामले के लिए, 16-बाय-17 ग्रिड के लिए, प्रमाण पुष्टि करता है कि आप निश्चित रूप से 132 सड़कें बना सकते हैं, लेकिन ऊपरी सीमा अभी भी 132 और 133 के बीच एक कड़ा दायरा है।

यह कार्य इसलिए विशेष है क्योंकि इसे कैसे किया गया। लेखक ने केवल एक ब्लैक-बॉक्स कंप्यूटर प्रोग्राम नहीं चलाया जिसने कहा "कोई समाधान नहीं मिला।" इसके बजाय, उन्होंने एक "प्रमाण-आधारित" (certificate-based) प्रमाण बनाया। कल्पना कीजिए कि एक जासूस ब्रेडक्रंब्स (रोटी के टुकड़े) का रास्ता छोड़ रहा है: प्रत्येक असंभव परिदृश्य जिसे उन्होंने खारिज किया, उसके लिए उन्होंने एक गणितीय "रसीद" (प्रमाणपत्र) छोड़ी जिसे कोई भी साधारण कैलकुलेटर के साथ जांच सकता है। शोध पत्र में एक डिजिटल पैकेज शामिल है जहाँ आप पूरे अन्वेषण को फिर से चलाने के लिए एक एकल कमांड चला सकते हैं, जिससे लाखों रसीदों की जांच की जा सके ताकि यह सुनिश्चित हो सके कि कोई गलती नहीं हुई है। यह गणितीय समुदाय के लिए एक कठोर, पारदर्शी और पूरी तरह से पुनरुत्पादक विजय है, जो "शायद" वाले उत्तरों को "निश्चित रूप से" वाले तथ्यों में बदल देता है।

तकनीकी सारांश: दो परिमित सीमांत खंडों पर सटीक ज़ारंकेविज़िक मान (Exact Zarinkiewicz Values)

समस्या विवरण
यह शोध पत्र ज़ारंकेविज़िक समस्या (Zarankiewicz problem) को संबोधित करता है, जो एक द्विपक्षीय ग्राफ (bipartite graph) में किनारों की अधिकतम संख्या $Z(m, n, s, t)$ खोजने का प्रयास करती है, जिसमें $m$ और $n$ आकार के दो भाग होते हैं और इसमें कोई पूर्ण द्विपक्षीय उपग्राफ $K_{s,t}$ नहीं होता है। विशेष रूप से, लेखक $s=t=3$ (अर्थात $K_{3,3}$ से बचने के लिए) के मामले पर ध्यान केंद्रित करते हैं, जो मध्यम परिमित मापदंडों (moderate finite parameters) के लिए है। जबकि विषम (asymptotic) सिद्धांत अच्छी तरह से विकसित है, विशिष्ट परिमित आयामों के लिए सटीक मान प्राप्त करना कठिन बना हुआ है क्योंकि इसमें अत्यधिक समरूपता (symmetry) और प्रमाण प्रमाणीकरण (proof certification) की उच्च लागत शामिल है। यह शोध पत्र पहले से अनसुलझे या आंशिक रूप से हल किए गए मूल्यों के एक "परिमित सीमांत" (finite frontier) को लक्षित करता है, जिसमें $18 \le n \le 22$ के लिए स्ट्रिप $Z(12, n, 3, 3)$ , विशिष्ट मामला $Z(13, 22, 3, 3)$ , और $13 \times 18$ तथा $16 \times 17$ के आसपास के पड़ोसी मानों का एक समूह शामिल है।

कार्यप्रणाली (Methodology)
यह प्रमाण कंप्यूटर-सहायतित है लेकिन पूर्णतः प्रमाण-आधारित (certificate-based) है, जो इसे केवल मिश्रित-पूर्णांक रैखिक प्रोग्रामिंग (MILP) सॉल्वर द्वारा "असंभव" (infeasible) घोषित करने या बिना स्पष्ट साक्ष्य के SAT सॉल्वर पर निर्भर करने वाली विधियों से अलग करता है। सत्यापन सटीक पूर्णांक और परिमेय अंकगणित (Python के Fraction और मानक पुस्तकालयों का उपयोग करके) पर निर्भर करता है, जिसमें फ्लोटिंग-पॉइंट अनुकूलन का उपयोग केवल प्रमाणपत्रों की प्रारंभिक खोज के लिए किया गया है।

कार्यप्रणाली एक बहु-स्तरीय न्यूनीकरण रणनीति (multi-layered reduction strategy) का उपयोग करती है:

वैश्विक विश्राम और डिग्री प्रोफाइल (Global Relaxation and Degree Profiles): $13 \times 22$ के मामले के लिए, लेखक एक काल्पनिक मैट्रिक्स की कल्पना करते हैं जिसमें 138 किनारे हैं। कॉलम डिग्री से जुड़े "दंड" (penalty) फलन $p(d) = \binom{d}{3} - 15d + 70$ का विश्लेषण करके, खोज स्थान को सभी संभावित मैट्रिसेस से घटाकर केवल 83 विशिष्ट डिग्री प्रोफाइल (कॉलम डिग्री के हिस्टोग्राम) तक सीमित कर दिया जाता है।
फ़ार्कास प्रमाणपत्र (Farkas Certificates): इन 83 में से 77 प्रोफाइल के लिए, लेखक सटीक परिमेय फ़ार्कास प्रमाणपत्रों का निर्माण करते हैं। ये प्रमाणपत्र यह सिद्ध करके असंभवता (infeasibility) को प्रमाणित करते हैं कि $K_{3,3}$ -मुक्त स्थिति से उत्पन्न रैखिक बाधाओं (विशेष रूप से, कि प्रत्येक पंक्ति का त्रिक (triple) अधिकतम 2 कॉलमों में दिखाई देता है) को उस प्रोफाइल के लिए किसी भी गैर-ऋणात्मक पूर्णांक समाधान द्वारा संतुष्ट नहीं किया जा सकता है।
चिह्नित-पंक्ति और अवशेष गणना (Marked-Row and Leave Enumeration): शेष छह प्रोफाइल को अधिक सूक्ष्म तकनीकों का उपयोग करके बाहर निकाला जाता है। लेखक एक "चिह्नित पंक्ति" (marked row) को निर्धारित करते हैं, उसे हटाते हैं, और शेष 12 बिंदुओं पर परिणामी "लीव मल्टीग्राफ" (leave multigraph) का विश्लेषण करते हैं। इसमें शामिल हैं:
- योगसंगत तर्क (Congruence Arguments): पंक्ति घाटा (row deficit) पर मॉड्यूलर अंकगणित का उपयोग करके विशिष्ट विन्यासों को खारिज करना (जैसे, प्रोफाइल 61873 de91)।
- ग्राम मैट्रिक्स बाधाएं (Gram Matrix Constraints): अवशिष्ट ब्लॉकों (residual blocks) के घटना मैट्रिक्स (incidence matrix) के रैंक और निर्धारक (determinant) की स्थिति की जाँच करना।
- सटीक गणना (Exact Enumeration): अवशिष्ट ब्लॉक डिजाइनों का व्यापक रूप से गणना करना और शेष गुणनखंड प्रणालियों (factorization systems) पर पूर्णांक-स्केल किए गए फ़ार्कास प्रमाणपत्र लागू करना।
विलोपन लेम्मा और साक्षी (Deletion Lemmas and Witnesses): $12 \times n$ स्ट्रिप और सीमांत समापन (frontier closure) के लिए, लेखक "विलोपन लेम्मा" (जो $Z(m, n)$ को $Z(m, n-1)$ से संबंधित करते हैं) को स्पष्ट रचनात्मक साक्ष्यों (निर्माता मैट्रिसेस जो निचली सीमाओं को प्राप्त करते हैं) के साथ जोड़कर सटीक समानताएं स्थापित करते हैं।

प्रमुख योगदान और परिणाम
शोध पत्र निम्नलिखित सटीक मानों और सीमाओं के लिए एक संयुक्त, प्रमाण-आधारित प्रमाण प्रदान करता है:

$12 \times n$ स्ट्रिप: सिद्ध करता है कि $Z(12, n, 3, 3) = 6n$ है, जहाँ $18 \le n \le 22$ । यह $Z(12, 18, 3, 3) = 108$ के लिए एक सटीक प्रमाण और $n=19, 20, 21, 22$ के लिए स्पष्ट साक्ष्यों द्वारा समर्थित क्रमिक विलोपन तर्कों द्वारा स्थापित किया गया है।
$13 \times 22$ का मामला: सिद्ध करता है कि $Z(13, 22, 3, 3) = 137$ है। ऊपर वर्णित व्यापक प्रोफाइल विश्लेषण द्वारा 138 के ऊपरी स्तर को समाप्त कर दिया गया है। 137 का निचला स्तर एक स्पष्ट निर्माण (एक $13 \times 22$ बाइनरी मैट्रिक्स जिसमें 137 'ones' हैं और कोई $K_{3,3}$ नहीं है) के माध्यम से पुष्ट किया गया है।
सीमांत समापन (Frontier Closure): चार पड़ोसी सेल के लिए सटीक मान स्थापित करता है:
- $Z(13, 18, 3, 3) = 116$
- $Z(14, 17, 3, 3) = 118$
- $Z(14, 18, 3, 3) = 124$
- $Z(15, 17, 3, 3) = 126$
- $Z(15, 18, 3, 3) = 132$
$16 \times 17$ अंतराल: अंतराल $132 \le Z(16, 17, 3, 3) \le 133$ की रिपोर्ट करता है। निचला स्तर एक नए 132-एज साक्षी द्वारा समर्थित है; 133 का ऊपरी स्तर पूर्व साहित्य (कोलिन्स एट अल.) से लिया गया है। शोध पत्र स्पष्ट रूप से नोट करता है कि इस विशिष्ट सेल के लिए सटीक मान इस कार्य के भीतर निर्धारित नहीं है।

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

पुनरुत्पत्ति (Reproducibility): शोध पत्र में एक "एक-कमांड सत्यापन गेट" (one-command verification gate) शामिल है जो सभी 5.7 मिलियन सटीक गैर-ऋणात्मक जाँचों को फिर से चलाता है, जिसमें डिग्री प्रोफाइल का पुनरुत्पादन, फ़ार्कास प्रमाणपत्रों का पुनर्रक्षण, और अवशिष्ट ब्लॉक डिजाइनों की व्यापक गणना शामिल है।
विनम्रता (Modesty): लेखक स्पष्ट रूप से कहते हैं कि इन परिणामों को "स्वतंत्र पुनरुत्पादन और सहकर्मी समीक्षा के अधीन नए कंप्यूटर-सहायतित प्रमाण" के रूप में देखा जाना चाहिए। शोध पत्र यह दावा नहीं करता है कि उसने सामान्य ज़ारंकेविज़िक समस्या को हल कर दिया है या कोई सार्वभौमिक एल्गोरिथ्म प्रदान किया है, बल्कि यह परिमित चरम समस्याओं (finite extremal problems) के लिए श्रम विभाजन को प्रदर्शित करता है: अधिकांश मामलों को समाप्त करने के लिए मोटे वैश्विक विश्राम (coarse global relaxations) का उपयोग करना और कुछ "कठिन" अवशेष प्रोफाइल के लिए सटीक, गणना-गहन गणना को सुरक्षित रखना।
पूर्व कला (Prior Art): लेखक नोट करते हैं कि हालांकि $13 \times 22$ के लिए 137-एज निर्माण पहले से रिपोर्ट किया गया था, लेकिन सटीक ऊपरी सीमा एक नया योगदान है। इसी तरह, $12 \times n$ स्ट्रिप के विशिष्ट मान ( $n=18$ से $21$) और सीमांत समापन मानों को पूर्व अनुक्रमित साहित्य (अगस्त 2026 तक की तिथि के अनुसार) में नहीं पाए गए नए सटीक परिणाम के रूप में रिपोर्ट किया गया है।

शोध पत्र इस बात पर जोर देते हुए समाप्त होता है कि कोई भी अपुष्ट DRAT दावे, SAT टाइमआउट, या फ्लोटिंग-पॉइंट सॉल्वर स्टेटस को प्रमेयों के लिए आधार के रूप में उपयोग नहीं किया गया है, जिससे यह सुनिश्चित होता है कि गणितीय दावे पूरी तरह से स्पष्ट परिमित डेटा और सटीक अंकगणित पर आधारित हैं।

इसी तरह के और पेपर