🔢 mathematics

Limit theorems for walks and triangles on Erdös-Rényi random graphs with large interaction radius

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

मूल लेखक: O. Khorunzhiy

प्रकाशित 2026-06-05

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: O. Khorunzhiy

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

एक बड़ी तस्वीर: एक बदलते शहर का मानचित्रण

कल्पना कीजिए कि आप एक शहरी योजनाकार (urban planner) हैं जो एक विशाल, निरंतर विस्तार करते शहर में यातायात के प्रवाह को समझने की कोशिश कर रहे हैं। इस शहर में, "सड़कें" लोगों (या नोड्स) के बीच के संबंध हैं, और "ट्रैफिक" इन सड़कों पर सूचना या ऊर्जा की गति है।

आमतौर पर, गणितज्ञ एक ऐसे शहर का अध्ययन करते हैं जहाँ हर व्यक्ति के पास दूरी की परवाह किए बिना हर दूसरे व्यक्ति को जानने का समान अवसर होता है। यह क्लासिक एर्दोश-रेनी (Erdős-Rényi) मॉडल है। लेकिन इस शोध पत्र में, लेखक, ओ. खोरुनज़ी (O. Khorunzhiy), एक अधिक यथार्थवादी शहर का अध्ययन करते हैं: दूरी-निर्भर शहर (The Distance-Dependent City)।

इस शहर में, आपके अपने पड़ोसी से सड़क होने की संभावना, दुनिया के दूसरे छोर पर रहने वाले व्यक्ति से सड़क होने की तुलना में बहुत अधिक है। "इंटरैक्शन रेडियस" ( $R$ ) आपके पड़ोस के आकार की तरह है। यदि $R$ छोटा है, तो आप केवल अपने निकटतम पड़ोसियों को जानते हैं। यदि $R$ बहुत बड़ा है, तो आप पूरे शहर के लोगों को जानते हैं।

यह शोध पत्र पूछता है: जब शहर अनंत रूप से बड़ा हो जाता है, जनसंख्या बढ़ती है, और पड़ोस का आकार ( $R$ ) भी बढ़ता है, तो ट्रैफिक पैटर्न में क्या बदलाव आता है?

तीन परिदृश्य (Asymptotic Regimes)

लेखक ने खोजा है कि इस शहर का व्यवहार शहर के आकार ( $N$ ), जनसंख्या घनत्व ( $c$ ), और पड़ोस के आकार ( $R$ ) के बीच के संबंध के आधार पर नाटकीय रूप से बदल जाता है। उन्होंने तीन अलग-अलग "मौसम के पैटर्न" या रेजिम की पहचान की है:

घना कोहरा (उच्च सांद्रता - High Concentration): यहाँ, पड़ोस इतना बड़ा और जनसंख्या इतनी घनी है कि प्रभावी रूप से हर कोई हर किसी से जुड़ा हुआ है। यह एक भीड़ भरे कमरे की तरह है जहाँ आप हर किसी की बातें सुन सकते हैं।
संतुलित पड़ोस (मध्यम सांद्रता - Medium Concentration): पड़ोस का आकार और जनसंख्या पूरी तरह से संतुलित है। आपके पास कनेक्शनों की एक स्थिर संख्या है, न बहुत कम और न ही बहुत अधिक।
विरल रेगिस्तान (कम सांद्रता - Low Concentration): पड़ोस बहुत बड़ा है, लेकिन जनसंख्या इतनी बिखरी हुई है कि कनेक्शन दुर्लभ हैं। यह एक विशाल रेगिस्तान की तरह है जहाँ आपको मीलों तक शायद ही कोई दूसरा व्यक्ति दिखाई दे।

दो मुख्य माप

शहर को समझने के लिए, लेखक दो विशिष्ट चीजों को गिनते हैं:

चक्कर/भ्रमण (Open Paths): कल्पना कीजिए कि एक यात्री एक घर से शुरू होकर एक अलग घर पर समाप्त होने वाले $q$ चरणों के माध्यम से शहर में यात्रा करता है। लेखक इस लंबाई के कितने अद्वितीय पथ मौजूद हैं, उन्हें गिनते हैं।
- निष्कर्ष: तीनों रेजिम्स में, इन चक्करों की संख्या एक अनुमानित पैटर्न (एक "नॉर्मल डिस्ट्रीब्यूशन" या बेल कर्व की तरह) का पालन करती है। यह ऐसा है जैसे शहर की अराजकता एक सुचारू, अनुमानित प्रवाह में औसत हो जाती है।
त्रिकोण (बंद लूप - Closed Loops): कल्पना कीजिए कि एक यात्री एक घर से शुरू होता है, दो अन्य घरों का दौरा करता है, और वापस शुरुआती बिंदु पर लौट आता है। यह एक त्रिकोण बनाता है। ग्राफ थ्योरी में, इन्हें "ट्रायंगल्स" (triangles) कहा जाता है।
- निष्कर्ष: यहीं पर मामला जटिल हो जाता है।
  - घने (Dense) और संतुलित (Balanced) रेजिम्स में, त्रिकोणों की संख्या भी एक सुचारू, अनुमानित बेल कर्व का पालन करती है।
  - हालाँकि, विरल (Sparse) रेजिम में, कुछ जादुई होता है। यदि पैरामीटर बिल्कुल सही हैं, तो त्रिकोणों की संख्या बेल कर्व का पालन नहीं करती है; यह एक पॉइसन डिस्ट्रीब्यूशन (Poisson Distribution) का पालन करती है।
  - उपमा: बेल कर्व को बारिश की एक स्थिर धारा (अनुमानित, निरंतर) के रूप में सोचें। पॉइसन डिस्ट्रीब्यूशन बिजली गिरने (lightning strikes) की तरह है। आप जानते हैं कि बिजली गिरती है, लेकिन आप ठीक-ठीक भविष्यवाणी नहीं कर सकते कि अगली बार कब गिरेगी। यह दुर्लभ, यादृच्छिक और "स्पाइकी" (अचानक होने वाली) होती है।

"ग्राफ कोलैप्स" की समस्या का समाधान

इस शोध पत्र के सबसे रोमांचक दावों में से एक "ग्राफ कोलैप्स" (Graph Collapse) नामक समस्या को हल करना है।

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

रूपक (Metaphor): एक पार्टी की कल्पना करें। आमतौर पर, यदि आप चाहते हैं कि लाखों तीन-व्यक्ति वाली बातचीत हो रही हो, तो आपको एक स्टेडियम की आवश्यकता होगी जो कंधों से कंधा मिलाकर भरा हो। लेखक दिखाते हैं कि आप इन बड़ी संख्या में बातचीत को तब भी प्राप्त कर सकते हैं जब हर कोई एक-दूसरे से दूर खड़ा हो, बशर्ते कि "कमरा" (इंटरैक्शन रेडियस) सही आकार का हो। संरचना बिना टूटे बनी रहती है।

गणित के लिए "पेड़" (Tree) की उपमा

इन परिणामों को सिद्ध करने के लिए, लेखक डायग्रामेटिक्स (Diagrammatics) नामक एक तकनीक का उपयोग करते हैं। वह रैंडम ग्राफ के जटिल गणित को पेड़ों (trees) के चित्रों में अनुवादित करते हैं।

कल्पना कीजिए कि शहर में कनेक्शन शाखाओं (branches) की तरह हैं।
वह इन शाखाओं को "मैक्सिमल ट्रीज़" (बड़ी, फैलती हुई शाखाएं), "मिनिमल ट्रीज़" (छोटी टहनियां), और उनके बीच की हर चीज़ में वर्गीकृत करते हैं।
वह इन ट्री स्ट्रक्चर्स को सटीक रूप से गिनने के लिए प्रुफर कोडिफिकेशन (Prüfer Codification) नामक कोडिंग सिस्टम (संख्याओं की एक अनूठी स्ट्रिंग, जैसे बारकोड) का उपयोग करते हैं।
इन "ट्री बारकोड" को गिनकर, वह ठीक से गणना कर सकते हैं कि शहर के व्यवहार की सटीक संभावना क्या है।

"लिमिट थ्योरम्स" का सारांश

यह शोध पत्र सिद्ध करता है कि जैसे-जैसे शहर अनंत तक बढ़ता है:

ओपन वॉक्स (Open Walks): हमेशा एक सुचारू, अनुमानित बेल कर्व की तरह व्यवहार करते हैं।
त्रिकोण (Triangles): बेल कर्व या बिजली गिरने (पॉइसन) की तरह व्यवहार कर सकते हैं, यह इस पर निर्भर करता है कि शहर कैसे बनाया गया है।
"कोलैप्स" (The Collapse): यह गणितीय रूप से संभव है कि आपके पास घनिष्ठ समूहों (त्रिकोणों) का एक विशाल, जटिल नेटवर्क हो, बिना उस नेटवर्क के इतना सघन हुए कि वह टूट जाए।

संक्षेप में, लेखक ने एक विशाल, दूरी-संवेदनशील नेटवर्क के "भौतिकी" का मानचित्र तैयार किया है, यह दिखाते हुए कि यह हमें ठीक से बताता है कि कब यह सुचारू रूप से व्यवहार करता है और कब यह यादृच्छिक, दुर्लभ घटनाओं की एक श्रृंखला की तरह व्यवहार करता है, और यह भी सिद्ध करता है कि हम बिना किसी पतन (collapse) के जटिल संरचनाएं बना सकते हैं।

तकनीकी सारांश: बड़े इंटरेक्शन रेडियस वाले अर्दोस-रेनी रैंडम ग्राफ्स पर वॉक्स और ट्रायंगल्स के लिए लिमिट थ्योरम्स

समस्या विवरण
यह शोध पत्र एक संशोधित अर्दोस-रेनी रैंडम ग्राफ एनसेंबल पर $q$ -स्टेप वॉक्स की संख्या और ट्रायंगल्स (3-स्टेप क्लोज्ड वॉक्स) की संख्या से जुड़े क्यूमलेंट्स (cumulants) के एसिम्प्टोटिक व्यवहार की जांच करता है। शास्त्रीय अर्दोस-रेनी मॉडल के विपरीत, जहाँ एज प्रोबेबिलिटी यूनिफॉर्म होती है, यह अध्ययन उन ग्राफ्स पर विचार करता है जहाँ वर्टिक्स के बीच की एज प्रोबेबिलिटी, एक इंटरेक्शन रेडियस $R$ द्वारा नियंत्रित, वर्टिक्स के बीच की दूरी पर निर्भर करती है। विश्लेषण उन तीन विशिष्ट एसिम्प्टोटिक रेजीमों (regimes) पर केंद्रित है जो मापदंडों के स्केलिंग ( $q$ -स्टेप नॉन-क्लोज्ड वॉक्स के लिए $cR/N $और ट्रायंगल्स के लिए$ c^2R/N^2$) द्वारा परिभाषित होते हैं। मुख्य उद्देश्य "ग्राफ कोलैप्स समस्या" को हल करना है, जो एक ऐसी घटना है जहाँ ट्रायंगल्स की कुल संख्या बढ़ सकती है जबकि औसत वर्टेक्स डिग्री सीमित रहती है—एक ऐसी स्थिति जो मानक अर्दोस-रेनी एनसेंबल में संभव नहीं है।

कार्यप्रणाली
लेखक रैंडम मैट्रिक्स थ्योरी तकनीकों और कॉम्बिनेटोरियल डायग्राम विधियों के संयोजन का उपयोग करते हैं। मुख्य कार्यप्रणाली निम्नलिखित है:

क्यूमलेंट एक्सपेंशन: अध्ययन मैट्रिक्स मॉडल्स के फ्री एनर्जी के क्यूमलेंट एक्सपेंशन का उपयोग करता है। रुचि के रैंडम वेरिएबल्स $Y^{(q)}$ (कुल नॉन-क्लोज्ड वॉक्स) और $X^{(q)}$ (कुल क्लोज्ड वॉक्स) को एडजेसेंसी मैट्रिक्स की पावर्स के ट्रेसेस के माध्यम से व्यक्त किया जाता है।
डायग्राम तकनीक: लेखक इन वेरिएबल्स के मिक्स्ड क्यूमलेंट्स की गणना करने के लिए एक डायग्रामैटिक दृष्टिकोण (कनेक्टेड डायग्राम्स) को अनुकूलित करते हैं। वे रैंडम वेरिएबल्स के उत्पाद को लीनियर एलिमेंट्स ( $\lambda_q$ वॉक्स के लिए) या ट्रायंगल एलिमेंट्स ( $\mu_3$ ट्रायंगल्स के लिए) से निर्मित मल्टी-ग्राफ्स के रूप में निरूपित करते हैं।
डायग्रामों का वर्गीकरण: डायग्रामों को उनकी टोपोलॉजिकल संरचना के आधार पर तीन प्रकारों में वर्गीकृत किया गया है:
- मैक्सिमल ट्री-टाइप डायग्राम्स: वे जिनमें दिए गए वर्टिक्स के लिए अधिकतम किनारों (edges) की संख्या होती है।
- जनरल ट्री-टाइप डायग्राम्स: वे सभी डायग्राम जो एक ट्री संरचना बनाते हैं।
- मिनिमल ट्री-टाइप डायग्राम्स: वे जिनमें न्यूनतम किनारों की संख्या होती है (अक्सर उच्च मल्टीसिटी के साथ सिंगल एजेस)।
एसिम्प्टोटिक विश्लेषण: $N, c, R \to \infty$ की सीमा में इन डायग्राम्स से जुड़े वेट्स के ऑर्डर ऑफ मैग्नीट्यूड का विश्लेषण करके, लेखक यह निर्धारित करते हैं कि प्रत्येक तीन रेजीम में कौन सा डायग्राम क्लास क्यूमलेंट एक्सपेंशन पर हावी होता है।
कॉम्बिनेटोरियल एन्यूमरेशन: स्पष्ट लिमिटिंग क्यूमलेंट्स प्राप्त करने के लिए, शोध पत्र एक संशोधित प्रुफर कोडीफिकेशन प्रक्रिया (कलर प्रुफर कोड्स) का उपयोग करता है ताकि मैक्सिमल और मिनिमल ट्री-टाइप डायग्राम्स की संख्या को गिना जा सके।

मुख्य परिणाम

नॉन-क्लोज्ड वॉक्स ( $Y^{(q)}$ के लिए लिमिटिंग क्यूमलेंट्स:
शोध पत्र $cR/N $द्वारा निर्धारित तीन रेजीमों में$ Y^{(q)} $के$ k$-वें क्यूमलेंट्स के अस्तित्व को स्थापित करता है:
- डेंस रेजीम ( $cR/N \gg 1$ ): लिमिटिंग क्यूमलेंट्स मैक्सिमल ट्री-टाइप डायग्राम्स की संख्या द्वारा निर्धारित होते हैं।
- इंटरमीडिएट रेजीम ($cR/N = s$): लिमिटिंग क्यूमलेंट्स सभी ट्री-टाइप डायग्राम्स के योग द्वारा निर्धारित होते हैं।
- स्पार्स रेजीम ( $cR/N \ll 1$ ): लिमिटिंग क्यूमलेंट्स मिनिमल ट्री-टाइप डायग्राम्स द्वारा निर्धारित होते हैं।
  इन लिमिट्स के लिए स्पष्ट सूत्र प्रदान किए गए हैं, जिनमें इंटरेक्शन फंक्शन $\psi(x)$ के इंटीग्रल्स और प्रुफर कोड एन्यूमरेशन से प्राप्त कॉम्बिनेटोरियल फैक्टर्स शामिल हैं।
ट्रायंगल्स ( $X^{(3)}$ के लिए लिमिटिंग क्यूमलेंट्स):
इसी तरह के परिणाम ट्रायंगल्स की संख्या के लिए प्राप्त किए गए हैं, जो पैरामीटर $c^2R/N^2$ द्वारा नियंत्रित होते हैं:
- डेंस और इंटरमीडिएट रेजीम में, लिमिट्स मैक्सिमल और जनरल ट्री-टाइप डायग्राम्स के अनुरूप होते हैं।
- स्पार्स रेजीम ( $c^2R/N^2 \ll 1$ ) में, लिमिट्स मिनिमल डायग्राम्स द्वारा निर्धारित होते हैं, जिससे इंटरेक्शन कर्नेल के फूरियर ट्रांसफॉर्म से जुड़े एक्सप्रेशन प्राप्त होते हैं।
लिमिट थ्योरम्स (डिस्ट्रिब्यूशनल कन्वर्जेंस):
- सेंट्रल लिमिट थ्योरम (CLT): नॉन-क्लोज्ड वॉक्स ( $Y^{(q)}$ ) के लिए, नॉर्मलाइज्ड वेरिएबल्स तीनों रेजीम में गाऊसी (Gaussian) वितरण की ओर अभिसरित होते हैं। ट्रायंगल्स ( $X^{(3)}$ ) के लिए, CLT पहले दो रेजीम में और तीसरे रेजीम में केवल तभी लागू होता है जब औसत ट्रायंगल्स की संख्या ( $c^3R^2/N^2$ ) अनंत की ओर बढ़ती है।
- पॉइसन लिमिट: उस विशिष्ट रेजीम में जहाँ $c^2R/N^2 \to 0$ लेकिन $c^3R^2/N^2 \to \Lambda$ (परिमित), ट्रायंगल्स की संख्या पॉइसन वितरण (या यदि $\alpha=1$ है तो कंपाउंड पॉइसन वितरण) की ओर अभिसरित होती है। यह गाऊसी और पॉइसन व्यवहारों के बीच एक एसिम्प्टोटिक थ्रेशोल्ड की पहचान करता है।
ग्राफ कोलैप्स समस्या का समाधान:
शोध पत्र कठोरता से यह सिद्ध करता है कि एक ऐसा एसिम्प्टोटिक रेजीम मौजूद है जहाँ औसत वर्टेक्स डिग्री परिमित (बाउंडेड) रहती है, फिर भी ट्रायंगल्स की कुल संख्या अनंत हो जाती है। विशेष रूप से, ऐसे सीक्वेंस चुनकर जहाँ $cR/N \to \delta$ (परिमित) और $c^3R^2/N^2 \to \infty$ है, लेखक सिद्ध करते हैं कि ग्राफ "कोलैप्स" नहीं होता है (अर्थात संरचना खोने के अर्थ में); बल्कि, यह बाउंडेड लोकल डेंसिटी बनाए रखते हुए अनंत संख्या में ट्रायंगल्स को सपोर्ट करता है, जो एक ऐसी समस्या को हल करता है जो अनुप्रयोगों में ज्ञात है।

महत्व और दावे

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

सामान्यीकरण: यूनिफॉर्म रैंडम ग्राफ्स से लिमिट थ्योरम्स को इंटरेक्शन रेडियस वाले ग्राफ्स तक विस्तारित करना, जो रैंडम मैट्रिक्स थ्योरी और ज्योमेट्रिक रैंडम ग्राफ्स के बीच के अंतर को पाटता है।
फेज ट्रांजिशन विश्लेषण: सटीक एसिम्प्टोटिक थ्रेशोल्ड की पहचान करना जो यह निर्धारित करते हैं कि सबग्राफ काउंट्स गाऊसी या पॉइसन लॉ का पालन करते हैं, और एक्सपोनेंशियल रैंडम ग्राफ मॉडल्स के लिए फ्री एनर्जी की एनालिटिसिटी को निर्धारित करना।
कोलैप्स समस्या का समाधान: यह एक रचनात्मक प्रमाण प्रदान करता है कि ग्राफ का "कोलैप्स" (जहाँ ट्रायल्स गायब हो जाते हैं या डिग्री अनबाउंड हो जाती है) अपरिहार्य नहीं है; हम बाउंडेड डिग्री और डाइवर्जिंग ट्रायंगल काउंट के साथ एनसेंबल्स बना सकते हैं।
कॉम्बिनेटोरियल इनसाइट: संशोधित प्रुफर कोड्स के माध्यम से ट्री-टाइप डायग्राम्स का स्पष्ट एन्यूमरेशन प्रदान करना, जो लिमिटिंग क्यूमलेंट्स के सटीक एक्सप्रेशन देते हैं।

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