एक क्लोज़-अप दृश्य एक अनंत ग्राफ़ के 'पिघलने' बिंदु को प्रकट करता है | क्वांटा पत्रिका

2008 में, सिएटल से लगभग 50 मील पूर्व में कैस्केड पहाड़ों में एक पदयात्रा दुर्घटना में गणितज्ञ ओडेड श्राम की मृत्यु हो गई। हालाँकि वह केवल 46 वर्ष के थे, फिर भी उन्होंने गणित के बिल्कुल नए क्षेत्रों का निर्माण किया था।

"वह एक शानदार गणितज्ञ थे," उन्होंने कहा इताई बेन्जामिनी, वीज़मैन इंस्टीट्यूट ऑफ साइंस में गणितज्ञ और श्राम के मित्र और सहयोगी। "बेहद रचनात्मक, बेहद खूबसूरत, बेहद मौलिक।"

उनके द्वारा पूछे गए प्रश्न अभी भी संभाव्यता सिद्धांत और सांख्यिकीय भौतिकी की सीमाओं को आगे बढ़ा रहे हैं। इनमें से कई प्रश्न गणितीय संरचनाओं से संबंधित हैं जिनमें एक चरण संक्रमण होता है - अचानक स्थूल परिवर्तन, जैसे बर्फ का पानी में पिघलना। जिस तरह विभिन्न सामग्रियों के गलनांक अलग-अलग होते हैं, उसी तरह गणितीय संरचनाओं के चरण संक्रमण भी अलग-अलग होते हैं।

श्राम ने अनुमान लगाया कि परकोलेशन नामक प्रक्रिया में चरण संक्रमण का अनुमान कई महत्वपूर्ण गणितीय संरचनाओं के लिए सिस्टम के केवल क्लोज-अप दृश्य - जिसे स्थानीय परिप्रेक्ष्य कहा जाता है - का उपयोग करके लगाया जा सकता है। पूरी तरह से ज़ूम करके और पूरी चीज़ को देखने से गणना में कोई खास बदलाव नहीं आएगा। पिछले 15 वर्षों में, गणितज्ञों ने अनुमान के छोटे-छोटे टुकड़े कर दिए हैं, लेकिन अब तक, वे इसे पूरी तरह से हल नहीं कर पाए हैं।

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

“यह एक उल्लेखनीय पेपर है। यह लंबे समय तक किए गए काम का संचय है,'' बेन्जामिनी ने कहा।

अनंत समूह

शब्द "पेरकोलेशन" मूल रूप से एक छिद्रपूर्ण माध्यम के माध्यम से तरल पदार्थ की गति को संदर्भित करता है, जैसे कि कॉफी के मैदान से बहने वाला पानी या चट्टान में दरारों से रिसने वाला तेल।

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

"यह गणितज्ञों के लिए एक विहित मॉडल की तरह है," हचक्रॉफ्ट ने कहा। “आप चीजों के बारे में दृष्टिगत रूप से सोच सकते हैं। इससे उनके साथ काम करना वाकई अच्छा लगता है।”

परकोलेशन एक ग्राफ़ से शुरू होता है, जो शीर्षों (बिंदुओं) का एक संग्रह है जिसे किनारों (रेखाओं) से जोड़ा जा सकता है। सबसे सरल उदाहरणों में से एक एक वर्गाकार ग्रिड है, जिसमें शीर्ष पंक्तिबद्ध होकर वर्गों के कोने बनाते हैं और किनारे उनमें से कुछ को जोड़ते हैं।

अपनी मृत्यु से कुछ समय पहले, श्राम ने अनुमान लगाया कि ग्रिमेट और मार्स्ट्रैंड के प्रमेय को सामान्यीकृत किया जा सकता है। उन्होंने सोचा कि अंतःस्राव सीमा पूरी तरह से ग्राफ़ के एक बड़े वर्ग के लिए क्लोज़-अप, या "सूक्ष्मदर्शी" परिप्रेक्ष्य द्वारा निर्धारित की जाती है, जिसे संक्रमणीय ग्राफ़ के रूप में जाना जाता है।

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

एक संक्रमणीय ग्राफ़ में, सभी शीर्ष समान दिखते हैं। द्वि-आयामी ग्रिड इसका एक उदाहरण है। यदि आप कोई दो शीर्ष चुनते हैं, तो आप हमेशा एक समरूपता पा सकते हैं जो एक शीर्ष से दूसरे तक जाती है।

यह संबंध किसी भी संक्रमणीय ग्राफ़ के लिए लागू होता है। इन समरूपताओं के कारण, यदि आप ज़ूम इन करते हैं और संक्रमणीय ग्राफ़ के किन्हीं दो समान आकार के पैच को देखते हैं, तो वे समान दिखेंगे। इस कारण से, श्राम का मानना ​​​​था कि क्लोज़-अप परिप्रेक्ष्य गणितज्ञों को सभी संक्रमणीय ग्राफ़ के लिए अंतःक्षेपण सीमा की गणना करने की अनुमति देने के लिए पर्याप्त था।

सकर्मक ग्राफ़ कई आकार और रूप ले सकते हैं। वे एक साधारण ग्रिड हो सकते हैं, जो वर्गों, त्रिकोणों, षट्भुजों या किसी अन्य आकार से बने होते हैं। या वे एक अधिक जटिल वस्तु बना सकते हैं, जैसे "3-नियमित पेड़", जहां एक केंद्रीय बिंदु तीन शीर्षों से जुड़ता है, और फिर प्रत्येक शीर्ष पर शाखाएं बनती हैं, जिससे अनंत तक दो नए शिखर बनते हैं, जिनमें से पहले कुछ चरण यहां देखे गए हैं:

सकर्मक ग्राफ़ की विविधता ने श्राम के स्थानीय अनुमान को साबित करने में कठिनाई में योगदान दिया। श्राम के अनुमान और ईसो और हचक्रॉफ्ट के प्रमाण के बीच 15 वर्षों में, गणितज्ञों के विभिन्न समूहों ने विशिष्ट प्रकार के ग्राफ़ के लिए अनुमान को सिद्ध किया, लेकिन उनके विचार कभी भी सामान्य मामले तक विस्तारित नहीं हुए।

हचक्रॉफ्ट ने कहा, "सभी संभावित ज्यामितियों का स्थान इतना विशाल है, और वहां हमेशा अजीब चीजें छिपी रहती हैं।"

लेंस को चौड़ा करना

ईसो और हचक्रॉफ्ट शुरू में श्राम के स्थानीयता अनुमान के समाधान की तलाश में नहीं थे, जो अनंत ग्राफ़ पर लागू होता है। इसके बजाय वे परिमित ग्राफ़ पर अंतःस्राव का अध्ययन कर रहे थे। लेकिन उन्हें एक ऐसा विचार आया जिससे अचानक उनका ध्यान अनुमान की ओर चला गया।

"हम इस नए उपकरण के साथ आए, और हमने सोचा, ओह, यह उस तरह की चीज़ लगती है जो इलाके पर हमला करने में मददगार हो सकती है," ईसो ने कहा।

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

उन्होंने एक ऐसी तकनीक पर भरोसा किया जिसे "लेंस को चौड़ा करना" के रूप में सोचा जा सकता है। एक ही शीर्ष से प्रारंभ करें. फिर उन सभी शीर्षों को देखने के लिए ज़ूम आउट करें जो मूल ग्राफ़ पर केवल एक किनारे की दूरी पर हैं। वर्गाकार ग्रिड पर, अब आप कुल पाँच शीर्ष देख सकेंगे। दो किनारों की दूरी के भीतर सभी शीर्षों को देखने के लिए लेंस को फिर से चौड़ा करें, और फिर तीन किनारों, चार किनारों और इसी तरह की दूरी देखें।

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

वे यह दिखाने में सक्षम थे कि बड़े समूह छोटे समूहों की तुलना में तेजी से बढ़ते हैं, इसलिए, जैसा कि ईज़ो ने कहा, "आपका समूह तेजी से बढ़ता है क्योंकि यह बड़ा और बड़ा होता जाता है, ठीक उसी तरह जब आप एक स्नोबॉल घुमा रहे होते हैं।"

वर्गाकार ग्रिड के लिए, शीर्ष संख्या अपेक्षाकृत धीरे-धीरे बढ़ती है। यह लगभग आपके लेंस की चौड़ाई का वर्ग है। 10 चरणों के बाद, आपको लगभग 100 शीर्ष मिलेंगे। लेकिन एक 3-नियमित पेड़ तेजी से बढ़ता है - लगभग 2 आपके लेंस की चौड़ाई की शक्ति तक बढ़ा हुआ। 10 चरणों के बाद, आपको लगभग 1,024 शीर्ष दिखाई देंगे। नीचे दिए गए चित्रण से पता चलता है कि कैसे 3-नियमित पेड़ केवल सात चरणों के बाद बहुत बड़ा हो जाता है, भले ही वर्गाकार ग्रिड में पहले अधिक कोने हों। सामान्य तौर पर, ग्राफ़ में अलग-अलग पैमानों पर अलग-अलग विकास दर हो सकती हैं - वे तेजी से शुरू हो सकते हैं, और फिर धीमे हो सकते हैं।

2018 में वापस, हचक्रॉफ्ट एक समान विचार का प्रयोग किया 3-नियमित पेड़ जैसे तेजी से बढ़ते ग्राफ़ के लिए स्थानीय अनुमान को साबित करने के लिए। लेकिन यह वर्ग ग्रिड जैसे धीमी वृद्धि वाले ग्राफ़ के लिए या मध्यवर्ती गति से बढ़ने वाले ग्राफ़ के लिए काम नहीं करता है, जो न तो तेज़ विकास के लिए गणितीय मानदंडों को पूरा करते हैं और न ही धीमी वृद्धि के लिए।

हचक्रॉफ्ट ने कहा, "यह वह जगह है जहां चीजें तीन साल तक वास्तव में निराशाजनक हो जाती हैं।"

संरचना बनाम विस्तार

विभिन्न पैमानों पर विकास दर को मिलाने वाले ग्राफ़ के लिए, आपको विभिन्न तकनीकों का उपयोग करना होगा।

एक बहुत उपयोगी तथ्य यह है कि, जैसा कि ईज़ो ने समझाया, "यदि कोई ग्राफ़ किसी पैमाने पर धीमी वृद्धि वाला दिखता है, तो वह अटक जाता है।" यह बड़े पैमाने पर धीरे-धीरे बढ़ता रहेगा। क्योंकि धीमी वृद्धि वाले ग्राफ़ में गणित की एक शाखा द्वारा निर्धारित अतिरिक्त संरचना होती है जिसे समूह सिद्धांत कहा जाता है, यह भी ज्ञात था कि यदि आप काफी दूर तक ज़ूम आउट करते हैं, तो धीमी वृद्धि वाले ग्राफ़ ज्यामिति प्रदर्शित करते हैं जो गणितीय रूप से नियंत्रित होती है।

2021 में, पेरिस में सोरबोन विश्वविद्यालय के सेबेस्टियन मार्टिनो, डैनियल कॉन्ट्रेरास के साथ काम कर रहे हैं और विंसेंट टैशन ETH ज्यूरिख का, इस संपत्ति का उपयोग करने में सक्षम था श्राम के स्थानीयता अनुमान को सिद्ध करें ग्राफ़ के लिए जो अंततः धीरे-धीरे बढ़ते हैं।

इस बिंदु पर, गणितज्ञों के दो समूहों ने अलग-अलग दिशाओं से अनुमान को सफलतापूर्वक हल किया था: तेज-विकास और धीमी-विकास। लेकिन इससे काफ़ी कमियाँ रह गईं। एक के लिए, एक मध्यवर्ती-विकास श्रेणी है जो ईसो और हचक्रॉफ्ट की तकनीक या कॉन्ट्रेरास, मार्टिनो और टैशन के प्रमाण द्वारा कवर नहीं की गई थी। एक और समस्या यह थी कि तर्क अभी भी बदलती विकास दर वाले ग्राफ़ पर लागू नहीं होते थे - केवल वे ग्राफ़ जो तेज़ रहे या धीमे रहे। कॉन्ट्रेरास, मार्टिनो और टैसियन तर्क को मनमाने ग्राफ़ पर लागू करने के लिए, यह पर्याप्त नहीं था कि जब आप ज़ूम आउट करते हैं तो ज्यामिति अंततः सामान्य दिखती है, ईसो ने समझाया: "हमें वर्तमान पैमाने के करीब, अब इसे नियंत्रित करने की आवश्यकता है।"

सुदूरवर्ती स्थान पर

मध्यवर्ती विकास के सकर्मक ग्राफ बहुत रहस्यमय हैं। गणितज्ञों को ऐसे संक्रमणीय ग्राफ का उदाहरण कभी नहीं मिला जिसकी वृद्धि इस सीमा में होती हो। यह संभव है कि उनका अस्तित्व ही न हो. लेकिन गणितज्ञों ने यह साबित नहीं किया है कि उनका अस्तित्व नहीं है, इसलिए श्राम के स्थानीय अनुमान के किसी भी पूर्ण प्रमाण में उन्हें संबोधित किया जाना चाहिए। चुनौती को बढ़ाते हुए, ईसो और हचक्रॉफ्ट को ऐसे ग्राफ़ को संबोधित करने की आवश्यकता थी, जिनमें एक विशेष लंबाई के पैमाने पर केवल संक्षेप में मध्यवर्ती वृद्धि हो सकती है, भले ही जब आप ज़ूम इन या ज़ूम आउट करते हैं तो वे तेजी से या धीमी गति से बढ़ते हैं।

ईसो और हचक्रॉफ्ट ने पिछले वर्ष का अधिकांश समय उन ग्राफ़ों पर लागू करने के लिए अपने परिणामों को विस्तारित करने में बिताया जो पहले के किसी भी तरीके से कवर नहीं किए गए थे।

सबसे पहले, उन्होंने 2018 तकनीक को संशोधित किया जिसे हचक्रॉफ्ट ने तेजी से बढ़ते ग्राफ़ पर लागू किया था ताकि उन ग्राफ़ पर काम किया जा सके जो विभिन्न स्तरों पर विकास स्तर को बदलते हैं। इसके बाद उन्होंने धीमी वृद्धि के मामले को निपटाया 27 पेज का पेपर उन्होंने अगस्त में कॉन्ट्रेरास, मार्टिनो और टैशन पर काम का विस्तार किया। अंत में, अपने अक्टूबर प्रीप्रिंट में, उन्होंने मध्यवर्ती-विकास मामले को संभालने के लिए यादृच्छिक चलने के सिद्धांत का उपयोग करते हुए एक और तर्क तैयार किया - रेखाएं जो अंतरिक्ष के माध्यम से यादृच्छिक रूप से घूमती हैं। ट्राइकोटॉमी पूरी होने के साथ, उन्होंने श्राम के स्थानीय अनुमान को साबित कर दिया था।

हचक्रॉफ्ट ने कहा, "हमें समस्या पर वह सब कुछ झोंकना पड़ा जो हम जानते थे।"

समाधान गणितज्ञों को इस बात की बेहतर जानकारी देता है कि अंतःस्राव सीमा के ऊपर क्या होता है, जहां एक अनंत क्लस्टर की संभावना 100% है, और इसके नीचे, जहां संभावना 0% है। लेकिन गणितज्ञ अभी भी त्रि-आयामी ग्रिड सहित अधिकांश ग्राफ़ की दहलीज पर जो होता है उससे स्तब्ध हैं। "यह संभवतः परकोलेशन सिद्धांत में सबसे प्रसिद्ध, सबसे बुनियादी खुला प्रश्न है," ने कहा रसेल ल्योंस इंडियाना यूनिवर्सिटी के.

द्वि-आयामी ग्रिड उन कुछ मामलों में से एक है जहां गणितज्ञों ने यह साबित कर दिया है कि वास्तव में दहलीज पर क्या होता है: अनंत क्लस्टर नहीं बनते हैं। और ग्रिमेट और मार्स्ट्रैंड ने बड़े स्लैब के लिए स्थानीयता अनुमान का एक संस्करण साबित करने के बाद, ग्रिमेट और सहयोगियों ने दिखाया कि यदि आप एक 3 डी ग्रिड को आधे क्षैतिज रूप से काटते हैं, एक फर्श बनाते हैं, और डायल को बिल्कुल परकोलेशन थ्रेशोल्ड पर ट्यून करते हैं, तो कोई अनंत क्लस्टर दिखाई नहीं देता है। उनका परिणाम संकेत देता है कि पूर्ण त्रि-आयामी ग्रिड, अपने द्वि-आयामी समकक्ष की तरह, अंतःस्राव सीमा पर एक अनंत क्लस्टर नहीं हो सकता है।

1996 में, बेन्जामिनी और श्राम अनुमान लगाया कि थ्रेशोल्ड पर एक अनंत क्लस्टर खोजने की संभावना सभी संक्रमणीय ग्राफ़ के लिए शून्य है - जैसे कि यह 2 डी ग्रिड के लिए है या आधे में कटे हुए 3 डी ग्रिड के लिए है। अब जबकि स्थानीयता का अनुमान तय हो गया है, संक्रमण के बिंदु पर क्या होता है इसकी समझ थोड़ी और करीब हो सकती है।

भूल सुधार: दिसम्बर 18/2023
3-नियमित ग्राफ़ पर शुरुआती नोड के n लिंक के भीतर नोड्स की संख्या लगभग 2 हो जाती हैⁿ, 3 नहींⁿ जैसा कि इस लेख में मूल रूप से कहा गया है। लेख को सही कर दिया गया है.

क्वांटा अपने दर्शकों को बेहतर सेवा देने के लिए सर्वेक्षणों की एक श्रृंखला आयोजित कर रहा है। हमारा ले गणित पाठक सर्वेक्षण और आपको निःशुल्क जीतने के लिए प्रवेश दिया जाएगा क्वांटा merch।