एक्सट्रीमल ग्राफ सिद्धांत

तुरान ग्राफ टी(एन,आर) चरम ग्राफ का उदाहरण है। इसमें (r + 1)-क्लिक (ग्राफ़ सिद्धांत) के बिना n शीर्षों पर ग्राफ़ के लिए किनारों की अधिकतम संभव संख्या है। यह टी(13,4) है।

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

एक्सट्रीमल ग्राफ सिद्धांत रैमसे सिद्धांत, वर्णक्रमीय ग्राफ सिद्धांत, कम्प्यूटेशनल समिष्ट सिद्धांत और एडिटिव कॉम्बिनेटरिक्स जैसे क्षेत्रों से निकटता से संबंधित है, और प्रायः संभाव्य पद्धति को नियोजित करता है।

इतिहास

Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians.

Bollobás (2004)

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

विषय और अवधारणाएँ

ग्राफ़ रंग

Main article: ग्राफ़ रंग

पीटरसन ग्राफ में वर्णिक संख्या 3 है।

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

ग्राफ़ की रंगीन संख्या की दो सरल निचली सीमाएँ $G$ क्लिक संख्या द्वारा दिया गया है $\omega (G)$-समूह के सभी शीर्षों में अलग-अलग रंग होने चाहिए-और इसके द्वारा $|V(G)|/\alpha (G)$, कहाँ $\alpha (G)$ स्वतंत्रता संख्या है, क्योंकि किसी दिए गए रंग के साथ शीर्षों के सेट को स्वतंत्र सेट (ग्राफ़ सिद्धांत) बनाना होगा।

लालची रंग ऊपरी सीमा देता है $\chi (G)\leq \Delta (G)+1$, कहाँ $\Delta (G)$ की अधिकतम डिग्री है $G$. कब $G$ यह कोई अजीब चक्र या गुट नहीं है, ब्रूक्स प्रमेय कहता है कि ऊपरी सीमा को कम किया जा सकता है $\Delta (G)$. कब $G$ समतलीय ग्राफ़ है, चार-रंग प्रमेय यह बताता है $G$ इसकी वर्णिक संख्या अधिकतम चार है।

सामान्य तौर पर, यह निर्धारित करना कि किसी दिए गए ग्राफ़ में रंगों की निर्धारित संख्या के साथ रंग है या नहीं, एनपी कठिन के रूप में जाना जाता है।

शीर्ष रंग के अतिरिक्त , अन्य प्रकार के रंग का भी अध्ययन किया जाता है, जैसे किनारे का रंग। रंगीन सूचकांक $\chi '(G)$ ग्राफ का $G$ ग्राफ़ के उचित किनारे-रंग में रंगों की न्यूनतम संख्या है, और विज़िंग के प्रमेय में कहा गया है कि ग्राफ़ का रंगीन सूचकांक $G$ भी है $\Delta (G)$ या $\Delta (G)+1$.

निषिद्ध उपग्राफ

Main article: निषिद्ध उपग्राफ समस्या

निषिद्ध सबग्राफ समस्या चरम ग्राफ सिद्धांत में केंद्रीय समस्याओं में से है। ग्राफ दिया गया $G$, निषिद्ध सबग्राफ समस्या किनारों की अधिकतम संख्या मांगती है $\operatorname {ex} (n,G)$ में $n$-वर्टेक्स ग्राफ़ जिसमें सबग्राफ आइसोमोर्फिक सम्मिलित नहीं है $G$.

कब $G=K_{r}$ संपूर्ण ग्राफ़ है, तुरान का प्रमेय इसका सटीक मान देता है $\operatorname {ex} (n,K_{r})$ और इस अधिकतम को प्राप्त करने वाले सभी ग्राफ़ को चित्रित करता है; ऐसे ग्राफ़ को तुरान ग्राफ़|तुरान ग्राफ़ के रूप में जाना जाता है। गैर-द्विपक्षीय ग्राफ़ के लिए $G$, एर्दो-स्टोन प्रमेय स्पर्शोन्मुख मूल्य देता है $\operatorname {ex} (n,G)$ की वर्णिक संख्या के संदर्भ में $G$. के स्पर्शोन्मुखता का निर्धारण करने की समस्या $\operatorname {ex} (n,G)$ कब $G$ द्विदलीय ग्राफ खुला है; कब $G$ यह पूर्ण द्विदलीय ग्राफ है, इसे ज़ारांकिविज़ समस्या के रूप में जाना जाता है।

समरूपता घनत्व

Main article: समरूपता घनत्व

समरूपता घनत्व $t(H,G)$ ग्राफ का $H$ ग्राफ में $G$ इस संभावना का वर्णन करता है कि शीर्ष सेट से यादृच्छिक रूप से चुना गया नक्शा $H$ के शीर्ष सेट के लिए $G$ यह ग्राफ समरूपता भी है। यह सबग्राफ़ घनत्व से निकटता से संबंधित है, जो बताता है कि ग्राफ़ कितनी बार होता है $H$ के उपसमूह के रूप में पाया जाता है $G$.

निषिद्ध सबग्राफ़ समस्या को ग्राफ़ के किनारे घनत्व को अधिकतम करने के रूप में पुनर्स्थापित किया जा सकता है $G$-घनत्व शून्य, और यह स्वाभाविक रूप से ग्राफ समरूपता असमानताओं के रूप में सामान्यीकरण की ओर ले जाता है, जो संबंधित असमानताएं हैं $t(H,G)$ विभिन्न ग्राफ़ के लिए $H$. समरूपता घनत्व को ग्राफॉन तक विस्तारित करके, जो कि घने ग्राफ की सीमा के रूप में उत्पन्न होने वाली वस्तुएं हैं, ग्राफ समरूपता घनत्व को अभिन्न के रूप में लिखा जा सकता है, और कॉची-श्वार्ज़ असमानता और होल्डर की असमानता जैसी असमानताओं को प्राप्त करने के लिए उपयोग किया जा सकता है समरूपता असमानताएँ।

समरूपता घनत्व से संबंधित प्रमुख खुली समस्या सिडोरेंको का अनुमान है, जो ग्राफ में द्विदलीय ग्राफ के समरूपता घनत्व पर सख्त निचली सीमा बताता है। $G$ के किनारे घनत्व के संदर्भ में $G$.

ग्राफ़ नियमितता

Main article: ज़ेमेरेडी नियमितता लेम्मा

नियमित विभाजन में हिस्सों के मध्य के किनारे बेतरतीब ढंग से व्यवहार करते हैं।

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

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

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

यह भी देखें

संबंधित क्षेत्रों

• रैमसे सिद्धांत
• रैमसे-तुरान सिद्धांत
• वर्णक्रमीय ग्राफ सिद्धांत
• एडिटिव कॉम्बिनेटरिक्स
• कम्प्यूटेशनल जटिलता सिद्धांत
• संभाव्य कॉम्बिनेटरिक्स

तकनीक और तरीके

• संभाव्य विधि
• आश्रित यादृच्छिक विकल्प
• कंटेनर विधि
• हाइपरग्राफ नियमितता विधि

प्रमेय और अनुमान (ऊपर उल्लिखित प्रमेय के अतिरिक्त )

• अयस्क प्रमेय
• रुज़सा-ज़ेमेरेडी समस्या