Graphon
ग्राफ सिद्धांत और सांख्यिकी में, एक ग्राफॉन (जिसे ग्राफ सीमा के रूप में भी जाना जाता है) एक सममित मापने योग्य कार्य है, जो घने ग्राफ के अध्ययन में महत्वपूर्ण है। ग्राफ़न घने ग्राफ़ों के अनुक्रम की सीमा के लिए एक प्राकृतिक धारणा के रूप में और विनिमय योग्य यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में उत्पन्न होते हैं। ग्राफ़न को टिप्पणियों की निम्नलिखित जोड़ी द्वारा घने ग्राफ़ से जोड़ा जाता हैः ग्राफ़न द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से घने ग्राफ़ को जन्म देते हैं, और नियमितता लेम्मा द्वारा, ग्राफ़न मनमाने ढंग से बड़े घने ग्राफ़ की संरचना को पकड़ते हैं। सांख्यिकीय सूत्रीकरण ग्राफॉन एक सममित मापने योग्य कार्य है। आम तौर पर एक ग्राफॉन को निम्नलिखित योजना के अनुसार एक विनिमय योग्य यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता हैः ग्राफ के प्रत्येक शीर्ष को एक स्वतंत्र यादृच्छिक मूल्य सौंपा जाता है एज को स्वतंत्र रूप से प्रायिकता के साथ ग्राफ में शामिल किया जाता है। एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है यदि और केवल तभी जब इसे इस तरह से एक (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफ पर आधारित मॉडल को कभी-कभी यादृच्छिक ग्राफ के एर्दोस-रेनी मॉडल के साथ सादृश्य द्वारा दर्शाया जाता है। इस तरह से एक ग्राफॉन से उत्पन्न ग्राफ को यादृच्छिक ग्राफ कहा जाता है। यह इस परिभाषा और बड़ी संख्या के नियम का अनुसरण करता है कि, यदि, विनिमय योग्य यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से घने हैं। उदाहरण ग्राफॉन का सबसे सरल उदाहरण कुछ स्थिरांक के लिए है। इस मामले में संबंधित विनिमय योग्य यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है जिसमें प्रत्येक किनारे को संभावना के साथ स्वतंत्र रूप से शामिल किया गया है। यदि हम इसके बजाय एक ग्राफॉन के साथ शुरू करते हैं जो टुकड़ों में स्थिरांक हैः इकाई वर्ग को ब्लॉकों में विभाजित करता है, और ब्लॉक के बराबर सेट करता है, तो परिणामी विनिमय योग्य यादृच्छिक ग्राफ मॉडल सामुदायिक यादृच्छिक ब्लॉक मॉडल है, जो एर्दोस-रेनी मॉडल का एक सामान्यीकरण है। हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं जिसमें क्रमशः मापदंडों के साथ अलग-अलग एर्डोस-रेनी ग्राफ होते हैं, उनके बीच बड़े ग्राफ होते हैं जहां ब्लॉकों के बीच प्रत्येक संभावित किनारे को संभावना के साथ स्वतंत्र रूप से शामिल किया जाता है। कई अन्य लोकप्रिय यादृच्छिक ग्राफ मॉडल को कुछ ग्राफॉन द्वारा परिभाषित विनिमय योग्य यादृच्छिक ग्राफ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ऑर्बैंज़ और रॉय में शामिल किया गया है। संयुक्त रूप से विनिमय योग्य निकटता मैट्रिक्स आकार के एक यादृच्छिक ग्राफ को एक यादृच्छिक निकटता मैट्रिक्स के रूप में दर्शाया जा सकता है। विभिन्न आकारों के यादृच्छिक ग्राफों के बीच स्थिरता (प्रक्षेपकता के अर्थ में) लागू करने के लिए यादृच्छिक चर की कुछ अनंत सरणी के ऊपरी-बाएँ उप-मैट्रिक के रूप में उत्पन्न होने वाले निकटता मैट्रिक्स के अनुक्रम का अध्ययन करना स्वाभाविक है; यह हमें एक नोड जोड़कर और किनारों का नमूना लेकर उत्पन्न करने की अनुमति देता है। इस परिप्रेक्ष्य के साथ, यादृच्छिक ग्राफ को यादृच्छिक अनंत सममित सरणियों के रूप में परिभाषित किया जाता है। शास्त्रीय संभाव्यता में विनिमय योग्य अनुक्रमों के मौलिक महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक अनुरूप धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय मैट्रिक्स द्वारा दी जाती है; अर्थात। प्राकृतिक संख्याओं के सभी क्रमपरिवर्तनों के लिए संतोषजनक यादृच्छिक मैट्रिक्स, जहाँ का अर्थ वितरण में बराबर है। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के पुनर्नामकरण द्वारा अपरिवर्तित हैः यानी, शीर्षों के लेबल में कोई जानकारी नहीं होती है। संयुक्त रूप से विनिमेय यादृच्छिक आसन्नता मैट्रिक्स के लिए एक प्रतिनिधित्व प्रमेय है, जो विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष मामला है और इस सेटिंग में, यह दावा किया गया है कि यादृच्छिक मैट्रिक्स निम्न द्वारा उत्पन्न होता हैः संभावना के साथ यादृच्छिक रूप से स्वतंत्र रूप से नमूना जहां एक (संभवतः यादृच्छिक) ग्राफॉन है। अर्थात्, एक यादृच्छिक ग्राफ मॉडल में एक संयुक्त रूप से विनिमेय निकटता मैट्रिक्स होता है यदि और केवल तभी जब यह कुछ ग्राफॉन के संदर्भ में परिभाषित एक संयुक्त रूप से विनिमेय यादृच्छिक ग्राफ मॉडल हो। ग्राफॉन आकलन पहचान संबंधी मुद्दों के कारण, ग्राफॉन फ़ंक्शन या नोड अव्यक्त स्थितियों का अनुमान लगाना असंभव है और ग्राफॉन आकलन की दो मुख्य दिशाएँ हैं। एक दिशा का उद्देश्य एक समतुल्यता वर्ग तक का अनुमान लगाना है, या द्वारा प्रेरित प्रायिकता मैट्रिक्स का अनुमान लगाना है। विश्लेषणात्मक सूत्रीकरण शीर्षों पर किसी भी ग्राफ को इसके निकटता मैट्रिक्स के साथ पहचाना जा सकता है। यह मैट्रिक्स एक स्टेप फंक्शन से मेल खाता है, जिसे अंतरालों में विभाजन करके परिभाषित किया जाता है जिसमें आंतरिक होता है और प्रत्येक के लिए, की प्रविष्टि के बराबर सेटिंग होती है। यह फलन ग्राफ का संबद्ध ग्राफ है। सामान्य तौर पर, यदि हमारे पास ग्राफ का एक क्रम है जहां के शीर्षों की संख्या अनंत तक जाती है, तो हम कार्यों के सीमित व्यवहार पर विचार करके अनुक्रम के सीमित व्यवहार का विश्लेषण कर सकते हैं। यदि ये ग्राफ अभिसरण करते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफों की सीमा इन संबद्ध कार्यों की सीमा के अनुरूप होगी। यह एक सममित मापने योग्य फलन के रूप में एक ग्राफॉन ("ग्राफ फ़ंक्शन" के लिए छोटा) की परिभाषा को प्रेरित करता है जो ग्राफ के अनुक्रम की सीमा की धारणा को पकड़ता है। यह पता चला है कि घने आलेखों के अनुक्रमों के लिए, अभिसरण की कई स्पष्ट रूप से अलग धारणाएं समतुल्य हैं और उन सभी के तहत प्राकृतिक सीमा वस्तु एक ग्राफॉन है। निरंतर ग्राफॉन के उदाहरण कुछ निश्चित मापदंड के साथ एर्डोस-रेनी यादृच्छिक ग्राफ का एक क्रम लें। सहज रूप से, जैसा कि अनंत की ओर जाता है, ग्राफों के इस अनुक्रम की सीमा पूरी तरह से इन ग्राफों के किनारे के घनत्व से निर्धारित की जाती है। ग्राफों के स्थान में, यह पता चलता है कि इस तरह का अनुक्रम लगभग निश्चित रूप से स्थिरांक में परिवर्तित हो जाता है, जो उपरोक्त अंतर्ज्ञान को पकड़ता है। अर्ध-ग्राफ का अनुक्रम लें, जिसे शीर्षों पर द्विदलीय ग्राफ के रूप में परिभाषित किया गया है और ऐसा जो सटीक रूप से कब के निकट है। यदि शीर्ष प्रस्तुत क्रम में सूचीबद्ध हैं, तो निकटता मैट्रिक्स में "आधा वर्ग" ब्लॉक मैट्रिक्स के दो कोने होते हैं, जो शून्य के बराबर शेष प्रविष्टियों के साथ भरे होते हैं। उदाहरण के लिए, के निकटता मैट्रिक्स को ए. एस. द्वारा दिया जाता है जो बड़ा हो जाता है, इन कोनों को बाहर "चिकना" किया जाता है। इस अंतर्ज्ञान से मेल खाते हुए, अनुक्रम कब और अन्यथा द्वारा परिभाषित अर्ध-ग्राफॉन में परिवर्तित हो जाता है। पूर्ण द्विदलीय ग्राफ समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ का अनुक्रम लें। यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखते हुए और दूसरे भाग के शीर्षों को अंत में रखते हुए शीर्षों को क्रमबद्ध करते हैं, तो एक के निकटता मैट्रिक्स एक ब्लॉक ऑफ-डायगोनल मैट्रिक्स की तरह दिखता है, जिसमें एक के दो ब्लॉक और शून्य के दो ब्लॉक होते हैं। उदाहरण के लिए, जैसा कि बड़ा होता जाता है, आसन्नता मैट्रिक्स की यह ब्लॉक संरचना स्थिर रहती है, ताकि ग्राफ का यह अनुक्रम जब भी और द्वारा परिभाषित "पूर्ण द्विदलीय" ग्राफॉन में परिवर्तित हो जाए, और अन्यथा सेटिंग हो। यदि हम इसके बजाय भागों के बीच बारी-बारी से शीर्षों को क्रमबद्ध करते हैं, तो निकटता मैट्रिक्स में शून्य और एक की शतरंज की संरचना होती है। उदाहरण के लिए, इस क्रम के तहत, के निकटता मैट्रिक्स द्वारा दिया जाता है जैसे-जैसे बड़ा होता जाता है, निकटता मैट्रिक्स एक महीन और महीन शतरंज की बिसात बन जाते हैं। इस व्यवहार के बावजूद, हम अभी भी चाहते हैं कि की सीमा अद्वितीय हो और उदाहरण 3 से ग्राफॉन में परिणाम हो। इसका मतलब है कि जब हम औपचारिक रूप से ग्राफ के अनुक्रम के लिए अभिसरण को परिभाषित करते हैं, तो एक सीमा की परिभाषा शीर्षों के पुनर्नामकरण के लिए अज्ञेयवादी होनी चाहिए। डब्ल्यू-यादृच्छिक ग्राफ की सीमा कुछ निश्चित ग्राफॉन के लिए आरेखित करके यादृच्छिक ग्राफ का एक यादृच्छिक अनुक्रम लें। फिर इस खंड के पहले उदाहरण की तरह, यह पता चला है कि लगभग निश्चित रूप से अभिसरण होता है। ग्राफ़न से ग्राफ़ मापदंडों को पुनर्प्राप्त करना संबंधित ग्राफ़न के साथ दिया गया ग्राफ़, हम ग्राफ़ के परिवर्तनों को एकीकृत करके ग्राफ़ के सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं। उदाहरण के लिए, किनारे का घनत्व (अर्थात। ) की औसत डिग्री को शीर्षों की संख्या से विभाजित करके समाकलन द्वारा दिया जाता है क्योंकि यह-मूल्यवान है, और प्रत्येक किनारा क्षेत्र के उस क्षेत्र से मेल खाता है जहां यह बराबर है। इसी तरह के तर्क से पता चलता है कि त्रिभुजों की संख्या अभिसरण की धारणाओं के बराबर है दो ग्राफों के बीच की दूरी को मापने के कई अलग-अलग तरीके हैं। यदि हम ऐसे मेट्रिक्स में रुचि रखते हैं जो ग्राफ के चरम गुणों को "संरक्षित" करते हैं, तो हमें अपना ध्यान उन मेट्रिक्स पर सीमित रखना चाहिए जो यादृच्छिक ग्राफ को समान रूप से पहचानते हैं। उदाहरण के लिए, यदि हम कुछ निश्चित के लिए एक एर्दोस-रेनी मॉडल से स्वतंत्र रूप से दो ग्राफ यादृच्छिक रूप से खींचते हैं, तो "उचित" मीट्रिक के तहत इन दो ग्राफों के बीच की दूरी शून्य के करीब होनी चाहिए और बड़ी के लिए उच्च संभावना होनी चाहिए। स्वाभाविक रूप से, एक ही शीर्ष समूह पर दो ग्राफ दिए जाने पर, एक व्यक्ति अपनी दूरी को उन किनारों की संख्या के रूप में परिभाषित कर सकता है जिन्हें एक ग्राफ से दूसरे में जाने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात। उनकी संपादन दूरी। हालाँकि, संपादन दूरी यादृच्छिक ग्राफ की पहचान समान रूप से नहीं करती है; वास्तव में, स्वतंत्र रूप से बनाए गए दो ग्राफों की अपेक्षित (सामान्यीकृत) संपादन दूरी है। दो प्राकृतिक मेट्रिक्स हैं जो घने यादृच्छिक ग्राफ पर उस अर्थ में अच्छा व्यवहार करते हैं जो हम चाहते हैं। पहला एक नमूना मीट्रिक है, जो कहता है कि दो ग्राफ करीब हैं यदि उनके उपग्राफ के वितरण करीब हैं। दूसरा एक किनारे की विसंगति मीट्रिक है, जो कहता है कि दो ग्राफ करीब होते हैं जब उनकी किनारे की घनत्व उनके सभी संबंधित शीर्षों के सबसेट पर करीब होती है। चमत्कारिक रूप से, ग्राफ का एक क्रम एक मीट्रिक के संबंध में तब अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। इसके अलावा, दोनों मेट्रिक्स के तहत सीमा वस्तुएं ग्राफॉन निकलती हैं। अभिसरण की इन दो धारणाओं की समानता दर्शाती है कि क्वासिरैंडम ग्राफ की विभिन्न धारणाएं कैसे समतुल्य हैं। समरूपता घनत्व दो ग्राफों के बीच की दूरी को मापने का एक तरीका है और उनकी सापेक्ष उपग्राफ गणनाओं की तुलना करना है। अर्थात्, प्रत्येक ग्राफ के लिए हम इन और इन की प्रतियों की संख्या की तुलना कर सकते हैं। यदि ये संख्याएँ प्रत्येक ग्राफ के लिए करीब हैं, तो सहज ज्ञान से और समान दिखने वाले ग्राफ हैं। हालाँकि, उपग्राफ के साथ सीधे काम करने के बजाय, ग्राफ समरूपता के साथ काम करना आसान हो जाता है। बड़े, घने ग्राफों के साथ काम करते समय यह ठीक है, क्योंकि इस परिदृश्य में उपग्राफों की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या स्पर्शोन्मुख रूप से बराबर होती है। दो ग्राफ दिए गए हैं और, समरूपता घनत्व को ग्राफ समरूपता की संख्या के रूप में परिभाषित किया गया है। दूसरे शब्दों में, संभावना है कि एक यादृच्छिक रूप से चुना गया मानचित्र शीर्षों से शीर्षों तक निकटवर्ती शीर्षों को निकटवर्ती शीर्षों में भेजता है। ग्राफॉन समरूपता घनत्वों की गणना करने का एक सरल तरीका प्रदान करते हैं। वास्तव में, संबद्ध ग्राफ और दूसरे के साथ एक ग्राफ दिए जाने पर, हमारे पास है जहां समाकलन बहुआयामी है, जिसे इकाई हाइपरक्यूब पर लिया गया है। यह एक संबद्ध ग्राफॉन की परिभाषा से इस बात पर विचार करता है कि उपरोक्त समाकलन कब के बराबर है। फिर हम समरूपता घनत्व की परिभाषा को मनमाने ग्राफॉन तक बढ़ा सकते हैं, उसी समाकलन का उपयोग करके और किसी भी ग्राफ के लिए परिभाषित कर सकते हैं। इस सेटअप को देखते हुए, हम कहते हैं कि ग्राफ का एक अनुक्रम लेफ्ट-कन्वर्जेंट है यदि प्रत्येक निश्चित ग्राफ के लिए, समरूपता घनत्वों का अनुक्रम अभिसरण करता है। यद्यपि केवल परिभाषा से स्पष्ट नहीं है, यदि इस अर्थ में अभिसरण होता है, तो हमेशा एक ग्राफॉन मौजूद रहता है कि प्रत्येक ग्राफ के लिए, हमारे पास एक साथ होता है। दूरी काटें दो ग्राफ लें और एक ही शीर्ष समूह पर। चूँकि ये ग्राफ एक ही शीर्ष साझा करते हैं, इसलिए उनकी दूरी को मापने का एक तरीका शीर्ष सेट के सबसेट तक सीमित है, और ऐसे प्रत्येक जोड़ी सबसेट के लिए किनारों की संख्या की तुलना अंदर और बीच के किनारों की संख्या से की जाती है। यदि ये संख्याएँ उपसमुच्चय की प्रत्येक जोड़ी के लिए समान हैं (शीर्षों की कुल संख्या के सापेक्ष), तो यह सुझाव देता है और समान ग्राफ हैं। दूरी की इस धारणा के प्रारंभिक औपचारिकरण के रूप में, ग्राफ की किसी भी जोड़ी के लिए और आकार के एक ही शीर्ष सेट पर, और के बीच लेबल की गई कटौती दूरी को परिभाषित करें। दूसरे शब्दों में, लेबल की गई कटौती दूरी और के बीच किनारे के घनत्व की अधिकतम विसंगति को कूटबद्ध करती है। हम इस अवधारणा को संबंधित ग्राफॉन के संदर्भ में किनारे के घनत्व को व्यक्त करके ग्राफॉन के लिए सामान्यीकृत कर सकते हैं, जिससे समानता मिलती है जहां और में शीर्षों के अनुरूप अंतराल के संघ हैं। ध्यान दें कि इस परिभाषा का उपयोग तब भी किया जा सकता है जब तुलना किए जा रहे ग्राफ एक शीर्ष समूह को साझा नहीं करते हैं। यह निम्नलिखित अधिक सामान्य परिभाषा को प्रेरित करता है। परिभाषा 1. किसी भी सममित, मापने योग्य फलन के लिए, कट मानक को इकाई अंतराल के सभी मापने योग्य उपसमुच्चय पर ली गई मात्रा के रूप में परिभाषित करें। यह लेबल की गई दूरी की हमारी पहले की धारणा को दर्शाता है, क्योंकि हमारे पास समानता है। इस दूरी माप की अभी भी एक प्रमुख सीमा हैः यह दो समरूप ग्राफों को गैर-शून्य दूरी निर्धारित कर सकता है। यह सुनिश्चित करने के लिए कि समरूप ग्राफ की दूरी शून्य है, हमें शीर्षों के सभी संभावित "रिलेबलिंग" पर न्यूनतम कट मानक की गणना करनी चाहिए। यह कट दूरी की निम्नलिखित परिभाषा को प्रेरित करता है। परिभाषा 2. ग्राफों की किसी भी जोड़ी के लिए और, उनकी कटौती की दूरी को परिभाषित करें कि मानचित्र के साथ संरचना कहाँ है, और असीम को इकाई अंतराल से सभी माप-संरक्षित बाइजेक्शन पर लिया जाता है। दो ग्राफों के बीच की कटौती दूरी को उनके संबंधित ग्राफों के बीच की कटौती दूरी के रूप में परिभाषित किया गया है। अब हम कहते हैं कि ग्राफ का एक अनुक्रम कट दूरी के तहत अभिसारी है यदि यह कट दूरी के तहत एक कौची अनुक्रम है। यद्यपि परिभाषा का प्रत्यक्ष परिणाम नहीं है, यदि ग्राफ का ऐसा अनुक्रम कौची है, तो यह हमेशा किसी ग्राफॉन में परिवर्तित हो जाता है। अभिसरण की समतुल्यता जैसा कि यह पता चला है, ग्राफ के किसी भी अनुक्रम के लिए, लेफ्ट-कन्वर्जेंस कट दूरी के तहत अभिसरण के बराबर है, और इसके अलावा, सीमा ग्राफॉन समान है। हम समान परिभाषाओं का उपयोग करके स्वयं ग्राफॉनों के अभिसरण पर भी विचार कर सकते हैं, और वही समानता सच है। वास्तव में, अभिसरण की दोनों धारणाएँ अधिक दृढ़ता से संबंधित हैं जिन्हें काउंटिंग लेम्मा कहा जाता है। लेम्मा की गिनती। ग्राफों की किसी भी जोड़ी के लिए और, हमारे पास सभी ग्राफों के लिए है। "काउंटिंग लेम्मा" नाम उन सीमाओं से आता है जो यह लेम्मा समरूपता घनत्वों पर देता है, जो ग्राफ की उपग्राफ गिनती के अनुरूप हैं। यह लेम्मा ग्राफ काउंटिंग लेम्मा का एक सामान्यीकरण है जो नियमित विभाजन के क्षेत्र में दिखाई देता है, और यह तुरंत दर्शाता है कि कट दूरी के तहत अभिसरण बाएं-अभिसरण का तात्पर्य है। व्युत्क्रम गणना लेम्मा। प्रत्येक वास्तविक संख्या के लिए, एक वास्तविक संख्या और एक सकारात्मक पूर्णांक मौजूद होता है जैसे कि ग्राफों की किसी भी जोड़ी के लिए और सभी ग्राफों को संतुष्ट करने के लिए, हमारे पास होना चाहिए। यह लेम्मा दर्शाता है कि बाएं-अभिसरण का अर्थ है कट दूरी के तहत अभिसरण। ग्राफों का स्थान हम सभी ग्राफों के समूह को लेकर और जब भी दो ग्राफों की पहचान करके दूरी को एक मीट्रिक में काट सकते हैं। ग्राफ़न के परिणामी स्थान को दर्शाया जाता है, और एक साथ एक मीट्रिक स्थान बनाता है। यह स्थान कॉम्पैक्ट हो जाता है। इसके अलावा, इसमें सभी परिमित ग्राफों का सेट होता है, जिन्हें उनके संबंधित ग्राफों द्वारा एक घने उपसमुच्चय के रूप में दर्शाया जाता है। इन टिप्पणियों से पता चलता है कि ग्राफों का स्थान कट दूरी के संबंध में ग्राफों के स्थान का पूरा होना है। इसका एक तात्कालिक परिणाम निम्नलिखित है। कोरोलरी 1. प्रत्येक वास्तविक संख्या के लिए, एक पूर्णांक ऐसा होता है कि प्रत्येक ग्राफॉन के लिए, अधिकांश शीर्षों के साथ एक ग्राफ होता है। यह देखने के लिए कि क्यों, ग्राफ का सेट होने दें। प्रत्येक ग्राफ़ के लिए सभी ग्राफ़न वाली खुली गेंद पर विचार करें। सभी ग्राफों के लिए खुली गेंदों का सेट कवर करता है, इसलिए कॉम्पैक्टनेस का तात्पर्य है कि कुछ परिमित सबसेट के लिए एक परिमित सब-कवर है। हम अब ग्राफों में शीर्षों की सबसे बड़ी संख्या मान सकते हैं। अनुप्रयोग नियमितता लेम्मा ग्राफ़न के स्थान की सघनता को स्ज़ेमेरेडी की नियमितता लेम्मा के विश्लेषणात्मक सूत्रीकरण के रूप में सोचा जा सकता है; वास्तव में, मूल लेम्मा की तुलना में एक मजबूत परिणाम। स्ज़ेमेरेदी के नियमित लेम्मा का अनुवाद ग्राफ़न की भाषा में निम्नानुसार किया जा सकता है। एक चरण फलन को एक ग्राफॉन के रूप में परिभाषित करें जो टुकड़ों में स्थिरांक है, अर्थात। के कुछ विभाजन के लिए, सभी के लिए स्थिर है। यह कथन कि एक ग्राफ में एक नियमित विभाजन है, यह कहने के बराबर है कि इसका संबंधित ग्राफॉन एक चरण फलन के करीब है। सघनता के प्रमाण के लिए केवल कमजोर नियमितता लेम्मा की आवश्यकता होती हैः ग्राफॉन के लिए कमजोर नियमितता लेम्मा। प्रत्येक ग्राफॉन के लिए और, अधिक से अधिक चरणों के साथ एक स्टेप फंक्शन होता है। लेकिन इसका उपयोग मजबूत नियमितता परिणामों को साबित करने के लिए किया जा सकता है, जैसे कि मजबूत नियमितता लेमाः ग्राफॉन के लिए मजबूत नियमितता लेम्मा। सकारात्मक वास्तविक संख्याओं के प्रत्येक अनुक्रम के लिए, एक सकारात्मक पूर्णांक ऐसा होता है कि प्रत्येक ग्राफॉन के लिए, एक ग्राफॉन और इस तरह के चरणों के साथ एक चरण फलन होता है और मजबूत नियमितता का प्रमाण अवधारणा में उपरोक्त कोरोलरी 1 के समान है। यह पता चला है कि प्रत्येक ग्राफॉन को मानक में एक स्टेप फंक्शन के साथ अनुमानित किया जा सकता है, जो दर्शाता है कि गेंदों का सेट कवर करता है। ये सेट मीट्रिक में खुले नहीं होते हैं, लेकिन उन्हें खुला रखने के लिए थोड़ा बड़ा किया जा सकता है। अब, हम एक परिमित उप-आवरण ले सकते हैं, और कोई यह दिखा सकता है कि वांछित स्थिति का पालन होता है। सिडोरेंको का अनुमान ग्राफों की विश्लेषणात्मक प्रकृति समरूपता से संबंधित असमानताओं पर हमला करने में अधिक लचीलेपन की अनुमति देती है। उदाहरण के लिए, सिडोरेंको का अनुमान चरम ग्राफ सिद्धांत में एक प्रमुख खुली समस्या है, जो इस बात पर जोर देता है कि शीर्षों पर औसत डिग्री (कुछ के लिए) और शीर्षों और किनारों पर द्विदलीय ग्राफ के साथ किसी भी ग्राफ के लिए, समरूपता की संख्या कम से कम से कम है। चूँकि यह मात्रा यादृच्छिक ग्राफ में लेबल किए गए उपग्राफ की अपेक्षित संख्या है, इसलिए अनुमान की व्याख्या इस दावे के रूप में की जा सकती है कि किसी भी द्विदलीय ग्राफ के लिए, यादृच्छिक ग्राफ कुछ निश्चित किनारे के घनत्व के साथ सभी ग्राफ की प्रतियों की न्यूनतम संख्या (अपेक्षा में) प्राप्त करता है। सिडोरेंको के अनुमान के कई दृष्टिकोण समस्या को ग्राफॉन पर एक अभिन्न असमानता के रूप में तैयार करते हैं, जो तब अन्य विश्लेषणात्मक दृष्टिकोणों का उपयोग करके समस्या पर हमला करने की अनुमति देता है। सामान्यीकरण ग्राफॉन स्वाभाविक रूप से घने सरल ग्राफों से जुड़े होते हैं। घने निर्देशित भारित ग्राफों के लिए इस मॉडल के विस्तार हैं, जिन्हें अक्सर सजाए गए ग्राफोन के रूप में जाना जाता है। यादृच्छिक ग्राफ मॉडल और ग्राफ सीमा सिद्धांत दोनों के दृष्टिकोण से, विरल ग्राफ व्यवस्था के हाल के विस्तार भी हैं। संदर्भ ग्राफ सिद्धांत संभाव्यता सिद्धांत