गणितज्ञों ने ग्राफ़ में संरचना की भविष्यवाणी करने का नया तरीका खोजा | क्वांटा पत्रिका

कॉम्बिनेटरिक्स अनुसंधान में यह एक उत्साहजनक वर्ष रहा है। 2023 की शुरुआत में गणितज्ञ तब दंग रह गए जब में से दो la सबसे बड़ी समस्या क्षेत्र में कई महीनों में हल किया गया। अब, एक तीसरा प्रमुख प्रश्न 14 पेज के प्रमाण के साथ सामने आया है "जिसमें बिल्कुल सही विचार हैं," ने कहा मेहताब साहनी मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी के, जिन्होंने कहा: "यह पूरी तरह से चौंकाने वाला है।"

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

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

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

पार्टी योजना ग्राफ सिद्धांत से मिलती है

यह समझने के लिए कि रैमसे नंबर क्या है, कल्पना करें कि आप एक पार्टी की मेजबानी कर रहे हैं।

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

आपसी परिचितों या अजनबियों के एक समूह को एक संरचना द्वारा दर्शाया जाता है जिसे क्लिक कहा जाता है: एक ही रंग के किनारों से जुड़े शीर्षों का एक सेट। रैमसे नंबर r(s, t) लोगों की वह न्यूनतम संख्या है जिसे आपको आमंत्रित करना चाहिए ताकि किसी समूह को शामिल करने से बचना असंभव हो जाए s परिचितों या t अजनबी - ग्राफ सिद्धांत की भाषा में, आकार का एक लाल समूह s या आकार का एक नीला समूह t.

उदाहरण के लिए, हम यह जानते हैं r(4, 5) = 25. तो आप चार आपसी परिचितों या पांच अजनबियों के समूह को शामिल किए बिना, 24 लोगों के साथ एक पार्टी की मेजबानी कर सकते हैं, जिनमें से कुछ एक-दूसरे को जानते हैं। लेकिन एक और व्यक्ति जोड़ें, और आप इनमें से कम से कम एक संरचना बनाने से बच नहीं सकते।

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

गणितज्ञ केवल कुछ ही सबसे छोटी रैमसे संख्याओं की सटीक गणना करने में सक्षम हैं। उन्होंने यह साबित कर दिया r(4)=5 में 25। लेकिन इसका मूल्य कोई नहीं जानता r(4, 6). इसी तरह, 1980 के दशक की शुरुआत में, उन्होंने दिखाया कि r(3, 9) = 36, लेकिन r(3) एक खुली समस्या बनी हुई है। (सममित मामला उतना ही कठिन है: r(4) = 18, लेकिन का मान r(5) ज्ञात नहीं है.)

और इसलिए गणितज्ञ इसके बजाय रैमसे संख्याओं का अनुमान लगाने की कोशिश करते हैं - उनके मूल्यों पर ऊपरी और निचली सीमाएँ लेकर आते हैं।

1990 के दशक में, उन्होंने यह साबित करने के लिए बेतरतीब ढंग से ग्राफ़ बनाने की तकनीकों का उपयोग किया कि यदि लाल क्लिक 3 पर तय हो गया है, और नीला बड़ा और बड़ा हो जाता है, तो रैमसे संख्या का आकार नीले क्लिक के आकार के वर्ग के रूप में बढ़ता है। दूसरे शब्दों में, r(3, t) लगभग t².

नया प्रमाण पूछता है कि क्या होता है जब लाल गुट का आकार 4 के बजाय 3 पर सेट किया जाता है। 1930 के दशक में, यह स्थापित किया गया था कि r(4, t) आसपास से अधिक तेजी से नहीं बढ़ता है t³. लेकिन 1970 के दशक में पाई गई सबसे अच्छी निचली सीमा इसके बारे में है t^5/2 - काफी छोटा।

निचली सीमा को बढ़ाकर या ऊपरी सीमा को कम करके अंतर को बंद करने के प्रयास दशकों तक विफल रहे, जब तक कि गणितज्ञों की एक जोड़ी ने एक प्रमुख घटक नहीं जोड़ा।

सादी दृष्टि में छिपा हुआ

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

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

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

2022 में, मैथ्यूस को फ़ुलब्राइट (साथ में) से सम्मानित किए जाने के तुरंत बाद एक और फ़ेलोशिप), वह यूसीएसडी में चले गए और वेरस्ट्रेट के साथ काम करना शुरू कर दिया r(4,t). गणितज्ञ ज्ञात ऊपरी सीमा को पूरा करने के लिए निचली सीमा को ऊपर उठाना चाहते थे। ऐसा करने के लिए, उन्हें लगभग वाला एक ग्राफ ढूंढना होगा t³ वे शीर्ष जिनमें आकार 4 के लाल समूह या आकार के नीले समूह नहीं थे t.

अपने प्रमाण को काम में लाने के लिए, उन्होंने समस्या को दोबारा तैयार किया। बस हर नीले किनारे को हटाने की कल्पना करें। लक्ष्य अब एक ऐसा ग्राफ ढूंढना है जिसमें आकार 4 के कोई लाल क्लिक न हों, और आकार का कोई स्वतंत्र सेट न हो t (अर्थात, के सेट t बिना किसी किनारे के शीर्ष)।

मुबायी और वेरस्ट्रेट के 2019 के काम में निहित है कि यदि आप आकार 4 के लाल क्लिक्स के बिना एक छद्म यादृच्छिक ग्राफ का निर्माण कर सकते हैं, तो आप बिना किसी बड़े स्वतंत्र सेट के छोटे ग्राफ़ प्राप्त करने के लिए इसके यादृच्छिक टुकड़े ले सकते हैं। मैथ्यूस और वेरस्ट्रेट बिल्कुल यही खोजना चाहते थे। इससे भी बड़े ग्राफ़ के साथ शुरुआत करके, उन्हें लगभग एक ग्राफ़ खोजने की उम्मीद थी t³ शिखर जो उनके मानदंडों पर खरे उतरे। वेरस्ट्रेट ने कहा, "इन ग्राफ़ के अंदर बेहतर रैमसे ग्राफ़ छिपे हुए हैं।"

समस्या शुरू करने के लिए सही छद्म आयामी निर्माण का पता लगाने की थी।

गणितज्ञों को कुछ हद तक घूमकर वहां पहुंचना पड़ा। उन्होंने छद्म यादृच्छिक ग्राफ़ से शुरुआत नहीं की। उन्होंने बिल्कुल भी ग्राफ़ से शुरुआत नहीं की।

इसके बजाय, मैथ्यूस को एक अजीब वस्तु याद आई जिसे हर्मिटियन यूनिटल कहा जाता है, कुछ ऐसा जिससे परिमित जियोमीटर बहुत परिचित होते हैं - लेकिन कॉम्बिनेटरिक्स में काम करने वाले गणितज्ञ को कभी भी इसका सामना करने की संभावना नहीं थी।

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

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

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

इन विलोपनों ने उन्हें 4 क्लिक्स के आकार के बिना एक नया ग्राफ़ दिया - लेकिन इसमें अभी भी बड़े स्वतंत्र सेट शामिल थे। मैथ्यूस और वेरस्ट्रेट को अब यह साबित करने की जरूरत थी कि यह ग्राफ छद्म यादृच्छिक था। ऐसा करने पर, वे अंततः 2019 के प्रमाण का उपयोग करने में सक्षम हो गए जैसा कि उन्हें उम्मीद थी। उन्होंने इसके बारे में यादृच्छिक सबग्राफ़ लिए t³ शीर्ष, और यह गारंटी दे सकता है कि वे सबग्राफ़ आकार के स्वतंत्र सेटों से मुक्त थे t.

इससे प्रमाण पूरा हो गया। साहनी ने कहा, "यह निर्माण बिल्कुल सुंदर है।"

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