रूसी गणितज्ञ 53-वर्षीय परिकल्पना का हवाला देते हुए नेटवर्क के रंग के बारे में बताते हैं

रूसी गणितज्ञ के लिए केवल तीन पृष्ठों की आवश्यकता होती है, जो एक निश्चित प्रकार के रंग नेटवर्क का वर्णन करने के लिए विशेषज्ञों की अपेक्षाओं को पार करते हैं

53-वर्षीय परिकल्पना को नेटवर्क नोड्स में रंगों को असाइन करने के सर्वोत्तम तरीके के बारे में ऑनलाइन पेपर में मना किया गया है। केवल तीन पृष्ठों पर काम कुछ रंगों को रंगने के तरीकों के अस्तित्व को दर्शाता है जो विशेषज्ञों की सभी अपेक्षाओं को पार कर गए हैं।

रंग जाल के लिए कार्य [ रंगीन संख्या / लगभग देखें। ट्रांस। ], मानचित्रों के इस तरह के रंग के सवाल से प्रेरित, जिसमें पड़ोसी देशों के अलग-अलग रंग हैं, लगभग 200 वर्षों से गणितज्ञों द्वारा अनुसंधान के फोकस में हैं। कार्य यह समझना है कि किसी निश्चित नेटवर्क के नोड्स को कैसे रंग दिया जाए (या ग्राफ , उनके गणितज्ञ उन्हें क्या कहते हैं) ताकि किसी भी दो जुड़े हुए नोड्स में अलग-अलग रंग हों। संदर्भ के आधार पर, यह रंग मेहमानों को शादी में बैठने का एक प्रभावी तरीका प्रदान कर सकता है, खाली समय अंतराल के लिए उत्पादन कार्यों की व्यवस्था कर सकता है, या यहां तक ​​कि सुडोकू को हल कर सकता है।

ग्राफ रंग कार्य अक्सर तैयार करना आसान होता है, लेकिन हल करने के लिए अविश्वसनीय रूप से कठिन होता है। यहां तक ​​कि उस प्रश्न के उत्तर की तलाश में जिसके साथ अनुसंधान का यह पूरा क्षेत्र शुरू हुआ, क्या चार रंग किसी भी नक्शे को रंग देने के लिए पर्याप्त हैं ? - इसमें सौ साल से अधिक समय लगा (यदि आप रुचि रखते हैं, तो उत्तर हां है)।

नए काम में अब तक माना जाने वाला कार्य अपवाद नहीं माना गया था। इसे 50 से अधिक वर्षों तक हल नहीं किया जा सकता था, और यह टेंसर उत्पादों की चिंता करता है - ग्राफ़ दो अलग-अलग ग्राफ़ के एक विशेष संयोजन से बना है (चलो उन्हें जी और एच कहते हैं)। ग्राफ G और H का टेंसर उत्पाद एक नया, बड़ा ग्राफ है, जिसमें से प्रत्येक शीर्ष पर मूल ग्राफ़ के शीर्षों की एक जोड़ी को दर्शाया गया है - जी से एक और एच से एक - जबकि टेंसर उत्पाद के दो कोने जुड़े हुए हैं जब दोनों जी में संगत कोने हैं और एच में उनके संबंधित कोने।

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

1966 में, दक्षिण कैरोलिना के क्लेमसन विश्वविद्यालय में प्रोफेसर स्टीफन हेडेतेनिमी ने अपने डॉक्टरेट शोध प्रबंध में सुझाव दिया कि एक टेंसर उत्पाद को रंगने के लिए आवश्यक न्यूनतम रंगों में से दो रंगों में से किसी एक को रंगने के लिए आवश्यक दो रंगों में सबसे छोटा है। । "यह ग्राफ सिद्धांत में मुख्य परिकल्पनाओं में से एक है," यरूशलेम में हिब्रू विश्वविद्यालय के गिल कलाई ने कहा। "कई लोगों ने उसे इंगित करने की कोशिश की।"

पिछले दशकों में, गणितज्ञों ने सबूतों का एक पहाड़ इकट्ठा किया है, जिनमें से कुछ ने परिकल्पना की सच्चाई के बारे में बात की, और कुछ - इसकी मिथ्याता के बारे में। विभिन्न गणितज्ञों की अलग-अलग धारणाएँ थीं कि कौन सा विकल्प अंततः जीत जाएगा। लेकिन सभी सहमत थे कि कम से कम यह एक मुश्किल काम था।

"व्यक्तिगत रूप से, मुझे लगा कि यह परिकल्पना सच थी, क्योंकि बड़ी संख्या में स्मार्ट लोगों ने इसका अध्ययन किया था, और एक प्रतिरूप के साथ आना होगा," अगर यह अस्तित्व में है, तो टोरंटो में रायर्सन यूनिवर्सिटी के एंथनी बोनाटो ने कहा।

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

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

रंगीन हैंगआउट

टेंसर ग्राफ को रंगने से कौन सी जानकारी निकाली जा सकती है, यह कल्पना करने के लिए कि आप हर सप्ताहांत में अपने दोस्तों को अपनी उपनगरीय संपत्ति में आमंत्रित करने जा रहे हैं। और, एक अच्छे मेजबान के रूप में, आप ऐसे लोगों को इकट्ठा करना चाहते हैं जो एक-दूसरे की कंपनी का आनंद लेंगे।

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


यारोस्लाव शितोव ने ग्राफ थ्योरी से 53 वर्षीय हेडेटेनेमी परिकल्पना का एक प्रतिरूप खोजा

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

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

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

और इसके विपरीत, शौक ग्राफ के किसी भी स्वीकार्य रंग को टेंसर उत्पाद पर ले जाया जाता है। हेदेतेनीमी ने सुझाव दिया कि एक टेंसर ग्राफ को रंगने का सबसे अच्छा तरीका यह होगा कि मूल ग्राफ़ में से एक में न्यूनतम रंग हों।

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

और फिर भी, 50 से अधिक वर्षों के लिए, गणितज्ञों को रंग के लिए एक भी टेंसर उत्पाद नहीं मिला, जिसके किसी भी घटक ग्राफ के लिए कम रंगों की आवश्यकता होगी। वे यह साबित करने में सक्षम थे कि परिकल्पना सच है अगर दो ग्राफ़ में से किसी एक को रंग देने के लिए चार से अधिक रंगों की आवश्यकता नहीं थी। यह "फ्रैक्शनल" रंग के सामान्य मामले में भी सच है, जब प्रत्येक शीर्ष को रंगों का संयोजन सौंपा जा सकता है - उदाहरण के लिए, 2/3 पीला और 1/3 हरा। (सप्ताहांत के समारोहों के संदर्भ में, यह एक ऐसी स्थिति के अनुरूप हो सकता है जहां आपकी मित्र सूची में तीन पत्रकार हैं, जिनमें से एक टेनिस खेलता है, और आपने उनमें से दो को "पीले" सप्ताहांत के लिए आमंत्रित किया है, और तीसरा "हरा")।

इन निष्कर्षों ने सुझाव दिया कि परिकल्पना सच हो सकती है, लेकिन दूसरों ने इसके विपरीत कहा। उदाहरण के लिए, गणितज्ञों ने दिखाया है कि हेटेटेनेमी परिकल्पना ऐसे रेखांकन के लिए अलग होती है जिसमें रंग भरने के लिए अनंत संख्या में रंगों की आवश्यकता होती है, या निर्देशित रेखांकन के लिए जिनके किनारों को दिशाएँ पसंद होती हैं। लेकिन, इस तथ्य के बावजूद कि गणितज्ञों ने कुछ मामलों के लिए हेटेटेनेमी परिकल्पना को साबित किया और दूसरों के लिए इसका खंडन किया, वे उस क्षेत्र की समस्या को हल नहीं कर सकते थे जो स्वयं हेटेतेनिमी ने मूल रूप से माना था: पूर्णांक के रंग के साथ अप्रत्यक्ष रूप से रेखांकन।

प्रिंसटन यूनिवर्सिटी के नोगा एलोन ने कहा, "आम तौर पर सभी को लगता था कि यह सच है, लेकिन इसे साबित करना या इसे टालना मुश्किल था।"

रंग पेज

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

शितोव अपने काम की शुरुआत यह देखकर करता है कि क्या होगा यदि हम ग्राफ G को अपने एक घातीय ग्राफ के साथ जोड़ते हैं और उनके दसियों उत्पाद को प्राप्त करते हैं। घातांक ग्राफ में एक निश्चित निश्चित संख्या में रंगों के साथ जी के प्रत्येक संभव रंग के लिए एक नोड है (सभी संभव रंगों को अनुमति दी जाती है, न केवल उन लोगों के लिए जिनके साथ जुड़े हुए कोने अलग रंग हैं)। यदि उदाहरण के लिए ग्राफ G में 7 कोने हैं, और हमारे पैलेट में 5 रंग हैं, तो घातीय ग्राफ में 5 ⁷ कोने होंगे - यही कारण है कि इसे घातीय कहा जाता है।


ग्राफ के टेंसर उत्पाद को रंगने के लिए स्टीफन हेडेनेमी की परिकल्पना की न्यूनतम संख्या 50 से अधिक वर्षों तक अपुष्ट रही है।

यदि हम रंग विकल्प पर लौटते हैं, जिसमें जुड़े हुए कोने अलग-अलग रंगों के होने चाहिए, तो हम गारंटी नहीं दे सकते कि हमारे पैलेट के पांच रंग ग्राफ G को रंगने के लिए पर्याप्त होंगे, और इसी तरह वे 5 ⁷ कोने के साथ घातीय ग्राफ को रंगने के लिए पर्याप्त नहीं हो सकते हैं। । हालांकि, गणितज्ञों ने लंबे समय से जाना है कि एक ग्राफ है जिसके लिए पांच रंग पर्याप्त हैं: यह एक टेनर उत्पाद है जिसमें जी और इसके घातीय ग्राफ शामिल हैं।

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

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

गणितज्ञों का कहना है कि नया प्रतिरूप चालाक और आविष्कारशील है, और इसके लिए जटिल उन्नत गणितीय साधनों की आवश्यकता नहीं है। "एक ग्राफ सिद्धांत विशेषज्ञ के लिए, इस डिजाइन को दो वाक्यों में समझाया जा सकता है," कलाई ने कहा।

50 वर्षों से अधिक समय तक किसी ने भी इस तर्क पर ध्यान नहीं दिया कि गणितज्ञों के लिए यह एक रहस्य है। "कभी-कभी एक छोटा मणि पत्ते के ढेर के नीचे छिप जाता है," नर्क ने कहा। "शितोव बस इस सवाल को बाकी सभी की तुलना में अधिक गहराई से समझने में कामयाब रहे।"

शितोव के रेखांकन विशाल होते हैं: उन्होंने अपने सटीक आकार की गणना नहीं की, लेकिन अनुमान है कि ग्राफ़ G में संभवतः लगभग ^4,100 कोने होंगे, और घातीय ग्राफ़ में कम से कम ^4,000 कोने होंगे, यानी प्राथमिक कणों की अनुमानित संख्या से बहुत अधिक अवलोकनीय ब्रह्मांड [ लगभग 10 ⁸⁰ / लगभग। ट्रांस। ]।

लेकिन, ज़ाहिर है, यह सब पर्यवेक्षक पर निर्भर करता है। शितोव का मानना ​​है कि उनका प्रतिपक्ष “इतना विशाल नहीं है। गणित में, आप प्रतिरूप देख सकते हैं, जिसकी तुलना में यह बहुत कम होगा। "

और यद्यपि आप अपने देश के घर में ^4,000 को आमंत्रित करने में सक्षम होने की संभावना नहीं रखते हैं, लेकिन शिटोव का काम बहुत छोटे आकार के काउंटरटेक्मेन्स के अस्तित्व को अस्वीकार नहीं करता है। लेकिन अब जब गणितज्ञों को पता है कि हेदेतेनीमी परिकल्पना झूठी है, तो स्वाभाविक सवाल यह होगा कि यह वास्तव में कितना गलत है: अपने घटक रेखांकन की तुलना में एक टेंसर उत्पाद को रंगने के लिए कितने कम रंगों की आवश्यकता हो सकती है, और नोड्स और किनारों की न्यूनतम संख्या क्या हो सकती है?

इस बीच, एलोन ने कहा कि नए काम में सभी गणितज्ञों के लिए एक महत्वपूर्ण सबक शामिल है: "कभी-कभी कारण यह है कि एक परिकल्पना साबित करना बहुत मुश्किल है कि यह गलत है।"