राडो ग्राफ

राडो ग्राफ़, जैसा कि एकरमैन (1937) और राडो (1964) द्वारा क्रमांकित है।

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

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

राडो ग्राफ़ अत्यधिक सममित है: इसके परिमित प्रेरित उपसमूहों के किसी भी समरूपता को पूरे ग्राफ़ की समरूपता तक बढ़ाया जा सकता है। प्रथम-क्रम तर्क वाक्य जो राडो ग्राफ के लिए सत्य हैं, वे लगभग सभी यादृच्छिक परिमित ग्राफ के लिए भी सत्य हैं, और जो वाक्य राडो ग्राफ के लिए गलत हैं, वे लगभग सभी परिमित ग्राफ के लिए भी गलत हैं। मॉडल सिद्धांत में, राडो ग्राफ ω-वर्गीकृत सिद्धांत के अद्वितीय गणनीय मॉडल का एक उदाहरण है।

इतिहास

राडो ग्राफ़ का निर्माण सबसे पहले एकरमैन (1937) द्वारा दो तरीकों से किया गया था, जिसमें शीर्ष या तो आनुवंशिक रूप से सीमित समुच्चय या प्राकृतिक संख्याएँ थीं। (यथार्थ रूप से, एकरमैन ने एक निर्देशित ग्राफ का वर्णन किया है, और राडो ग्राफ किनारों पर दिशाओं को भूलकर दिया गया संबंधित अप्रत्यक्ष ग्राफ है।) एर्दो और रेनी (1963) ने राडो ग्राफ को गणनीय संख्या में बिंदुओं पर यादृच्छिक ग्राफ के रूप में बनाया है। उन्होंने साबित किया कि इसमें असीमित रूप से कई ऑटोमोर्फिज्म (स्वाकारिता) हैं, और उनके तर्क से यह भी पता चलता है कि यह अद्वितीय है, हालांकि उन्होंने इसका स्पष्ट रूप से उल्लेख नहीं किया। रिचर्ड राडो (1964) ने राडो ग्राफ को एक सार्वभौमिक ग्राफ के रूप में फिर से खोजा और शीर्ष पर प्राकृतिक संख्याओं को समुच्चय करने के साथ इसका एक स्पष्ट निर्माण दिया। राडो का निर्माण अनिवार्य रूप से एकरमैन के निर्माणों में से एक के बराबर है।

निर्माण

बाइनरी संख्या

एकरमैन (1937) और राडो (1964) ने बीआईटी विधेय का उपयोग करते हुए राडो ग्राफ का निर्माण इस प्रकार किया। उन्होंने ग्राफ़ के शीर्षों की पहचान प्राकृतिक संख्याओं 0, 1, 2, के साथ की... एक कोर ग्राफ़ में शीर्षों $x$ और $y$ को जोड़ता है (जहाँ $x<y$) जब भी $y$ के द्विआधारी निरूपण का $x$वां बिट गैर-शून्य होता है। इस प्रकार, उदाहरण के लिए, शीर्ष 0 के पड़ोसियों में सभी विषम संख्या वाले शीर्ष सम्मिलित हैं, क्योंकि जिन संख्याओं का 0वां बिट शून्येतर है, वे बिल्कुल विषम संख्याएं हैं। शीर्ष 1 का एक छोटा पड़ोसी, शीर्ष 0 है, क्योंकि 1 विषम है और शीर्ष 0 सभी विषम शीर्षों से जुड़ा है। शीर्ष 1 के बड़े पड़ोसी वे सभी शीर्ष हैं जिनकी संख्याएँ 2 या 3 मॉड्यूल 4 के अनुरूप हैं क्योंकि वे बिल्कुल सूचकांक 1 पर एक गैर-शून्य बिट वाली संख्याएँ हैं।

यादृच्छिक ग्राफ

राडो ग्राफ़ लगभग निश्चित रूप से कई शीर्षों पर एक यादृच्छिक ग्राफ़ के एर्डो-रेनी मॉडल में उत्पन्न होता है। विशेष रूप से, कोई व्यक्ति स्वतंत्र रूप से और शीर्षों के प्रत्येक जोड़े के लिए 1/2 संभावना के साथ यह चुनकर एक अनंत ग्राफ बना सकता है कि दोनों शीर्षों को एक कोर से जोड़ना है या नहीं। प्रायिकता 1 के साथ परिणामी ग्राफ़ राडो ग्राफ़ के समरूपी है। यह निर्माण तब भी काम करता है जब 1/2 के स्थान पर कोई निश्चित संभाव्यता p जो 0 या 1 के बराबर न हो, का उपयोग किया जाता है।

पॉल एर्डोज़ और अल्फ़्रेड रेनी (1963) द्वारा दिखाया गया यह परिणाम, राडो ग्राफ़ के लिए सामान्य वैकल्पिक नाम "यादृच्छिक ग्राफ़" में निश्चित लेख को सही ठहराता है। एर्दो-रेनी मॉडल से बार-बार एक परिमित ग्राफ खींचने से सामान्यतः अलग-अलग ग्राफ बनेंगे; हालाँकि, जब एक गणनीय अनंत ग्राफ़ पर लागू किया जाता है, तो मॉडल लगभग हमेशा एक ही अनंत ग्राफ़ उत्पन्न करता है।

इस तरह से बेतरतीब ढंग से उत्पन्न किसी भी ग्राफ के लिए, सभी विकल्पों को उलट कर एक ही समय में पूरक ग्राफ प्राप्त किया जा सकता है: एक कोर सहित जब पहले ग्राफ़ में समान कोर सम्मिलित नहीं थी, और इसके विपरीत। पूरक ग्राफ़ का यह निर्माण यादृच्छिक रूप से और स्वतंत्र रूप से यह चुनने की उसी प्रक्रिया का एक उदाहरण है कि प्रत्येक कोर को सम्मिलित किया जाए या नहीं, इसलिए यह (संभावना 1 के साथ) राडो ग्राफ़ भी उत्पन्न करता है। इसलिए, राडो ग्राफ एक स्व-पूरक ग्राफ है।

अन्य रचनाएं

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

राडो ग्राफ का निर्माण पाले ग्राफ के सदृश एक निर्माण द्वारा भी किया जा सकता है, जिसमें सभी अभाज्य संख्याओं को एक ग्राफ के शीर्ष के रूप में लिया जाता है जो 1 मॉड्यूलो 4 के अनुरूप होते हैं, और जब भी दो संख्याओं में से एक द्विघात अवशेष मॉड्यूलो अन्य होता है तो दो शीर्षों को एक कोर से जोड़ते हैं। द्विघात पारस्परिकता और 1 मॉड 4 के अनुरूप अभाज्य संख्याओं के शीर्षों के प्रतिबंध द्वारा, यह एक सममित संबंध है, इसलिए यह एक अप्रत्यक्ष ग्राफ को परिभाषित करता है, जो राडो ग्राफ के लिए समरूपी हो जाता है।

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

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

गुण

विस्तार

राडो ग्राफ़ का विस्तार गुण: शीर्षों के प्रत्येक दो असंयुक्त परिमित सेटों के लिए $U$ और $V$, वहाँ एक और शिखर उपस्थित है $x$ में हर चीज़ से जुड़ा हुआ है $U$, और अंदर कुछ भी नहीं $V$

राडो ग्राफ़ निम्नलिखित विस्तार गुण को संतुष्ट करता है: शीर्ष $U$ और $V$ के प्रत्येक दो असंयुक्त परिमित सेटों के लिए, दोनों सेटों के बाहर एक शीर्ष $x$ उपस्थित होता है जो $U$ में सभी शीर्षों से जुड़ा होता है लेकिन $V$ में कोई पड़ोसी नहीं होता है। उदाहरण के लिए, राडो ग्राफ़ की द्विआधारी-संख्या परिभाषा के साथ, आइए

$$x=2^{1+\max(U\cup V)}+\sum _{u\in U}2^{u}.$$

फिर x के द्विआधारी प्रतिनिधित्व में गैर-शून्य बिट्स के कारण यह $U$ में हर चीज के निकट होता है। हालाँकि, $x$ के पास $V$ में शीर्षों के अनुरूप अपने द्विआधारी प्रतिनिधित्व में कोई गैर-शून्य बिट्स नहीं है, और $x$ इतना अधिक है कि $V$ के प्रत्येक अवयव का $x$ बिट शून्य है। इस प्रकार, $x$, $V$ में किसी भी शीर्ष के निकट नहीं है।

राडो ग्राफ़ की यादृच्छिक-ग्राफ़ परिभाषा के साथ, $U$ और $V$ के संघ के बाहर प्रत्येक शीर्ष की संभावना $1/2^{|U|+|V|}$विस्तार गुण को पूरा करने के लिए, अन्य शीर्षों से स्वतंत्र रूप से है। चूँकि चुनने के लिए अनंत रूप से कई शीर्ष हैं, प्रत्येक की सफलता की समान सीमित संभावना है, संभावना यह है कि एक शीर्ष उपस्थित है जो विस्तार गुण को पूरा करता है। पेली ग्राफ परिभाषा के साथ, चीनी शेषफल प्रमेय के अनुसार, किसी भी समुच्चय $U$और $V$ के लिए, वे संख्याएँ जो $U$ में प्रत्येक अभाज्य के द्विघात अवशेष मॉड्यूलो हैं और $V$ में प्रत्येक अभाज्य गैर-अवशेष मॉड्यूलो हैं, एक आवधिक अनुक्रम बनाते हैं, इसलिए अंकगणितीय प्रगति में अभाज्य पर डिरिक्लेट के प्रमेय के अनुसार इस संख्या-सैद्धांतिक ग्राफ में विस्तार गुण है।

प्रेरित सबग्राफ

विस्तार गुण का उपयोग राडो ग्राफ के भीतर किसी भी परिमित या गणनीय अनंत ग्राफ $G$ की समरूपी प्रतियों को प्रेरित सबग्राफ के रूप में बनाने के लिए किया जा सकता है। ऐसा करने के लिए, $G$ के शीर्षों को क्रमबद्ध करें, और राडो ग्राफ़ के भीतर $G$ की आंशिक प्रतिलिपि में उसी क्रम में शीर्ष जोड़ें। प्रत्येक चरण में, $G$ में अगला शीर्ष $G$ में शीर्षों के कुछ समुच्चय $U$ के निकट होगा जो कि शीर्षों के क्रम में पहले हैं, और $G$ में पहले के शीर्षों के शेष समुच्चय $V$ के निकट नहीं होगा। विस्तार गुण के अनुसार, राडो ग्राफ में एक शीर्ष $x$ भी होगा जो आंशिक प्रतिलिपि में सभी शीर्षों के समीप है जो $U$ के सदस्यों के अनुरूप है, और आंशिक प्रतिलिपि में सभी शीर्षों के निकट नहीं है जो $V$ के सदस्यों के अनुरूप है। की आंशिक प्रतिलिपि में $x$ जोड़ना $G$ एक और शीर्ष के साथ, एक बड़ी आंशिक प्रतिलिपि तैयार करता है।[

यह विधि प्रेरण द्वारा प्रमाण के लिए आधार बनाती है, इसके आधार स्तिथि के रूप में 0-वर्टेक्स सबग्राफ के साथ, कि प्रत्येक परिमित या गणनीय अनंत ग्राफ राडो ग्राफ का एक प्रेरित सबग्राफ है।

अद्वितीयता

रैडो ग्राफ़, ग्राफ़ समरूपता तक, विस्तार गुण वाला एकमात्र गणनीय ग्राफ़ है। उदाहरण के लिए, मान लीजिए कि $G$ और $H$ विस्तार गुण वाले दो गणनीय ग्राफ हैं, मान लीजिए $G_{i}$और $H_{i}$ क्रमशः $G$ और $H$ के समरूपी परिमित प्रेरित सबग्राफ हैं, और मान लीजिए कि $g_{i}$और $h_{i}$ क्रमशः $G$ और $H$ के शीर्षों की गणना में पहले शीर्ष हैं जो $G_{i}$ और $H_{i}$ से संबंधित नहीं हैं। फिर, एक्सटेंशन प्रॉपर्टी को दो बार लागू करके, कोई समरूपी-प्रेरित सबग्राफ $G_{i+1}$और $H_{i+1}$पा सकता है जिसमें पिछले सबग्राफ के सभी शीर्षों के साथ $g_{i}$ और सम्मिलित हैं। इस प्रक्रिया को दोहराकर, कोई प्रेरित उपसमूहों के बीच समरूपता का एक क्रम बना सकता है जिसमें अंततः $G$ और $H$ में प्रत्येक शीर्ष सम्मिलित होता है। इस प्रकार, आगे-पीछे विधि द्वारा, $G$ और $H$ को समरूपी होना चाहिए। चूँकि यादृच्छिक ग्राफ़ निर्माण, बाइनरी संख्या निर्माण और पैली ग्राफ़ निर्माण द्वारा निर्मित ग्राफ़ सभी विस्तार संपत्ति के साथ गणनीय ग्राफ़ हैं, यह तर्क दर्शाता है कि वे सभी एक दूसरे के लिए समरूपी हैं।

समरूपता समूह

राडो ग्राफ़ के किन्हीं दो समरूपी परिमित उपसमूहों के आगे-पीछे निर्माण को लागू करने से उनकी समरूपता पूरे राडो ग्राफ़ के एक ग्राफ ऑटोमोर्फिज्म तक विस्तारित हो जाती है। तथ्य यह है कि परिमित उपग्राफों की प्रत्येक समरूपता पूरे ग्राफ के ऑटोमोर्फिज्म तक फैली हुई है, यह कहकर व्यक्त किया जाता है कि राडो ग्राफ सजातीय ग्राफ है। विशेष रूप से, आसन्न शीर्षों के किसी भी क्रमित जोड़े को ऐसे किसी अन्य क्रमित जोड़े में ले जाने वाली एक ऑटोमोर्फिज्म होती है, इसलिए राडो ग्राफ एक सममित ग्राफ है।

राडो ग्राफ का ऑटोमोर्फिज्म समूह एक सरल समूह है, जिसके अवयवों की संख्या सातत्य की प्रमुखता है। इस समूह का प्रत्येक उपसमूह, जिसके उपसमूह का सूचकांक सातत्य की कार्डिनैलिटी से कम है, में शीर्षों के एक सीमित समुच्चय का बिंदुवार स्टेबलाइजर होता है, और इसके अलावा उसी समुच्चय के सेटवाइज स्टेबलाइजर के भीतर समाहित होता है। बिंदुवार स्टेबिलाइजर्स के बारे में बयान को लघु सूचकांक गुण कहा जाता है,और इसे साबित करने के लिए प्रत्येक परिमित ग्राफ़ के लिए इसे दिखाना आवश्यक है $X$, एक परिमित ग्राफ है $Z$ युक्त $X$ एक प्रेरित सबग्राफ के रूप में, जैसे कि प्रेरित सबग्राफ के बीच प्रत्येक समरूपता $X$ की ऑटोमोर्फिज्म तक फैली हुई है $Z$. इसे आंशिक ऑटोमोर्फिज्म के लिए विस्तार गुण कहा जाता है और तब से छोटी सूचकांक गुण और अन्य गुणों को दिखाने के लिए इसे आगे की संरचनाओं में सामान्यीकृत किया गया है।

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

परिमित परिवर्तनों के प्रति दृढ़ता

यदि एक ग्राफ $G$ राडो ग्राफ़ से किसी भी सीमित संख्या में किनारों या शीर्षों को हटाकर, या किनारों की एक सीमित संख्या जोड़कर बनाया जाता है, परिवर्तन ग्राफ़ की विस्तार गुण को प्रभावित नहीं करता है। समुच्चय की किसी भी जोड़ी के लिए $U$ और $V$ संशोधित ग्राफ़ में एक शीर्ष खोजना अभी भी संभव है जो कि हर चीज़ के निकट है $U$ और हर चीज़ से असन्निकट $V$, के संशोधित भागों को जोड़कर $G$ को $V$ और असंशोधित राडो ग्राफ़ में एक्सटेंशन प्रॉपर्टी को लागू करना। इसलिए, इस प्रकार के किसी भी सीमित संशोधन के परिणामस्वरूप एक ग्राफ बनता है जो राडो ग्राफ के समरूपी होता है।

विभाजन

राडो ग्राफ के शीर्षों के किसी भी विभाजन के लिए दो समुच्चय $A$ और $B$ में, या अधिक सामान्यतः किसी भी विभाजन के लिए बहुत से उपसमुच्चयों में, विभाजन सेटों में से एक से प्रेरित कम से कम एक सबग्राफ पूरे राडो ग्राफ के लिए सोमॉर्फिक है। कैमरून (2001) निम्नलिखित संक्षिप्त प्रमाण देता है: यदि कोई भी भाग राडो ग्राफ़ में एक सबग्राफ आइसोमोर्फिक को प्रेरित नहीं करता है, तो वे सभी विस्तार गुण रखने में विफल हो जाते हैं, और कोई समुच्चय $U_{i}$और $V_{i}$ के जोड़े पा सकता है जिन्हें प्रत्येक सबग्राफ के भीतर विस्तारित नहीं किया जा सकता है। लेकिन फिर, समुच्चयों का संघ $U_{i}$और समुच्चयों का संघ $V_{i}$ एक ऐसा समुच्चय बनाएगा जिसे पूरे ग्राफ़ में नहीं बढ़ाया जा सकता, जो राडो ग्राफ़ की विस्तार संपत्ति के विपरीत है। किसी भी विभाजन के प्रेरित उपग्राफों में से एक के समरूपी होने की यह संपत्ति केवल तीन गणनीय अनंत अप्रत्यक्ष ग्राफ़ द्वारा धारण की जाती है: राडो ग्राफ़, पूर्ण ग्राफ़ और खाली ग्राफ़। बोनाटो, कैमरून और डेलीक (2000) और डायस्टेल एट अल। (2007) समान विभाजन गुण के साथ अनंत निर्देशित ग्राफ़ की जांच करें; सभी पूर्ण ग्राफ़ या राडो ग्राफ़ के किनारों के लिए अभिविन्यास चुनकर बनाए जाते हैं।

एक संबंधित परिणाम शीर्ष विभाजन के बजाय कोर विभाजन से संबंधित है: राडो ग्राफ़ के किनारों के प्रत्येक विभाजन के लिए कई सेटों में, पूरे राडो ग्राफ़ के लिए एक सबग्राफ आइसोमोर्फिक है जो अधिकतम दो रंगों का उपयोग करता है। हालाँकि, जरूरी नहीं कि एक आइसोमॉर्फिक सबग्राफ उपस्थित हो जो किनारों के केवल एक रंग का उपयोग करता हो। अधिक सामान्यतः, प्रत्येक परिमित ग्राफ $A$ के लिए एक संख्या $d_{A}$होती है (जिसे राडो ग्राफ में $A$ की बड़ी रैमसे डिग्री कहा जाता है) जैसे कि राडो ग्राफ में $A$ की प्रतियों के प्रत्येक विभाजन के लिए कई सेटों में, पूरे राडो ग्राफ में एक प्रेरित सबग्राफ आइसोमोर्फिक होता है जो रंगों के अधिकतम $d_{A}$ का उपयोग करता है।

मॉडल सिद्धांत और 0-1 नियम

फ़ागिन (1976) ने ग्राफ़ के तर्क में प्रथम-क्रम कथनों के लिए शून्य-एक नियम को साबित करने के लिए राडो ग्राफ़ का उपयोग किया। जब इस प्रकार का तार्किक कथन राडो ग्राफ़ के लिए सत्य या ग़लत है, तो यह लगभग सभी परिमित ग्राफ़ के लिए भी सत्य या ग़लत (क्रमशः) है।

प्रथम-क्रम गुण

ग्राफ़ की प्रथम-क्रम भाषा गणितीय तर्क में अच्छी तरह से निर्मित वाक्यों का संग्रह है, जो ग्राफ़ के शीर्षों, सार्वभौमिक और अस्तित्वगत परिमाणकों, तार्किक संयोजकों और शीर्षों की समानता और आसन्नता के लिए विधेय का प्रतिनिधित्व करने वाले चर से निर्मित होती है। उदाहरण के लिए, यह शर्त कि किसी ग्राफ़ में कोई अलग-अलग शीर्ष न हो, वाक्य द्वारा व्यक्त की जा सकती है।

$$\forall u:\exists v:u\sim v$$

जहां $\sim$ प्रतीक दो शीर्षों के बीच आसन्न संबंध को दर्शाता है। यह वाक्य $S$ कुछ ग्राफ़ के लिए सत्य है, और अन्य के लिए ग़लत है; एक ग्राफ $G$ मॉडलिंग करने के लिए कहा जाता है $S$, लिखा हुआ $G\models S$, अगर $S$ के शीर्ष और आसन्न संबंध के बारे में सत्य है $G$. राडो ग्राफ़ की विस्तार गुण को प्रथम-क्रम वाक्यों के संग्रह द्वारा व्यक्त किया जा सकता है $E_{i,j}$, यह बताते हुए कि हर विकल्प के लिए $i$ एक समुच्चय में शीर्ष $A$ और $j$ एक समुच्चय में शीर्ष $B$, सभी अलग-अलग, हर चीज से सटे एक शीर्ष उपस्थित है $A$ और हर चीज़ से असन्निकट $B$. उदाहरण के लिए, $E_{1,1}$ के रूप में लिखा जा सकता है।

$$\forall a:\forall b:a\neq b\rightarrow \exists c:c\neq a\wedge c\neq b\wedge c\sim a\wedge \lnot (c\sim b).$$

सम्पूर्णता

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

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

परिमित ग्राफ़ और कम्प्यूटेशनल जटिलता

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

इस 0-1 नियम के कारण, n का एक अधिक पर्याप्त मान चुनकर और वाक्य को मॉडल करने वाले $n$-वर्टेक्स ग्राफ़ की संख्या की गणना करके, यह परीक्षण करना संभव है कि क्या किसी विशेष प्रथम-क्रम वाक्य को सीमित समय में राडो ग्राफ द्वारा मॉडल किया गया है। हालाँकि, यहाँ, "काफ़ी अधिक" वाक्य के आकार में कम से कम घातांकीय है। उदाहरण के लिए, विस्तार अभिगृहीत ,$E_{k,0}$ एक $(k+1)$-वर्टेक्स क्लिक के अस्तित्व को दर्शाता है, लेकिन उस आकार का एक गुट केवल $k$ में आकार घातांक के यादृच्छिक ग्राफ़ में उच्च संभावना के साथ उपस्थित है। यह निर्धारित करना असंभव है कि राडो ग्राफ किसी दिए गए वाक्य को मॉडल करता है या नहीं, इसे घातीय समय की तुलना में अधिक तेज़ी से किया जा सकता है, क्योंकि समस्या पीस्पेस-पूर्ण है।

अन्य मॉडल-सैद्धांतिक गुण

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

राडो ग्राफ का सिद्धांत स्वतंत्रता संपत्ति के साथ एक सिद्धांत का एक प्रोटोटाइपिक उदाहरण है, और एक सरल सिद्धांत का जो स्थिर नहीं है।

संबंधित अवधारणाएँ

यद्यपि राडो ग्राफ़ प्रेरित सबग्राफ के लिए सार्वभौमिक है, यह ग्राफ़ के आइसोमेट्रिक एम्बेडिंग के लिए सार्वभौमिक नहीं है, जहां एक आइसोमेट्रिक एम्बेडिंग एक ग्राफ़ आइसोमोर्फिज्म है जो दूरी को संरक्षित करता है। राडो ग्राफ़ का व्यास दो है, और इसलिए बड़े व्यास वाला कोई भी ग्राफ़ इसमें आइसोमेट्रिक रूप से एम्बेड नहीं होता है। मॉस (1989, 1991) ने आइसोमेट्रिक एम्बेडिंग के लिए सार्वभौमिक ग्राफ के एक परिवार का वर्णन किया है, प्रत्येक संभावित परिमित ग्राफ व्यास के लिए एक; उनके परिवार में व्यास दो के साथ ग्राफ राडो ग्राफ है।

हेन्सन ग्राफ़ गणनीय ग्राफ़ हैं (प्रत्येक धनात्मक पूर्णांक के लिए एक)। $i$) जिसमें i$i$-वर्टेक्स क्लिक नहीं है और ये $i$-क्लिक-मुक्त ग्राफ़ के लिए सार्वभौमिक हैं। इन्हें राडो ग्राफ के प्रेरित सबग्राफ के रूप में बनाया जा सकता है। राडो ग्राफ, हेंसन ग्राफ और उनके पूरक, अनगिनत अनंत समूहों और उनके पूरकों के असंयुक्त संघ, और आइसोमोर्फिक परिमित गुटों और उनके पूरकों के अनंत असंयुक्त संघ ही एकमात्र संभव गिनती योग्य अनंत सजातीय ग्राफ हैं।

राडो ग्राफ़ की सार्वभौमिकता संपत्ति को कोर के रंग वाले ग्राफ़ तक बढ़ाया जा सकता है; अर्थात्, ऐसे ग्राफ़ जिनमें किनारों को अलग-अलग रंग वर्गों को सौंपा गया है, लेकिन किनारों के रंग की सामान्य आवश्यकता के बिना कि प्रत्येक रंग वर्ग एक संघ बनाता है। रंगों की किसी भी परिमित या गणनीय अनंत संख्या के लिए, एक अद्वितीय गणनीय-अनंत $\chi$-कोर-रंगीन ग्राफ $G_{\chi }$ उपस्थित है, जैसे कि $\chi$-कोर-रंगीन परिमित ग्राफ के प्रत्येक आंशिक आइसोमोर्फिज्म को पूर्ण आइसोमोर्फिज्म तक बढ़ाया जा सकता है। इस अंकन के साथ, राडो ग्राफ सिर्फ $G_{1}$ है। ट्रस (1985) ग्राफ़ के इस अधिक सामान्य परिवार के ऑटोमोर्फिज़्म समूहों की जाँच करता है।

जबकि राडो ग्राफ़ सभी ग्राफ़ों के वर्ग के लिए गणनीय सार्वभौमिक ग्राफ़ है, सभी ग्राफ़ वर्गों में गणनीय सार्वभौमिक ग्राफ़ नहीं है। उदाहरण के लिए, 4-चक्र को सबग्राफ के रूप में छोड़ने वाला कोई गणनीय ग्राफ़ नहीं है जिसमें अन्य सभी ऐसे गणनीय ग्राफ़ (आवश्यक रूप से प्रेरित नहीं) सबग्राफ के रूप में सम्मिलित हैं।

यह एक संतृप्त मॉडल के निर्माण के शास्त्रीय मॉडल सिद्धांत के विचारों का अनुसरण करता है कि सातत्य परिकल्पना सीएच के तहत, कई शीर्षों के सातत्य के साथ एक सार्वभौमिक ग्राफ है। निस्संदेह, सीएच के तहत, सातत्य $\aleph _{1}$ के बराबर है, पहला बेशुमार कार्डिनल। शेला (1984, 1990) सार्वभौमिक ग्राफ़ की जांच के लिए फोर्सिंग का उपयोग करता है $\aleph _{1}$ कई शीर्ष और दर्शाते हैं कि CH की अनुपस्थिति में भी, आकार $\aleph _{1}$ का एक सार्वभौमिक ग्राफ उपस्थित हो सकता है। वह उच्च कार्डिनैलिटी के लिए समान प्रश्नों की भी जांच करता है।

संदर्भ

• Ackermann, Wilhelm (1937), "Die Widerspruchsfreiheit der allgemeinen Mengenlehre", Mathematische Annalen, 114 (1): 305–315, doi:10.1007/BF01594179, S2CID 120576556
• Bonato, Anthony; Cameron, Peter; Delić, Dejan (2000), "Tournaments and orders with the pigeonhole property", Canadian Mathematical Bulletin, 43 (4): 397–405, doi:10.4153/CMB-2000-047-6, MR 1793941.
• Baldwin, John T. (2018), Model theory and the philosophy of mathematical practice: formalization without foundationalism, Cambridge University Press, doi:10.1017/9781316987216, ISBN 978-1-107-18921-8, MR 3793636, S2CID 126311148.
• Cameron, Peter J. (1990), Oligomorphic permutation groups, London Mathematical Society Lecture Note Series, vol. 152, Cambridge: Cambridge University Press, ISBN 0-521-38836-8, MR 1066691.
• Cameron, Peter J. (1997), "The random graph", The mathematics of Paul Erdős, II, Algorithms and Combinatorics, vol. 14, Berlin: Springer, pp. 333–351, arXiv:1301.7544, Bibcode:2013arXiv1301.7544C, MR 1425227.
• Cameron, Peter J. (2001), "The random graph revisited" (PDF), European Congress of Mathematics, Vol. I (Barcelona, 2000), Progr. Math., vol. 201, Basel: Birkhäuser, pp. 267–274, doi:10.1007/978-3-0348-8268-2_15, MR 1905324.
• Cherlin, Gregory (2011), "Forbidden substructures and combinatorial dichotomies: WQO and universality", Discrete Mathematics, 311 (15): 1543–1584, doi:10.1016/j.disc.2011.03.014, MR 2800977.
• Diestel, Reinhard; Leader, Imre; Scott, Alex; Thomassé, Stéphan (2007), "Partitions and orientations of the Rado graph", Transactions of the American Mathematical Society, 359 (5): 2395–2405, doi:10.1090/S0002-9947-06-04086-4, MR 2276626.
• Dobrinen, Natasha (2021), "Ramsey theory of homogeneous structures: current trends and open problems", arXiv:2110.00655v1 [math.LO].
• Enderton, Herbert B. (1972), A mathematical introduction to logic, Academic Press, New York-London, MR 0337470.
• Erdős, P.; Rényi, A. (1963), "Asymmetric graphs", Acta Mathematica Academiae Scientiarum Hungaricae, 14 (3–4): 295–315, doi:10.1007/BF01895716, MR 0156334.
• Fagin, Ronald (1976), "Probabilities on finite models" (PDF), The Journal of Symbolic Logic, 41 (1): 50–58, doi:10.1017/s0022481200051756, JSTOR 2272945, MR 0476480, S2CID 2563318.
• Gaifman, Haim (1964), "Concerning measures in first order calculi", Israel Journal of Mathematics, 2: 1–18, doi:10.1007/BF02759729, MR 0175755.
• Grandjean, Étienne (1983), "Complexity of the first-order theory of almost all finite structures", Information and Control, 57 (2–3): 180–204, doi:10.1016/S0019-9958(83)80043-6, MR 0742707.
• Henson, C. Ward (1971), "A family of countable homogeneous graphs", Pacific Journal of Mathematics, 38: 69–83, doi:10.2140/pjm.1971.38.69, MR 0304242.
• Hodges, Wilfrid (1997), A Shorter Model Theory, Cambridge University Press, ISBN 0-521-58713-1, OCLC 468298248
• Horsley, Daniel; Pike, David A.; Sanaei, Asiyeh (2011), "Existential closure of block intersection graphs of infinite designs having infinite block size", Journal of Combinatorial Designs, 19 (4): 317–327, doi:10.1002/jcd.20283, MR 2838911, S2CID 120707836.
• Hrushovski, Ehud (1992), "Extending partial isomorphisms of graphs", Combinatorica, 12 (4): 411–416, doi:10.1007/BF01305233, MR 1194731, S2CID 19939702.
• Lachlan, A. H.; Woodrow, Robert E. (1980), "Countable ultrahomogeneous undirected graphs", Transactions of the American Mathematical Society, 262 (1): 51–94, doi:10.2307/1999974, JSTOR 1999974, MR 0583847.
• Łoś, J. (1954), "On the categoricity in power of elementary deductive systems and some related problems", Colloquium Math., 3: 58–62, doi:10.4064/cm-3-1-58-62, MR 0061561.
• Macpherson, Dugald (2011), "A survey of homogeneous structures", Discrete Mathematics, 311 (15): 1599–1634, doi:10.1016/j.disc.2011.01.024, MR 2800979.
• Marker, David (2002), Model theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, ISBN 0-387-98760-6, MR 1924282.
• McNulty, George F. (2016), Elementary Model Theory (PDF), pp. 71–75, retrieved 5 April 2023.
• Moss, Lawrence S. (1989), "Existence and nonexistence of universal graphs", Polska Akademia Nauk. Fundamenta Mathematicae, 133 (1): 25–37, doi:10.4064/fm-133-1-25-37, MR 1059159.
• Moss, Lawrence S. (1991), "The universal graphs of fixed finite diameter", Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., New York: Wiley, pp. 923–937, MR 1170834.
• Pouzet, Maurice; Sauer, Norbert (1996), "Edge partitions of the Rado graph", Combinatorica, 16 (4): 505–520, doi:10.1007/BF01271269, MR 1433638, S2CID 206793062.
• Rado, Richard (1964), "Universal graphs and universal functions" (PDF), Acta Arith., 9 (4): 331–340, doi:10.4064/aa-9-4-331-340.
• Rothmaler, Philipp (2000), Introduction to model theory, Algebra, logic and applications, vol. 15, Gordon and Breach Science Publishers, ISBN 90-5699-287-2, MR 1800596.
• Sauer, Norbert (2006), "Coloring subgraphs of the Rado graph", Combinatorica, 26 (2): 231–253, doi:10.1007/s00493-006-0015-0, MR 2223636, S2CID 19251747.
• Shelah, Saharon (1984), "On universal graphs without instances of CH", Annals of Pure and Applied Logic, 26 (1): 75–87, doi:10.1016/0168-0072(84)90042-3, MR 0739914.
• Shelah, Saharon (1990), "Universal graphs without instances of CH: revisited", Israel Journal of Mathematics, 70 (1): 69–81, doi:10.1007/BF02807219, MR 1057268.
• Spencer, Joel (2001), The Strange Logic of Random Graphs, Algorithms and Combinatorics, vol. 22, Springer-Verlag, Berlin, doi:10.1007/978-3-662-04538-1, ISBN 3-540-41654-4, MR 1847951.
• Truss, J. K. (1985), "The group of the countable universal graph", Mathematical Proceedings of the Cambridge Philosophical Society, 98 (2): 213–245, Bibcode:1985MPCPS..98..213T, doi:10.1017/S0305004100063428, MR 0795890, S2CID 122772888.
• Vaught, Robert L. (1954), "Applications to the Löwenheim-Skolem-Tarski theorem to problems of completeness and decidability", Indagationes Mathematicae, 16: 467–472, doi:10.1016/S1385-7258(54)50058-2, MR 0063993.