राडो ग्राफ: Difference between revisions

Latest revision as of 11:09, 14 August 2023

राडो ग्राफ, जैसा कि एकरमैन (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]

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

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

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

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

अन्य रचनाएं

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

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

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

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

गुण

विस्तार

राडो ग्राफ का विस्तार गुण: शीर्षों के प्रत्येक दो असंयुक्त परिमित समुच्चय के लिए

U

और

V

, वहाँ एक और शिखर उपस्थित है

x

में हर चीज़ से जुड़ा हुआ है

U

, और अंदर कुछ भी नहीं

V

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

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

फिर x के द्विआधारी प्रतिनिधित्व में गैर-शून्य बिट्स के कारण यह

U

में हर चीज के निकट होता है। हालाँकि,

x

के पास

V

में शीर्षों के अनुरूप अपने द्विआधारी प्रतिनिधित्व में कोई गैर-शून्य बिट्स नहीं है, और

x

इतना अधिक है कि

V

के प्रत्येक अवयव का

x

बिट शून्य है। इस प्रकार,

x

,

V

में किसी भी शीर्ष के निकट नहीं है।^[10]

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

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

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

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

अद्वितीयता

रैडो ग्राफ, ग्राफ समरूपता तक, विस्तार गुण वाला एकमात्र गणनीय ग्राफ है। उदाहरण के लिए, मान लीजिए कि $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$ को समरूपी होना चाहिए।^[12] चूँकि यादृच्छिक ग्राफ निर्माण, बाइनरी संख्या निर्माण और पैली ग्राफ निर्माण द्वारा निर्मित ग्राफ सभी विस्तार गुण के साथ गणनीय ग्राफ हैं, यह तर्क दर्शाता है कि वे सभी एक दूसरे के लिए समरूपी हैं।^[13]

समरूपता समूह

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

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

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

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

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

विभाजन

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

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

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

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

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

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

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

जहां $\sim$ प्रतीक दो शीर्षों के बीच आसन्न संबंध को दर्शाता है।^[23] यह वाक्य $S$ कुछ ग्राफ के लिए सत्य है, और अन्य के लिए ग़लत है; एक ग्राफ $G$ मॉडलिंग करने के लिए कहा जाता है $S$ , लिखा हुआ $G\models S$ , अगर $S$ के शीर्ष और आसन्न संबंध के बारे में सत्य है $G$ .^[24] राडो ग्राफ की विस्तार गुण को प्रथम-क्रम वाक्यों के संग्रह द्वारा व्यक्त किया जा सकता है $E_{i,j}$ , यह बताते हुए कि हर विकल्प के लिए $i$ एक समुच्चय में शीर्ष $A$ और $j$ एक समुच्चय में शीर्ष $B$ , सभी अलग-अलग, हर चीज से सटे एक शीर्ष उपस्थित है $A$ और हर चीज़ से असन्निकट $B$ .^[25] उदाहरण के लिए, $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$ में से एक और इसका निषेध इन सिद्धांतों से सिद्ध किया जा सकता है। क्योंकि राडो ग्राफ विस्तार सिद्धांतों को मॉडल करता है, यह इस सिद्धांत के सभी वाक्यों को मॉडल करता है।^[26]

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

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

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

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

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

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

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

↑ Ackermann (1937); Rado (1964).
↑ ^2.0 ^2.1 ^2.2 See Cameron (1997), Fact 1 and its proof.
↑ Erdős & Rényi (1963).
↑ Cameron (1997), Proposition 5.
↑ Cameron (1997), Theorem 2.
↑ ^6.0 ^6.1 Cameron (1997, 2001)
↑ Cameron (1997), Section 1.2.
↑ Horsley, Pike & Sanaei (2011)
↑ Hodges (1997), p. 350.
↑ Essentially the same construction, described in set-theoretic terms rather than using binary numbers, is given as Theorem 2 of Cameron (1997).
↑ ^11.0 ^11.1 Cameron (1997), Proposition 6.
↑ ^12.0 ^12.1 Cameron (2001).
↑ Cameron (1997), Fact 2.
↑ ^14.0 ^14.1 Cameron (1997), Section 1.8: The automorphism group.
↑ Hrushovski (1992)
↑ Macpherson (2011), Sections 5.2 and 5.3.
↑ ^17.0 ^17.1 Henson (1971).
↑ Cameron (1997), Section 1.3: Indestructibility.
↑ Cameron (1990); Diestel et al. (2007).
↑ Pouzet & Sauer (1996).
↑ Sauer (2006)
↑ Dobrinen (2021)
↑ Spencer (2001), Section 1.2, "What Is a First Order Theory?", pp. 15–17.
↑ See, e.g., Grandjean (1983), p. 184.
↑ Spencer (2001), Section 1.3, "Extension Statements and Rooted Graphs", pp. 17–18.
↑ Gaifman (1964); Marker (2002), Theorem 2.4.2, p. 50.
↑ Łoś (1954); Vaught (1954); Enderton (1972), p. 147.
↑ Marker (2002), Theorem 2.2.6, p. 42.
↑ Fagin (1976); Marker (2002), Theorem 2.4.4, pp. 51–52.
↑ Grandjean (1983).
↑ Macpherson (2011), Theorem 2.1.3, Example 2.2.1.
↑ Macpherson (2011), Corollary 3.1.3, Proposition 3.1.6.
↑ Rothmaler (2000), Theorem 13.3.1, Theorem 13.2.1.
↑ McNulty (2016), p.71 and p.75.
↑ Baldwin (2018)
↑ Lachlan & Woodrow (1980).
↑ Cherlin (2011), Fact 1.3

संदर्भ

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.

[1] Ackermann (1937); Rado (1964).

[binary-extension-2] 2.0 ^2.1 ^2.2 See Cameron (1997), Fact 1 and its proof.

[FOOTNOTEErdősRényi1963-3] Erdős & Rényi (1963).

[4] Cameron (1997), Proposition 5.

[5] Cameron (1997), Theorem 2.

[paley-6] 6.0 ^6.1 Cameron (1997, 2001)

[7] Cameron (1997), Section 1.2.

[8] Horsley, Pike & Sanaei (2011)

[FOOTNOTEHodges1997350-9] Hodges (1997), p. 350.

[10] Essentially the same construction, described in set-theoretic terms rather than using binary numbers, is given as Theorem 2 of Cameron (1997).

[induced-11] 11.0 ^11.1 Cameron (1997), Proposition 6.

[cam-12] 12.0 ^12.1 Cameron (2001).

[13] Cameron (1997), Fact 2.

[cam2-14] 14.0 ^14.1 Cameron (1997), Section 1.8: The automorphism group.

[15] Hrushovski (1992)

[16] Macpherson (2011), Sections 5.2 and 5.3.

[FOOTNOTEHenson1971-17] 17.0 ^17.1 Henson (1971).

[18] Cameron (1997), Section 1.3: Indestructibility.

[19] Cameron (1990); Diestel et al. (2007).

[20] Pouzet & Sauer (1996).

[21] Sauer (2006)

[22] Dobrinen (2021)

[23] Spencer (2001), Section 1.2, "What Is a First Order Theory?", pp. 15–17.

[24] See, e.g., Grandjean (1983), p. 184.

[25] Spencer (2001), Section 1.3, "Extension Statements and Rooted Graphs", pp. 17–18.

[26] Gaifman (1964); Marker (2002), Theorem 2.4.2, p. 50.

[27] Łoś (1954); Vaught (1954); Enderton (1972), p. 147.

[28] Marker (2002), Theorem 2.2.6, p. 42.

[29] Fagin (1976); Marker (2002), Theorem 2.4.4, pp. 51–52.

[FOOTNOTEGrandjean1983-30] Grandjean (1983).

[31] Macpherson (2011), Theorem 2.1.3, Example 2.2.1.

[32] Macpherson (2011), Corollary 3.1.3, Proposition 3.1.6.

[33] Rothmaler (2000), Theorem 13.3.1, Theorem 13.2.1.

[34] McNulty (2016), p.71 and p.75.

[35] Baldwin (2018)

[FOOTNOTELachlanWoodrow1980-36] Lachlan & Woodrow (1980).

[37] Cherlin (2011), Fact 1.3

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

@@ Line 1: / Line 1: @@
 {{good article}}
 {{short description|Infinite graph containing all countable graphs}}
-[[File:Rado graph.svg|thumb|upright=1.35|राडो ग्राफ़, जैसा कि एकरमैन (1937) और राडो (1964) द्वारा क्रमांकित है।]][[ग्राफ सिद्धांत]] के गणितीय क्षेत्र में, '''राडो ग्राफ''', '''एर्डोस-रेनी ग्राफ''', या '''यादृच्छिक ग्राफ''' एक गणनीय अनंत ग्राफ है जिसका निर्माण (संभावना एक के साथ) इसके शीर्षों की प्रत्येक जोड़ी के लिए यादृच्छिक रूप से स्वतंत्र रूप से चुनकर किया जा सकता है कि क्या शीर्षों को एक किनारे से जोड़ा जाए। इस ग्राफ़ के नाम [[रिचर्ड राडो]], पॉल एर्डोज़ और अल्फ़्रेड रेनी, गणितज्ञों का सम्मान करते हैं जिन्होंने 1960 के दशक की शुरुआत में इसका अध्ययन किया था; यह विल्हेम एकरमैन (1937) के काम में और भी पहले दिखाई देता है। राडो ग्राफ का निर्माण गैर-यादृच्छिक रूप से भी किया जा सकता है, आनुवंशिक रूप से परिमित सेटों के सदस्यता संबंध को सममित करके, प्राकृतिक संख्याओं के द्विआधारी प्रतिनिधित्व के लिए बीआईटी विधेय को लागू करके, या एक अनंत पैली ग्राफ के रूप में जिसमें 1 मॉड 4 के अनुरूप अभाज्य संख्याओं के जोड़े को जोड़ने वाले किनारे होते हैं जो एक दूसरे के द्विघात अवशेष मॉड्यूलो होते हैं।
+[[File:Rado graph.svg|thumb|upright=1.35|राडो ग्राफ, जैसा कि एकरमैन (1937) और राडो (1964) द्वारा क्रमांकित है।]][[ग्राफ सिद्धांत]] के गणितीय क्षेत्र में, '''राडो ग्राफ''', '''एर्डोस-रेनी ग्राफ''', या '''यादृच्छिक ग्राफ''' एक गणनीय अनंत ग्राफ है जिसका निर्माण (संभावना एक के साथ) इसके शीर्षों की प्रत्येक जोड़ी के लिए यादृच्छिक रूप से स्वतंत्र रूप से चुनकर किया जा सकता है कि क्या शीर्षों को एक कोर से जोड़ा जाए। इस ग्राफ के नाम [[रिचर्ड राडो]], पॉल एर्डोज़ और अल्फ़्रेड रेनी, गणितज्ञों का सम्मान करते हैं जिन्होंने 1960 के दशक की प्रारम्भ में इसका अध्ययन किया था; यह विल्हेम एकरमैन (1937) के काम में और भी पहले दिखाई देता है। राडो ग्राफ का निर्माण गैर-यादृच्छिक रूप से भी किया जा सकता है, आनुवंशिक रूप से परिमित समुच्चय के सदस्यता संबंध को सममित करके, प्राकृतिक संख्याओं के द्विआधारी प्रतिनिधित्व के लिए बीआईटी विधेय को प्रयुक्त करके, या एक अनंत पैली ग्राफ के रूप में जिसमें 1 मॉड 4 के अनुरूप अभाज्य संख्याओं के जोड़े को जोड़ने वाले कोर होते हैं जो एक दूसरे के द्विघात अवशेष मॉड्यूलो होते हैं।
-प्रत्येक परिमित या गणनीय अनंत ग्राफ राडो ग्राफ का एक प्रेरित उपग्राफ है और इसे एक ग्रीडी एल्गोरिथ्म द्वारा एक प्रेरित उपग्राफ के रूप में पाया जा सकता है जो एक समय में एक शीर्ष पर उपग्राफ बनाता है। राडो ग्राफ को गणनीय ग्राफों के बीच, एक ''विस्तार गुण'' द्वारा विशिष्ट रूप से परिभाषित किया गया है जो इस एल्गोरिदम की शुद्धता की प्रत्याभूति देता है: इससे कोई फर्क नहीं पड़ता कि [[प्रेरित सबग्राफ]] का हिस्सा बनने के लिए कौन से कोने पहले से ही चुने गए हैं, और इससे कोई फर्क नहीं पड़ता कि सबग्राफ को एक और शीर्ष तक विस्तारित करने के लिए आसन्नताओं के किस पैटर्न की आवश्यकता है, हमेशा आसन्न पैटर्न के साथ एक और शीर्ष मौजूद होगा जिसे ग्रीडी एल्गोरिदम चुन सकता है।
+प्रत्येक परिमित या गणनीय अनंत ग्राफ राडो ग्राफ का प्रेरित सबग्राफ है और इसे एक ग्रीडी एल्गोरिथ्म द्वारा प्रेरित सबग्राफ के रूप में पाया जा सकता है जो एक समय में शीर्ष पर सबग्राफ बनाता है। राडो ग्राफ को गणनीय ग्राफों के बीच, ''विस्तार गुण'' द्वारा विशिष्ट रूप से परिभाषित किया गया है जो इस एल्गोरिदम की शुद्धता की प्रत्याभूति देता है: इससे कोई फर्क नहीं पड़ता कि [[प्रेरित सबग्राफ]] का हिस्सा बनने के लिए कौन से कोण पहले से ही चुने गए हैं, और इससे कोई फर्क नहीं पड़ता कि सबग्राफ को एक और शीर्ष तक विस्तारित करने के लिए आसन्नताओं के किस पैटर्न की आवश्यकता है, हमेशा आसन्न पैटर्न के साथ एक और शीर्ष उपस्थित होगा जिसे ग्रीडी एल्गोरिदम चुन सकता है।
-राडो ग्राफ़ अत्यधिक सममित है: इसके परिमित प्रेरित उपसमूहों के किसी भी समरूपता को पूरे ग्राफ़ की समरूपता तक बढ़ाया जा सकता है। [[प्रथम-क्रम तर्क]] वाक्य जो राडो ग्राफ के लिए सत्य हैं, वे लगभग सभी यादृच्छिक परिमित ग्राफ के लिए भी सत्य हैं, और जो वाक्य राडो ग्राफ के लिए गलत हैं, वे लगभग सभी परिमित ग्राफ के लिए भी गलत हैं। [[मॉडल सिद्धांत]] में, राडो ग्राफ ω-वर्गीकृत सिद्धांत के अद्वितीय गणनीय मॉडल का एक उदाहरण है।
+राडो ग्राफ अत्यधिक सममित है: इसके परिमित प्रेरित उपसमूहों के किसी भी समरूपता को पूरे ग्राफ की समरूपता तक बढ़ाया जा सकता है। [[प्रथम-क्रम तर्क]] वाक्य जो राडो ग्राफ के लिए सत्य हैं, वे लगभग सभी यादृच्छिक परिमित ग्राफ के लिए भी सत्य हैं, और जो वाक्य राडो ग्राफ के लिए गलत हैं, वे लगभग सभी परिमित ग्राफ के लिए भी गलत हैं। [[मॉडल सिद्धांत]] में, राडो ग्राफ ω-वर्गीकृत सिद्धांत के अद्वितीय गणनीय मॉडल का एक उदाहरण है।
 ==इतिहास==
-राडो ग्राफ़ का निर्माण सबसे पहले एकरमैन (1937) द्वारा दो तरीकों से किया गया था, जिसमें शीर्ष या तो आनुवंशिक रूप से सीमित सेट या प्राकृतिक संख्याएँ थीं। (यथार्थ रूप से, एकरमैन ने एक [[निर्देशित ग्राफ]] का वर्णन किया है, और राडो ग्राफ किनारों पर दिशाओं को भूलकर दिया गया संबंधित अप्रत्यक्ष ग्राफ है।) एर्दो और रेनी (1963) ने राडो ग्राफ को गणनीय संख्या में बिंदुओं पर यादृच्छिक ग्राफ के रूप में बनाया है। उन्होंने साबित किया कि इसमें असीमित रूप से कई ऑटोमोर्फिज्म हैं, और उनके तर्क से यह भी पता चलता है कि यह अद्वितीय है, हालांकि उन्होंने इसका स्पष्ट रूप से उल्लेख नहीं किया। रिचर्ड राडो (1964) ने राडो ग्राफ को एक सार्वभौमिक ग्राफ के रूप में फिर से खोजा और शीर्ष पर प्राकृतिक संख्याओं को सेट करने के साथ इसका एक स्पष्ट निर्माण दिया। राडो का निर्माण अनिवार्य रूप से एकरमैन के निर्माणों में से एक के बराबर है।
+राडो ग्राफ का निर्माण सबसे पहले एकरमैन (1937) द्वारा दो विधियों से किया गया था, जिसमें शीर्ष या तो आनुवंशिक रूप से सीमित समुच्चय या प्राकृतिक संख्याएँ थीं। (यथार्थ रूप से, एकरमैन ने एक [[निर्देशित ग्राफ]] का वर्णन किया है, और राडो ग्राफ किनारों पर दिशाओं को भूलकर दिया गया संबंधित अप्रत्यक्ष ग्राफ है।) एर्दो और रेनी (1963) ने राडो ग्राफ को गणनीय संख्या में बिंदुओं पर यादृच्छिक ग्राफ के रूप में बनाया है। उन्होंने सिद्ध किया कि इसमें असीमित रूप से कई ऑटोमोर्फिज्म (स्वाकारिता) हैं, और उनके तर्क से यह भी पता चलता है कि यह अद्वितीय है, हालांकि उन्होंने इसका स्पष्ट रूप से उल्लेख नहीं किया। रिचर्ड राडो (1964) ने राडो ग्राफ को एक सार्वभौमिक ग्राफ के रूप में फिर से खोजा और शीर्ष पर प्राकृतिक संख्याओं को समुच्चय करने के साथ इसका एक स्पष्ट निर्माण दिया। राडो का निर्माण अनिवार्य रूप से एकरमैन के निर्माणों में से एक के बराबर है।
 ==निर्माण==
 ===बाइनरी संख्या===
-एकरमैन (1937) और राडो (1964) ने बीआईटी विधेय का उपयोग करते हुए राडो ग्राफ का निर्माण इस प्रकार किया। उन्होंने ग्राफ़ के शीर्षों की पहचान प्राकृतिक संख्याओं 0, 1, 2, के साथ की... एक किनारा ग्राफ़ में शीर्षों <math>x</math> और <math>y</math> को जोड़ता है (जहाँ <math>x < y</math>) जब भी <math>y</math> के द्विआधारी निरूपण का <math>x</math>वां बिट गैर-शून्य होता है। इस प्रकार, उदाहरण के लिए, शीर्ष 0 के पड़ोसियों में सभी विषम संख्या वाले शीर्ष शामिल हैं, क्योंकि जिन संख्याओं का 0वां बिट शून्येतर है, वे बिल्कुल विषम संख्याएं हैं। शीर्ष 1 का एक छोटा पड़ोसी, शीर्ष 0 है, क्योंकि 1 विषम है और शीर्ष 0 सभी विषम शीर्षों से जुड़ा है। शीर्ष 1 के बड़े पड़ोसी वे सभी शीर्ष हैं जिनकी संख्याएँ 2 या 3 मॉड्यूल 4 के अनुरूप हैं क्योंकि वे बिल्कुल सूचकांक 1 पर एक गैर-शून्य बिट वाली संख्याएँ हैं।<ref>{{harvtxt|Ackermann|1937}}; {{harvtxt|Rado|1964}}.</ref>
+एकरमैन (1937) और राडो (1964) ने बीआईटी विधेय का उपयोग करते हुए राडो ग्राफ का निर्माण इस प्रकार किया। उन्होंने ग्राफ के शीर्षों की पहचान प्राकृतिक संख्याओं 0, 1, 2, के साथ की... एक कोर ग्राफ में शीर्षों <math>x</math> और <math>y</math> को जोड़ता है (जहाँ <math>x < y</math>) जब भी <math>y</math> के द्विआधारी निरूपण का <math>x</math>वां बिट गैर-शून्य होता है। इस प्रकार, उदाहरण के लिए, शीर्ष 0 के प्रतिवेश में सभी विषम संख्या वाले शीर्ष सम्मिलित हैं, क्योंकि जिन संख्याओं का 0वां बिट शून्येतर है, वे बिल्कुल विषम संख्याएं हैं। शीर्ष 1 का एक छोटा प्रतिवेश, शीर्ष 0 है, क्योंकि 1 विषम है और शीर्ष 0 सभी विषम शीर्षों से जुड़ा है। शीर्ष 1 के बड़े प्रतिवेश वे सभी शीर्ष हैं जिनकी संख्याएँ 2 या 3 मॉड्यूल 4 के अनुरूप हैं क्योंकि वे बिल्कुल सूचकांक 1 पर एक गैर-शून्य बिट वाली संख्याएँ हैं।<ref>{{harvtxt|Ackermann|1937}}; {{harvtxt|Rado|1964}}.</ref>
 ===यादृच्छिक ग्राफ===
-राडो ग्राफ़ लगभग निश्चित रूप से कई शीर्षों पर एक यादृच्छिक ग्राफ़ के एर्डो-रेनी मॉडल में उत्पन्न होता है। विशेष रूप से, कोई व्यक्ति स्वतंत्र रूप से और शीर्षों के प्रत्येक जोड़े के लिए 1/2 संभावना के साथ यह चुनकर एक अनंत ग्राफ बना सकता है कि दोनों शीर्षों को एक किनारे से जोड़ना है या नहीं। प्रायिकता 1 के साथ परिणामी ग्राफ़ राडो ग्राफ़ के समरूपी है। यह निर्माण तब भी काम करता है जब 1/2 के स्थान पर कोई निश्चित संभाव्यता p जो 0 या 1 के बराबर न हो, का उपयोग किया जाता है।<ref name="binary-extension">See {{harvtxt|Cameron|1997}}, Fact 1 and its proof.</ref>
+राडो ग्राफ लगभग निश्चित रूप से कई शीर्षों पर एक यादृच्छिक ग्राफ के एर्डो-रेनी मॉडल में बना होता है। विशेष रूप से, कोई व्यक्ति स्वतंत्र रूप से और शीर्षों के प्रत्येक जोड़े के लिए 1/2 संभावना के साथ यह चुनकर एक अनंत ग्राफ बना सकता है कि दोनों शीर्षों को एक कोर से जोड़ना है या नहीं। प्रायिकता 1 के साथ परिणामी ग्राफ राडो ग्राफ के समरूपी है। यह निर्माण तब भी काम करता है जब 1/2 के स्थान पर कोई निश्चित संभाव्यता p जो 0 या 1 के बराबर न हो, का उपयोग किया जाता है।<ref name="binary-extension">See {{harvtxt|Cameron|1997}}, Fact 1 and its proof.</ref>
-पॉल एर्डोज़ और अल्फ़्रेड रेनी (1963) द्वारा दिखाया गया यह परिणाम, राडो ग्राफ़ के लिए सामान्य वैकल्पिक नाम "यादृच्छिक ग्राफ़" में निश्चित लेख को सही ठहराता है। एर्दो-रेनी मॉडल से बार-बार एक परिमित ग्राफ खींचने से आम तौर पर अलग-अलग ग्राफ बनेंगे; हालाँकि, जब एक गणनीय अनंत ग्राफ़ पर लागू किया जाता है, तो मॉडल लगभग हमेशा एक ही अनंत ग्राफ़ उत्पन्न करता है।{{sfnp|Erdős|Rényi|1963}}
+पॉल एर्डोज़ और अल्फ़्रेड रेनी (1963) द्वारा दिखाया गया यह परिणाम, राडो ग्राफ के लिए सामान्य वैकल्पिक नाम "यादृच्छिक ग्राफ" में निश्चित लेख को सही ठहराता है। एर्दो-रेनी मॉडल से बार-बार एक परिमित ग्राफ खींचने से सामान्यतः अलग-अलग ग्राफ बनेंगे; हालाँकि, जब एक गणनीय अनंत ग्राफ पर प्रयुक्त किया जाता है, तो मॉडल लगभग हमेशा एक ही अनंत ग्राफ बना करता है।{{sfnp|Erdős|Rényi|1963}}
-इस तरह से बेतरतीब ढंग से उत्पन्न किसी भी ग्राफ के लिए, सभी विकल्पों को उलट कर एक ही समय में पूरक ग्राफ प्राप्त किया जा सकता है: एक किनारे सहित जब पहले ग्राफ़ में समान किनारा शामिल नहीं था, और इसके विपरीत। पूरक ग्राफ़ का यह निर्माण यादृच्छिक रूप से और स्वतंत्र रूप से यह चुनने की उसी प्रक्रिया का एक उदाहरण है कि प्रत्येक किनारे को शामिल किया जाए या नहीं, इसलिए यह (संभावना 1 के साथ) राडो ग्राफ़ भी उत्पन्न करता है। इसलिए, राडो ग्राफ एक स्व-पूरक ग्राफ है।<ref>{{harvtxt|Cameron|1997}}, Proposition 5.</ref>
+इस तरह से यादृच्छिक रूप से बने किसी भी ग्राफ के लिए, सभी विकल्पों को विपरीत कर एक ही समय में पूरक ग्राफ प्राप्त किया जा सकता है: एक कोर सहित जब पहले ग्राफ में समान कोर सम्मिलित नहीं थी, और इसके विपरीत पूरक ग्राफ का यह निर्माण यादृच्छिक रूप से और स्वतंत्र रूप से यह चुनने की उसी प्रक्रिया का एक उदाहरण है कि प्रत्येक कोर को सम्मिलित किया जाए या नहीं, इसलिए यह (संभावना 1 के साथ) राडो ग्राफ भी बनाता है। इसलिए, राडो ग्राफ एक स्व-पूरक ग्राफ है।<ref>{{harvtxt|Cameron|1997}}, Proposition 5.</ref>
 ===अन्य रचनाएं===
-एकरमैन के 1937 के मूल निर्माणों में से एक में, राडो ग्राफ के शीर्षों को आनुवंशिक रूप से परिमित सेटों द्वारा अनुक्रमित किया जाता है, और दो शीर्षों के बीच एक किनारा होता है, ठीक उसी समय जब संबंधित परिमित सेटों में से एक दूसरे का सदस्य होता है। एक समान निर्माण स्कोलेम के विरोधाभास पर आधारित हो सकता है, यह तथ्य कि सेट के प्रथम-क्रम सिद्धांत के लिए एक गणनीय मॉडल मौजूद है। प्रत्येक सेट के लिए एक शीर्ष बनाकर, ऐसे मॉडल से राडो ग्राफ का निर्माण किया जा सकता है, जिसमें सेट की प्रत्येक जोड़ी को जोड़ने वाला एक किनारा होता है, जहां जोड़ी में एक सेट दूसरे का सदस्य होता है।<ref>{{harvtxt|Cameron|1997}}, Theorem 2.</ref>
+एकरमैन के 1937 के मूल निर्माणों में से एक में, राडो ग्राफ के शीर्षों को आनुवंशिक रूप से परिमित समुच्चय द्वारा अनुक्रमित किया जाता है, और दो शीर्षों के बीच एक कोर होता है, ठीक उसी समय जब संबंधित परिमित समुच्चय में से एक दूसरे का सदस्य होता है। समान निर्माण स्कोलेम के विरोधाभास पर आधारित हो सकता है, यह तथ्य कि समुच्चय के प्रथम-क्रम सिद्धांत के लिए एक गणनीय मॉडल उपस्थित है। प्रत्येक समुच्चय के लिए एक शीर्ष बनाकर, ऐसे मॉडल से राडो ग्राफ का निर्माण किया जा सकता है, जिसमें समुच्चय की प्रत्येक जोड़ी को जोड़ने वाला एक कोर होता है, जहां जोड़ी में एक समुच्चय दूसरे का सदस्य होता है।<ref>{{harvtxt|Cameron|1997}}, Theorem 2.</ref>
-राडो ग्राफ का निर्माण पाले ग्राफ के सदृश एक निर्माण द्वारा भी किया जा सकता है, जिसमें सभी अभाज्य संख्याओं को एक ग्राफ के शीर्ष के रूप में लिया जाता है जो 1 मॉड्यूलो 4 के अनुरूप होते हैं, और जब भी दो संख्याओं में से एक द्विघात अवशेष मॉड्यूलो अन्य होता है तो दो शीर्षों को एक किनारे से जोड़ते हैं। द्विघात पारस्परिकता और 1 मॉड 4 के अनुरूप अभाज्य संख्याओं के शीर्षों के प्रतिबंध द्वारा, यह एक [[सममित संबंध]] है, इसलिए यह एक अप्रत्यक्ष ग्राफ को परिभाषित करता है, जो राडो ग्राफ के लिए समरूपी हो जाता है।<ref name="paley" />
+राडो ग्राफ का निर्माण पाले ग्राफ के सदृश एक निर्माण द्वारा भी किया जा सकता है, जिसमें सभी अभाज्य संख्याओं को एक ग्राफ के शीर्ष के रूप में लिया जाता है जो 1 मॉड्यूलो 4 के अनुरूप होते हैं, और जब भी दो संख्याओं में से एक द्विघात अवशेष मॉड्यूलो अन्य होता है तो दो शीर्षों को एक कोर से जोड़ते हैं। द्विघात पारस्परिकता और 1 मॉड 4 के अनुरूप अभाज्य संख्याओं के शीर्षों के प्रतिबंध द्वारा, यह एक [[सममित संबंध]] है, इसलिए यह एक अप्रत्यक्ष ग्राफ को परिभाषित करता है, जो राडो ग्राफ के लिए समरूपी हो जाता है।<ref name="paley" />
-राडो ग्राफ के एक अन्य निर्माण से पता चलता है कि यह एक अनंत परिचालित ग्राफ है, जिसके शीर्ष पूर्णांक हैं और प्रत्येक दो पूर्णांकों के बीच एक किनारा है, जिनकी दूरी (उनके अंतर का पूर्ण मान) एक विशेष सेट <math>S</math> से संबंधित है। इस तरह से राडो ग्राफ का निर्माण करने के लिए, <math>S</math> को यादृच्छिक रूप से चुना जा सकता है, या सभी परिमित बाइनरी अनुक्रमों के संयोजन के लिए <math>S</math> के संकेतक फ़ंक्शन को चुनकर।<ref>{{harvtxt|Cameron|1997}}, Section 1.2.</ref>
+राडो ग्राफ के एक अन्य निर्माण से पता चलता है कि यह एक अनंत परिचालित ग्राफ है, जिसके शीर्ष पूर्णांक हैं और प्रत्येक दो पूर्णांकों के बीच एक कोर है, जिनकी दूरी (उनके अंतर का पूर्ण मान) एक विशेष समुच्चय <math>S</math> से संबंधित है। इस तरह से राडो ग्राफ का निर्माण करने के लिए, <math>S</math> को यादृच्छिक रूप से , या सभी परिमित बाइनरी अनुक्रमों के संयोजन के लिए <math>S</math> के संकेतक फलन को चुनकर चुना जा सकता है।<ref>{{harvtxt|Cameron|1997}}, Section 1.2.</ref>
-राडो ग्राफ़ को एक अनंत ब्लॉक डिज़ाइन के ब्लॉक प्रतिच्छेदन ग्राफ़ के रूप में भी बनाया जा सकता है जिसमें बिंदुओं की संख्या और प्रत्येक ब्लॉक का आकार अनगिनत रूप से अनंत होता है।<ref>{{harvtxt|Horsley|Pike|Sanaei|2011}}</ref> इसे परिमित ग्राफ़ के वर्ग की फ़्रैसे सीमा के रूप में भी बनाया जा सकता है।{{sfnp|Hodges|1997|p=350}}
+राडो ग्राफ को एक अनंत ब्लॉक डिज़ाइन के ब्लॉक प्रतिच्छेदन ग्राफ के रूप में भी बनाया जा सकता है जिसमें बिंदुओं की संख्या और प्रत्येक ब्लॉक का आकार अनगिनत रूप से अनंत होता है।<ref>{{harvtxt|Horsley|Pike|Sanaei|2011}}</ref> इसे परिमित ग्राफ के वर्ग की फ़्रैसे सीमा के रूप में भी बनाया जा सकता है।{{sfnp|Hodges|1997|p=350}}
 ==गुण==
 ===विस्तार===
-[[File:Rado extension.svg|thumb|upright=1.35|राडो ग्राफ़ का विस्तार गुण: शीर्षों के प्रत्येक दो असंयुक्त परिमित सेटों के लिए <math>U</math> और <math>V</math>, वहाँ एक और शिखर मौजूद है <math>x</math> में हर चीज़ से जुड़ा हुआ है <math>U</math>, और अंदर कुछ भी नहीं <math>V</math>]]राडो ग्राफ़ निम्नलिखित विस्तार गुण को संतुष्ट करता है: शीर्ष <math>U</math> और <math>V</math> के प्रत्येक दो असंयुक्त परिमित सेटों के लिए, दोनों सेटों के बाहर एक शीर्ष <math>x</math> मौजूद होता है जो <math>U</math> में सभी शीर्षों से जुड़ा होता है लेकिन <math>V</math> में कोई पड़ोसी नहीं होता है।<ref name="binary-extension"/> उदाहरण के लिए, राडो ग्राफ़ की द्विआधारी-संख्या परिभाषा के साथ, आइए
+[[File:Rado extension.svg|thumb|upright=1.35|राडो ग्राफ का विस्तार गुण: शीर्षों के प्रत्येक दो असंयुक्त परिमित समुच्चय के लिए <math>U</math> और <math>V</math>, वहाँ एक और शिखर उपस्थित है <math>x</math> में हर चीज़ से जुड़ा हुआ है <math>U</math>, और अंदर कुछ भी नहीं <math>V</math>]]राडो ग्राफ निम्नलिखित विस्तार गुण को संतुष्ट करता है: शीर्ष <math>U</math> और <math>V</math> के प्रत्येक दो असंयुक्त परिमित समुच्चय के लिए, दोनों समुच्चय के बाहर एक शीर्ष <math>x</math> उपस्थित होता है जो <math>U</math> में सभी शीर्षों से जुड़ा होता है लेकिन <math>V</math> में कोई प्रतिवेश नहीं होता है।<ref name="binary-extension"/> उदाहरण के लिए, राडो ग्राफ की द्विआधारी-संख्या परिभाषा के साथ, आइए
-<math display="block">x=2^{1+\max(U\cup V)} + \sum_{u\in U} 2^u.</math>फिर x के द्विआधारी प्रतिनिधित्व में गैर-शून्य बिट्स के कारण यह <math>U</math> में हर चीज के निकट होता है। हालाँकि, <math>x</math> के पास <math>V</math> में शीर्षों के अनुरूप अपने द्विआधारी प्रतिनिधित्व में कोई गैर-शून्य बिट्स नहीं है, और <math>x</math> इतना बड़ा है कि <math>V</math> के प्रत्येक तत्व का <math>x</math> बिट शून्य है। इस प्रकार, <math>x</math>, <math>V</math> में किसी भी शीर्ष के निकट नहीं है।<ref>Essentially the same construction, described in set-theoretic terms rather than using binary numbers, is given as Theorem 2 of {{harvtxt|Cameron|1997}}.</ref>
+<math display="block">x=2^{1+\max(U\cup V)} + \sum_{u\in U} 2^u.</math>फिर x के द्विआधारी प्रतिनिधित्व में गैर-शून्य बिट्स के कारण यह <math>U</math> में हर चीज के निकट होता है। हालाँकि, <math>x</math> के पास <math>V</math> में शीर्षों के अनुरूप अपने द्विआधारी प्रतिनिधित्व में कोई गैर-शून्य बिट्स नहीं है, और <math>x</math> इतना अधिक है कि <math>V</math> के प्रत्येक अवयव का <math>x</math> बिट शून्य है। इस प्रकार, <math>x</math>, <math>V</math> में किसी भी शीर्ष के निकट नहीं है।<ref>Essentially the same construction, described in set-theoretic terms rather than using binary numbers, is given as Theorem 2 of {{harvtxt|Cameron|1997}}.</ref>
+राडो ग्राफ की यादृच्छिक-ग्राफ परिभाषा के साथ, <math>U</math> और <math>V</math> के संघ के बाहर प्रत्येक शीर्ष की संभावना <math>1/2^{|U|+|V|}</math>विस्तार गुण को पूरा करने के लिए, अन्य शीर्षों से स्वतंत्र रूप से है। चूँकि चुनने के लिए अनंत रूप से कई शीर्ष हैं, प्रत्येक की सफलता की समान सीमित संभावना है, संभावना यह है कि एक शीर्ष उपस्थित है जो विस्तार गुण को पूरा करता है।<ref name="binary-extension" /> पेली ग्राफ परिभाषा के साथ, चीनी शेषफल प्रमेय के अनुसार, किसी भी समुच्चय <math>U</math>और <math>V</math> के लिए, वे संख्याएँ जो <math>U</math> में प्रत्येक अभाज्य के द्विघात अवशेष मॉड्यूलो हैं और <math>V</math> में प्रत्येक अभाज्य गैर-अवशेष मॉड्यूलो हैं, एक आवधिक अनुक्रम बनाते हैं, इसलिए अंकगणितीय प्रगति में अभाज्य पर डिरिक्लेट के प्रमेय के अनुसार इस संख्या-सैद्धांतिक ग्राफ में विस्तार गुण है।<ref name="paley">{{harvs|last=Cameron|year=1997|year2=2001|txt}}</ref>
-राडो ग्राफ़ की यादृच्छिक-ग्राफ़ परिभाषा के साथ, <math>U</math> और <math>V</math> के मिलन के बाहर प्रत्येक शीर्ष की संभावना <math>1/2^{|U|+|V|}</math>अन्य शीर्षों से स्वतंत्र रूप से, विस्तार गुण को पूरा करने का। चूँकि चुनने के लिए अनंत रूप से कई शीर्ष हैं, प्रत्येक की सफलता की समान सीमित संभावना है, संभावना यह है कि एक शीर्ष मौजूद है जो विस्तार गुण को पूरा करता है।<ref name="binary-extension" /> पेली ग्राफ परिभाषा के साथ, चीनी शेषफल प्रमेय के अनुसार, किसी भी सेट <math>U</math>और <math>V</math> के लिए, वे संख्याएँ जो <math>U</math> में प्रत्येक अभाज्य के द्विघात अवशेष मॉड्यूलो हैं और <math>V</math> में प्रत्येक अभाज्य गैर-अवशेष मॉड्यूलो हैं, एक आवधिक अनुक्रम बनाते हैं, इसलिए अंकगणितीय प्रगति में अभाज्य पर डिरिक्लेट के प्रमेय के अनुसार इस संख्या-सैद्धांतिक ग्राफ में विस्तार गुण है।<ref name="paley">{{harvs|last=Cameron|year=1997|year2=2001|txt}}</ref>
 ===प्रेरित सबग्राफ===
-विस्तार गुण का उपयोग राडो ग्राफ के भीतर किसी भी परिमित या गणनीय अनंत ग्राफ <math>G</math> की आइसोमोर्फिक प्रतियों को प्रेरित सबग्राफ के रूप में बनाने के लिए किया जा सकता है। ऐसा करने के लिए, <math>G</math> के शीर्षों को क्रमबद्ध करें, और राडो ग्राफ़ के भीतर <math>G</math> की आंशिक प्रतिलिपि में उसी क्रम में शीर्ष जोड़ें। प्रत्येक चरण में, <math>G</math> में अगला शीर्ष <math>G</math> में शीर्षों के कुछ सेट <math>U</math> के निकट होगा जो कि शीर्षों के क्रम में पहले हैं, और <math>G</math> में पहले के शीर्षों के शेष सेट <math>V</math> के निकट नहीं होगा। विस्तार गुण के अनुसार, राडो ग्राफ में एक शीर्ष <math>x</math> भी होगा जो आंशिक प्रतिलिपि में सभी शीर्षों के समीप है जो <math>U</math> के सदस्यों के अनुरूप है, और आंशिक प्रतिलिपि में सभी शीर्षों के निकट नहीं है जो <math>V</math> के सदस्यों के अनुरूप है। की आंशिक प्रतिलिपि में <math>x</math> जोड़ना <math>G</math> एक और शीर्ष के साथ, एक बड़ी आंशिक प्रतिलिपि तैयार करता है।[<ref name="induced">{{harvtxt|Cameron|1997}}, Proposition 6.</ref>
+विस्तार गुण का उपयोग राडो ग्राफ के भीतर किसी भी परिमित या गणनीय अनंत ग्राफ <math>G</math> की समरूपी प्रतियों को प्रेरित सबग्राफ के रूप में बनाने के लिए किया जा सकता है। ऐसा करने के लिए, <math>G</math> के शीर्षों को क्रमबद्ध करें, और राडो ग्राफ के भीतर <math>G</math> की आंशिक प्रतिलिपि में उसी क्रम में शीर्ष जोड़ें। प्रत्येक चरण में, <math>G</math> में अगला शीर्ष <math>G</math> में शीर्षों के कुछ समुच्चय <math>U</math> के निकट होगा जो कि शीर्षों के क्रम में पहले हैं, और <math>G</math> में पहले के शीर्षों के शेष समुच्चय <math>V</math> के निकट नहीं होगा। विस्तार गुण के अनुसार, राडो ग्राफ में एक शीर्ष <math>x</math> भी होगा जो आंशिक प्रतिलिपि में सभी शीर्षों के समीप है जो <math>U</math> के सदस्यों के अनुरूप है, और आंशिक प्रतिलिपि में सभी शीर्षों के निकट नहीं है जो <math>V</math> के सदस्यों के अनुरूप है। की आंशिक प्रतिलिपि में <math>x</math> जोड़ना <math>G</math> एक और शीर्ष के साथ, एक बड़ी आंशिक प्रतिलिपि तैयार करता है।[<ref name="induced">{{harvtxt|Cameron|1997}}, Proposition 6.</ref>
-यह विधि प्रेरण द्वारा प्रमाण के लिए आधार बनाती है, इसके आधार मामले के रूप में 0-वर्टेक्स सबग्राफ के साथ, कि प्रत्येक परिमित या गणनीय अनंत ग्राफ राडो ग्राफ का एक प्रेरित सबग्राफ है।<ref name="induced" />
+यह विधि प्रेरण द्वारा प्रमाण के लिए आधार बनाती है, इसके आधार स्तिथि के रूप में 0-वर्टेक्स सबग्राफ के साथ, कि प्रत्येक परिमित या गणनीय अनंत ग्राफ राडो ग्राफ का एक प्रेरित सबग्राफ है।<ref name="induced" />
 ===अद्वितीयता===
-रैडो ग्राफ़, ग्राफ़ समरूपता तक, विस्तार गुण वाला एकमात्र गणनीय ग्राफ़ है। उदाहरण के लिए, चलो <math>G</math> और <math>H</math> विस्तार गुण के साथ दो गणनीय ग्राफ़ हों, मान लीजिए <math>G_i</math> और <math>H_i</math> समरूपी परिमित प्रेरित उपसमूह बनें <math>G</math> और <math>H</math> क्रमशः, और चलो <math>g_i</math> और <math>h_i</math> के शीर्षों की गणना में पहला शीर्ष बनें <math>G</math> और <math>H</math> क्रमशः जो संबंधित नहीं हैं <math>G_i</math> और <math>H_i</math>. फिर, विस्तार गुण को दो बार लागू करके, कोई आइसोमोर्फिक प्रेरित सबग्राफ पा सकता है <math>G_{i+1}</math> और <math>H_{i+1}</math> यह शामिल <math>g_i</math> और <math>h_i</math> पिछले सबग्राफ़ के सभी शीर्षों के साथ। इस प्रक्रिया को दोहराकर, कोई प्रेरित उपसमूहों के बीच समरूपता का एक क्रम बना सकता है जिसमें अंततः प्रत्येक शीर्ष शामिल होता है <math>G</math> और <math>H</math>. इस प्रकार, आगे-पीछे विधि द्वारा, <math>G</math> और <math>H</math> समरूपी होना चाहिए.<ref name="cam">{{harvtxt|Cameron|2001}}.</ref>
+रैडो ग्राफ, ग्राफ समरूपता तक, विस्तार गुण वाला एकमात्र गणनीय ग्राफ है। उदाहरण के लिए, मान लीजिए कि <math>G</math> और <math>H</math> विस्तार गुण वाले दो गणनीय ग्राफ हैं, मान लीजिए <math>G_i</math>और <math>H_i</math> क्रमशः <math>G</math> और <math>H</math> के समरूपी परिमित प्रेरित सबग्राफ हैं, और मान लीजिए कि <math>g_i</math>और <math>h_i</math> क्रमशः <math>G</math> और <math>H</math> के शीर्षों की गणना में पहले शीर्ष हैं जो <math>G_i</math> और <math>H_i</math> से संबंधित नहीं हैं। फिर, विस्तार गुण को दो बार प्रयुक्त करके, कोई समरूपी-प्रेरित सबग्राफ <math>G_{i+1}</math>और <math>H_{i+1}</math>पा सकता है जिसमें पिछले सबग्राफ के सभी शीर्षों के साथ <math>g_i</math> और सम्मिलित हैं। इस प्रक्रिया को दोहराकर, कोई प्रेरित उपसमूहों के बीच समरूपता का एक क्रम बना सकता है जिसमें अंततः <math>G</math> और <math>H</math> में प्रत्येक शीर्ष सम्मिलित होता है। इस प्रकार, आगे-पीछे विधि द्वारा, <math>G</math> और <math>H</math> को समरूपी होना चाहिए।<ref name="cam">{{harvtxt|Cameron|2001}}.</ref> चूँकि यादृच्छिक ग्राफ निर्माण, बाइनरी संख्या निर्माण और पैली ग्राफ निर्माण द्वारा निर्मित ग्राफ सभी विस्तार गुण के साथ गणनीय ग्राफ हैं, यह तर्क दर्शाता है कि वे सभी एक दूसरे के लिए समरूपी हैं।<ref>{{harvtxt|Cameron|1997}}, Fact 2.</ref>
-क्योंकि यादृच्छिक ग्राफ़ निर्माण, बाइनरी संख्या निर्माण, और पैली ग्राफ़ निर्माण द्वारा निर्मित ग्राफ़ सभी विस्तार गुण के साथ गणनीय ग्राफ़ हैं, यह तर्क दर्शाता है कि वे सभी एक दूसरे के लिए आइसोमोर्फिक हैं।<ref>{{harvtxt|Cameron|1997}}, Fact 2.</ref>
 ===समरूपता समूह===
-राडो ग्राफ़ के किन्हीं दो समरूपी परिमित उपसमूहों के आगे-पीछे निर्माण को लागू करने से उनकी समरूपता पूरे राडो ग्राफ़ के एक [[ग्राफ ऑटोमोर्फिज्म]] तक विस्तारित हो जाती है। तथ्य यह है कि परिमित उपग्राफों की प्रत्येक समरूपता पूरे ग्राफ के ऑटोमोर्फिज्म तक फैली हुई है, यह कहकर व्यक्त किया जाता है कि राडो ग्राफ [[सजातीय ग्राफ]] है। विशेष रूप से, आसन्न शीर्षों के किसी भी क्रमित जोड़े को ऐसे किसी अन्य क्रमित जोड़े में ले जाने वाली एक ऑटोमोर्फिज्म होती है, इसलिए राडो ग्राफ एक [[सममित ग्राफ]] है।<ref name="cam"/>
+राडो ग्राफ के किन्हीं दो समरूपी परिमित उपसमूहों के आगे-पीछे निर्माण को प्रयुक्त करने से उनकी समरूपता पूरे राडो ग्राफ के एक [[ग्राफ ऑटोमोर्फिज्म]] तक विस्तारित हो जाती है। तथ्य यह है कि परिमित उपग्राफों की प्रत्येक समरूपता पूरे ग्राफ के ऑटोमोर्फिज्म तक फैली हुई है, यह कहकर व्यक्त किया जाता है कि राडो ग्राफ [[सजातीय ग्राफ]] है। विशेष रूप से, आसन्न शीर्षों के किसी भी क्रमित जोड़े को ऐसे किसी अन्य क्रमित जोड़े में ले जाने वाली एक ऑटोमोर्फिज्म होती है, इसलिए राडो ग्राफ एक [[सममित ग्राफ]] है।<ref name="cam"/>
-राडो ग्राफ का [[ऑटोमोर्फिज्म समूह]] एक [[सरल समूह]] है, जिसके तत्वों की संख्या [[सातत्य की प्रमुखता]] है। इस समूह का प्रत्येक [[उपसमूह]], जिसके उपसमूह का सूचकांक सातत्य की कार्डिनैलिटी से कम है, में शीर्षों के एक सीमित सेट का बिंदुवार स्टेबलाइजर होता है, और इसके अलावा उसी सेट के सेटवाइज स्टेबलाइजर के भीतर समाहित होता है।<ref name = "cam2">{{harvtxt|Cameron|1997}}, Section 1.8: The automorphism group.</ref> बिंदुवार स्टेबिलाइजर्स के बारे में बयान को लघु सूचकांक गुण कहा जाता है,<ref name= "cam2"/>और इसे साबित करने के लिए प्रत्येक परिमित ग्राफ़ के लिए इसे दिखाना आवश्यक है <math>X</math>, एक परिमित ग्राफ है <math>Z</math> युक्त <math>X</math> एक प्रेरित सबग्राफ के रूप में, जैसे कि प्रेरित सबग्राफ के बीच प्रत्येक समरूपता <math>X</math> की ऑटोमोर्फिज्म तक फैली हुई है <math>Z</math>.<ref>{{harvtxt|Hrushovski|1992}}</ref> इसे आंशिक ऑटोमोर्फिज्म के लिए विस्तार गुण कहा जाता है और तब से छोटी सूचकांक गुण और अन्य गुणों को दिखाने के लिए इसे आगे की संरचनाओं में सामान्यीकृत किया गया है।<ref>{{harvtxt|Macpherson|2011}}, Sections 5.2 and 5.3.</ref>
+राडो ग्राफ का [[ऑटोमोर्फिज्म समूह]] एक [[सरल समूह]] है, जिसके अवयवों की संख्या [[सातत्य की प्रमुखता]] है। इस समूह का प्रत्येक [[उपसमूह]], जिसके उपसमूह का सूचकांक सातत्य की प्रमुखता से कम है, में शीर्षों के एक सीमित समुच्चय का बिंदुवार स्टेबलाइजर होता है, और इसके अलावा उसी समुच्चय के सेटवाइज स्टेबलाइजर के भीतर समाहित होता है।<ref name = "cam2">{{harvtxt|Cameron|1997}}, Section 1.8: The automorphism group.</ref> बिंदुवार स्टेबिलाइजर्स के बारे में बयान को लघु सूचकांक गुण कहा जाता है,<ref name= "cam2"/>और इसे सिद्ध करने के लिए प्रत्येक परिमित ग्राफ के लिए इसे दिखाना आवश्यक है <math>X</math>, एक परिमित ग्राफ है <math>Z</math> युक्त <math>X</math> एक प्रेरित सबग्राफ के रूप में, जैसे कि प्रेरित सबग्राफ के बीच प्रत्येक समरूपता <math>X</math> की ऑटोमोर्फिज्म तक फैली हुई है <math>Z</math>.<ref>{{harvtxt|Hrushovski|1992}}</ref> इसे आंशिक ऑटोमोर्फिज्म के लिए विस्तार गुण कहा जाता है और तब से छोटी सूचकांक गुण और अन्य गुणों को दिखाने के लिए इसे आगे की संरचनाओं में सामान्यीकृत किया गया है।<ref>{{harvtxt|Macpherson|2011}}, Sections 5.2 and 5.3.</ref>
-एक अनंत वृत्ताकार ग्राफ के रूप में राडो ग्राफ के निर्माण से पता चलता है कि इसके समरूपता समूह में ऑटोमोर्फिज्म शामिल हैं जो एक संक्रमणीय [[अनंत चक्रीय समूह]] उत्पन्न करते हैं। इस निर्माण के अंतर सेट (आसन्न शीर्षों के बीच पूर्णांकों में दूरियों का सेट) को इस निर्माण की शुद्धता को प्रभावित किए बिना, अंतर 1 को शामिल करने के लिए बाध्य किया जा सकता है, जिससे यह पता चलता है कि राडो ग्राफ में एक अनंत [[हैमिल्टनियन पथ]] होता है जिसकी समरूपता पूरे ग्राफ की समरूपता का एक उपसमूह है।{{sfnp|Henson|1971}}
-===परिमित परिवर्तनों के विरुद्ध मजबूती===
+एक अनंत वृत्ताकार ग्राफ के रूप में राडो ग्राफ के निर्माण से पता चलता है कि इसके समरूपता समूह में ऑटोमोर्फिज्म सम्मिलित हैं जो एक संक्रमणीय [[अनंत चक्रीय समूह]] उत्पन्न करते हैं। इस निर्माण के अंतर समुच्चय (आसन्न शीर्षों के बीच पूर्णांकों में दूरियों का समुच्चय) को इस निर्माण की शुद्धता को प्रभावित किए बिना, अंतर 1 को सम्मिलित करने के लिए बाध्य किया जा सकता है, जिससे यह पता चलता है कि राडो ग्राफ में एक अनंत [[हैमिल्टनियन पथ]] होता है जिसकी समरूपता पूरे ग्राफ की समरूपता का एक उपसमूह है।{{sfnp|Henson|1971}}
-यदि एक ग्राफ <math>G</math> राडो ग्राफ़ से किसी भी सीमित संख्या में किनारों या शीर्षों को हटाकर, या किनारों की एक सीमित संख्या जोड़कर बनाया जाता है, परिवर्तन ग्राफ़ की विस्तार गुण को प्रभावित नहीं करता है। सेट की किसी भी जोड़ी के लिए <math>U</math> और <math>V</math> संशोधित ग्राफ़ में एक शीर्ष खोजना अभी भी संभव है जो कि हर चीज़ के निकट है <math>U</math> और हर चीज़ से असन्निकट <math>V</math>, के संशोधित भागों को जोड़कर <math>G</math> को <math>V</math> और असंशोधित राडो ग्राफ़ में एक्सटेंशन प्रॉपर्टी को लागू करना। इसलिए, इस प्रकार के किसी भी सीमित संशोधन के परिणामस्वरूप एक ग्राफ बनता है जो राडो ग्राफ के समरूपी होता है।<ref>{{harvtxt|Cameron|1997}}, Section 1.3: Indestructibility.</ref>
+===परिमित परिवर्तनों के प्रति दृढ़ता===
+यदि एक ग्राफ <math>G</math> राडो ग्राफ से किसी भी सीमित संख्या में किनारों या शीर्षों को हटाकर, या किनारों की एक सीमित संख्या जोड़कर बनाया जाता है, परिवर्तन ग्राफ की विस्तार गुण को प्रभावित नहीं करता है। समुच्चय की किसी भी जोड़ी के लिए <math>U</math> और <math>V</math> संशोधित ग्राफ में एक शीर्ष खोजना अभी भी संभव है जो कि हर चीज़ के निकट है <math>U</math> और हर चीज़ से असन्निकट <math>V</math>, के संशोधित भागों को जोड़कर <math>G</math> को <math>V</math> और असंशोधित राडो ग्राफ में विस्तार गुण को प्रयुक्त करना। इसलिए, इस प्रकार के किसी भी सीमित संशोधन के परिणामस्वरूप एक ग्राफ बनता है जो राडो ग्राफ के समरूपी होता है।<ref>{{harvtxt|Cameron|1997}}, Section 1.3: Indestructibility.</ref>
 ===विभाजन===
-राडो ग्राफ़ के शीर्षों के किसी भी विभाजन के लिए दो सेटों में <math>A</math> और <math>B</math>, या अधिक आम तौर पर किसी भी विभाजन के लिए सीमित रूप से कई उपसमूहों में, विभाजन सेटों में से एक द्वारा प्रेरित उपग्राफ़ों में से कम से कम एक पूरे राडो ग्राफ़ के लिए आइसोमोर्फिक है। {{harvtxt|Cameron|2001}} निम्नलिखित संक्षिप्त प्रमाण देता है: यदि कोई भी भाग राडो ग्राफ़ में सबग्राफ़ आइसोमॉर्फिक को प्रेरित नहीं करता है, तो वे सभी विस्तार गुण रखने में विफल हो जाते हैं, और कोई भी सेट के जोड़े पा सकता है <math>U_i</math> और <math>V_i</math> जिसे प्रत्येक सबग्राफ के भीतर विस्तारित नहीं किया जा सकता है। लेकिन फिर, सेट का मिलन <math>U_i</math> और सेट का मिलन <math>V_i</math> एक ऐसा सेट बनेगा जिसे पूरे ग्राफ़ में विस्तारित नहीं किया जा सकता है, जो राडो ग्राफ़ की विस्तार गुण का खंडन करता है। किसी भी विभाजन के प्रेरित उपग्राफों में से एक के समरूपी होने की यह गुण केवल तीन गणनीय अनंत अप्रत्यक्ष ग्राफ़ द्वारा आयोजित की जाती है: राडो ग्राफ़, पूर्ण ग्राफ़, और खाली ग्राफ़।<ref>{{harvtxt|Cameron|1990}}; {{harvtxt|Diestel|Leader|Scott|Thomassé|2007}}.</ref> {{harvtxt|Bonato|Cameron|Delić|2000}} और {{harvtxt|Diestel|Leader|Scott|Thomassé|2007}} समान विभाजन गुण के साथ अनंत निर्देशित ग्राफ़ की जांच करें; सभी पूर्ण ग्राफ़ या राडो ग्राफ़ के किनारों के लिए अभिविन्यास चुनकर बनाए जाते हैं।
+राडो ग्राफ के शीर्षों के किसी भी विभाजन के लिए दो समुच्चय <math>A</math> और <math>B</math> में, या अधिक सामान्यतः किसी भी विभाजन के लिए बहुत से उपसमुच्चयों में, विभाजन समुच्चय में से एक से प्रेरित कम से कम एक सबग्राफ पूरे राडो ग्राफ के लिए सोमॉर्फिक है। कैमरून (2001) निम्नलिखित संक्षिप्त प्रमाण देता है: यदि कोई भी भाग राडो ग्राफ में एक सबग्राफ समरूपी को प्रेरित नहीं करता है, तो वे सभी विस्तार गुण रखने में विफल हो जाते हैं, और कोई समुच्चय <math>U_i</math>और <math>V_i</math> के जोड़े पा सकता है जिन्हें प्रत्येक सबग्राफ के भीतर विस्तारित नहीं किया जा सकता है। लेकिन फिर, समुच्चयों का संघ <math>U_i</math>और समुच्चयों का संघ <math>V_i</math> एक ऐसा समुच्चय बनाएगा जिसे पूरे ग्राफ में नहीं बढ़ाया जा सकता, जो राडो ग्राफ की विस्तार गुण के विपरीत है। किसी भी विभाजन के प्रेरित उपग्राफों में से एक के समरूपी होने की यह गुण केवल तीन गणनीय अनंत अप्रत्यक्ष ग्राफ द्वारा धारण की जाती है: राडो ग्राफ, पूर्ण ग्राफ और खाली ग्राफ।<ref>{{harvtxt|Cameron|1990}}; {{harvtxt|Diestel|Leader|Scott|Thomassé|2007}}.</ref> बोनाटो, कैमरून और डेलीक (2000) और डायस्टेल एट अल। (2007) समान विभाजन गुण के साथ अनंत निर्देशित ग्राफ की जांच करें; सभी पूर्ण ग्राफ या राडो ग्राफ के किनारों के लिए अभिविन्यास चुनकर बनाए जाते हैं।
-एक संबंधित परिणाम शीर्ष विभाजन के बजाय किनारे विभाजन से संबंधित है: राडो ग्राफ़ के किनारों के प्रत्येक विभाजन के लिए कई सेटों में, पूरे राडो ग्राफ़ में एक सबग्राफ आइसोमोर्फिक होता है जो अधिकतम दो रंगों का उपयोग करता है। हालाँकि, आवश्यक रूप से एक आइसोमोर्फिक सबग्राफ मौजूद नहीं हो सकता है जो किनारों के केवल एक रंग का उपयोग करता है।<ref>{{harvtxt|Pouzet|Sauer|1996}}.</ref> अधिक सामान्यतः, प्रत्येक परिमित ग्राफ़ के लिए <math>A</math> वहाँ एक संख्या है <math>d_A</math> (बड़ी रैमसे डिग्री कहा जाता है <math>A</math> राडो ग्राफ़ में) जैसे कि प्रतियों के प्रत्येक विभाजन के लिए <math>A</math> राडो ग्राफ़ में सीमित रूप से कई सेटों में, पूरे राडो ग्राफ़ के लिए एक प्रेरित सबग्राफ आइसोमोर्फिक है जो अधिकतम उपयोग करता है <math>d_A</math> रंगों का.<ref>{{harvtxt|Sauer|2006}}</ref><ref>{{harvtxt|Dobrinen|2021}}</ref>
-==मॉडल सिद्धांत और 0-1 कानून==
+एक संबंधित परिणाम शीर्ष विभाजन के बजाय कोर विभाजन से संबंधित है: राडो ग्राफ के किनारों के प्रत्येक विभाजन के लिए कई समुच्चय में, पूरे राडो ग्राफ के लिए एक सबग्राफ समरूपी है जो अधिकतम दो रंगों का उपयोग करता है। हालाँकि, जरूरी नहीं कि एक आइसोमॉर्फिक सबग्राफ उपस्थित हो जो किनारों के केवल एक रंग का उपयोग करता हो।<ref>{{harvtxt|Pouzet|Sauer|1996}}.</ref> अधिक सामान्यतः, प्रत्येक परिमित ग्राफ <math>A</math> के लिए एक संख्या <math>d_A</math>होती है (जिसे राडो ग्राफ में <math>A</math> की बड़ी रैमसे डिग्री कहा जाता है) जैसे कि राडो ग्राफ में <math>A</math> की प्रतियों के प्रत्येक विभाजन के लिए कई समुच्चय में, पूरे राडो ग्राफ में एक प्रेरित सबग्राफ समरूपी होता है जो रंगों के अधिकतम <math>d_A</math> का उपयोग करता है।<ref>{{harvtxt|Sauer|2006}}</ref><ref>{{harvtxt|Dobrinen|2021}}</ref>
-{{harvtxt|Fagin|1976}} ग्राफ़ के तर्क में प्रथम-क्रम तर्क|प्रथम-क्रम कथनों के लिए शून्य-एक नियम सिद्ध करने के लिए राडो ग्राफ़ का उपयोग किया। जब इस प्रकार का तार्किक कथन राडो ग्राफ़ के लिए सही या गलत होता है, तो यह लगभग सभी परिमित ग्राफ़ के लिए भी सही या गलत (क्रमशः) होता है।
+==मॉडल सिद्धांत और 0-1 नियम==
+फ़ागिन (1976) ने ग्राफ के तर्क में प्रथम-क्रम कथनों के लिए शून्य-एक नियम को सिद्ध करने के लिए राडो ग्राफ का उपयोग किया। जब इस प्रकार का तार्किक कथन राडो ग्राफ के लिए सत्य या ग़लत है, तो यह लगभग सभी परिमित ग्राफ के लिए भी सत्य या ग़लत (क्रमशः) है।
 ===प्रथम-क्रम गुण===
-ग्राफ़ की प्रथम-क्रम भाषा ग्राफ़ के शीर्षों, [[सार्वभौमिक परिमाणीकरण]] और [[अस्तित्वगत परिमाणीकरण]], [[तार्किक संयोजक]]ों और शीर्षों की समानता और आसन्नता के लिए [[विधेय (गणितीय तर्क)]] का प्रतिनिधित्व करने वाले चर से गठित अच्छी तरह से गठित [[वाक्य (गणितीय तर्क)]] का संग्रह है। उदाहरण के लिए, यह शर्त कि ग्राफ़ में कोई [[पृथक शीर्ष]] न हो, वाक्य द्वारा व्यक्त की जा सकती है
+ग्राफ की प्रथम-क्रम भाषा गणितीय तर्क में अच्छी तरह से निर्मित वाक्यों का संग्रह है, जो ग्राफ के शीर्षों, सार्वभौमिक और अस्तित्वगत परिमाणकों, तार्किक संयोजकों और शीर्षों की समानता और आसन्नता के लिए विधेय का प्रतिनिधित्व करने वाले चर से निर्मित होती है। उदाहरण के लिए, यह शर्त कि किसी ग्राफ में कोई अलग-अलग शीर्ष न हो, वाक्य द्वारा व्यक्त की जा सकती है।<math display=block>\forall u:\exists v: u\sim v</math>
-<math display=block>\forall u:\exists v: u\sim v</math>
-जहां <math>\sim</math> प्रतीक दो शीर्षों के बीच आसन्न संबंध को दर्शाता है।<ref>{{harvtxt|Spencer|2001}}, Section 1.2, "What Is a First Order Theory?", [https://books.google.com/books?id=ZJfsCAAAQBAJ&pg=PA15 pp.&nbsp;15–17].</ref>
-यह वाक्य <math>S</math> कुछ ग्राफ़ के लिए सत्य है, और अन्य के लिए ग़लत है; एक ग्राफ <math>G</math> मॉडलिंग करने के लिए कहा जाता है <math>S</math>, लिखा हुआ <math>G\models S</math>, अगर <math>S</math> के शीर्ष और आसन्न संबंध के बारे में सत्य है <math>G</math>.<ref>See, e.g., {{harvtxt|Grandjean|1983}}, p. 184.</ref>
-राडो ग्राफ़ की विस्तार गुण को प्रथम-क्रम वाक्यों के संग्रह द्वारा व्यक्त किया जा सकता है <math>E_{i,j}</math>, यह बताते हुए कि हर विकल्प के लिए <math>i</math> एक सेट में शीर्ष <math>A</math> और <math>j</math> एक सेट में शीर्ष <math>B</math>, सभी अलग-अलग, हर चीज से सटे एक शीर्ष मौजूद है <math>A</math> और हर चीज़ से असन्निकट <math>B</math>.<ref>{{harvtxt|Spencer|2001}}, Section 1.3, "Extension Statements and Rooted Graphs", [https://books.google.com/books?id=ZJfsCAAAQBAJ&pg=PA17 pp.&nbsp;17–18].</ref> उदाहरण के लिए, <math>E_{1,1}</math> के रूप में लिखा जा सकता है
-<math display=block>\forall a:\forall b:a\ne b\rightarrow\exists c:c\ne a\wedge c\ne b\wedge c\sim a\wedge\lnot(c\sim b).</math>
+जहां <math>\sim</math> प्रतीक दो शीर्षों के बीच आसन्न संबंध को दर्शाता है।<ref>{{harvtxt|Spencer|2001}}, Section 1.2, "What Is a First Order Theory?", [https://books.google.com/books?id=ZJfsCAAAQBAJ&pg=PA15 pp.&nbsp;15–17].</ref> यह वाक्य <math>S</math> कुछ ग्राफ के लिए सत्य है, और अन्य के लिए ग़लत है; एक ग्राफ <math>G</math> मॉडलिंग करने के लिए कहा जाता है <math>S</math>, लिखा हुआ <math>G\models S</math>, अगर <math>S</math> के शीर्ष और आसन्न संबंध के बारे में सत्य है <math>G</math>.<ref>See, e.g., {{harvtxt|Grandjean|1983}}, p. 184.</ref> राडो ग्राफ की विस्तार गुण को प्रथम-क्रम वाक्यों के संग्रह द्वारा व्यक्त किया जा सकता है <math>E_{i,j}</math>, यह बताते हुए कि हर विकल्प के लिए <math>i</math> एक समुच्चय में शीर्ष <math>A</math> और <math>j</math> एक समुच्चय में शीर्ष <math>B</math>, सभी अलग-अलग, हर चीज से सटे एक शीर्ष उपस्थित है <math>A</math> और हर चीज़ से असन्निकट <math>B</math>.<ref>{{harvtxt|Spencer|2001}}, Section 1.3, "Extension Statements and Rooted Graphs", [https://books.google.com/books?id=ZJfsCAAAQBAJ&pg=PA17 pp.&nbsp;17–18].</ref> उदाहरण के लिए, <math>E_{1,1}</math> के रूप में लिखा जा सकता है।
+<math display="block">\forall a:\forall b:a\ne b\rightarrow\exists c:c\ne a\wedge c\ne b\wedge c\sim a\wedge\lnot(c\sim b).</math>
 ===सम्पूर्णता===
-{{harvtxt|Gaifman|1964}} साबित हुआ कि वाक्य  <math>E_{i,j}</math>, अतिरिक्त वाक्यों के साथ जो बताते हैं कि आसन्न संबंध सममित संबंध और रिफ्लेक्सिव संबंध है (अर्थात्, इन वाक्यों को मॉडलिंग करने वाला एक ग्राफ अप्रत्यक्ष है और इसमें कोई स्व-लूप नहीं है), एक पूर्ण सिद्धांत के स्वयंसिद्ध हैं। इसका मतलब यह है कि, प्रत्येक प्रथम-क्रम वाक्य के लिए <math>S</math>, बिल्कुल एक <math>S</math> और इसका निषेध इन सूक्तियों से सिद्ध किया जा सकता है।
+गैफ़मैन (1964) ने सिद्ध किया कि वाक्य, <math>E_{i,j}</math>, अतिरिक्त वाक्यों के साथ, जो बताते हैं कि आसन्न संबंध सममित और एंटीरिफ्लेक्सिव है (अर्थात, इन वाक्यों को मॉडलिंग करने वाला ग्राफ अप्रत्यक्ष है और इसमें कोई स्व-लूप नहीं है), एक पूर्ण सिद्धांत के स्वयंसिद्ध हैं। इसका मतलब यह है कि, प्रत्येक प्रथम-क्रम वाक्य <math>S</math> के लिए, बिल्कुल <math>S</math> में से एक और इसका निषेध इन सिद्धांतों से सिद्ध किया जा सकता है। क्योंकि राडो ग्राफ विस्तार सिद्धांतों को मॉडल करता है, यह इस सिद्धांत के सभी वाक्यों को मॉडल करता है।<ref>{{harvtxt|Gaifman|1964}}; {{harvtxt|Marker|2002}}, Theorem&nbsp;2.4.2, p.&nbsp;50.</ref>
-क्योंकि राडो ग्राफ़ विस्तार सिद्धांतों को मॉडल करता है, यह इस सिद्धांत के सभी वाक्यों को मॉडल करता है।<ref>{{harvtxt|Gaifman|1964}}; {{harvtxt|Marker|2002}}, Theorem&nbsp;2.4.2, p.&nbsp;50.</ref>
-तर्कशास्त्र में, एक सिद्धांत जिसमें दी गई अनंत [[प्रमुखता]] के साथ केवल एक मॉडल (आइसोमोर्फिज्म तक) होता है <math>\lambda</math> मॉर्ले की श्रेणीबद्धता प्रमेय कहा जाता है|<math>\lambda</math>-श्रेणीबद्ध। तथ्य यह है कि राडो ग्राफ विस्तार गुण के साथ अद्वितीय गणनीय ग्राफ है, इसका तात्पर्य यह है कि यह अपने सिद्धांत के लिए अद्वितीय गणनीय मॉडल भी है। राडो ग्राफ की इस विशिष्टता गुण को यह कहकर व्यक्त किया जा सकता है कि राडो ग्राफ का सिद्धांत ओमेगा-श्रेणीबद्ध सिद्धांत|ω-श्रेणीबद्ध है। जेरज़ी Łoś|Łoś और [[रॉबर्ट लॉसन वॉट]] ने 1954 में साबित किया कि जब कोई सिद्धांत होता है <math>\lambda</math>-श्रेणीबद्ध (कुछ अनंत कार्डिनल के लिए <math>\lambda</math>) और, इसके अलावा, कोई सीमित मॉडल नहीं है, तो सिद्धांत पूरा होना चाहिए।<ref>{{harvtxt|Łoś|1954}}; {{harvtxt|Vaught|1954}}; {{harvtxt|Enderton|1972}}, [https://books.google.com/books?id=LHjNCgAAQBAJ&pg=PA147 p.&nbsp;147].</ref> इसलिए, गैफ़मैन का प्रमेय कि राडो ग्राफ़ का सिद्धांत पूर्ण है, Łoś-Vaught परीक्षण द्वारा राडो ग्राफ़ की विशिष्टता से अनुसरण करता है।<ref>{{harvtxt|Marker|2002}}, Theorem&nbsp;2.2.6, p.&nbsp;42.</ref>
+तर्कशास्त्र में, एक सिद्धांत जिसमें दी गई अनंत प्रमुखता <math>\lambda</math> के साथ केवल एक मॉडल (समरूपता तक) होता है, <math>\lambda</math>-श्रेणीबद्ध कहा जाता है। तथ्य यह है कि राडो ग्राफ विस्तार गुण के साथ अद्वितीय गणनीय ग्राफ है, इसका तात्पर्य यह है कि यह अपने सिद्धांत के लिए अद्वितीय गणनीय मॉडल भी है। राडो ग्राफ की इस विशिष्टता गुण को यह कहकर व्यक्त किया जा सकता है कि राडो ग्राफ का सिद्धांत ω-वर्गीकृत है। Łoś और वॉट ने 1954 में सिद्ध किया कि जब कोई सिद्धांत एक <math>\lambda</math>-श्रेणीबद्ध (कुछ अनंत कार्डिनल <math>\lambda</math> के लिए) होता है और, इसके अलावा, कोई परिमित मॉडल नहीं होता है, तो सिद्धांत पूर्ण होना चाहिए।<ref>{{harvtxt|Łoś|1954}}; {{harvtxt|Vaught|1954}}; {{harvtxt|Enderton|1972}}, [https://books.google.com/books?id=LHjNCgAAQBAJ&pg=PA147 p.&nbsp;147].</ref> इसलिए, गैफमैन का प्रमेय कि राडो ग्राफ का सिद्धांत पूर्ण है, लोश-वाउट परीक्षण द्वारा राडो ग्राफ की विशिष्टता का अनुसरण करता है।<ref>{{harvtxt|Marker|2002}}, Theorem&nbsp;2.2.6, p.&nbsp;42.</ref>
-===परिमित ग्राफ़ और कम्प्यूटेशनल जटिलता===
+===परिमित ग्राफ और कम्प्यूटेशनल जटिलता===
-जैसा {{harvtxt|Fagin|1976}} साबित हुआ, विस्तार सिद्धांतों से साबित होने वाले और राडो ग्राफ द्वारा मॉडलिंग किए गए प्रथम-क्रम वाक्य लगभग हमेशा यादृच्छिक परिमित ग्राफ़ के लिए बिल्कुल सही वाक्य हैं। इसका मतलब यह है कि यदि कोई एक चुनता है <math>n</math>-सभी ग्राफ़ों के बीच यादृच्छिक रूप से वर्टेक्स ग्राफ़ समान रूप से <math>n</math> लेबल किए गए शीर्ष, तो संभावना है कि चुने गए ग्राफ़ के लिए ऐसा वाक्य सत्य होगा, सीमा में एक के करीब पहुंचता है <math>n</math> अनंत तक पहुंचता है। सममित रूप से, जो वाक्य राडो ग्राफ़ द्वारा प्रतिरूपित नहीं किए गए हैं वे लगभग सभी यादृच्छिक परिमित ग्राफ़ के लिए झूठे हैं। यह इस प्रकार है कि प्रत्येक प्रथम-क्रम वाक्य या तो लगभग हमेशा सत्य होता है या यादृच्छिक परिमित ग्राफ़ के लिए लगभग हमेशा गलत होता है, और इन दो संभावनाओं को यह निर्धारित करके अलग किया जा सकता है कि राडो ग्राफ़ वाक्य को मॉडल करता है या नहीं। फेगिन का प्रमाण [[सघनता प्रमेय]] का उपयोग करता है।<ref>{{harvtxt|Fagin|1976}}; {{harvtxt|Marker|2002}}, Theorem&nbsp;2.4.4, pp.&nbsp;51–52.</ref> इस तुल्यता के आधार पर, राडो ग्राफ़ द्वारा प्रतिरूपित वाक्यों के सिद्धांत को यादृच्छिक ग्राफ़ का सिद्धांत या ग्राफ़ का लगभग निश्चित सिद्धांत कहा गया है।
+जैसा कि फागिन (1976) ने सिद्ध किया, विस्तार सिद्धांतों से सिद्ध और राडो ग्राफ द्वारा प्रतिरूपित प्रथम-क्रम वाक्य लगभग सभी यादृच्छिक परिमित ग्राफ के लिए बिल्कुल सही वाक्य हैं। इसका मतलब यह है कि यदि कोई <math>n</math> लेबल वाले शीर्षों पर सभी ग्राफ़ों के बीच समान रूप से यादृच्छिक रूप से एक <math>n</math>-वर्टेक्स ग्राफ चुनता है, तो संभावना है कि चुने गए ग्राफ के लिए ऐसा वाक्य सत्य होगा क्योंकि n अनंत तक पहुंचने पर सीमा में एक के समीप पहुंचता है। सममित रूप से, जो वाक्य राडो ग्राफ द्वारा प्रतिरूपित नहीं होते हैं वे लगभग सभी यादृच्छिक परिमित ग्राफ के लिए ग़लत होते हैं। यह इस प्रकार है कि यादृच्छिक परिमित ग्राफ के लिए प्रत्येक प्रथम-क्रम वाक्य या तो लगभग हमेशा सत्य होता है या लगभग हमेशा गलत होता है, और इन दो संभावनाओं को यह निर्धारित करके अलग किया जा सकता है कि क्या राडो ग्राफ वाक्य को मॉडल करता है। फ़ैगिन का प्रमाण कॉम्पैक्टनेस प्रमेय का उपयोग करता है।<ref>{{harvtxt|Fagin|1976}}; {{harvtxt|Marker|2002}}, Theorem&nbsp;2.4.4, pp.&nbsp;51–52.</ref> इस तुल्यता के आधार पर, राडो ग्राफ द्वारा प्रतिरूपित वाक्यों के सिद्धांत को "यादृच्छिक ग्राफ का सिद्धांत" या "ग्राफ का लगभग निश्चित सिद्धांत" कहा गया है।
-इस 0-1 कानून के कारण, पर्याप्त बड़े मूल्य का चयन करके, यह परीक्षण करना संभव है कि क्या किसी विशेष प्रथम-क्रम वाक्य को एक सीमित समय में राडो ग्राफ द्वारा मॉडल किया गया है। <math>n</math> और की संख्या गिनना <math>n</math>-वर्टेक्स ग्राफ़ जो वाक्य को मॉडल करते हैं। हालाँकि, यहाँ, पर्याप्त बड़ा वाक्य के आकार में कम से कम घातीय है। उदाहरण के लिए विस्तार स्वयंसिद्ध <math>E_{k,0}</math> के अस्तित्व का तात्पर्य है <math>(k+1)</math>-वर्टेक्स क्लिक (ग्राफ़ सिद्धांत), लेकिन उस आकार का एक गुट केवल उच्च संभावना के साथ आकार के घातांक के यादृच्छिक ग्राफ़ में मौजूद है <math>k</math>.
+इस 0-1 नियम के कारण, n का एक अधिक पर्याप्त मान चुनकर और वाक्य को मॉडल करने वाले <math>n</math>-वर्टेक्स ग्राफ की संख्या की गणना करके, यह परीक्षण करना संभव है कि क्या किसी विशेष प्रथम-क्रम वाक्य को सीमित समय में राडो ग्राफ द्वारा मॉडल किया गया है। हालाँकि, यहाँ, "काफ़ी अधिक" वाक्य के आकार में कम से कम घातांकीय है। उदाहरण के लिए, विस्तार अभिगृहीत ,<math>E_{k,0}</math> एक <math>(k+1)</math>-वर्टेक्स क्लिक के अस्तित्व को दर्शाता है, लेकिन उस आकार का एक समूह केवल <math>k</math> में आकार घातांक के यादृच्छिक ग्राफ में उच्च संभावना के साथ उपस्थित है। यह निर्धारित करना असंभव है कि राडो ग्राफ किसी दिए गए वाक्य को मॉडल करता है या नहीं, इसे घातीय समय की तुलना में अधिक तेज़ी से किया जा सकता है, क्योंकि समस्या पीस्पेस-पूर्ण है।{{sfnp|Grandjean|1983}}
-यह निर्धारित करना असंभव है कि राडो ग्राफ किसी दिए गए वाक्य को मॉडल करता है या नहीं, घातीय समय की तुलना में अधिक तेज़ी से किया जा सकता है, क्योंकि समस्या पीएसपीएसीई-पूर्ण है।{{sfnp|Grandjean|1983}}
 ===अन्य मॉडल-सैद्धांतिक गुण===
-राडो ग्राफ़ [[अतिसजातीय ग्राफ]] है, और इस प्रकार यह परिमित उपसंरचनाओं के वर्ग की फ्रैसे सीमा है, यानी परिमित ग्राफ़ का वर्ग।<ref>{{harvtxt|Macpherson|2011}}, Theorem 2.1.3, Example 2.2.1.</ref> यह देखते हुए कि यह एक सीमित संबंधपरक भाषा में भी है, अल्ट्राहोमोजेनिटी इसके सिद्धांत के बराबर है जिसमें क्वांटिफायर उन्मूलन और ω-श्रेणीबद्ध है।<ref>{{harvtxt|Macpherson|2011}}, Corollary 3.1.3, Proposition 3.1.6.</ref> चूंकि राडो ग्राफ इस प्रकार गणनीय ω-श्रेणीबद्ध सिद्धांत का गणनीय मॉडल है, यह [[ प्रमुख मॉडल ]] और [[संतृप्त मॉडल]] दोनों है।<ref>{{harvtxt|Rothmaler|2000}}, Theorem 13.3.1, Theorem 13.2.1.</ref><ref>{{harvtxt|McNulty|2016}}, p.71 and p.75.</ref>
+राडो ग्राफ अति-सजातीय है और इस प्रकार यह इसके परिमित उपसंरचनाओं के वर्ग की फ्रैसे सीमा है, यानी परिमित ग्राफ का वर्ग है।<ref>{{harvtxt|Macpherson|2011}}, Theorem 2.1.3, Example 2.2.1.</ref> यह देखते हुए कि यह एक सीमित संबंधपरक भाषा में भी है, अल्ट्रा समरूपता इसके सिद्धांत के बराबर है जिसमें क्वांटिफायर उन्मूलन और ω-वर्गीकृत है।<ref>{{harvtxt|Macpherson|2011}}, Corollary 3.1.3, Proposition 3.1.6.</ref> चूंकि राडो ग्राफ इस प्रकार गणनीय ω-श्रेणीबद्ध सिद्धांत का गणनीय मॉडल है, यह अभाज्य और संतृप्त दोनों है।<ref>{{harvtxt|Rothmaler|2000}}, Theorem 13.3.1, Theorem 13.2.1.</ref><ref>{{harvtxt|McNulty|2016}}, p.71 and p.75.</ref>
-राडो ग्राफ का सिद्धांत [[एनआईपी (मॉडल सिद्धांत)]] और एक [[सरल सिद्धांत (मॉडल सिद्धांत)]] के साथ एक सिद्धांत का एक प्रोटोटाइप उदाहरण है जो [[स्थिर सिद्धांत]] नहीं है।<ref>{{harvtxt|Baldwin|2018}}</ref>
+राडो ग्राफ का सिद्धांत स्वतंत्रता गुण के साथ एक सिद्धांत का एक प्रोटोटाइपिक उदाहरण है, और एक सरल सिद्धांत का जो स्थिर नहीं है।<ref>{{harvtxt|Baldwin|2018}}</ref>
 ==संबंधित अवधारणाएँ==
-यद्यपि राडो ग्राफ़ प्रेरित उपग्राफ़ों के लिए सार्वभौमिक है, यह ग्राफ़ की [[आइसोमेट्री]] के लिए सार्वभौमिक नहीं है,
+यद्यपि राडो ग्राफ प्रेरित सबग्राफ के लिए सार्वभौमिक है, यह ग्राफ के सममितीय अंत:स्थापन के लिए सार्वभौमिक नहीं है, जहां एक सममितीय अंत:स्थापन एक ग्राफ समरूपता है जो दूरी को संरक्षित करता है। राडो ग्राफ का व्यास दो है, और इसलिए बड़े व्यास वाला कोई भी ग्राफ इसमें सममितीय रूप से एम्बेड नहीं होता है। मॉस (1989, 1991) ने सममितीय अंत:स्थापन के लिए सार्वभौमिक ग्राफ के एक परिवार का वर्णन किया है, प्रत्येक संभावित परिमित ग्राफ व्यास के लिए एक; उनके परिवार में व्यास दो के साथ ग्राफ राडो ग्राफ है।
-जहां एक आइसोमेट्रिक एम्बेडिंग एक ग्राफ आइसोमोर्फिज्म है जो [[दूरी (ग्राफ सिद्धांत)]] को संरक्षित करता है। राडो ग्राफ़ का व्यास (ग्राफ़ सिद्धांत) दो है, और इसलिए बड़े व्यास वाला कोई भी ग्राफ़ इसमें सममितीय रूप से एम्बेड नहीं होता है। {{harvs|last=Moss|year=1989|year2=1991|txt}} ने आइसोमेट्रिक एम्बेडिंग के लिए सार्वभौमिक ग्राफ़ के एक परिवार का वर्णन किया है, प्रत्येक संभावित परिमित ग्राफ़ व्यास के लिए एक; उनके परिवार में व्यास दो वाला ग्राफ राडो ग्राफ है।
-[[हेंसन ग्राफ]]़ गणनीय ग्राफ़ हैं (प्रत्येक सकारात्मक पूर्णांक के लिए एक)। <math>i</math>) जिसमें कोई शामिल नहीं है <math>i</math>-वर्टेक्स क्लिक (ग्राफ सिद्धांत), और के लिए सार्वभौमिक हैं <math>i</math>-क्लिक-मुक्त ग्राफ़। इन्हें राडो ग्राफ के प्रेरित उपग्राफ के रूप में बनाया जा सकता है।{{sfnp|Henson|1971}} राडो ग्राफ़, हेंसन ग्राफ़ और उनके पूरक, गणनीय अनंत समूहों और उनके पूरकों के असंयुक्त संघ, और समरूपी परिमित गुटों और उनके पूरकों के अनंत असंयुक्त संघ ही एकमात्र संभावित गणनीय अनंत सजातीय ग्राफ़ हैं।{{sfnp|Lachlan|Woodrow|1980}}
+हेन्सन ग्राफ गणनीय ग्राफ हैं (प्रत्येक धनात्मक पूर्णांक के लिए एक)। <math>i</math>) जिसमें i<math>i</math>-वर्टेक्स क्लिक नहीं है और ये <math>i</math>-क्लिक-मुक्त ग्राफ के लिए सार्वभौमिक हैं। इन्हें राडो ग्राफ के प्रेरित सबग्राफ के रूप में बनाया जा सकता है।{{sfnp|Henson|1971}} राडो ग्राफ, हेंसन ग्राफ और उनके पूरक, अनगिनत अनंत समूहों और उनके पूरकों के असंयुक्त संघ, और समरूपी परिमित समूहों और उनके पूरकों के अनंत असंयुक्त संघ ही एकमात्र संभव गिनती योग्य अनंत सजातीय ग्राफ हैं।{{sfnp|Lachlan|Woodrow|1980}}
-राडो ग्राफ़ की सार्वभौमिकता गुण को किनारे के रंग वाले ग्राफ़ तक बढ़ाया जा सकता है; यानी, ऐसे ग्राफ़ जिनमें किनारों को अलग-अलग रंग वर्गों को सौंपा गया है, लेकिन सामान्य किनारे रंग की आवश्यकता के बिना कि प्रत्येक रंग वर्ग एक मिलान (ग्राफ़ सिद्धांत) बनाता है। रंगों की किसी भी सीमित या गणनीय अनंत संख्या के लिए <math>\chi</math>, वहाँ एक अद्वितीय गणनीय-अनंत मौजूद है <math>\chi</math>-किनारे के रंग का ग्राफ <math>G_\chi</math> जैसे कि प्रत्येक आंशिक समरूपता <math>\chi</math>-किनारे के रंग के परिमित ग्राफ को पूर्ण समरूपता तक बढ़ाया जा सकता है। इस अंकन के साथ, राडो ग्राफ़ बस है <math>G_1</math>. {{harvtxt|Truss|1985}} ग्राफ़ के इस अधिक सामान्य परिवार के ऑटोमोर्फिज्म समूहों की जांच करता है।
+राडो ग्राफ की सार्वभौमिकता गुण को कोर के रंग वाले ग्राफ तक बढ़ाया जा सकता है; अर्थात्, ऐसे ग्राफ जिनमें किनारों को अलग-अलग रंग वर्गों को सौंपा गया है, लेकिन किनारों के रंग की सामान्य आवश्यकता के बिना कि प्रत्येक रंग वर्ग एक संघ बनाता है। रंगों की किसी भी परिमित या गणनीय अनंत संख्या के लिए, एक अद्वितीय गणनीय-अनंत <math>\chi</math>-कोर-रंगीन ग्राफ <math>G_\chi</math> उपस्थित है, जैसे कि <math>\chi</math>-कोर-रंगीन परिमित ग्राफ के प्रत्येक आंशिक समरूपता को पूर्ण समरूपता तक बढ़ाया जा सकता है। इस अंकन के साथ, राडो ग्राफ सिर्फ <math>G_1</math> है। ट्रस (1985) ग्राफ के इस अधिक सामान्य परिवार के ऑटोमोर्फिज़्म समूहों की जाँच करता है।
-जबकि राडो ग्राफ़ सभी ग्राफ़ के वर्ग के लिए गणनीय सार्वभौमिक है, सभी ग्राफ़ वर्गों में गणनीय सार्वभौमिक ग्राफ़ नहीं है। उदाहरण के लिए, 4-चक्र को सबग्राफ के रूप में छोड़ने वाला कोई गणनीय ग्राफ़ नहीं है जिसमें ऐसे अन्य सभी गणनीय ग्राफ़ (आवश्यक रूप से प्रेरित नहीं) सबग्राफ के रूप में शामिल हैं।<ref>{{harvtxt|Cherlin|2011}}, Fact 1.3</ref>
+जबकि राडो ग्राफ सभी ग्राफ़ों के वर्ग के लिए गणनीय सार्वभौमिक ग्राफ है, सभी ग्राफ वर्गों में गणनीय सार्वभौमिक ग्राफ नहीं है। उदाहरण के लिए, 4-चक्र को सबग्राफ के रूप में छोड़ने वाला कोई गणनीय ग्राफ नहीं है जिसमें अन्य सभी ऐसे गणनीय ग्राफ (आवश्यक रूप से प्रेरित नहीं) सबग्राफ के रूप में सम्मिलित हैं।<ref>{{harvtxt|Cherlin|2011}}, Fact 1.3</ref>
-संतृप्त मॉडल के निर्माण के शास्त्रीय मॉडल सिद्धांत के विचारों से यह पता चलता है कि सातत्य परिकल्पना सीएच के तहत, सातत्य के कई शीर्षों की कार्डिनैलिटी के साथ एक सार्वभौमिक ग्राफ है। बेशक, सीएच के तहत, सातत्य बराबर है <math>\aleph_1</math>, एलेफ़ संख्या। {{harvs|last=Shelah|year=1984|year2=1990|txt}} सार्वभौमिक ग्राफ़ की जांच करने के लिए फ़ोर्सिंग (गणित) का उपयोग करता है <math>\aleph_1</math> कई शीर्षों से पता चलता है कि सीएच की अनुपस्थिति में भी, आकार का एक सार्वभौमिक ग्राफ मौजूद हो सकता है <math>\aleph_1</math>. वह उच्च कार्डिनैलिटी के लिए अनुरूप प्रश्नों की भी जांच करता है।
+यह एक संतृप्त मॉडल के निर्माण के शास्त्रीय मॉडल सिद्धांत के विचारों का अनुसरण करता है कि सातत्य परिकल्पना सीएच के तहत, कई शीर्षों के सातत्य के साथ एक सार्वभौमिक ग्राफ है। निस्संदेह, सीएच के तहत, सातत्य <math>\aleph_1</math> के बराबर है, पहला बेशुमार कार्डिनल। शेला (1984, 1990) सार्वभौमिक ग्राफ की जांच के लिए फोर्सिंग का उपयोग करता है <math>\aleph_1</math> कई शीर्ष और दर्शाते हैं कि CH की अनुपस्थिति में भी, आकार <math>\aleph_1</math> का एक सार्वभौमिक ग्राफ उपस्थित हो सकता है। वह उच्च प्रमुखता के लिए समान प्रश्नों की भी जांच करता है।
 ==टिप्पणियाँ==
 {{reflist|30em}}
 ==संदर्भ==
 {{refbegin|30em}}
@@ Line 444: / Line 429: @@
   | year = 1954| doi = 10.1016/S1385-7258(54)50058-2 }}.
 {{refend}}
-[[Category: व्यक्तिगत ग्राफ़]] [[Category: यादृच्छिक रेखांकन]] [[Category: अनंत रेखांकन]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 20/07/2023]]
+[[Category:Good articles]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:अनंत रेखांकन]]
+[[Category:यादृच्छिक रेखांकन]]
+[[Category:व्यक्तिगत ग्राफ़]]

Anonymous

Search

राडो ग्राफ: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:09, 14 August 2023

Contents

इतिहास