Container method
(हाइपरग्राफ) पात्रों की विधि एक शक्तिशाली उपकरण है जो विशिष्ट संरचना को चिह्नित करने और/या स्थानीय बाधाओं के निर्धारित सेट के साथ असतत वस्तुओं के परिवारों के बारे में चरम प्रश्नों का उत्तर देने में मदद कर सकता है। इस तरह के प्रश्न स्वाभाविक रूप से चरम ग्राफ सिद्धांत, योगात्मक संयोजन, असतत ज्यामिति, कोडिंग सिद्धांत और रैमसे सिद्धांत में उत्पन्न होते हैं; इनमें संबंधित क्षेत्रों में कुछ सबसे शास्त्रीय समस्याएं शामिल हैं। इन समस्याओं को निम्नलिखित रूप के प्रश्नों के रूप में व्यक्त किया जा सकता हैः किनारे सेट के साथ परिमित शीर्ष सेट पर एक हाइपरग्राफ दिया गया है (यानी। कुछ आकार की बाधाओं के साथ उपसमुच्चय का एक संग्रह), हम स्वतंत्र सेटों के बारे में क्या कह सकते हैं (यानी। उन उपसमुच्चय में कोई तत्व नहीं है)? हाइपरग्राफ कंटेनर लेम्मा ऐसे प्रश्नों से निपटने के लिए एक विधि प्रदान करता है। इतिहास चरम ग्राफ सिद्धांत की मूलभूत समस्याओं में से एक, जो 1907 में मेंटेल और 1940 के दशक के तुरान के काम से संबंधित है, उन ग्राफों को चिह्नित करने के लिए कहता है जिनमें उपग्राफ के रूप में निषिद्ध कुछ निश्चित की प्रति नहीं होती है। एक अलग क्षेत्र में, योगात्मक संयोजन में प्रेरक प्रश्नों में से एक यह समझना है कि पूर्णांकों का एक समूह कितना बड़ा हो सकता है, जिसमें एक-शब्द अंकगणितीय प्रगति शामिल नहीं है, इस आकार पर ऊपरी सीमाएँ रोथ () और स्ज़ेमेरेडी (सामान्य) द्वारा दी गई हैं। पात्रों की विधि (ग्राफ में) शुरू में 1980 में क्लेटमैन और विंस्टन द्वारा शुरू की गई थी, जिन्होंने 4-चक्रों के बिना जाली और ग्राफ की संख्या को सीमित किया था। कंटेनर-शैली के लेम्मा को अलग-अलग संदर्भों में कई गणितविदों द्वारा स्वतंत्र रूप से विकसित किया गया था, विशेष रूप से सपोझेंको सहित, जिन्होंने शुरू में इस दृष्टिकोण का उपयोग नियमित ग्राफ में स्वतंत्र सेटों की गणना करने के लिए किया था, अबेलियन समूहों में योग-मुक्त सेट, और विभिन्न अन्य गणना समस्याओं का अध्ययन एक हाइपरग्राफ कंटेनर लेम्मा के लिए इन विचारों का सामान्यीकरण 2015 में सैक्सटन और थॉमसन और बालोग, मॉरिस और समोतिज द्वारा स्वतंत्र रूप से तैयार किया गया था, जो पिछले विभिन्न संबंधित कार्यों से प्रेरित था। मुख्य विचार और अनौपचारिक कथन संयोजन विज्ञान में कई समस्याओं को ग्राफ और हाइपरग्राफ में स्वतंत्र सेट के बारे में प्रश्नों के रूप में पुनर्गठित किया जा सकता है। उदाहरण के लिए, मान लीजिए कि हम पूर्णांकों के उपसमुच्चय को समझना चाहते हैं, जिसे हम एक-पद अंकगणितीय प्रगति की कमी से दर्शाते हैं। ये समुच्चय एक समान हाइपरग्राफ में बिल्कुल स्वतंत्र समुच्चय हैं, जहाँ सभी अवधि के अंकगणितीय प्रगति का संग्रह है। उपरोक्त (और कई अन्य) उदाहरणों में, आमतौर पर एक हाइपरग्राफ के बारे में उत्पन्न समस्याओं के दो प्राकृतिक वर्ग होते हैंः एक अधिकतम स्वतंत्र सेट का आकार क्या है? अधिकतम आकार के स्वतंत्र सेटों का संग्रह कैसा दिखता है? स्वतंत्र सेट कैसे हो सकते हैं? एक "विशिष्ट" स्वतंत्र समूह कैसा दिखता है? ये समस्याएं एक सरल अवलोकन से जुड़ी हुई हैं। मान लीजिए कि एक सबसे बड़े स्वतंत्र सेट का आकार है और मान लीजिए कि स्वतंत्र सेट हैं। फिर, जहां निचली सीमा एक अधिकतम स्वतंत्र सेट के सभी सबसेटों को लेकर आगे बढ़ती है। ये सीमाएँ एक-दूसरे से अपेक्षाकृत बहुत दूर हैं जब तक कि बहुत बड़ी न हों, हाइपरग्राफ के शीर्षों की संख्या के करीब न हों। हालांकि, कई हाइपरग्राफ में जो स्वाभाविक रूप से संयोजन समस्याओं में उत्पन्न होते हैं, हमारे पास यह मानने का कारण है कि निचली सीमा सही मूल्य के करीब है; इस प्रकार प्राथमिक लक्ष्य ऊपरी सीमा में सुधार करना है। हाइपरग्राफ कंटेनर लेम्मा एक हाइपरग्राफ में स्वतंत्र सेटों के परिवार की संरचना और आकार को समझने के लिए एक शक्तिशाली दृष्टिकोण प्रदान करता है। इसके मूल में, हाइपरग्राफ कंटेनर विधि हमें एक हाइपरग्राफ, कंटेनरों का एक संग्रह, शीर्षों के उपसमुच्चय से निकालने में सक्षम बनाती है जो निम्नलिखित गुणों को संतुष्ट करते हैंः बहुत अधिक कंटेनर नहीं हैं। प्रत्येक पात्र सबसे बड़े स्वतंत्र समूह से बहुत बड़ा नहीं होता है। प्रत्येक पात्र के कुछ किनारे होते हैं। हाइपरग्राफ में प्रत्येक स्वतंत्र सेट पूरी तरह से किसी न किसी पात्र में शामिल होता है। पात्र नाम इस अंतिम शर्त को दर्शाता है। इस तरह के कंटेनर अक्सर स्वतंत्र सेटों (कंटेनरों के सबसेट) के परिवार को चिह्नित करने और हाइपरग्राफ के स्वतंत्र सेटों की गणना करने (केवल एक कंटेनर के सभी संभावित सबसेटों पर विचार करके) के लिए एक प्रभावी दृष्टिकोण प्रदान करते हैं। हाइपरग्राफ कंटेनर लेम्मा उपरोक्त कंटेनर के अपघटन को दो टुकड़ों में प्राप्त करता है। यह एक निर्धारक कार्य का निर्माण करता है। फिर, यह एक एल्गोरिथ्म प्रदान करता है जो हाइपरग्राफ में प्रत्येक स्वतंत्र सेट से निकालता है, शीर्षों का एक अपेक्षाकृत छोटा संग्रह, जिसे फिंगरप्रिंट कहा जाता है, उस गुण के साथ। फिर, कंटेनर उपरोक्त प्रक्रिया में उत्पन्न होने वाले सेटों का संग्रह है, और उंगलियों के निशान का छोटा आकार ऐसे कंटेनर सेटों की संख्या पर अच्छा नियंत्रण प्रदान करता है। ग्राफ कंटेनर एल्गोरिथ्म हम पहले एक ग्राफ में स्वतंत्र सेटों की संख्या पर मजबूत ऊपरी सीमा दिखाने के लिए एक विधि का वर्णन करते हैं; इस प्रदर्शनी को ग्राफ कंटेनर विधि के बारे में समोतिज के एक सर्वेक्षण से अनुकूलित किया गया है, जिसे मूल रूप से क्लेटमैन-विंस्टन और सापोज़ेंको द्वारा नियोजित किया गया है। हम नीचे दिए गए खंड में निम्नलिखित संकेतन का उपयोग करते हैं। यह शीर्षों पर एक ग्राफ है, जहां शीर्ष समूह (मनमाना) क्रम से सुसज्जित है। आकार के साथ स्वतंत्र सेटों का संग्रह होने दें। मान लीजिए कि आकार के स्वतंत्र सेटों की संख्या कितनी है। एक शीर्ष उपसमुच्चय का अधिकतम-डिग्री क्रम प्रेरित उपलेख में उनकी डिग्री द्वारा शीर्षों का क्रम है। क्लेटमैन-विंस्टन एल्गोरिथ्म निम्नलिखित एल्गोरिथ्म एक ग्राफ में प्रत्येक स्वतंत्र सेट के लिए एक छोटा "फिंगरप्रिंट" देता है और एक बहुत बड़े उपसमुच्चय के निर्माण के लिए फिंगरप्रिंट का एक निर्धारक कार्य देता है जिसमें संपूर्ण स्वतंत्र सेट फिक्स ग्राफ, स्वतंत्र सेट और सकारात्मक पूर्णांक शामिल होते हैं। आरंभ करेंः चलो। के लिए पुनरावृत्तिः न्यूनतम सूचकांक का पता लगाने के लिए अधिकतम-डिग्री क्रम का निर्माण करें जैसे कि (अर्थात। प्रेरित उपग्राफ में सबसे बड़ी डिग्री का शीर्ष) मान लीजिए, शीर्ष का पड़ोस कहाँ है। वेक्टर और वर्टेक्स सेट को आउटपुट करें। विश्लेषण निर्माण द्वारा, उपरोक्त एल्गोरिथ्म के आउटपुट में गुण है कि, यह देखते हुए कि यह एक शीर्ष उपसमुच्चय है जो पूरी तरह से निर्धारित किया जाता है और अन्यथा एक कार्य नहीं है। इस पर जोर देने के लिए हम लिखेंगे। हम यह भी देखते हैं कि हम केवल वेक्टर से उपरोक्त एल्गोरिदम में सेट का पुनर्निर्माण कर सकते हैं। इससे पता चलता है कि यह फिंगरप्रिंट का एक अच्छा विकल्प और कंटेनर के लिए एक अच्छा विकल्प हो सकता है। अधिक सटीक रूप से, हम कुछ आकार के स्वतंत्र सेटों की संख्या को आउटपुट अनुक्रमों के योग के रूप में बांध सकते हैं, जहां हम ग्राफ के स्वतंत्र सेटों की कुल संख्या पर एक सीमा प्राप्त करने के लिए जोड़ सकते हैंः इस ऊपरी सीमा को कम करने का प्रयास करते समय, हम उस संतुलन को चुनना चाहते हैं/इन दो शब्दों को कम करना चाहते हैं। यह परिणाम शीर्षों को अधिकतम डिग्री (न्यूनतम करने के लिए) से क्रमबद्ध करने के मूल्य को दर्शाता है। लेम्मास उपरोक्त असमानताओं और टिप्पणियों को अधिक सामान्य सेटिंग में कहा जा सकता है, जो वैक्टरों पर एक स्पष्ट योग से अलग है। लेम्मा 1: के साथ एक ग्राफ दिया गया है और मान लीजिए कि पूर्णांक और वास्तविक संख्याएँ संतुष्ट करती हैं। मान लीजिए कि कम से कम शीर्षों पर प्रत्येक प्रेरित उपग्राफ में कम से कम किनारे का घनत्व होता है। फिर प्रत्येक पूर्णांक के लिए, लेम्मा 2: मान लीजिए कि शीर्षों पर एक ग्राफ है और मान लीजिए कि एक पूर्णांक और वास्तविक इस तरह से चुने गए हैं। यदि कम से कम शीर्षों के सभी उपसमुच्चय में कम से कम किनारे होते हैं, तो शीर्षों के उपसमुच्चय ("उंगलियों के निशान") और एक निर्धारक कार्य का संग्रह होता है, ताकि प्रत्येक स्वतंत्र समुच्चय के लिए ऐसा हो। हाइपरग्राफ कंटेनर लेम्मा अनौपचारिक रूप से, हाइपरग्राफ कंटेनर लेम्मा हमें बताता है कि हम प्रत्येक स्वतंत्र सेट को एक छोटा फिंगरप्रिंट दे सकते हैं, ताकि एक ही फिंगरप्रिंट वाले सभी स्वतंत्र सेट एक ही बड़े सेट, संबंधित कंटेनर से संबंधित हों, जिसका आकार हाइपरग्राफ के शीर्षों की संख्या से दूर हो। इसके अलावा, ये उंगलियों के निशान छोटे होते हैं (और इस प्रकार कुछ पात्र होते हैं), और हम हाइपरग्राफ के कुछ सरल गुणों का उपयोग करके अनिवार्य रूप से इष्टतम तरीके से उनके आकार को ऊपर से बांध सकते हैं। हम यूनिफॉर्म हाइपरग्राफ से जुड़े निम्नलिखित संकेतन को याद करते हैं। धनात्मक पूर्णांक के लिए परिभाषित करें, जहाँ। मान लीजिए स्वतंत्र सेटों का संग्रह है। इस तरह के कुछ स्वतंत्र सेट को दर्शाता है। कथन हम बालोग, मॉरिस, समोतिज और सैक्सटन के एक काम में पाए गए इस लेम्मा के संस्करण का उल्लेख करते हैं और मान लीजिए कि प्रत्येक और कुछ के लिए, हमारे पास यह है। फिर, एक संग्रह और एक कार्य ऐसा होता है कि प्रत्येक के लिए और के साथ मौजूद होता है। प्रत्येक और के लिए। उदाहरण अनुप्रयोग नियमित ग्राफ स्वतंत्र समुच्चयों की संख्या पर ऊपरी सीमा हम दिखाएँगे कि एक निरपेक्ष स्थिरांक ऐसा है कि प्रत्येक-वर्टेक्स-नियमित ग्राफ संतुष्ट करता है। हम के लिए तुच्छ सीमा का उपयोग करके प्रत्येक आकार के स्वतंत्र सेटों की संख्या को बांध सकते हैं। इन मापदंडों के साथ,-नियमित ग्राफ लेम्मा 1 की शर्तों को संतुष्ट करता है और इस प्रकार, सभी का सारांश देता है, जो वांछित परिणाम देता है जब हम सम-फ्री सेट में प्लग करते हैं एक अबेलियन समूह के तत्वों के एक समूह को सम-फ्री कहा जाता है यदि कोई संतोषजनक नहीं है। हम दिखाएँगे कि अधिक से अधिक राशि-मुक्त उपसमुच्चय हैं। यह एक नियमित ग्राफ में स्वतंत्र सेटों की संख्या पर हमारी उपरोक्त सीमाओं का अनुसरण करेगा। इसे देखने के लिए, हमें एक सहायक ग्राफ बनाने की आवश्यकता होगी। हम सबसे पहले देखते हैं कि निचले क्रम की शर्तों तक, हम अपना ध्यान कम से कम छोटे तत्वों के साथ योग-मुक्त सेटों तक सीमित कर सकते हैं (क्योंकि इसके पूरक में सबसेटों की संख्या अधिक से अधिक है)। कुछ सबसेट को देखते हुए, हम वर्टेक्स सेट और एज सेट के साथ एक सहायक ग्राफ को परिभाषित करते हैं, और देखते हैं कि हमारा सहायक ग्राफ नियमित है क्योंकि इसका प्रत्येक तत्व उससे छोटा है। फिर यदि सबसे छोटे उपसमुच्चय के तत्व हैं, तो समुच्चय ग्राफ में एक स्वतंत्र समुच्चय है। फिर, हमारी पिछली सीमा से, हम देखते हैं कि योग-मुक्त उपसमुच्चय की संख्या अधिक से अधिक त्रिभुज-मुक्त आलेखों पर है हम शीर्षों के साथ त्रिभुज-मुक्त आलेखों की संख्या पर एक स्पर्शोन्मुख रूप से तंग ऊपरी सीमा देकर एक गणनात्मक प्रश्न का उत्तर देने के लिए हाइपरग्राफ कंटेनर लेम्मा का उपयोग करने का एक चित्रण देते हैं। अनौपचारिक कथन चूंकि द्विदलीय ग्राफ त्रिभुज-मुक्त होते हैं, इसलिए शीर्षों के साथ त्रिभुज मुक्त ग्राफ की संख्या कम से कम संतुलित पूर्ण द्विदलीय ग्राफ के सभी संभावित उपग्राफ की गणना करके प्राप्त की जाती है। हम वर्टेक्स सेट और एज सेट के साथ एक सहायक-समान हाइपरग्राफ का निर्माण कर सकते हैं। यह हाइपरग्राफ त्रिभुज को इस अर्थ में "कूटबद्ध" करता है कि शीर्षों पर त्रिभुज-मुक्त ग्राफ का परिवार बिल्कुल इस हाइपरग्राफ के स्वतंत्र सेटों का संग्रह है। उपरोक्त हाइपरग्राफ का एक अच्छा डिग्री वितरण हैः का प्रत्येक किनारा, और इस प्रकार शीर्ष बिल्कुल त्रिभुजों में निहित है और इसमें तत्वों की प्रत्येक जोड़ी अधिकतम 1 त्रिभुज में निहित है। इसलिए, हाइपरग्राफ कंटेनर लेम्मा (पुनरावृत्त रूप से) को लागू करते हुए, हम यह दिखाने में सक्षम हैं कि कंटेनरों का एक परिवार है जिसमें प्रत्येक में कुछ त्रिकोण होते हैं जिनमें प्रत्येक त्रिभुज-मुक्त ग्राफ/हाइपरग्राफ का स्वतंत्र सेट होता है। त्रिभुज-मुक्त ग्राफों की संख्या पर ऊपरी सीमा हम पहले सामान्य हाइपरग्राफ कंटेनर लेम्मा को 3-समान हाइपरग्राफों के लिए इस प्रकार विशेषज्ञता देते हैंः लेम्माः प्रत्येक के लिए, ऐसा मौजूद है जो निम्नलिखित धारण करता है। मान लीजिए कि औसत डिग्री के साथ एक 3-समान हाइपरग्राफ है। फिर अधिकांश पात्रों का एक संग्रह मौजूद है जैसे कि प्रत्येक के लिए, सभी के लिए मौजूद है इस लेम्मा को बार-बार लागू करने से निम्नलिखित प्रमेय मिलेगा (जैसा कि नीचे सिद्ध किया गया है): प्रमेयः सभी के लिए, ऐसा मौजूद है जो निम्नलिखित धारण करता है। प्रत्येक धनात्मक पूर्णांक के लिए, शीर्षों पर ग्राफ का एक संग्रह मौजूद होता है जिसमें प्रत्येक में त्रिभुज से कम होते हैं, शीर्षों पर प्रत्येक त्रिभुज-मुक्त ग्राफ कुछ में निहित होता है। प्रमाणः ऊपर परिभाषित हाइपरग्राफ पर विचार करें। जैसा कि अनौपचारिक रूप से पहले देखा गया है, हाइपरग्राफ प्रत्येक के लिए संतुष्ट करता है। इसलिए, हम उपसमुच्चय के कुछ संग्रह को खोजने के लिए उपरोक्त लेम्मा को साथ में लागू कर सकते हैं (अर्थात। शीर्षों पर ग्राफ) जैसे कि प्रत्येक त्रिभुज मुक्त ग्राफ कुछ का उपग्राफ है, प्रत्येक में अधिकांश किनारे होते हैं। यह उतना मजबूत नहीं है जितना हम परिणाम दिखाना चाहते हैं, इसलिए हम कंटेनर लेम्मा को बार-बार लागू करेंगे। मान लीजिए कि हमारे पास कम से कम त्रिभुज वाला कोई पात्र है। हम कंटेनर लेम्मा को प्रेरित उप-हाइपरग्राफ पर लागू कर सकते हैं। की औसत डिग्री कम से कम है, क्योंकि प्रत्येक त्रिभुज में एक किनारा होता है, और इस प्रेरित उपग्राफ में अधिकांश शीर्ष होते हैं। इस प्रकार, हम लेम्मा को पैरामीटर के साथ लागू कर सकते हैं, अपने कंटेनरों के सेट से हटा सकते हैं, इसे कंटेनरों के इस सेट, कंटेनरों के आवरण द्वारा प्रतिस्थापित कर सकते हैं। हम तब तक पुनरावृत्ति करते रह सकते हैं जब तक कि हमारे पास पात्रों का अंतिम संग्रह न हो जिसमें प्रत्येक में त्रिभुज से कम हों। हम देखते हैं कि यह संग्रह बहुत बड़ा नहीं हो सकता है; हमारे सभी प्रेरित उपलेखों में अधिक से अधिक शीर्ष और कम से कम औसत डिग्री होती है, जिसका अर्थ है कि प्रत्येक पुनरावृत्ति के परिणामस्वरूप अधिक से अधिक नए पात्र होते हैं। इसके अलावा, पात्र का आकार प्रत्येक बार के एक कारक से सिकुड़ जाता है, इसलिए पुनरावृत्तियों की एक सीमित (निर्भर) संख्या के बाद, पुनरावृत्ति प्रक्रिया समाप्त हो जाएगी। स्वतंत्र समुच्चय (ग्राफ सिद्धांत) स्ज़ेमेरेडी की प्रमेय स्ज़ेमेरेडी नियमितता लेम्मा संदर्भ अतिरिक्त ग्राफ सिद्धांत हाइपरग्राफ योगात्मक संयोजन भी देखें।