राडो ग्राफ

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

प्रेरित उपग्राफ

विस्तार गुण का उपयोग किसी भी परिमित या गणनीय अनंत ग्राफ की आइसोमोर्फिक प्रतियां बनाने के लिए किया जा सकता है $G$ राडो ग्राफ़ के भीतर, प्रेरित सबग्राफ़ के रूप में। ऐसा करने के लिए, के शीर्षों को ऑर्डर करें $G$, और की आंशिक प्रतिलिपि में उसी क्रम में शीर्ष जोड़ें $G$ राडो ग्राफ़ के भीतर। प्रत्येक चरण पर, अगला शीर्ष आता है $G$ किसी सेट के निकट होगा $U$ शीर्षों में से $G$ जो शीर्षों के क्रम में पहले हैं, और शेष सेट से गैर-आसन्न $V$ पहले के शीर्षों में से $G$. विस्तार गुण के अनुसार, राडो ग्राफ़ में एक शीर्ष भी होगा $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}$ और $h_{i}$ पिछले सबग्राफ़ के सभी शीर्षों के साथ। इस प्रक्रिया को दोहराकर, कोई प्रेरित उपसमूहों के बीच समरूपता का एक क्रम बना सकता है जिसमें अंततः प्रत्येक शीर्ष शामिल होता है $G$ और $H$. इस प्रकार, आगे-पीछे विधि द्वारा, $G$ और $H$ समरूपी होना चाहिए. क्योंकि यादृच्छिक ग्राफ़ निर्माण, बाइनरी संख्या निर्माण, और पैली ग्राफ़ निर्माण द्वारा निर्मित ग्राफ़ सभी विस्तार गुण के साथ गणनीय ग्राफ़ हैं, यह तर्क दर्शाता है कि वे सभी एक दूसरे के लिए आइसोमोर्फिक हैं।

समरूपता समूह

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

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

परिमित परिवर्तनों के विरुद्ध मजबूती

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

विभाजन

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

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

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

Fagin (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).$$

सम्पूर्णता

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

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

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

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

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

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

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

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

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

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

जबकि राडो ग्राफ़ सभी ग्राफ़ के वर्ग के लिए गणनीय सार्वभौमिक है, सभी ग्राफ़ वर्गों में गणनीय सार्वभौमिक ग्राफ़ नहीं है। उदाहरण के लिए, 4-चक्र को सबग्राफ के रूप में छोड़ने वाला कोई गणनीय ग्राफ़ नहीं है जिसमें ऐसे अन्य सभी गणनीय ग्राफ़ (आवश्यक रूप से प्रेरित नहीं) सबग्राफ के रूप में शामिल हैं। संतृप्त मॉडल के निर्माण के शास्त्रीय मॉडल सिद्धांत के विचारों से यह पता चलता है कि सातत्य परिकल्पना सीएच के तहत, सातत्य के कई शीर्षों की कार्डिनैलिटी के साथ एक सार्वभौमिक ग्राफ है। बेशक, सीएच के तहत, सातत्य बराबर है $\aleph _{1}$, एलेफ़ संख्या। Shelah (1984, 1990) सार्वभौमिक ग्राफ़ की जांच करने के लिए फ़ोर्सिंग (गणित) का उपयोग करता है $\aleph _{1}$ कई शीर्षों से पता चलता है कि सीएच की अनुपस्थिति में भी, आकार का एक सार्वभौमिक ग्राफ मौजूद हो सकता है $\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.