Blow-up lemma
1997 में जानोस कोम्लोस, गैबर एन. सार्कोजी और एंड्रे स्ज़ेमेरेडी द्वारा साबित किया गया ब्लो-अप लेम्मा, चरम ग्राफ सिद्धांत में एक महत्वपूर्ण परिणाम है, विशेष रूप से नियमितता विधि के संदर्भ में। यह बताता है कि स्ज़ेमेरेडी की नियमितता लेम्मा के कथन में नियमित जोड़े सीमित डिग्री के फैले हुए ग्राफ को एम्बेड करने के संदर्भ में पूर्ण द्विदलीय ग्राफ की तरह व्यवहार करते हैं। परिभाषाएँ और कथन ब्लो-अप लेम्मा को औपचारिक रूप से बताने के लिए, हमें पहले एक अति-नियमित जोड़ी की धारणा को परिभाषित करने की आवश्यकता है। अति-नियमित जोड़े शीर्ष समूह के उपसमुच्चय की एक जोड़ी को-अति-नियमित कहा जाता है यदि प्रत्येक और संतोषजनक के लिए और हमारे पास है और इसके अलावा, सभी के लिए और सभी के लिए। यहाँ जोड़ों की संख्या को दर्शाता है और ऐसा जो एक किनारा है। ब्लो-अप लेम्मा का कथन क्रम और सकारात्मक मापदंडों के एक ग्राफ को देखते हुए, एक सकारात्मक इस तरह मौजूद है कि निम्नलिखित धारण करता है। आइए मनमाने ढंग से सकारात्मक पूर्णांक हों और आइए हम के शीर्षों को आकारों के जोड़ीदार असंबद्ध सेटों (उड़ाने वाले) के साथ प्रतिस्थापित करें। हम एक ही शीर्ष समूह पर दो ग्राफ बनाते हैं। पहला ग्राफ संबंधित शीर्ष समुच्चय और के बीच पूर्ण द्विदलीय ग्राफ के साथ प्रत्येक किनारे को प्रतिस्थापित करके प्राप्त किया जाता है। एक स्पार्स ग्राफ जी का निर्माण प्रत्येक किनारे को और के बीच एक-सुपर-नियमित जोड़ी के साथ बदलकर किया जाता है। यदि एक ग्राफ के साथ एम्बेडेबल है तो यह पहले से ही जी. प्रूफ स्केच में एम्बेडेबल है ब्लो-अप लेम्मा का प्रमाण क्रमिक रूप से शीर्षों को एम्बेड करने के लिए एक यादृच्छिक लालची एल्गोरिदम (आरजीए) का उपयोग करने पर आधारित है। तर्क तब एल्गोरिथ्म की विफलता दर को इस तरह से सीमित करके आगे बढ़ता है कि यह मापदंडों के उचित चयन के लिए 1 (और वास्तव में) से कम है। इसका मतलब है कि एल्गोरिथ्म के सफल होने की एक गैर-शून्य संभावना है, इसलिए एक एम्बेडिंग मौजूद होनी चाहिए। इस तरह से सभी शीर्षों को सीधे एम्बेड करने का प्रयास काम नहीं करता है क्योंकि एल्गोरिथ्म तब अटक सकता है जब केवल कुछ ही शीर्ष बचे हों। इसके बजाय, हम शीर्ष समूह के एक छोटे से अंश को अलग रखते हैं, जिसे बफर शीर्ष कहा जाता है, और बाकी शीर्षों को एम्बेड करने का प्रयास करते हैं। बफर शीर्षों को बाद में हॉल के विवाह प्रमेय का उपयोग करके बफर शीर्षों और के शेष शीर्षों के बीच एक सही मिलान खोजने के लिए एम्बेड किया जाता है। संकेतन हम पिछले खंडों में पेश किए गए सभी संकेतन उधार लेते हैं। जाने दीजिए। चूँकि इसे शामिल किया जा सकता है, हम सभी के लिए लिख सकते हैं। एक शीर्ष के लिए, दर्शाते हैं। के लिए, के संबंधित शीर्ष सेटों के बीच किनारों के घनत्व को दर्शाता है। यह एम्बेडिंग है जिसका हम निर्माण करना चाहते हैं। यह अंतिम समय है जिसके बाद एल्गोरिथ्म समाप्त होता है। एल्गोरिथम चरण 0 की रूपरेखाः आरंभीकरण लालच से शीर्षों के अधिकतम सेट के रूप में शीर्षों के सेट का चयन करें कम से कम एक दूसरे से दूरी एक सूची में शेष शीर्षों (उन में) को क्रम दें, पहले के पड़ोसियों को रखें। वर्तमान में प्राथमिकता वाले शीर्षों की एक कतार घोषित करें, जो शुरू में खाली है। के शीर्षों द्वारा अनुक्रमित सेटों की एक सरणी घोषित करें, जो सभी "मुक्त धब्बों" के सेट का प्रतिनिधित्व करते हैं, यानी, शीर्ष में खाली शीर्षों के सेट को पहले से ही एम्बेडेड पड़ोसियों से किसी भी निकटता शर्तों का उल्लंघन किए बिना मैप किया जा सकता है। आरंभ किया जाता है। चरण 1: यादृच्छिक लालची एम्बेडिंग शेष शीर्षों के सेट से एक शीर्ष निम्नानुसार चुनेंः यदि प्राथमिकता वाले शीर्षों की कतार खाली नहीं है, तो शीर्ष से शीर्ष चुनें अन्यथा, शेष शीर्षों की सूची से एक शीर्ष चुनें "अच्छे" विकल्पों के सेट से यादृच्छिक रूप से शीर्ष के लिए छवि चुनें, जहां एक विकल्प अच्छा है यदि कोई भी नया फ्री-सेट अपेक्षित मूल्य से आकार में बहुत अधिक भिन्न नहीं है। मुक्त सेटों को अद्यतन करें, और ऐसे शीर्ष रखें जिनके मुक्त सेट प्राथमिकता वाले शीर्षों के सेट में अंतिम अद्यतन में अपने आकार के संबंध में बहुत छोटे हो गए हैं यदि कतार में किसी भी सेट का पर्याप्त बड़ा अंश है यदि गैर-बफर शीर्ष दोनों में से किसी एक में एम्बेड करने के लिए बचे हैं या, समय को अद्यतन करें और चरण 1 पर वापस जाएं; अन्यथा चरण 2 पर आगे बढ़ें। चरण 2: शेष शीर्षों के लिए कनिग-हॉल मिलान एम्बेडेड होने के लिए छोड़े गए शीर्षों के सेट पर विचार करें, जो सटीक रूप से है, और मुक्त धब्बों का सेट। इन दोनों सेटों के बीच एक द्विदलीय ग्राफ बनाएँ, प्रत्येक को जोड़ते हुए, और इस द्विदलीय ग्राफ में एक सही मिलान खोजें। इस मिलान के अनुसार एम्बेड करें। शुद्धता का प्रमाण शुद्धता का प्रमाण तकनीकी और काफी शामिल है, इसलिए हम विवरण को छोड़ देते हैं। मुख्य तर्क इस प्रकार आगे बढ़ता हैः चरण 1: अधिकांश शीर्ष अच्छे हैं, और पर्याप्त शीर्ष मुक्त हैं, एक साथ उस पर शामिल करके साबित करें कि यदि समय पर शीर्ष अंतर्निहित है, तो विकल्पों का केवल एक छोटा सा अंश खराब है, सभी मुक्त सेट बिना एम्बेडेड शीर्षों के लिए काफी बड़े हैं चरण 2: "मुख्य लेम्मा" पर विचार करें, और ऐसा जो बहुत छोटा नहीं है। उस घटना पर विचार करें जहां पहले चरण के दौरान कोई शीर्ष अंतर्निहित नहीं हैं, प्रत्येक के लिए एक समय ऐसा होता है कि उस समय के मुक्त शीर्षों का अंश छोटा था। फिर, हम साबित करते हैं कि ऐसा होने की संभावना कम है। चरण 3: चरण 1 उच्च संभावना के साथ सफल होता है पहला चरण विफल होने का एकमात्र तरीका यह है कि अगर यह निरस्त हो जाता है, क्योंकि पहले चरण से हम जानते हैं कि हमेशा अच्छे शीर्षों का पर्याप्त विकल्प होता है। कार्यक्रम तभी बंद होता है जब कतार बहुत लंबी होती है। तर्क तब विफलता के सभी तरीकों पर संघ-सीमा द्वारा आगे बढ़ता है, यह देखते हुए कि किसी भी विशेष विकल्प के लिए, और विफल होने वाली कतार के सबसेट का प्रतिनिधित्व करने के साथ, ट्रिपल "मुख्य लेम्मा" की शर्तों को पूरा करता है, और इस प्रकार होने की संभावना कम होती है। चरण 4: प्रारंभिक चरण में कोई कतार नहीं याद रखें कि सूची सेट की गई थी ताकि बफर में शीर्षों के पड़ोसी पहले एम्बेड हो जाएं। इन सभी शीर्षों के जुड़ने तक के समय को प्रारंभिक चरण कहा जाता है। प्रेरण द्वारा साबित करें कि प्रारंभिक चरण के दौरान कतार में कोई शीर्ष नहीं जोड़ा जाता है। यह इस प्रकार है कि बफर शीर्षों के सभी पड़ोसी शेष शीर्षों से पहले जुड़ जाते हैं। चरण 5: बफर शीर्षों में पर्याप्त मुक्त धब्बे होते हैं किसी भी के लिए और, हम इस संभावना पर पर्याप्त रूप से बड़ी निचली सीमा पा सकते हैं कि, इस धारणा पर सशर्त कि किसी भी शीर्ष से पहले मुक्त था। चरण 6: चरण 2 उच्च संभावना के साथ सफल होता है हॉल के विवाह प्रमेय के अनुसार, चरण 2 विफल हो जाता है अगर और केवल तभी जब हॉल की स्थिति का उल्लंघन किया जाता है। ऐसा होने के लिए, कुछ और ऐसा होना चाहिए। मुक्त सेटों की विशालता से बहुत छोटा नहीं हो सकता है (चरण 1)। यदि बहुत बड़ा है, तो उच्च संभावना के साथ, इसलिए ऐसे मामले में विफलता की संभावना कम होगी। यदि न तो बहुत छोटा है और न ही बहुत बड़ा है, तो यह ध्यान में रखते हुए कि अप्रयुक्त शीर्षों का एक बड़ा समूह है, हम मुख्य लेम्मा और यूनियन-बाउंड विफलता संभावना का उपयोग कर सकते हैं। अनुप्रयोग ब्लो-अप लेम्मा के घने ग्राफ को एम्बेड करने में कई अनुप्रयोग हैं। पोसा-सीमोर अनुमान 1962 में, लाजोस पोसा ने अनुमान लगाया कि न्यूनतम डिग्री वाले प्रत्येक-वर्टेक्स ग्राफ में कम से कम हैमिल्टनियन चक्र का वर्ग होता है, जो डीराक के प्रमेय को सामान्य करता है। 1974 में पॉल सीमोर द्वारा इस अनुमान को आगे निम्नलिखित तक बढ़ाया गया थाः न्यूनतम डिग्री वाले शीर्षों पर प्रत्येक ग्राफ में कम से कम हैमिल्टनियन चक्र की-th शक्ति होती है। 1998 में (एक निश्चित के लिए) सभी पर्याप्त रूप से बड़े मूल्यों के लिए अनुमान को साबित करने के लिए कोम्लोस, सार्कोजी और स्ज़ेमेरेडी द्वारा ब्लो-अप लेम्मा का उपयोग किया गया था। 1995 में, नोगा एलोन और राफेल यूस्टर ने प्रसिद्ध हाजनाल-ज़ेमेरेदी प्रमेय के सामान्यीकरण को मनमाने-कारकों (केवल पूर्ण ग्राफ के बजाय) पर विचार किया, और निम्नलिखित कथन को साबित कियाः शीर्षों के साथ प्रत्येक निश्चित ग्राफ के लिए, n शीर्षों के साथ और न्यूनतम डिग्री के साथ किसी भी ग्राफ G में H की शीर्ष विच्छेदित प्रतियां होती हैं। उन्होंने यह भी अनुमान लगाया कि परिणाम केवल एक स्थिरांक (रैखिक के बजाय) त्रुटि के साथ होता हैः प्रत्येक पूर्णांक के लिए एक स्थिरांक मौजूद होता है कि शीर्षों के साथ प्रत्येक ग्राफ के लिए, शीर्षों के साथ और न्यूनतम डिग्री के साथ किसी भी ग्राफ में कम से कम शीर्ष विच्छेदित प्रतियां होती हैं। यह अनुमान 2001 में कोम्लोस, सार्कोजी और स्ज़ेमेरेडी द्वारा ब्लो-अप लेम्मा का उपयोग करके साबित किया गया था। इतिहास और प्रकार पहली बार 1997 में कोम्लोस, सार्कोजी और स्ज़ेमेरेडी द्वारा प्रकाशित ब्लो-अप लेम्मा, फैले हुए ग्राफ को एम्बेड करने के लिए नियमितता विधि का उपयोग करके मौजूदा प्रमाण तकनीकों के परिशोधन के रूप में उभरा, जैसा कि फैले हुए पेड़ों पर बोलोबस अनुमान के प्रमाण में, हैमिल्टनियन चक्र की के-th ग्राफ शक्ति को नियंत्रित करने के लिए आवश्यक न्यूनतम डिग्री के बारे में पोसा-सीमोर अनुमान पर काम करते हैं, और एक ग्राफ के लिए आवश्यक न्यूनतम डिग्री पर एलोन-यूस्टर अनुमान का प्रमाण एक परिपूर्ण एच-कारक है। इन सभी प्रमेयों के प्रमाण अधिकांश शीर्षों को एम्बेड करने के लिए एक यादृच्छिक लालची एल्गोरिथ्म का उपयोग करने पर निर्भर थे, और फिर शेष शीर्षों के लिए एक एम्बेडिंग खोजने के लिए कनिग-हॉल जैसे तर्क का उपयोग करते थे। ब्लो-अप लेम्मा के पहले प्रमाण में भी इसी तरह के तर्क का इस्तेमाल किया गया था। हालाँकि, बाद में 1997 में, उन्हीं लेखकों ने एक और पेपर प्रकाशित किया जिसमें यादृच्छिक एल्गोरिदम को निर्धारक बनाने के लिए सुधार पाया गया। पीटर कीवाश ने 2010 में हाइपरग्राफ के लिए ब्लो-अप लेम्मा का सामान्यीकरण पाया। स्टीफन ग्लॉक और फेलिक्स जूस ने 2018 में इंद्रधनुष ग्राफ के लिए ब्लो-अप लेम्मा के एक प्रकार की खोज की। 2019 में, पीटर एलन, जूलिया बोचर, हीप हेन, योशीहारू कोहायाकावा और यूरी पर्सन ने ग्राफ सिद्धांत में बाउंडेड डिग्री ग्राफ को यादृच्छिक और छद्म ग्राफ में एम्बेड करने के लिए ब्लो-अप लेम्मा के विरल अनुरूप पाए।