रैमसे का प्रमेय और रैमसे संख्याएँ
रैमसे का प्रमेय यह गारंटी देता है कि कोई भी पर्याप्त रूप से बड़ा दो-रंगों वाला पूर्ण ग्राफ एक एकरंगा गुट (क्लिक) को समाहित करता है, और रैमसे संख्याएँ यह निर्धारित करती हैं कि कितना बड़ा पर्याप्त है।
Definition
रैमसे संख्या R(s,t) सबसे छोटी पूर्णांक n है जैसे कि n शीर्षों पर पूर्ण ग्राफ के किनारों का प्रत्येक लाल-नीला रंग s शीर्षों पर एक लाल गुट या t शीर्षों पर एक नीला गुट समाहित करता है।
Scope
यह विषय रैमसे के प्रमेय के ग्राफ रूप, रैमसे संख्याओं R(s,t) की परिभाषा, R(3,3)=6 जैसे शास्त्रीय छोटे मामले, एर्डोस-सेकेरेस ऊपरी सीमा और एर्डोस की संभाव्य निचली सीमा, और बहुरंगी तथा हाइपरग्राफ रैमसे संख्याओं के विस्तार को शामिल करता है। यह रैमसे सिद्धांत का मात्रात्मक केंद्र है।
Core questions
- एक दिए गए आकार के एकरंगा गुट को बल देने के लिए एक पूर्ण ग्राफ कितना बड़ा होना चाहिए?
- रैमसे संख्याओं के लिए ज्ञात सटीक मान और सीमाएँ क्या हैं?
- संभाव्य तर्क रैमसे संख्याओं पर निचली सीमाएँ कैसे देते हैं?
- प्रमेय कई रंगों और हाइपरग्राफों के लिए कैसे सामान्यीकृत होता है?
Key concepts
- ग्राफ के लिए रैमसे का प्रमेय
- रैमसे संख्या R(s,t)
- एकरंगा गुट (क्लिक)
- एर्डोस-सेकेरेस सीमा
- संभाव्य निचली सीमाएँ
- बहुरंगी और हाइपरग्राफ रैमसे संख्याएँ
Key theories
- एर्डोस-सेकेरेस ऊपरी सीमा
- रैमसे संख्याएँ परिमित होती हैं और R(s,t) द्वारा s+t-2 में से s-1 के द्विपद गुणांक से अधिक नहीं होती हैं, एक पुनरावृत्ति-आधारित सीमा जो स्पष्ट अनुमानों के साथ रैमसे के प्रमेय को सिद्ध करती है।
- एर्डोस की संभाव्य निचली सीमा
- एक यादृच्छिक रंग में अपेक्षित एकरंगा गुटों की गणना करके, एर्डोस ने 1947 में दिखाया कि विकर्ण रैमसे संख्या R(s,s) कम से कम घातीय रूप से बढ़ती है, जो संभाव्य विधि का एक संस्थापक अनुप्रयोग है।
Clinical relevance
रैमसे-संख्या निचली सीमाओं के माध्यम से प्रस्तुत संभाव्य विधि संयोजकता और सैद्धांतिक कंप्यूटर विज्ञान में एक केंद्रीय उपकरण बन गई, और रैमसे-प्रकार की गारंटी संचार और डेटा संरचनाओं में निचली सीमाओं को रेखांकित करती है।
History
एर्डोस और सेकेरेस ने 1935 में उत्तल बहुभुजों का अध्ययन करते हुए रैमसे के प्रमेय को फिर से खोजा और परिमाणित किया; एर्डोस की 1947 की यादृच्छिक-रंग निचली सीमा ने संभाव्य विधि को जन्म दिया।
Key figures
- Frank Ramsey
- Paul Erdos
- George Szekeres
Related topics
Seminal works
- graham1990
Frequently asked questions
- R(3,3) छह के बराबर क्यों है?
- किसी भी छह लोगों में से, कोई तीन आपसी परिचित होते हैं या कोई तीन आपसी अजनबी होते हैं, जबकि पाँच लोगों को दोनों से बचने के लिए व्यवस्थित किया जा सकता है, इसलिए छह सटीक सीमा है।
- क्या सटीक रैमसे संख्याएँ ज्ञात हैं?
- केवल कुछ ही सटीक रूप से ज्ञात हैं; R(5,5) भी अज्ञात है, वर्तमान ज्ञान इसे केवल एक सीमा तक ही सीमित करता है, क्योंकि गणना द्वारा इसे हल करने के लिए खोज स्थान बहुत तेज़ी से बढ़ता है।