Ramsey-Turán theory
रामसे-तुरान सिद्धांत चरम ग्राफ सिद्धांत का एक उपक्षेत्र है। यह रामसे के प्रमेय और तुरान के प्रमेय के सामान्य सामान्यीकरण का अध्ययन करता है। संक्षेप में, रामसे-तुरान सिद्धांत एक ग्राफ के किनारों की अधिकतम संख्या के लिए पूछता है जो इसके उपग्राफ और संरचना पर बाधाओं को संतुष्ट करता है। यह सिद्धांत कई प्राकृतिक प्रश्नों को व्यवस्थित करता है जो चरम ग्राफ सिद्धांत में उत्पन्न होते हैं। इस सिद्धांत के केंद्रीय विचारों को औपचारिक रूप देने वाले पहले लेखक 1969 में एर्डोस और सोस थे, हालांकि गणितविदों ने पहले कई रैमसे-तुरान-प्रकार की समस्याओं की जांच की थी। दो रंगों के लिए रैमसे की प्रमेय और तुरान की प्रमेय और पूर्ण ग्राफ के लिए रैमसे की प्रमेय, जो 1930 में अपने मूल रूप में साबित हुई, बताती है कि किसी भी सकारात्मक पूर्णांक के लिए इतना बड़ा एक पूर्णांक मौजूद है कि दो रंगों का उपयोग करके पूर्ण ग्राफ के किनारों के किसी भी रंग के लिए इसकी एक एकवर्णी प्रति होती है। अधिक आम तौर पर, किसी भी ग्राफ के लिए, एक सीमा ऐसी होती है कि यदि और इसके किनारों को मनमाने ढंग से रंगों से रंगा जाता है, तो कुछ के लिए th रंग में a होता है। तुरान की प्रमेय, जो 1941 में सिद्ध हुई, शीर्षों पर किनारों की अधिकतम संख्या के साथ ग्राफ की विशेषता है जिसमें a नहीं है। विशेष रूप से, प्रमेय में कहा गया है कि सभी सकारात्मक पूर्णांकों के लिए, एक-वर्टेक्स ग्राफ के किनारों की संख्या जिसमें एक उपग्राफ के रूप में शामिल नहीं है, अधिक से अधिक है और अधिकतम तुरान ग्राफ द्वारा विशिष्ट रूप से प्राप्त किया जाता है। ये दोनों उत्कृष्ट परिणाम इस बारे में सवाल पूछते हैं कि एक निश्चित गुण होने से पहले एक ग्राफ कितना बड़ा हो सकता है। हालाँकि, एक उल्लेखनीय शैलीगत अंतर है। तुरान के प्रमेय में चरम ग्राफ की एक बहुत ही सख्त संरचना है, जिसमें एक छोटी रंगीन संख्या है और इसमें बड़ी संख्या में बड़े स्वतंत्र सेट हैं। दूसरी ओर, रैमसे समस्याओं में माना जाने वाला ग्राफ पूर्ण ग्राफ है, जिसमें बड़ी रंगीन संख्या होती है और कोई गैर-तुच्छ स्वतंत्र सेट नहीं होता है। इन दो प्रकार की समस्याओं को संयोजित करने का एक स्वाभाविक तरीका एंड्रसफाई द्वारा प्रस्तुत निम्नलिखित प्रश्न पूछना हैः समस्या 1: दिए गए सकारात्मक पूर्णांक के लिए, एक-वर्टेक्स ग्राफ होना चाहिए जिसमें स्वतंत्र संख्या न हो। इस तरह के ग्राफ में किनारों की अधिकतम संख्या क्या हो सकती है? अनिवार्य रूप से, यह प्रश्न रामसे सेटिंग में तुरान समस्या का उत्तर पूछता है; यह तुरान की समस्या को कम व्यवस्थित, अधिक यादृच्छिक संरचना वाले ग्राफ के सबसेट तक सीमित करता है। निम्नलिखित प्रश्न समस्याओं को विपरीत दिशा में जोड़ता हैः समस्या 2: मान लीजिए कि ग्राफ निश्चित हैं। शीर्षों पर एक किनारे वाले रंगीन ग्राफ के किनारों की अधिकतम संख्या इस शर्त पर क्या हो सकती है कि इसमें th रंग में an न हो? सामान्य समस्या रैमसे-तुरान सिद्धांत की रीढ़ उपरोक्त समस्याओं का सामान्यीकरण है। समस्या 3: मान लीजिए कि ग्राफ स्थिर हैं। मान लीजिए कि एक-किनारे-रंग का-वर्टेक्स ग्राफ संतोषजनक है (1) (2) th रंग द्वारा परिभाषित उपग्राफ में नहीं है। किनारों की अधिकतम संख्या क्या हो सकती है? हम अधिकतम को दर्शाते हैं। रामसे-तुरान-प्रकार की समस्याएं समस्या 3 के विशेष मामले हैं। इस समस्या के कई मामले खुले रहते हैं, लेकिन कई दिलचस्प मामलों को सटीक एसिम्प्टोटिक समाधानों के साथ हल किया गया है। उल्लेखनीय परिणाम समस्या 3 को स्वतंत्रता संख्या पर प्रतिबंध के आधार पर तीन अलग-अलग मामलों में विभाजित किया जा सकता है। प्रतिबंध-मुक्त मामला है, जहाँ, जो क्लासिक रैमसे समस्या तक कम हो जाता है। वहाँ "मध्यवर्ती" मामला है, जहाँ एक निश्चित के लिए। अंत में, एक मामला है, जिसमें सबसे बड़ी समस्याएं हैं। सीमा में सबसे बुनियादी गैर-तुच्छ समस्या यह है कि जब और एर्दोस और सोस ने 1969 में इस स्थिति में रामसे-तुरान संख्या के स्पर्शोन्मुख मूल्य का निर्धारण कियाः शीर्षों की एक सम संख्या पर पूर्ण ग्राफ का मामला बहुत अधिक चुनौतीपूर्ण है, और 1983 में एर्दोस, हाजनल, सोस और स्ज़ेमेरेडी द्वारा हल किया गया थाः ध्यान दें कि दोनों मामलों में, समस्या को तुरान के प्रमेय में अतिरिक्त शर्त जोड़ने के रूप में देखा जा सकता है। दोनों ही मामलों में, यह देखा जा सकता है कि स्पर्शोन्मुख रूप से, प्रभाव वैसा ही है जैसे कि हमने या के बजाय बाहर कर दिया था। संदर्भ ग्राफ सिद्धांत