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

तुरान ग्राफ टी(एन,आर) एक चरम ग्राफ का एक उदाहरण है। इसमें (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: Graph coloring

पीटरसन ग्राफ में वर्णिक संख्या 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: Forbidden subgraph problem

निषिद्ध सबग्राफ समस्या चरम ग्राफ सिद्धांत में केंद्रीय समस्याओं में से एक है। एक ग्राफ दिया गया $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: Homomorphism density

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

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

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

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

Main article: Szemerédi regularity lemma

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

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

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

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

यह भी देखें

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

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

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

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

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

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