Hypergraph regularity method
गणित में, हाइपरग्राफ नियमितता विधि चरम ग्राफ सिद्धांत में एक शक्तिशाली उपकरण है जो हाइपरग्राफ नियमितता लेम्मा और संबंधित गणना लेम्मा के संयुक्त अनुप्रयोग को संदर्भित करता है। यह ग्राफ नियमितता विधि का एक सामान्यीकरण है, जो स्ज़ेमेरेडी की नियमितता और गणना लेम्मा के उपयोग को संदर्भित करता है। बहुत अनौपचारिक रूप से, हाइपरग्राफ नियमितता लेम्मा किसी भी दिए गए-समान हाइपरग्राफ को बंधी हुई भागों (एक उपयुक्त सीमा और यादृच्छिक धारणाओं के साथ) के साथ एक यादृच्छिक जैसी वस्तु में विघटित कर देता है जिसके साथ काम करना आमतौर पर आसान होता है। दूसरी ओर, हाइपरग्राफ काउंटिंग लेम्मा यादृच्छिक जैसे भागों के कुछ संग्रहों में दिए गए समरूपता वर्ग के हाइपरग्राफ की संख्या का अनुमान लगाता है। यह स्ज़ेमेरेडी के नियमितता सिद्धांत का एक विस्तार है जो किसी भी दिए गए ग्राफ को सीमित संख्या भागों में विभाजित करता है जैसे कि भागों के बीच के किनारे लगभग यादृच्छिक रूप से व्यवहार करते हैं। इसी तरह, हाइपरग्राफ काउंटिंग लेम्मा ग्राफ काउंटिंग लेम्मा का एक सामान्यीकरण है जो एक बड़े ग्राफ के उपग्राफ के रूप में एक निश्चित ग्राफ की प्रतियों की संख्या का अनुमान लगाता है। विधि के कई अलग-अलग सूत्रीकरण हैं, जिनमें से सभी हाइपरग्राफ हटाने वाले लेम्मा और कई अन्य शक्तिशाली परिणामों का संकेत देते हैं, जैसे कि स्ज़ेमेरेडी की प्रमेय, साथ ही साथ इसके कुछ बहुआयामी विस्तार। निम्नलिखित सूत्रीकरण वी. रोड्ल, बी. नागले, जे. स्कोकन, एम. स्काच्ट और वाई. कोहायाकावा के कारण हैं, वैकल्पिक संस्करणों के लिए ताओ (2006), और गोवर्स (2007) देखें। परिभाषाएं हाइपरग्राफ की नियमितता और गणना को औपचारिक रूप से बताने के लिए, हमें छद्म-यादृच्छिकता (यादृच्छिक-समानता) और सीमा की उपयुक्त धारणाओं को औपचारिक रूप देने के साथ-साथ यादृच्छिक जैसे खंडों और विभाजनों का वर्णन करने के लिए कई तकनीकी शब्दों को परिभाषित करने की आवश्यकता है। संकेतन शीर्षों पर एक समान गुट को दर्शाता है। शीर्ष विभाजन पर एक-पार्टाइट-ग्राफ है। सभी-तत्व शीर्ष समुच्चयों का परिवार है जो गुट में फैला हुआ है। विशेष रूप से, एक पूर्ण-पार्टाइट-ग्राफ है। निम्नलिखित सापेक्ष घनत्व की एक महत्वपूर्ण धारणा को परिभाषित करता है, जो मोटे तौर पर हाइपरग्राफ में-किनारों द्वारा फैले-किनारों के अंश का वर्णन करता है। उदाहरण के लिए, जब मात्रा सबहाइपरग्राफ में 2-धार वाले त्रिभुजों के अंश के बराबर होती है जो 3-धार वाले होते हैं। परिभाषा [सापेक्ष घनत्व]। के लिए, कुछ वर्गों को ठीक करें। मान लीजिए कि यह एक पूर्णांक है। माना कि यह प्रेरित-पार्टाइट ग्राफ का एक सबहाइपरग्राफ है। सापेक्ष घनत्व को परिभाषित करें। निम्नलिखित सूडोरैंडमनेस की उचित धारणा है जो नियमितता विधि का उपयोग करेगी। अनौपचारिक रूप से, नियमितता की इस अवधारणा से,-एज () का-एज () पर कुछ नियंत्रण होता है। अधिक सटीक रूप से, यह एक ऐसी सेटिंग को परिभाषित करता है जहां बड़े सबहाइपरग्राफ में किनारों का घनत्व लगभग उतना ही होता है जितना कि केवल सापेक्ष घनत्व के आधार पर कोई उम्मीद करता है। औपचारिक रूप से, परिभाषा [()-नियमितता]। मान लीजिए कि ये धनात्मक वास्तविक संख्याएँ हैं और एक पूर्णांक है। ()-इस संबंध में नियमित है कि क्या वर्गों के किसी भी विकल्प और संतोषजनक सबहाइपरग्राफ के किसी भी संग्रह के लिए हमारे पास है। मोटे तौर पर, निम्नलिखित सूडोरैंडम ब्लॉकों का वर्णन करता है जिसमें हाइपरग्राफ नियमितता लेम्मा किसी भी बड़े पर्याप्त हाइपरग्राफ को विघटित करता है। स्ज़ेमेरेडी नियमितता में, 2-किनारे बनाम 1-किनारे (शीर्ष) को नियमित किया जाता है। इस सामान्यीकृत धारणा में, सभी के लिए-किनारे बनाम-किनारे नियमित किए जाते हैं। अधिक सटीक रूप से, यह नियमित हाइपरग्राफ की एक धारणा को परिभाषित करता है जिसे-कॉम्प्लेक्स कहा जाता है, जिसमें-एज का अस्तित्व सभी अंतर्निहित-किनारों के अस्तित्व के साथ-साथ उनकी सापेक्ष नियमितता को भी दर्शाता है। उदाहरण के लिए, यदि एक 3-किनारे है तो, और परिसर में 2-किनारे हैं। इसके अलावा, 2-किनारों द्वारा बनाए गए सभी संभावित त्रिकोणों पर 3-किनारों का घनत्व subhypergraphs.Definition [-नियमित-जटिल] के प्रत्येक संग्रह में लगभग समान है। एक-कॉम्प्लेक्स एक-पार्टाइट ग्राफ की प्रणाली है जो संतोषजनक है। सकारात्मक वास्तविक संख्याओं के सदिशों और एक पूर्णांक को देखते हुए, हम कहते हैं-जटिल-नियमित है यदि प्रत्येक के लिए, घनत्व के साथ-नियमित है। प्रत्येक के लिए, है ()-के संबंध में नियमित। निम्नलिखित न्यायसंगत विभाजन का वर्णन करता है जिसे हाइपरग्राफ नियमितता लेम्मा प्रेरित करेगा। विभाजन का एक-समतुल्य परिवार 1-किनारे (शीर्ष), 2-किनारे (जोड़े), 3-किनारे (ट्रिपल), आदि के विभाजन का एक क्रम है। यह स्ज़ेमेरेडी की नियमितता लेम्मा द्वारा प्राप्त विभाजन से एक महत्वपूर्ण अंतर है, जहां केवल शीर्षों को विभाजित किया जा रहा है। वास्तव में, गोवर्स ने प्रदर्शित किया कि केवल शीर्ष विभाजन हाइपरग्राफ काउंटिंग लेम्मा को इंगित करने के लिए नियमितता की पर्याप्त मजबूत धारणा नहीं दे सकता है। परिभाषा [-समान विभाजन]। मान लीजिए कि यह एक वास्तविक संख्या है, एक पूर्णांक है, और सकारात्मक वास्तविकताओं के वाहक हैं। मान लीजिए कि यह धनात्मक पूर्णांकों का एक सदिश है और एक-तत्व शीर्ष समुच्चय है। हम कहते हैं कि विभाजन का एक परिवार-समतुल्य है यदि यह निम्नलिखित को संतुष्ट करता हैः का समतुल्य शीर्ष विभाजन है। वह है। विभाजन ताकि यदि और फिर अधिकांश भागों में विभाजित किया जाता है, जो सभी सदस्य हैं। सभी के लिए लेकिन अधिक से अधिक-टुपल्स में अद्वितीय-नियमित-कॉम्प्लेक्स होता है जैसे कि सदस्यों के रूप में अलग-अलग विभाजन वर्ग होते हैं। अंत में, निम्नलिखित परिभाषित करता है कि विभाजन के संबंध में एक-समान हाइपरग्राफ के नियमित होने का क्या अर्थ है। विशेष रूप से, यह मुख्य परिभाषा है जो हाइपरग्राफ नियमितता लेम्मा bellow.Definition [विभाजन के संबंध में नियमितता] के उत्पादन का वर्णन करती है। हम कहते हैं कि विभाजनों के एक परिवार के संबंध में एक-ग्राफ नियमित है, यदि सभी के अधिकांश किनारों पर वह गुण है जो और यदि अद्वितीय है-जटिल जिसके लिए, तो इसके संबंध में नियमित है। कथन हाइपरग्राफ रेगुलेरिटी लेम्मा सभी सकारात्मक वास्तविक, और कार्यों के लिए, क्योंकि वहाँ मौजूद है और इसलिए निम्नलिखित धारण करता है। शीर्षों पर किसी भी समान हाइपरग्राफ के लिए, विभाजनों का एक परिवार और एक वेक्टर मौजूद है ताकि, सभी के लिए और जहां के लिए, निम्नलिखित धारण करता है। विभाजनों का एक समान परिवार है और प्रत्येक के लिए। के संबंध में नियमित है। हाइपरग्राफ काउंटिंग लेम्मा सभी पूर्णांकों के लिए निम्नलिखित धारण करता हैः और पूर्णांक हैं और इसलिए, के साथ, और, यदि शीर्ष विभाजन के साथ एक-नियमित कॉम्प्लेक्स है और, तो। अनुप्रयोग मुख्य अनुप्रयोग जिसके माध्यम से अधिकांश अन्य लोग पालन करते हैं, हाइपरग्राफ हटाने का सिद्धांत है, जो मोटे तौर पर बताता है कि दिए गए निश्चित और बड़े-समान हाइपरग्राफ, यदि कुछ प्रतियां हैं, तो सभी प्रतियों को समाप्त करने के लिए कुछ हाइपरएज को हटाया जा सकता है। इसे अधिक औपचारिक रूप से कहने के लिए, हाइपरग्राफ रिमूवल लेम्मा सभी के लिए मौजूद है और इसलिए निम्नलिखित लागू होता है। मान लीजिए कि यह शीर्षों पर एक समान हाइपरग्राफ है और शीर्षों पर है। यदि अधिकांश प्रतियां शामिल हैं, तो इसे मुक्त बनाने के लिए हाइपरएज हटा सकते हैं। ग्राफ नियमितता विधि के लिए मूल प्रेरणाओं में से एक स्ज़ेमेरेडी के प्रमेय को साबित करना था, जिसमें कहा गया है कि प्रत्येक घने उपसमुच्चय में मनमाना लंबाई की एक अंकगणितीय प्रगति होती है। वास्तव में, त्रिभुज हटाने वाले प्रमेय के अपेक्षाकृत सरल अनुप्रयोग से, यह साबित किया जा सकता है कि त्रिभुज के प्रत्येक घने उपसमुच्चय में लंबाई 3 की अंकगणितीय प्रगति होती है। हाइपरग्राफ नियमितता विधि और हाइपरग्राफ हटाने का लेम्मा स्ज़ेमेरेडी के प्रमेयों के घनत्व संस्करण के उच्च-आयामी और वलय अनुरूपों को साबित कर सकता है, जो मूल रूप से फ़र्स्टनबर्ग और काट्ज़नेल्सन द्वारा साबित किए गए थे। वास्तव में, यह दृष्टिकोण प्रमेयों के लिए पहली मात्रात्मक सीमा प्रदान करता है। इस प्रमेय का मोटे तौर पर तात्पर्य है कि के किसी भी घने उपसमुच्चय में का कोई भी परिमित पैटर्न होता है। मामला जब और पैटर्न कुछ लंबाई की अंकगणितीय प्रगति है जो स्ज़ेमेरेडी के प्रमेय के बराबर है। फुरस्टनबर्ग और काट्ज़नेल्सन प्रमेय को एक परिमित उपसमुच्चय माना जाता है और दिया जाता है। फिर एक परिमित उपसमुच्चय मौजूद होता है जैसे कि प्रत्येक के साथ एक समरूपी प्रति होती है। (अर्थात। रूप का समुच्चय, कुछ के लिए और) इसके अलावा, यदि कुछ के लिए, तो ऐसा मौजूद है जिसमें सभी के लिए यह गुण है। एक अन्य संभावित सामान्यीकरण जिसे हटाने वाले लेम्मा द्वारा साबित किया जा सकता है जब आयाम को बढ़ने दिया जाता है। तेनगन, टोकुशिगे, रोड्ल और स्काच प्रमेय को एक परिमित वलय माना जाता है। प्रत्येक के लिए, ऐसा मौजूद है कि, किसी भी उपसमुच्चय के साथ एक समरूप प्रतिलिपि का एक कोसेट होता है (एक बाएं-मॉड्यूल के रूप में)। दूसरे शब्दों में, कुछ ऐसे हैं जो, जहाँ, एक इंजेक्शन है। संदर्भ ग्राफ सिद्धांत