ग्राफॉन

एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ $n$ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है $k\in \{1,\dotsc ,n\}$ एक अव्यक्त यादृच्छिक चर $U_{k}\sim \mathrm {U} (0,1)$ (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक शीर्ष सहित $(k,l)$ संभावना के साथ स्वतंत्र रूप से $f(U_{k},U_{l})$. उदाहरण के लिए, किनारा $(3,5)$ (हरा, बिंदीदार) संभावना के साथ सम्मलित है $f(0.72,0.9)$; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य $(u_{3},u_{5})$ और $(u_{5},u_{3})$. ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।

ग्राफ़ सिद्धांत और सांख्यिकी में, एक ग्राफ़ॉन (जिसे ग्राफ़ सीमा के रूप में भी जाना जाता है) एक सममित फलन औसत दर्जे का कार्य है: $W:[0,1]^{2}\to [0,1]$, जो सघन रेखांकन के अध्ययन में महत्वपूर्ण है। सघन रेखांकन के अनुक्रम की सीमा के लिए ग्राफ़न्स एक प्राकृतिक धारणा के रूप में उत्पन्न होते हैं, और विनिमेय यादृच्छिक चर यादृच्छिक ग्राफ़ मॉडल की मौलिक परिभाषित वस्तुओं के रूप में हैं। ग्राफ़ॉन निम्नलिखित प्रेक्षणों के युग्म द्वारा सघन ग्राफ़ से बंधे हैं: ग्राफ़ॉन द्वारा परिभाषित यादृच्छिक ग्राफ़ मॉडल लगभग निश्चित रूप से सघन ग्राफ़ को वृद्धि देते हैं, और, नियमितता लेम्मा द्वारा, ग्राफ़ॉन यादृच्छिक बृहत् सघन ग्राफ़ की संरचना को प्रग्रहण करते हैं।

सांख्यिकीय सूत्रीकरण

एक ग्राफॉन एक सममित मापने योग्य कार्य है $W:[0,1]^{2}\to [0,1]$. सामान्यत: एक ग्राफॉन को निम्न योजना के अनुसार विनिमेय यादृच्छिक ग्राफ मॉडल को परिभाषित करने के रूप में समझा जाता है:

1. प्रत्येक शीर्ष $j$ ग्राफ का एक स्वतंत्र यादृच्छिक मान नियुक्त किया गया है $u_{j}\sim U[0,1]$।
2. किनारा $(i,j)$ संभावना के साथ ग्राफ में स्वतंत्र रूप से सम्मलित है $W(u_{i},u_{j})$।

एक यादृच्छिक ग्राफ मॉडल एक विनिमेय यादृच्छिक ग्राफ मॉडल है और केवल इसे इस तरह (संभवतः यादृच्छिक) ग्राफॉन के संदर्भ में परिभाषित किया जा सकता है। एक निश्चित ग्राफॉन पर अर्द्धरित मॉडल $W$ कभी-कभी निरूपित किया जाता है $\mathbb {G} (n,W)$, यादृच्छिक रेखांकन के एर्डोस-रेनी मॉडल के अनुरूप। ग्राफॉन से उत्पन्न ग्राफ $W$ इस प्रकार कहा जाता है $W$-यादृच्छिक ग्राफ है।

यह इस परिभाषा और बड़ी संख्या के कानून से चलता है कि, यदि $W\neq 0$ विनिमेय यादृच्छिक ग्राफ मॉडल लगभग निश्चित रूप से सघन हैं।

उदाहरण

ग्राफॉन का सबसे सरल उदाहरण है $W(x,y)\equiv p$ कुछ स्थिर के लिए $p\in [0,1]$. इस स्थितियों में संबंधित विनिमेय यादृच्छिक ग्राफ मॉडल एर्डोस-रेनी मॉडल है $G(n,p)$ जिसमें संभाव्यता के साथ स्वतंत्र रूप से प्रत्येक किनारा सम्मलित है $p$।

यदि हम इसके अतिरिक्त एक ग्राफ़ॉन के साथ शुरू करते हैं जो टुकड़े वार स्थिर है:

1. इकाई वर्ग को विभाजित करना $k\times k$ ब्लॉक, और
2. सेटिंग $W$ $p_{lm}$के बराबर है $(l,m)^{\text{th}}$ ब्लाक पर

परिणामी विनिमेय यादृच्छिक ग्राफ मॉडल $k$ सामुदायिक स्टोकेस्टिक ब्लॉक मॉडल, एर्डोस-रेनी मॉडल का एक सामान्यीकरण है। हम इसे एक यादृच्छिक ग्राफ मॉडल के रूप में व्याख्या कर सकते हैं $k$ मापदंडों के साथ विशिष्ट एर्डोस-रेनी ग्राफ $p_{ll}$ क्रमशः, उनके बीच बिग्राफ के साथ जहां ब्लॉक के बीच प्रत्येक संभावित किनारा $(l,l)$ और $(m,m)$ संभाव्यता के साथ स्वतंत्र रूप से सम्मलित है $p_{lm}$।

कई अन्य लोकप्रिय यादृच्छिक ग्राफ़ मॉडल को कुछ ग्राफ़ॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ़ मॉडल के रूप में समझा जा सकता है, एक विस्तृत सर्वेक्षण ओर्बंज़ और रॉय में सम्मलित किया गया है।

संयुक्त रूप से विनिमेय आसन्न आव्यूह

$n$ आकार का एक यादृच्छिक ग्राफ एक यादृच्छिक $n\times n$ सहखंडज आव्यूह के रूप में दर्शाया जा सकता है। विभिन्न आकारों के यादृच्छिक रेखांकन के बीच निरंतरता (प्रोजेक्टिविटी के अर्थ में) लगाने के लिए, ऊपरी-बाएँ n x n उप-आव्यूह के रूप में उत्पन्न होने वाले आसन्न आव्यूह के अनुक्रम का अध्ययन करना स्वाभाविक है। यह हमें $G_{n}$ उत्पन्न करने की अनुमति देता है एक $G_{n-1}$ नोड जोड़कर और अश्रि का नमूना $(j,n)$ $j<n$ के लिए। इस दृष्टिकोण से, यादृच्छिक रेखांकन को यादृच्छिक $(X_{ij})$ अनंत सममित सरणियों के रूप में परिभाषित किया जाता है।

शास्त्रीय संभाव्यता में विनिमेय यादृच्छिक चर के मूलभूत महत्व के बाद, यादृच्छिक ग्राफ सेटिंग में एक समान धारणा की तलाश करना स्वाभाविक है। ऐसी ही एक धारणा संयुक्त रूप से विनिमेय आव्यूह द्वारा दी गई है; अर्थात यादृच्छिक आव्यूह संतोषजनक है:

$(X_{ij})\ {\overset {d}{=}}\,(X_{\sigma (i)\sigma (j)})$

सभी क्रमपरिवर्तन के लिए $\sigma$ प्राकृतिक संख्याओं की, जहाँ ${\overset {d}{=}}$ का अर्थ है यादृच्छिक चर#वितरण में समानता। सहज रूप से, इस स्थिति का अर्थ है कि यादृच्छिक ग्राफ का वितरण इसके शीर्षों के लेबलिंग द्वारा अपरिवर्तित है: अर्थात, शीर्षों के लेबल में कोई जानकारी नहीं होती है।

विनिमेय अनुक्रमों के लिए डी फिनेटी के प्रतिनिधित्व प्रमेय के अनुरूप, संयुक्त रूप से विनिमेय यादृच्छिक आसन्न आव्यूह के लिए एक प्रतिनिधित्व प्रमेय है। यह संयुक्त रूप से विनिमेय सरणियों के लिए एल्डस-हूवर प्रमेय का एक विशेष स्थितिा है और इस सेटिंग में, यह दावा करता है कि यादृच्छिक आव्यूह $(X_{ij})$ द्वारा उत्पन्न होता है:

1. नमूना $u_{j}\sim U[0,1]$ स्वतंत्र रूप से है।
2. $X_{ij}=X_{ji}=1$ संभावना के साथ यादृच्छिक रूप से स्वतंत्र रूप से $W(u_{i},u_{j}),$

जहाँ $W:[0,1]^{2}\to [0,1]$ एक (संभवतः यादृच्छिक) ग्राफॉन है। यही है, एक यादृच्छिक ग्राफ़ मॉडल में संयुक्त रूप से विनिमेय आसन्न आव्यूह होता है यदि यह केवल कुछ ग्राफ़ॉन के संदर्भ में परिभाषित संयुक्त रूप से विनिमेय यादृच्छिक ग्राफ़ मॉडल है।

ग्राफॉन अनुमान

पहचानने योग्य मुद्दों के कारण, ग्राफॉन फलन का अनुमान लगाना असंभव है, $W$ नोड अव्यक्त स्थिति $u_{i},$ और ग्राफॉन अनुमान की दो मुख्य दिशाएँ हैं। एक दिशा का उद्देश्य $W$ अनुमान लगाना है एक समकक्ष वर्ग तक, या $W$ द्वारा प्रेरित प्रायिकता आव्यूह का अनुमान लगाएं है।

विश्लेषणात्मक सूत्रीकरण

कोई भी ग्राफ $n$ वर्टेक्स $\{1,2,\dots ,n\}$ इसके आसन्न आव्यूह के साथ पहचाना जा सकता है $A_{G}$. यह आव्यूह एक स्टेपफंक्शन से मेल खाता है $W_{G}:[0,1]^{2}\to [0,1]$, विभाजन द्वारा परिभाषित $[0,1]$ अंतराल में

$I_{1},I_{2},\dots ,I_{n}$ ऐसा है कि $I_{j}$ इंटीरियर है

$$\left({\frac {j-1}{n}},{\frac {j}{n}}\right)$$

और प्रत्येक के लिए $(x,y)\in I_{i}\times I_{j}$, सेटिंग $W_{G}(x,y)$ के बराबर

$(i,j)^{\text{th}}$

का प्रवेश $A_{G}$. यह फलन $W_{G}$ ग्राफ का संबद्ध ग्राफॉन $G$ से है।

सामान्य तौर पर, यदि हमारे पास रेखांकन का एक क्रम है $(G_{n})$ जहां शीर्षों की संख्या $G_{n}$ अनंत तक जाता है, हम इसका विश्लेषण कर सकते हैं कार्यों के सीमित संचालन पर विचार करके अनुक्रम के संचालन को सीमित करना $(W_{G_{n}})$. यदि ये ग्राफ़ अभिसरित होते हैं (अभिसरण की कुछ उपयुक्त परिभाषा के अनुसार), तो हम उम्मीद करते हैं कि इन ग्राफ़ की सीमा इन संबंधित कार्यों की सीमा के अनुरूप होगी।

यह एक सममित मापने योग्य फलन के रूप में एक ग्राफॉन (ग्राफ़ फलन के लिए छोटा) की परिभाषा को प्रेरित करता है $W:[0,1]^{2}\to [0,1]$ रेखांकन के अनुक्रम की सीमा की धारणा को पकड़ता है। यह पता चला है कि सघन रेखांकन के अनुक्रमों के लिए, अभिसरण की स्पष्ट रूप से भिन्न कई धारणाएँ समतुल्य हैं और उन सभी के अंतर्गत प्राकृतिक सीमा वस्तु एक ग्राफॉन है।

उदाहरण

लगातार ग्राफॉन

$(G_{n})$ एर्डोस-रेनी यादृच्छिक रेखांकन का क्रम लीजिए $G_{n}=G(n,p)$ कुछ निश्चित पैरामीटर के साथ $p$. सहज रूप से, जैसा $n$ अनंत की ओर जाता है, रेखांकन के इस क्रम की सीमा पूरी तरह से इन रेखांकन के शीर्ष घनत्व द्वारा निर्धारित की जाती है। ग्राफ़न्स के स्थान में, यह पता चला है कि ऐसा अनुक्रम यादृच्छिक चर के अभिसरण # लगभग_निश्चित_अभिसरण को स्थिरांक में परिवर्तित करता है $W(x,y)\equiv p$, जो उपरोक्त अंतर्ज्ञान को प्रग्रहण कर लेता है।

अर्द्ध ग्राफॉन

$(H_{n})$ अर्द्ध ग्राफ का क्रम लीजिए अर्द्ध ग्राफ, लेने से परिभाषित $H_{n}$ द्विदलीय ग्राफ पर होना $2n$ वर्टेक्स $u_{1},u_{2},\dots ,u_{n}$ और $v_{1},v_{2},\dots ,v_{n}$ ऐसा है कि $u_{i}$ लगी हुई है $v_{j}$ ठीक है जब $i\leq j$ है. यदि शीर्षों को प्रस्तुत क्रम में सूचीबद्ध किया गया है, तब निकटतम आव्यूह $A_{H_{n}}$अर्द्ध वर्ग ब्लॉक आव्यूह के दो वर्टेक्स पूरित हैं, शेष प्रविष्टियाँ शून्य के बराबर हैं। उदाहरण के लिए, आसन्न आव्यूह $H_{3}$ द्वारा दिया गया है:

$${\begin{bmatrix}0&0&0&1&1&1\\0&0&0&0&1&1\\0&0&0&0&0&1\\1&0&0&0&0&0\\1&1&0&0&0&0\\1&1&1&0&0&0\end{bmatrix}}.$$

जैसा $n$ बृहत् हो जाते हैं, उनके ये वर्टेक्स निर्बाध हो जाते हैं। इस अंतर्ज्ञान का मिलान, अनुक्रम $(H_{n})$ अर्द्ध ग्राफॉन में परिवर्तित हो जाता है $W$ द्वारा परिभाषित $W(x,y)=1$ जब $|x-y|\geq 1/2$ और $W(x,y)=0$।

पूर्ण द्विदलीय ग्राफॉन

क्रम लीजिए $(K_{n,n})$ समान आकार के भागों के साथ पूर्ण द्विदलीय ग्राफ का क्रम लीजिए। यदि हम शुरुआत में सभी शीर्षों को एक भाग में रखकर शीर्षों को क्रमित करते हैं और दूसरे भाग के शीर्षों को अंत में रखकर, निकटतम आव्यूह $(K_{n,n})$ एक ब्लॉक ऑफ-विकर्ण आव्यूह की तरह दिखता है, जिसमें दो ब्लॉक और शून्य के दो ब्लॉक होते हैं। उदाहरण के लिए, आसन्न आव्यूह $K_{2,2}$ द्वारा दिया गया है:

$${\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}.$$

जैसा $n$ बड़ा हो जाता है, आसन्न आव्यूह की यह ब्लॉक संरचना स्थिर रहती है, जिससे कि रेखांकन का यह क्रम पूर्ण द्विदलीय ग्राफॉन में परिवर्तित हो जाए $W$ द्वारा परिभाषित $W(x,y)=1$ जब कभी भी $\min(x,y)\leq 1/2$ और $\max(x,y)>1/2$, और सेटिंग $W(x,y)=0$ अन्यथा हो।

यदि हम इसके अतिरिक्त शीर्षों को आदेश दें $K_{n,n}$ भागों के बीच बारी-बारी से, आसन्न आव्यूह में शून्य और एक की शतरंज की संरचना होती है। उदाहरण के लिए, इस आदेश के अनुसार, आसन्न आव्यूह $K_{2,2}$ द्वारा दिया गया है:

$${\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}.$$

जैसा $n$ बड़ा हो जाता है, आसन्न आव्युह बेहतर और बेहतर शतरंजबोर्ड बन जाते हैं। इस संचालन के बावजूद, हम अभी भी चाहते हैं की सीमा $(K_{n,n})$ अद्वितीय हो और परिणाम उदाहरण 3 से ग्राफॉन में हो। इसका मतलब यह है कि जब हम औपचारिक रूप से रेखांकन के अनुक्रम के लिए अभिसरण को परिभाषित करते हैं, तो एक सीमा की परिभाषा शीर्षों के पुन: लेबलिंग के लिए अज्ञेयवादी होनी चाहिए।

ए-यादृच्छिक रेखांकन की सीमा

एक यादृच्छिक क्रम $(G_{n})$ ग्राफॉन का#सांख्यिकीय_सूत्रीकरण लें। $W$ आहरण आरेख द्वारा यादृच्छिक रेखांकन $G_{n}\sim \mathbb {G} (n,W)$ कुछ निश्चित ग्राफॉन के लिए $W$. फिर इस खंड से पहले उदाहरण की तरह, यह पता चला है $(G_{n})$ में विलीन हो जाता है $W$ लगभग निश्चित रूप से है।

ग्राफोन से ग्राफ पैरामीटर पुनर्प्राप्त करना

दिया गया ग्राफ $G$ संबद्ध ग्राफॉन के साथ $W=W_{G}$, हम ग्राफ $G$ सैद्धांतिक गुणों और मापदंडों को पुनर्प्राप्त कर सकते हैं $W$ के परिवर्तनों को एकीकृत करके। उदाहरण के लिए, शीर्ष का घनत्व (अर्थात शीर्षों की संख्या से विभाजित औसत डिग्री)। $G$ अभिन्न द्वारा दिया गया है:

$$\int _{0}^{1}\int _{0}^{1}W(x,y)\;\mathrm {d} x\,\mathrm {d} y.$$

यह है क्योंकि $W$ है $\{0,1\}$-मूल्यवान, और प्रत्येक किनारा $(i,j)$ में $G$ एक क्षेत्र से मेल खाता है $I_{i}\times I_{j}$ क्षेत्र के $1/n^{2}$ जहाँ $W$ बराबर होती है $1$ के।

इसी तरह के तर्क से पता चलता है कि त्रिभुजों की संख्या में $G$ के बराबर है।

$${\frac {1}{6}}\int _{0}^{1}\int _{0}^{1}\int _{0}^{1}W(x,y)W(y,z)W(z,x)\;\mathrm {d} x\,\mathrm {d} y\,\mathrm {d} z.$$

अभिसरण की धारणा

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

स्वाभाविक रूप से, एक ही वर्टेक्स सेट पर दो ग्राफ़ दिए गए हैं, कोई उनकी दूरी को अश्रि की संख्या के रूप में परिभाषित कर सकता है जिसे एक ग्राफ़ से दूसरे ग्राफ़ में प्राप्त करने के लिए जोड़ा या हटाया जाना चाहिए, अर्थात उनका ग्राफ़ एडिट डिस्टेंस है। चूंकि, संपादन दूरी समान रूप से यादृच्छिक ग्राफ़ की पहचान नहीं करती है; वास्तव में, दो रेखांकन स्वतंत्र रूप से खींचे गए हैं $G(n,{\tfrac {1}{2}})$ की अपेक्षित (सामान्यीकृत) संपादन दूरी ${\tfrac {1}{2}}$ है।

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

चमत्कारिक ढंग से, ग्राफ़ का एक क्रम ठीक उसी समय एक मीट्रिक के संबंध में अभिसरण करता है जब यह दूसरे के संबंध में अभिसरण करता है। इसके अतिरिक्त, दोनों आव्युह के अनुसार लिमिट ऑब्जेक्ट ग्राफॉन बन जाते हैं। अभिसरण की इन दो धारणाओं की समानता यह दर्शाती है कि फैन चुंग अर्ध-यादृच्छिक ग्राफ की विभिन्न धारणाएँ किस प्रकार समतुल्य हैं।

समरूपता घनत्व

दो रेखांकन के बीच की दूरी को मापने का एक तरीका $G$ और $H$ के सापेक्ष सबग्राफ गणनांक की तुलना करना है। अर्थात प्रत्येक ग्राफ के लिए हम $F$ की प्रतियों की संख्या की तुलना कर सकते हैं $F$ में $G$ और $F$ में $H$। यदि ये संख्याएं हर ग्राफ के करीब हैं $F$, तब सहज ज्ञान से $G$ और $H$ समान दिखने वाले ग्राफ हैं। सबग्राफ से सीधे डीलिंग के अतिरिक्त, यह ग्राफ समरूपता के साथ काम करने के लिए आसान हो जाता है। इस परिदृश्य में बृहत्,सघन ग्राफ से डीलिंग के दौरान यह ठीक है, सबग्राफ की संख्या और एक निश्चित ग्राफ से ग्राफ समरूपता की संख्या असम्बद्ध रूप से बराबर होती है।

दो रेखांकन दिए गए हैं $F$ और $G$, समरूपता घनत्व $t(F,G)$ का $F$ में $G$ से ग्राफ़ समरूपता की संख्या के रूप $F$ को $G$ में परिभाषित किया गया है। दूसरे शब्दों में, $t(F,G)$ के शीर्ष से यादृच्छिक रूप से चुने गए मानचित्र की प्रायिकता है $F$ के शिखर तक $G$ सन्निकट शीर्षों को अंदर भेजता है $F$ सन्निकट शीर्षों में $G$ है।

ग्राफोन समरूपता घनत्व की गणना करने का एक सरल तरीका प्रदान करते हैं। दरअसल, एक ग्राफ $G$ संबद्ध ग्राफॉन के साथ $W_{G}$ और दुसरी $F$, अपने पास है:

$$t(F,G)=\int \prod _{(i,j)\in E(F)}W_{G}(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}$$

जहां अविभाज्य बहुआयामी है, यूनिट अतिविम पर लिया गया है $[0,1]^{V(F)}$. यह संबंधित ग्राफॉन की परिभाषा से अनुसरण करता है, जब उपरोक्त एकीकृत के बराबर होता है $1$. फिर हम समरूपता घनत्व की परिभाषा को यादृच्छिक ग्राफॉन $W$ तक बढ़ा सकते हैं, एक ही अभिन्न और परिभाषित करने का उपयोग करके:

$$t(F,W)=\int \prod _{(i,j)\in E(F)}W(x_{i},x_{j})\;\left\{\mathrm {d} x_{i}\right\}_{i\in V(F)}$$

किसी भी ग्राफ के लिए $F$ है।

इस सेटअप को देखते हुए, हम रेखांकन का एक क्रम कहते हैं $(G_{n})$ यदि प्रत्येक नियत ग्राफ के लिए $F$ वाम-अभिसरण है, समरूपता घनत्व का क्रम $\left(t(F,G_{n})\right)$ अभिसरण। चूंकि अकेले परिभाषा से स्पष्ट नहीं है, यदि $(G_{n})$ इस अर्थ में अभिसरण करता है, तो हमेशा एक ग्राफॉन सम्मलित होता है $W$ ऐसा है कि हर ग्राफ के लिए $F$, अपने पास है:

$$\lim _{n\to \infty }t(F,G_{n})=t(F,W)$$

इसके साथ ही।

दूरी कम करें

दो ग्राफ लीजिए $G$ और $H$ उसी शीर्ष सेट पर। क्योंकि ये रेखांकन समान शीर्षों को साझा करते हैं, उनकी दूरी को मापने का एक तरीका $X,Y$ सबसेट तक सीमित करना है वर्टेक्स सेट की, और ऐसे प्रत्येक जोड़ी सबसेट के लिए अश्रि की संख्या की तुलना करें $e_{G}(X,Y)$ से $X$ को $Y$ में $G$ अश्रि की संख्या के लिए $e_{H}(X,Y)$ बीच में $X$ और $Y$ में $H$. यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है $G$ और $H$ समान रेखांकन हैं।

रेखांकन के किसी भी जोड़े के लिए दूरी की इस धारणा की प्रारंभिक औपचारिकता के रूप में $G$ और $H$ उसी शीर्ष सेट पर $V$ आकार का $|V|=n$, $G$ और $H$ के बीच लेबल कट दूरी को परिभाषित करें:

d_\square(G, H) = \frac 1{n^2} \max_{X, Y\subseteq V}\left|e_G(X,Y) - e_H(X,Y)\right|.</math>

दूसरे शब्दों में, लेबल की गई कट दूरी बीच के शीर्ष घनत्व की अधिकतम विसंगति को $G$ और $H$ कूटबद्ध करती है। हम शीर्ष के घनत्व को व्यक्त करके इस अवधारणा को ग्राफॉन के लिए सामान्यीकृत कर सकते हैं ${\tfrac {1}{n^{2}}}e_{G}(X,Y)$ संबंधित ग्राफॉन के संदर्भ में $W_{G}$, समानता दे रहा है:

$$d_{\square }(G,H)=\max _{X,Y\subseteq V}\left|\int _{I_{X}}\int _{I_{Y}}W_{G}(x,y)-W_{H}(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|$$

जहाँ $I_{X},I_{Y}\subseteq [0,1]$ में $X$ और $Y$ वर्टेक्स के अनुरूप अंतराल के संघ हैं। ध्यान दें कि इस परिभाषा का तब भी उपयोग किया जा सकता है जब तुलना किए जा रहे ग्राफ़ एक शीर्ष सेट को साझा नहीं करते हैं। यह निम्नलिखित अधिक सामान्य परिभाषा को प्रेरित करता है।

परिभाषा 1. किसी भी सममित, मापने योग्य कार्य के लिए $f:[0,1]^{2}\to \mathbb {R}$, के कट मानदंड को $f$ मात्रा परिभाषित करें:

$$\lVert f\rVert _{\square }=\sup _{S,T\subseteq [0,1]}\left|\int _{S}\int _{T}f(x,y)\;\mathrm {d} x\,\mathrm {d} y\right|$$

सभी औसत दर्जे का सबसेट ले लिया $S,T$ इकाई अंतराल है। </ब्लॉककोट>

यह लेबल कट दूरी की हमारी पहले की धारणा को दर्शाता है, क्योंकि हमारे पास समानता है $\lVert W_{G}-W_{H}\rVert _{\square }=d_{\square }(G,H)$.

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

परिभाषा 2. ग्राफॉन के किसी भी जोड़े के लिए $U$ और $W$, उनकी कट दूरी को परिभाषित करें:

$$\delta _{\square }(U,W)=\inf _{\varphi }\lVert U-W^{\varphi }\rVert _{\square }$$

जहाँ $W^{\varphi }(x,y)=W(\varphi (x),\varphi (y))$ की रचना है $W$ नक्शे के साथ $\varphi$, और न्यूनतम को सभी अपरिवर्तनीय उपाय पर ले लिया जाता है माप-संरक्षण आक्षेपों को इकाई अंतराल से स्वयं में। </ब्लॉककोट>

दो ग्राफ़ के बीच कट की दूरी को उनके संबंधित ग्राफ़ॉन के बीच कट की दूरी के रूप में परिभाषित किया गया है।

अब हम कहते हैं कि रेखांकन का एक क्रम $(G_{n})$ कट दूरी के अनुसार अभिसारी है यदि यह कट दूरी के अनुसार एक कॉची अनुक्रम है $\delta _{\square }$. चूंकि यह परिभाषा का सीधा परिणाम नहीं है, यदि ग्राफ का ऐसा क्रम कॉची है, तो $W$ हमेशा किसी ग्राफॉन में परिवर्तित हो जाता है।

अभिसरण की समानता

जैसे ही यह पता चला कि रेखांकन के किसी भी क्रम के लिए $(G_{n})$, बायाँ-अभिसरण कट दूरी के अनुसार अभिसरण के बराबर है, और इसके अतिरिक्त, सीमा रेखाचित्र $W$ एक ही है। हम समान परिभाषाओं का उपयोग करके स्वयं ग्राफोन के अभिसरण पर भी विचार कर सकते हैं, और समान समानता सत्य है। वास्तव में, अभिसरण की दोनों धारणाएं काउंटिंग लेम्मा के माध्यम से अधिक मजबूती से संबंधित हैं।

<ब्लॉककोट>काउंटिंग लेम्मा। ग्राफॉन की किसी भी जोड़ी के लिए $U$ और $W$, अपने पास है:

$$|t(F,U)-t(F,W)|\leq e(F)\delta _{\square }(U,W)$$

सभी रेखांकन के लिए $F$ है। </ब्लॉककोट>

गिनती लेम्मा नाम उस सीमा से आता है जो यह लेम्मा समरूपता घनत्व पर देती है $t(F,W)$, जो ग्राफ़ के सबग्राफ काउंट के अनुरूप हैं। यह लेम्मा ज़ेमेरेडी नियमितता लेम्मा# ग्राफ काउंटिंग लेम्मा का एक सामान्यीकरण है जो ज़ेमेरेडी नियमितता लेम्मा के क्षेत्र में दिखाई देता है, और यह तुरंत दिखाता है कि कट दूरी के अनुसार अभिसरण का अर्थ बाएं-अभिसरण है।

व्युत्क्रम काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए $\epsilon >0$, एक वास्तविक संख्या सम्मलित है $\eta >0$ और एक सकारात्मक पूर्णांक $k$ ऐसा कि किसी भी जोड़ी ग्राफोन के लिए $U$ और $W$ साथ

$$|t(F,U)-t(F,W)|\leq \eta$$

सभी रेखांकन के लिए $F$ संतुष्टि देने वाला $v(F)\leq k$, हमारे पास यह होना चाहिए $\delta _{\square }(U,W)<\epsilon$.

इस लेम्मा से पता चलता है कि वाम-अभिसरण का अर्थ कटी हुई दूरी के अंतर्गत अभिसरण है।

ग्राफोन का स्थान

हम सभी ग्राफ़ॉन और कोटिएंट_स्पेस_(टोपोलॉजी) दो ग्राफ़ॉन का सेट लेकर कट-दूरी को आव्यूह में बदल सकते हैं $U\sim W$ जब कभी भी $\delta _{\square }(U,W)=0$. ग्राफॉन के परिणामी स्थान को निरूपित किया जाता है ${\widetilde {\mathcal {W}}}_{0}$, और साथ में $\delta _{\square }$ एक मीट्रिक स्थान बनाता है।

यह स्थान सघन स्थान बन जाता है। इसके अतिरिक्त, इसमें सभी परिमित रेखांकन का सेट होता है, जो उनके संबंधित ग्राफों द्वारा एक सघन सेट के रूप में दर्शाया जाता है। इन अवलोकनों से पता चलता है कि ग्राफ़ॉन का स्थान एक पूर्ण_मीट्रिक_स्थान है#कट की गई दूरी के संबंध में ग्राफ़ के स्थान का पूरा होना। इसका एक तात्कालिक परिणाम निम्नलिखित है।

अनुप्रमेय 1. प्रत्येक वास्तविक संख्या के लिए $\epsilon >0$, एक पूर्णांक है $N$ ऐसा है कि हर ग्राफॉन के लिए $W$, एक ग्राफ है $G$ अधिक से अधिक के साथ $N$ ऐसा शिखर $\delta _{\square }(W,W_{G})<\epsilon$.

माना कि ${\mathcal {G}}$ रेखांकन का सेट हो। प्रत्येक ग्राफ के लिए विचार करें $G\in {\mathcal {G}}$ खुली गेंद $B_{\square }(G,\epsilon )$ जिसमें सभी ग्राफोन हों $W$ ऐसा है कि $\delta _{\square }(W,W_{G})<\epsilon$. सभी ग्राफ कवर के लिए खुली गेंदों का सेट ${\widetilde {\mathcal {W}}}_{0}$, इसलिए सघन का अर्थ है कि एक परिमित उपकवर है $\{B_{\square }(G,\epsilon )\mid G\in {\mathcal {G}}_{0}\}$ कुछ परिमित उपसमुच्चय के लिए ${\mathcal {G}}_{0}\subset {\mathcal {G}}$. अब हम ले सकते हैं $N$ रेखांकन के बीच शीर्षों की सबसे बड़ी संख्या होना ${\mathcal {G}}_{0}$.

अनुप्रयोग

नियमितता लेम्मा

ग्राफॉन के स्थान की सघनता $({\widetilde {\mathcal {W}}}_{0},\delta _{\square })$ ज़ेमेरीडी नियमितता लेम्मा के विश्लेषणात्मक सूत्रीकरण के रूप में सोचा जा सकता है ज़ेमेरीडी की नियमितता लेम्मा; वास्तव में, मूल लेम्मा की तुलना में एक मजबूत परिणाम है। ज़ेमेरेडी की नियमितता लेम्मा को ग्राफोन की भाषा में निम्नानुसार अनुवादित किया जा सकता है। एक ग्राफॉन बनने के लिए एक स्टेपफंक्शन को परिभाषित करें $W$ यह टुकड़े-टुकड़े स्थिर है, अर्थात कुछ विभाजन के लिए ${\mathcal {P}}$ का $[0,1]$, $W$ निरंतर चालू है $S\times T$ सभी के लिए $S,T\in {\mathcal {P}}$. बयान है कि एक ग्राफ $G$ एक नियमितता विभाजन यह कहने के बराबर है कि इससे संबंधित ग्राफॉन है $W_{G}$ एक स्टेपफंक्शन के करीब है।

सघननेस के प्रमाण के लिए केवल ज़ेमेरीडी नियमितता लेम्मा#फ्रीज़-कन्नन_नियमितता की आवश्यकता होती है:

ग्राफन के लिए कमजोर नियमितता प्रमेयिका। हर ग्राफन के लिए $W$ और $\epsilon >0$, एक स्टेपफंक्शन है $W'$ अधिक से अधिक के साथ $\lceil 4^{1/\epsilon ^{2}}\rceil$ ऐसे कदम $\lVert W-W'\rVert _{\square }\leq \epsilon$.

लेकिन इसका उपयोग मजबूत नियमितता परिणाम सिद्ध करने के लिए किया जा सकता है, जैसे कि ज़ेमेरीडी नियमितता लेम्मा#मजबूत नियमितता लेम्मा है।

ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए $\mathbf {\epsilon } =(\epsilon _{0},\epsilon _{1},\dots )$ धनात्मक वास्तविक संख्याओं का, एक धनात्मक पूर्णांक होता है $S$ ऐसा है कि हर ग्राफॉन के लिए $W$, एक ग्राफन है $W'$ और एक स्टेपफंक्शन $U$ साथ $k<S$ ऐसे कदम $\lVert W-W'\rVert _{1}\leq \epsilon _{0}$ और $\lVert W'-U\rVert _{\square }\leq \epsilon _{k}.$

मजबूत नियमितता प्रमेयिका का प्रमाण ऊपर दिए गए परिणाम 1 की अवधारणा के समान है। यह पता चला है कि हर ग्राफॉन $W$ एक स्टेपफंक्शन के साथ अनुमान लगाया जा सकता है $U$ एलपी_स्पेस#एलपी_स्पेस_एंड_लेब्सग्यू_इंटीग्रल्स में $L_{1}$ मानदंड, दिखा रहा है कि गेंदों का सेट $B_{1}(U,\epsilon _{0})$ ढकना ${\widetilde {\mathcal {W}}}_{0}$. ये सेट में नहीं खुले हैं $\delta _{\square }$ मीट्रिक, लेकिन खुले रहने के लिए उन्हें थोड़ा बड़ा किया जा सकता है। अब, हम एक परिमित उपकवर ले सकते हैं, और कोई यह दिखा सकता है कि वांछित स्थिति इस प्रकार है।

सिदोरेंको का अनुमान

Main article: सिदोरेंको का अनुमान

ग्राफोन की विश्लेषणात्मक प्रकृति समरूपता से संबंधित असमानताओं पर आक्षेप करने में अधिक लचीलेपन की अनुमति देती है।

उदाहरण के लिए, सिडोरेंको का अनुमान चरम ग्राफ सिद्धांत में एक बड़ी खुली समस्या है, जो किसी भी ग्राफ के लिए दावा करता है $G$ पर $n$ औसत डिग्री के साथ शिखर $pn$ (कुछ के लिए $p\in [0,1]$) और द्विदलीय ग्राफ $H$ पर $v$ शिखर और $e$ अश्रि, ग्राफ समरूपता की संख्या से $H$ को $G$ कम से कम है $p^{e}n^{v}$. चूंकि यह मात्रा लेबल दिए गए सबग्राफ की अपेक्षित संख्या है $H$ एक यादृच्छिक ग्राफ में $G(n,p)$, अनुमान की व्याख्या दावे के रूप में की जा सकती है कि किसी भी द्विदलीय ग्राफ के लिए $H$, यादृच्छिक ग्राफ प्राप्त करता है (उम्मीद में) प्रतियों की न्यूनतम संख्या $H$ कुछ निश्चित बढ़त घनत्व के साथ सभी रेखांकन पर है।

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

सामान्यीकरण

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