विस्तारक ग्राफ: Difference between revisions

Latest revision as of 10:42, 21 February 2023

ग्राफ़ सिद्धांत में, विस्तारक ग्राफ़ एक विरल ग्राफ के रूप में होता है, जिसमें वर्टेक्स किनारे या वर्णक्रमीय विस्तार का उपयोग करके प्रबल कनेक्टिविटी गुण होते हैं। विस्तारक निर्माण ने प्रबल कंप्यूटर नेटवर्क के जटिलता सिद्धांत और त्रुटि सुधार कोड के लिए कई अनुप्रयोगों के साथ शुद्ध और अनुप्रयुक्त गणित में अनुसंधान को जन्म दिया है।^[1]

परिभाषाएँ

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

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

किनारे का विस्तार

किनारे का विस्तार भी आइसोपेरिमेट्रिक संख्या या चीजर स्थिरांक $h (G)$ एक ग्राफ सिद्धांत का $G$ पर $n$ शिखर के रूप में परिभाषित किया गया है।

h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},

जहाँ

\partial S:=\{\{u,v\}\in E(G)\ :\ u\in S,v\in V(G)\setminus S\},

जिसे इस रूप में भी लिखा जा सकता है $\partial S = E (S, S)$ साथ $S := V(G) \ S$ का पूरक $S$ और

E(A,B)=\{\{u,v\}\in E(G)\ :\ u\in A,v\in B\}

शीर्षों के उपसमुच्चय के बीच के किनारे

A, B \subseteq V (G)

.

समीकरण में, न्यूनतम सभी गैर-रिक्त सेटों पर होती है $S$ अधिक से अधिक $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n⁄2$ शिखर और $\partial S$ की किनारा सीमा $S$ है अर्थात, किनारों का सेट $S$ में ठीक एक समापन बिंदु के साथ है।.^[2]

सहज रूप से,

\min {|\partial S|}=\min E({S},{\overline {S}})

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

ध्यान दें कि में $min | \partial S |$ , ऑप्टिमाइज़ेशन या तो अधिक समान रूप से किया जा सकता है $0 \leq | S | \leq n ⁄ 2$ या किसी गैर-रिक्त सबसेट पर, चूंकि $E(S,{\overline {S}})=E({\overline {S}},S)$ . के लिए सही नहीं है $h (G)$ द्वारा सामान्यीकरण के कारण $| S |$ .यदि हम $h (G)$ को सभी गैर-रिक्त सबसेट पर एक अनुकूलन के साथ लिखना चाहते हैं तो हम इसे फिर से लिख सकते हैं

h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {E({S},{\overline {S}})}{\min\{|S|,|{\overline {S}}|\}}}.

वर्टेक्स विस्तार

वर्टेक्स आइसोपेरिमेट्रिक संख्या $h out (G)$ वर्टेक्स विस्तरण या ग्राफ $G$ का आवर्धन इस रूप में परिभाषित किया गया है।

h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},

जहाँ $\partial out (S)$ की बाहरी सीमा $S$ है अर्थात शीर्षों का सेट $V(G) \ S$ कम से कम एक निकटतम के साथ $S$ के रूप में होते है.^[3] इस परिभाषा के एक अनुसार जिसे अद्वितीय निकटतम विस्तार कहा जाता है $\partial out (S)$ को $V$ में शीर्षों के सेट द्वारा $S$ में ठीक एक निकटतम के साथ प्रतिस्थापित किया जाता है।.^[4]

शीर्ष आइसोपेरिमेट्रिक संख्या $h in (G)$ एक ग्राफ का $G$ द्वारा परिभाषित किया जाता है।

h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},

जहाँ $\partial _{\text{in}}(S)$ की भीतरी सीमा $S$ है, अर्थात शीर्षों का सेट $S$ कम से कम एक निकटतम के साथ $V(G) \ S$ के रूप में होता है.^[3]

वर्णक्रमीय विस्तार

जब $G$ नियमित ग्राफ के रूप में होता है, तो विस्तार की एक रेखीय बीजगणितीय परिभाषा $d$ के आसन्न आव्यूह $A = A (G)$ का $G$ , के अभिलक्षणिक मान के आधार पर संभव होता है, जहाँ $A ij$ शीर्षों $i$ और $j$ के बीच किनारों की संख्या के रूप में होती है।.^[5] क्योंकि $A$ सममित आव्यूह है, वर्णक्रमीय प्रमेय का तात्पर्य है $A$ में $n$ वास्तविक मूल्यवान अभिलक्षणिक मान $λ 1 \geq λ 2 \geq \dots \geq λ n$ . के रूप में हैं यह ज्ञात है कि ये सभी अभिलक्षणिक मान $[- d, d]$ में हैं और अधिक विशेष रूप से यह ज्ञात है कि $λ n = - d$ यदि और केवल यदि $G$ द्विपक्षीय रूप में है।

अधिक औपचारिक रूप से, हम एक n वर्टेक्स $d$ -नियमित ग्राफ़ को संदर्भित करते हैं

\max _{i\neq 1}|\lambda _{i}|\leq \lambda

एक के रूप में

(n, d, λ)

-ग्राफ द्वारा दी गई सीमा

(n, d, λ)

-ग्राफ

λ i

के लिए

i \neq 1

विस्तारक मिश्रण लेम्मा सहित कई संदर्भों में उपयोगी रूप में होते है।

क्योंकि $G$ नियमित है, समान वितरण $u\in \mathbb {R} ^{n}$ साथ $u i = 1 ⁄ n$ सभी के लिए $i = 1, \dots, n$ का स्थिर वितरण $G$ .रूप में होते है अर्थात हमारे पास है $Au = du$ , और $u$ का अभिलक्षणिक सदिश $A$ है अभिलक्षणिक मान $λ 1 = d$ है, जहाँ $d$ , $G$ के शीर्षों की डिग्री (ग्राफ़ सिद्धांत) है।. $G$ का वर्णक्रमीय अंतर को $d - λ 2$ के रूप में परिभाषित किया गया है और यह वर्णक्रमीय विस्तार को मापता है ग्राफ $G$ का।.^[6]

यदि हम सेट बनाते हैं तो,

\lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}

क्योंकि यह एक अभिलक्षणिक सदिश ओर्थोगोनल के अनुरूप सबसे बड़ा अभिलक्षणिक मान है $u$ , इसे रेलेइग़ भागफल का उपयोग करके समान रूप से परिभाषित किया जा जाता है

\lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},

जहाँ

\|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}

सदिश का 2-मानक

v\in \mathbb {R} ^{n}

के रूप में होता है।

इन परिभाषाओं के सामान्यीकृत संस्करण भी व्यापक रूप से उपयोग किए जाते हैं और कुछ परिणामों को बताते हुए अधिक सुविधाजनक होते हैं। यहाँ एक आव्यूह $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/dA$ पर अवधारणा के रूप में होता है, जो कि ग्राफ $G$ . का मार्कोव ट्रांज़िशन आव्यूह होता है इसके अभिलक्षणिक मान -1 और 1 के बीच होते है। जरूरी नहीं कि नियमित ग्राफ़ के लिए, ग्राफ़ के स्पेक्ट्रम को लाप्लासियन मैट्रिक्स के अभिलक्षणिक मान का उपयोग करके इसी प्रकार परिभाषित किया जा सकता है। निर्देशित रेखांकन के लिए, आसन्न आव्यूह $A$ के विलक्षण मूल्य पर अवधारणा किया जाता है, जो सममित आव्यूह $A T A$ .के अभिलक्षणिक मान की रूट्स के बराबर होते है।

विभिन्न विस्तार गुणों के बीच संबंध

ऊपर परिभाषित विस्तार पैरामीटर एक दूसरे से संबंधित हैं। विशेष रूप से, किसी के लिए $d$ -नियमित ग्राफ $G$ ,के लिए इस प्रकार से होते है।

h_{\text{out}}(G)\leq h(G)\leq d\cdot h_{\text{out}}(G).

परिणामस्वरुप, निरंतर डिग्री ग्राफ के लिए, वर्टेक्स और किनारे एक्सपेंशन गुणात्मक रूप से समान होते है।

चीजर असमानताएं

कब $G$ , $d$ -नियमित होता है, जिसका अर्थ है कि प्रत्येक शीर्ष डिग्री $d$ का है, तो आइसोपेरिमेट्रिक स्थिरांक $h (G)$ और $G$ . के आसन्न ऑपरेटर के स्पेक्ट्रम में अंतराल $d - λ 2$ के बीच संबंध होता है। $d$ -नियमित ग्राफ का आसन्न ऑपरेटर λ1 = d है और पहला गैर-तुच्छ अभिलक्षणिक मान $λ 2$ .है यदि $G$ से जुड़ा हुआ है, तो $λ 2 < d$ . डोडिज़ुक के कारण एक असमानता^[7] और स्वतंत्र रूप से सावधान अलोन और विटाली मिलमैन^[8] बताता है कि ^[9]

{\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.

वास्तव में, निचला बाउंड घना है। हाइपरक्यूब ग्राफ के लिए सीमा में निचली सीमा $Q n$ ,प्राप्त की जाती है, जहाँ $h (G) = 1$ और $d - λ = 2$ . ऊपरी सीमा एक चक्र के लिए असामयिक रूप से प्राप्त की जाती है, जहां $H (C n) = 4/ n = Θ(1/ n)$ और $\pi$ .^[1] में एक अच्छा बाउंड दिया गया है ^[10] जैसा,

h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.

ये असमानताएँ मार्कोव श्रृंखलाओं के लिए बाध्य चीगर से निकटता से संबंधित होती है और इन्हें रीमैनियन ज्यामिति में चीगर की असमानता के असतत संस्करण के रूप में देखा जा सकता है।

वर्टेक्स आइसोपेरिमेट्रिक नंबर और वर्णक्रमीय गैप के बीच समान कनेक्शन का भी अध्ययन किया जाता है:^[11]

h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1

h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.

समान रूप से बोलते हुए, मात्रा $h 2 ⁄ d$ , $h out$ , और $h in 2$ सभी ऊपर वर्णक्रमीय अंतराल $O (d - λ 2)$ .से घिरी हुई हैं।

निर्माण

विस्तारक ग्राफ़ के समूहों को स्पष्ट रूप से बनाने के लिए तीन सामान्य रणनीतियाँ हैं।^[12] पहली रणनीति बीजगणितीय और समूह सिद्धांत है, दूसरी रणनीति विश्लेषणात्मक है और योगात्मक संयोजक का उपयोग करती है और तीसरी रणनीति कॉम्बिनेटरियल है और ज़िग ज़ैग और संबंधित ग्राफ़ उत्पादों का उपयोग करती है। नोगा अलोन ने दिखाया कि परिमित ज्यामिति से निर्मित कुछ ग्राफ़ अत्यधिक विस्तार वाले ग्राफ़ के सबसे दुर्लभ उदाहरण के रूप में हैं।^[13]

मार्गुलिस-गैबर-गैलिल

केली ग्राफ पर आधारित सार बीजगणित निर्माण विस्तारक ग्राफ़ के विभिन्न रूपों के लिए जाने जाते हैं। निम्नलिखित निर्माण मार्गुलिस के कारण है और गैबर और गैलिल द्वारा इसका विश्लेषण किया गया है।^[14] प्रत्येक प्राकृतिक संख्या के लिए $n$ , एक ग्राफ $G n$ पर अवधारणा करता है, वर्टेक्स सेट के साथ $\mathbb {Z} _{n}\times \mathbb {Z} _{n}$ , जहाँ $\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z}$ : प्रत्येक शीर्ष के लिए $(x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}$ , इसके आठ आसन्न शीर्ष हैं

(x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).

फिर निम्नलिखित धारण करता है

प्रमेय सभी के लिए $n$ , लेखाचित्र $G n$ का दूसरा सबसे बड़ा $\lambda (G)\leq 5{\sqrt {2}}$ अभिलक्षणिक मान है

रामनुजन ग्राफ्स

एक अलोन-बोपना बाउंड द्वारा, सभी पर्याप्त रूप से बड़े $d$ -नियमित रेखांकन संतुष्ट करते हैं $\lambda _{2}\geq 2{\sqrt {d-1}}-o(1)$ , जहाँ $λ 2$ निरपेक्ष मान में दूसरा सबसे बड़ा अभिलक्षणिक मान है।^[15] प्रत्यक्ष परिणाम के रूप में, हम जानते हैं कि प्रत्येक निश्चित के लिए $d$ और $\lambda <2{\sqrt {d-1}}$ , निश्चित रूप से अनेक हैं $(n, d, λ)$ -ग्राफ रामानुजन ग्राफ हैं, $d$ -नियमित रेखांकन जिसके लिए यह सीमा घनी संतोषजनक है ^[16] : $\lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.$

इसलिए रामानुजन के रेखांकन $λ 2$ .का एक विषम रूप से सबसे छोटा संभव मान है यह उन्हें उत्कृष्ट वर्णक्रमीय विस्तारक बनाता है।

अलेक्जेंडर लुबोत्ज़की, फिलिप्स और पीटर इतिहास (1988), मार्गुलिस (1988), और मॉर्गनस्टर्न (1994) दिखाते हैं कि रामानुजन ग्राफ को स्पष्ट रूप से कैसे बनाया जा सकता है।^[17]

1985 में, एलोन ने सबसे अधिक अनुमान लगाया $d$ -नियमित रेखांकन पर $n$ कोने पर्याप्त रूप से बड़े के लिए $n$ , लगभग रामानुजन हैं।^[18] अर्थात के लिए $φ > 0$ , वे

\lambda \leq 2{\sqrt {d-1}}+\varepsilon

.को संतुष्ट हैं

2003 में, जोएल फ्रीडमैन दोनों ने अनुमान को सिद्ध किया और निर्दिष्ट किया कि अधिकांश $d$ नियमित ग्राफ़ का क्या मतलब है यह दिखाते हुए कि यादृच्छिक $d$ नियमित ग्राफ़ में $\lambda \leq 2{\sqrt {d-1}}+\varepsilon$ हर $φ > 0$ के लिए प्रायिकता $1 - O (n τ)$ , के साथ हैं जहाँ ^[19]^[20]

\tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .

ज़िग-ज़ैग उत्पाद

2003 में ओमर रीनॉल्ड, सलिल वधान और एवी विगडरसन ने ज़िग-ज़ैग उत्पाद प्रस्तुत किया।^[21] मोटे तौर पर बोलते हुए, दो विस्तारक ग्राफों का ज़िग-ज़ैग उत्पाद केवल थोड़ा खराब विस्तार वाला ग्राफ बनाता है। इसलिए, विस्तारक ग्राफ के समूहों के निर्माण के लिए एक ज़िग-ज़ैग उत्पाद का भी उपयोग किया जा सकता है। यदि $G$ एक है $(n, m, λ 1)$ -ग्राफ और $H$ एक $(m, d, λ 1)$ -ग्राफ, फिर ज़िग-ज़ैग उत्पाद $G ◦ H$ एक है $(nm, d 2, φ (λ 1, λ 2))$ -ग्राफ जहां $φ$ निम्नलिखित गुण के रूप में होते है।

यदि $λ 1 < 1$ और $λ 2 < 1$ , तब $φ (λ 1, λ 2) < 1$ ;
$φ (λ 1, λ 2) \leq λ 1 + λ 2$ .

विशेष रूप से,^[21]: $f(\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.$

ध्यान दें कि गुण (1) का तात्पर्य है कि दो विस्तारक ग्राफों का ज़िग-ज़ैग उत्पाद भी एक विस्तारक ग्राफ के रूप में होता है, इस प्रकार ज़िग-ज़ैग उत्पादों का उपयोग विस्तारक ग्राफों के एक समूह को बनाने के लिए किया जाता है।

सहज रूप से, ज़िग-ज़ैग उत्पाद के निर्माण के बारे में निम्नलिखित विधि से सोचा जा सकता है। $G$ के प्रत्येक शीर्ष को m शीर्षों के एक बादल तक उड़ाया जाता है, प्रत्येक शीर्ष से जुड़े एक अलग किनारे से जुड़ा होता है। प्रत्येक शीर्ष को अब $(v, k)$ के रूप में लेबल किया गया है जहाँ $v$ , $G$ के मूल शीर्ष को संदर्भित करता है और $k$ इसका किनारा $v$ . दो शिखर, $(v, k)$ और $(w, l)$ जुड़े हुए हैं। निम्नलिखित अनुक्रम के माध्यम से $(v, k)$ को $(w, l)$ तक जाने के लिए उपयोग करते है।

ज़िग - $H$ के किनारे का उपयोग करके $(v, k)$ को $(v, k')$ पर जाते है।
$(w, l')$ . पर जाने के लिए $G$ में किनारे $k'$ ' का उपयोग करके घन पर जाते है।
ज़ैग - $H$ . के किनारे का उपयोग करके $(w, l')$ को $(w, l)$ पर जाते है।.^[21]

यादृच्छिक निर्माण

ऐसे कई परिणाम हैं जो संभाव्य तर्कों के माध्यम से अच्छे विस्तार गुणों वाले ग्राफ़ के अस्तित्व को दर्शाते हैं। वास्तव में, विस्तारकों के अस्तित्व को सबसे पहले पिंस्कर ने सिद्ध किया था^[22] जिसने दिखाया कि एक यादृच्छिक रूप से चुने गए के लिए $n$ शीर्ष छोड़ दिया $d$ नियमित द्विपक्षीय ग्राफ, $| N (S) | \geq (d - 2)| S |$ कोने के सभी सबसेट के लिए $| S | \leq c d n$ उच्च संभावना के साथ, जहाँ $c d$ एक स्थिरांक है जो $d$ पर निर्भर करता है जो कि $O (d -4)$ .है। अलोन और रोचमैन ^[23] ने दिखाया कि क्रम n के प्रत्येक समूह G के लिए और प्रत्येक $1 > ε > 0$ , में कुछ $c (ε) > 0$ होता है जैसे कि $G$ साथ $c (ε) log 2 n$ जनरेटर के साथ $G$ पर केली ग्राफ एक ε विस्तारक है अर्थात उच्च संभावना के साथ $1 - ε$ , से कम दूसरा अभिलक्षणिक मान है।।

अनुप्रयोग और उपयोगी गुण

विस्तारकों के लिए मूल प्रेरणा आर्थिक रूप से प्रबल नेटवर्क (फोन या कंप्यूटर) का निर्माण करना है: सीमाबद्ध डिग्री वाला एक विस्तारक सभी उपसमुच्चयों के लिए आकार (कोने की संख्या) के साथ रैखिक रूप से बढ़ने वाले किनारों की संख्या के साथ एक स्पर्शोन्मुख प्रबल ग्राफ है।

एक्सपैंडर ग्राफ़ को कंप्यूटर विज्ञान में कलन विधि, विस्तारक कोड, एक्सट्रैक्टर (गणित), छद्म यादृच्छिक जनरेटर, छँटाई नेटवर्क डिजाइन करने में व्यापक अनुप्रयोग मिले हैं।Ajtai, Komlós & Szemerédi (1983)) और प्रबल कंप्यूटर नेटवर्क। कम्प्यूटेशनल जटिलता सिद्धांत में कई महत्वपूर्ण परिणामों के प्रमाण में भी उनका उपयोग किया गया है, जैसे एसएल (जटिलता) = एल (जटिलता) (Reingold (2008)) और पीसीपी प्रमेय दिनूर (2007) क्रिप्टोग्राफी में, विस्तारक ग्राफ़ का उपयोग है फलन के निर्माण के लिए किया जाता है।

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

एक्सपैंडर मिक्सिंग लेम्मा

लेम्मा को मिलाने वाला विस्तारक बताता है कि एक के लिए $(n, d, λ)$ -ग्राफ़, किसी भी दो उपसमूहों के लिए $S, T \subseteq V$ , बीच किनारों की संख्या $S$ और $T$ लगभग वह है जो आप यादृच्छिक रूप से अपेक्षा करेंगे $d$ -नियमित ग्राफ। सन्निकटन अच्छा छोटा है $λ$ है। एक यादृच्छिक में $d$ -रेगुलर ग्राफ़, साथ ही एक एर्दोस-रेनी मॉडल में|एर्डोस-रेनी रैंडम ग्राफ़ किनारे प्रायिकता के साथ $d ⁄ n$ , हमें उम्मीद है $d ⁄ n • | S | • | T |$ किनारों के बीच $S$ और $T$ .

अधिक औपचारिक रूप से, चलो $E (S, T)$ के बीच किनारों की संख्या को निरूपित करें $S$ और $T$ . यदि दो सेट भिन्न नहीं होते हैं, तो उनके चौराहे के किनारों को दो बार गिना जाता है, अर्थात

E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).

फिर लेम्मा को मिलाने वाला विस्तारक कहता है कि निम्नलिखित असमानता है:

\left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.

के अनेक गुण $(n, d, λ)$ -ग्राफ विस्तारक मिश्रण लेम्मा के परिणाम हैं, जिनमें निम्नलिखित सम्मलित हैं।^[1]

एक ग्राफ का एक स्वतंत्र सेट (ग्राफ सिद्धांत) शीर्षों का एक उपसमुच्चय होता है जिसमें दो आसन्न कोने नहीं होते हैं। एक में $(n, d, λ)$ -ग्राफ, एक स्वतंत्र सेट का आकार अधिकतम होता है $λ n ⁄ d$ .
ग्राफ का ग्राफ रंगना $G$ , $χ(G)$ , आवश्यक रंगों की न्यूनतम संख्या है, जिससे कि आसन्न शीर्षों के भिन्न -भिन्न रंग हों। हॉफमैन ने दिखाया $d ⁄ λ \leq χ(G)$ ,^[24] जबकि अलोन, क्रिवेलेविच और सुदाकोव ने दिखाया कि यदि $d < 2 n ⁄ 3$ , तब^[25]
$\chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).$
किसी ग्राफ़ की दूरी (ग्राफ़ सिद्धांत) दो शीर्षों के बीच की अधिकतम दूरी होती है, जहाँ दो शीर्षों के बीच की दूरी को उनके बीच का सबसे छोटा पथ परिभाषित किया जाता है। चुंग ने दिखाया कि एक का व्यास $(n, d, λ)$ -ग्राफ अधिकतम है^[26]
$\left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .$

एक्सपैंडर वॉक सैंपलिंग

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

एकेएस सॉर्टिंग नेटवर्क और अनुमानित पड़ाव

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

एकेएस सॉर्टिंग नेटवर्क के भीतर, विस्तारक रेखांकन का उपयोग बंधी हुई गहराई ε-आधा करने के लिए किया जाता है। एक ε-हॉल्वर इनपुट के रूप में (1, …, n) की लंबाई n क्रमचय लेता है और इनपुट को दो अलग-अलग सेटों A और B में आधा कर देता है जैसे कि प्रत्येक पूर्णांक k ≤ n⁄2 के लिए k के सबसे छोटे इनपुट में सबसे अधिक εk होता है बी और सबसे अधिक εk के सबसे बड़े इनपुट $A$ .में हैं। सेट $A$ और $B$ एक हैं $ε$ आधा करते हैं।

अजताई, कोमलोस और ज़ेमेरेडी 1983 के बाद एक गहराई $d$ $ε$ - हॉल्वर का निर्माण निम्नानुसार किया जाता है। समान आकार के भागों X और Y के साथ एक $n$ शीर्ष, डिग्री $d$ द्विदलीय विस्तारक लें, जैसे कि अधिकतम εn आकार के शीर्षों के प्रत्येक उपसमुच्चय में कम से कम $1 - ε / ε$ निकटतम रूप में होता है।

ग्राफ़ के कोने को उन रजिस्टरों के रूप में माना जा सकता है जिनमें इनपुट होते हैं और किनारों को तारों के रूप में माना जा सकता है जो दो रजिस्टरों के इनपुट की तुलना करते हैं। प्रारंभ में, मनमाने ढंग से आधे इनपुट को X में और आधे इनपुट को Y में रखें और किनारों को d पूर्ण मिलान में विघटित करें। लक्ष्य X के साथ समाप्त होना है जिसमें मोटे तौर पर इनपुट का छोटा आधा भाग होता है और Y में इनपुट का बड़ा आधा भाग होता है। इसे प्राप्त करने के लिए इस मिलान के किनारों द्वारा जोड़े गए रजिस्टरों की तुलना करके प्रत्येक मिलान को क्रमिक रूप से संसाधित करें और किसी भी इनपुट को ठीक करें जो क्रम से बाहर हैं। विशेष रूप से, मिलान के प्रत्येक किनारे के लिए, यदि बड़ा इनपुट एक्स में रजिस्टर में है और छोटा इनपुट वाई में रजिस्टर में है तो दो इनपुट स्वैप करें ताकि छोटा एक्स में हो और बड़ा वाई में हो। यह स्पष्ट है कि इस प्रक्रिया में d समानांतर चरण के रूप में होते हैं

सभी $d$ राउंड के बाद $A$ को $X$ और $B$ में रजिस्टरों में इनपुट का सेट होने के लिए $Y$ में रजिस्टरों में इनपुट का सेट होने के लिए $ε$ आधा करते है। इसे देखने के लिए, ध्यान दें कि यदि X में कोई रजिस्टर u और Y में v एक किनारे uv से जुड़ा है तो इस किनारे के साथ मिलान करने के बाद संसाधित किया जाता है, u में इनपुट v से कम होता है। इसके अतिरिक्त, यह गुण बाकी प्रक्रिया के दौरान सही रहती है। अब मान लीजिए कि कुछ $k \leq n ⁄ 2$ के लिए इनपुट $(1, \dots, k)$ के εk से अधिक B में हैं। फिर ग्राफ के विस्तार गुणों द्वारा, Y में इन इनपुट के रजिस्टर कम से कम जुड़े हुए हैं $1 - ε / ε k$ में अंकित करता है, $X$ . कुल मिलाकर, यह k से अधिक रजिस्टर का गठन करता है, इसलिए X में कुछ रजिस्टर A होना चाहिए, जो Y में कुछ रजिस्टर B से जुड़ा हो, जैसे कि A का अंतिम इनपुट (1, ..., k) में नहीं है, जबकि अंतिम बी का इनपुट है।चूँकि यह पिछली संपत्ति का उल्लंघन करता है और इस प्रकार आउटपुट सेट ए और बी को ε-आधा होना चाहिए।

यह भी देखें

बीजगणितीय कनेक्टिविटी
ज़िग-ज़ैग उत्पाद
सुपरस्ट्रॉन्ग सन्निकटन
वर्णक्रमीय ग्राफ सिद्धांत

↑ ^1.0 ^1.1 ^1.2 Hoory, Linial & Wigderson (2006)
↑ Definition 2.1 in Hoory, Linial & Wigderson (2006)
↑ ^3.0 ^3.1 Bobkov, Houdré & Tetali (2000)
↑ Alon & Capalbo (2002)
↑ cf. Section 2.3 in Hoory, Linial & Wigderson (2006)
↑ This definition of the spectral gap is from Section 2.3 in Hoory, Linial & Wigderson (2006)
↑ Dodziuk 1984.
↑ Alon & Spencer 2011.
↑ Theorem 2.4 in Hoory, Linial & Wigderson (2006)
↑ B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291, 1989.
↑ See Theorem 1 and p.156, l.1 in Bobkov, Houdré & Tetali (2000). Note that $λ 2$ there corresponds to $2(d - λ 2)$ of the current article (see p.153, l.5)
↑ see, e.g., Yehudayoff (2012)
↑ Alon, Noga (1986). "Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory". Combinatorica. 6 (3): 207–219. CiteSeerX 10.1.1.300.5945. doi:10.1007/BF02579382. S2CID 8666466.
↑ see, e.g., p.9 of Goldreich (2011)
↑ Theorem 2.7 of Hoory, Linial & Wigderson (2006)
↑ Definition 5.11 of Hoory, Linial & Wigderson (2006)
↑ Theorem 5.12 of Hoory, Linial & Wigderson (2006)
↑ Alon, Noga (1986-06-01). "Eigenvalues and expanders". Combinatorica (in English). 6 (2): 83–96. doi:10.1007/BF02579166. ISSN 1439-6912. S2CID 41083612.
↑ Friedman, Joel (2004-05-05). "A proof of Alon's second eigenvalue conjecture and related problems". arXiv:cs/0405020.
↑ Theorem 7.10 of Hoory, Linial & Wigderson (2006)
↑ ^21.0 ^21.1 ^21.2 Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors". Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc: 3–13. doi:10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID 420651.
↑ Pinkser, M. (1973). "On the Complexity of a Concentrator". SIAM Journal on Computing. SIAM. CiteSeerX 10.1.1.393.1430.
↑ Alon, N.; Roichman, Y. (1994). "Random Cayley graphs and Expanders". Random Structures and Algorithms. Wiley Online Library. 5 (2): 271–284. doi:10.1002/rsa.3240050203.
↑ Hoffman, A. J.; Howes, Leonard (1970). "On Eigenvalues and Colorings of Graphs, Ii". Annals of the New York Academy of Sciences (in English). 175 (1): 238–242. Bibcode:1970NYASA.175..238H. doi:10.1111/j.1749-6632.1970.tb56474.x. ISSN 1749-6632. S2CID 85243045.
↑ Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999-09-01). "Coloring Graphs with Sparse Neighborhoods". Journal of Combinatorial Theory. Series B (in English). 77 (1): 73–82. doi:10.1006/jctb.1999.1910. ISSN 0095-8956.
↑ Chung, F. R. K. (1989). "Diameters and eigenvalues". Journal of the American Mathematical Society (in English). 2 (2): 187–196. doi:10.1090/S0894-0347-1989-0965008-X. ISSN 0894-0347.

संदर्भ

पाठ्यपुस्तकें और सर्वेक्षण

Alon, N.; Spencer, Joel H. (2011). "9.2. Eigenvalues and Expanders". संभाव्य विधि (3rd ed.). John Wiley & Sons.
Chung, Fan R. K. (1997), Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol. 92, American Mathematical Society, ISBN 978-0-8218-0315-8
Davidoff, Guiliana; Sarnak, Peter; Valette, Alain (2003), Elementary number theory, group theory and Ramanujan graphs, LMS student texts, vol. 55, Cambridge University Press, ISBN 978-0-521-53143-6
Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Expander graphs and their applications" (PDF), Bulletin of the American Mathematical Society, New Series, 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8
Krebs, Mike; Shaheen, Anthony (2011), Expander families and Cayley graphs: A beginner's guide, Oxford University Press, ISBN 978-0-19-976711-3

शोध लेख

Ajtai, M.; Komlós, J.; Szemerédi, E. (1983), "An O(n log n) sorting network", Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 1–9, doi:10.1145/800061.808726, ISBN 978-0-89791-099-6, S2CID 15311122
Ajtai, M.; Komlós, J.; Szemerédi, E. (1987), "Deterministic simulation in LOGSPACE", Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, pp. 132–140, doi:10.1145/28395.28410, ISBN 978-0-89791-221-1, S2CID 15323404
Alon, N.; Capalbo, M. (2002), "Explicit unique-neighbor expanders", The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, p. 73, CiteSeerX 10.1.1.103.967, doi:10.1109/SFCS.2002.1181884, ISBN 978-0-7695-1822-0, S2CID 6364755
Bobkov, S.; Houdré, C.; Tetali, P. (2000), "λ_∞, vertex isoperimetry and concentration", Combinatorica, 20 (2): 153–172, doi:10.1007/s004930070018, S2CID 1173532.
Dinur, Irit (2007), "The PCP theorem by gap amplification" (PDF), Journal of the ACM, 54 (3): 12–es, CiteSeerX 10.1.1.103.2644, doi:10.1145/1236457.1236459, S2CID 53244523.
Dodziuk, Jozef (1984), "Difference equations, isoperimetric inequality and transience of certain random walks", Trans. Amer. Math. Soc., 284 (2): 787–794, doi:10.2307/1999107, JSTOR 1999107.
Gillman, D. (1998), "A Chernoff Bound for Random Walks on Expander Graphs", SIAM Journal on Computing, 27 (4): 1203–1220, doi:10.1137/S0097539794268765
Goldreich, Oded (2011), "Basic Facts about Expander Graphs" (PDF), Studies in Complexity and Cryptography, Lecture Notes in Computer Science, 6650: 451–464, CiteSeerX 10.1.1.231.1388, doi:10.1007/978-3-642-22670-0_30, ISBN 978-3-642-22669-4
Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, S2CID 207168478
Yehudayoff, Amir (2012), "Proving expansion in three steps", ACM SIGACT News, 43 (3): 67–84, doi:10.1145/2421096.2421115, S2CID 18098370

हाल के अनुप्रयोग

Hartnett, Kevin (2018), "Universal Method to Sort Complex Information Found", Quanta Magazine (published 13 August 2018)

बाहरी संबंध

[Hoory_2006-1] 1.0 ^1.1 ^1.2 Hoory, Linial & Wigderson (2006)

[2] Definition 2.1 in Hoory, Linial & Wigderson (2006)

[BobkovHoudre-3] 3.0 ^3.1 Bobkov, Houdré & Tetali (2000)

[AlonCapalbo-4] Alon & Capalbo (2002)

[5] . Section 2.3 in Hoory, Linial & Wigderson (2006)

[6] This definition of the spectral gap is from Section 2.3 in Hoory, Linial & Wigderson (2006)

[FOOTNOTEDodziuk1984-7] Dodziuk 1984.

[FOOTNOTEAlonSpencer2011-8] Alon & Spencer 2011.

[9] Theorem 2.4 in Hoory, Linial & Wigderson (2006)

[10] B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291, 1989.

[11] See Theorem 1 and p.156, l.1 in Bobkov, Houdré & Tetali (2000). Note that $λ 2$ there corresponds to $2(d - λ 2)$ of the current article (see p.153, l.5)

[12] see, e.g., Yehudayoff (2012)

[13] Alon, Noga (1986). "Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory". Combinatorica. 6 (3): 207–219. CiteSeerX 10.1.1.300.5945. doi:10.1007/BF02579382. S2CID 8666466.

[14] see, e.g., p.9 of Goldreich (2011)

[15] Theorem 2.7 of Hoory, Linial & Wigderson (2006)

[16] Definition 5.11 of Hoory, Linial & Wigderson (2006)

[17] Theorem 5.12 of Hoory, Linial & Wigderson (2006)

[18] Alon, Noga (1986-06-01). "Eigenvalues and expanders". Combinatorica (in English). 6 (2): 83–96. doi:10.1007/BF02579166. ISSN 1439-6912. S2CID 41083612.

[19] Friedman, Joel (2004-05-05). "A proof of Alon's second eigenvalue conjecture and related problems". arXiv:cs/0405020.

[20] Theorem 7.10 of Hoory, Linial & Wigderson (2006)

[:0-21] 21.0 ^21.1 ^21.2 Reingold, O.; Vadhan, S.; Wigderson, A. (2000). "Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors". Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc: 3–13. doi:10.1109/sfcs.2000.892006. ISBN 0-7695-0850-2. S2CID 420651.

[22] Pinkser, M. (1973). "On the Complexity of a Concentrator". SIAM Journal on Computing. SIAM. CiteSeerX 10.1.1.393.1430.

[23] Alon, N.; Roichman, Y. (1994). "Random Cayley graphs and Expanders". Random Structures and Algorithms. Wiley Online Library. 5 (2): 271–284. doi:10.1002/rsa.3240050203.

[24] Hoffman, A. J.; Howes, Leonard (1970). "On Eigenvalues and Colorings of Graphs, Ii". Annals of the New York Academy of Sciences (in English). 175 (1): 238–242. Bibcode:1970NYASA.175..238H. doi:10.1111/j.1749-6632.1970.tb56474.x. ISSN 1749-6632. S2CID 85243045.

[25] Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999-09-01). "Coloring Graphs with Sparse Neighborhoods". Journal of Combinatorial Theory. Series B (in English). 77 (1): 73–82. doi:10.1006/jctb.1999.1910. ISSN 0095-8956.

[26] Chung, F. R. K. (1989). "Diameters and eigenvalues". Journal of the American Mathematical Society (in English). 2 (2): 187–196. doi:10.1090/S0894-0347-1989-0965008-X. ISSN 0894-0347.

[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]

@@ Line 1: / Line 1: @@
 {{short description|Sparse graph with strong connectivity}}
-ग्राफ़ सिद्धांत में, एक विस्तारक ग्राफ़ एक [[विरल ग्राफ]]़ है जिसमें मजबूत कनेक्टिविटी (ग्राफ़ सिद्धांत) गुण होते हैं, वर्टेक्स (ग्राफ़ सिद्धांत), बढ़त (ग्राफ़ सिद्धांत) या वर्णक्रमीय ग्राफ़ सिद्धांत विस्तार का उपयोग करके मात्रा निर्धारित की जाती है। [[कम्प्यूटेशनल जटिलता सिद्धांत]], मजबूत [[संगणक संजाल]] के डिजाइन और त्रुटि-सुधार कोड के सिद्धांत के लिए कई अनुप्रयोगों के साथ विस्तारक निर्माण ने शुद्ध और अनुप्रयुक्त गणित में अनुसंधान को जन्म दिया है।<ref name="Hoory 2006">{{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+ग्राफ़ सिद्धांत में, विस्तारक ग्राफ़ एक [[विरल ग्राफ]] के रूप में होता है, जिसमें वर्टेक्स किनारे या वर्णक्रमीय विस्तार का उपयोग करके प्रबल कनेक्टिविटी गुण होते हैं। विस्तारक निर्माण ने प्रबल [[कंप्यूटर नेटवर्क के जटिलता सिद्धांत]] और त्रुटि सुधार कोड के  लिए कई अनुप्रयोगों के साथ शुद्ध और अनुप्रयुक्त गणित में अनुसंधान को जन्म दिया है।<ref name="Hoory 2006">{{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
 == परिभाषाएँ ==
-सहजता से, एक विस्तारक ग्राफ एक परिमित, अप्रत्यक्ष [[मल्टीग्राफ]] है जिसमें कोने के प्रत्येक उपसमुच्चय जो बहुत बड़े नहीं हैं, उनकी एक बड़ी [[सीमा (ग्राफ सिद्धांत)]] है। इन धारणाओं की विभिन्न औपचारिकताएं विस्तारकों की विभिन्न धारणाओं को जन्म देती हैं: एज एक्सपेंडर्स, वर्टेक्स एक्सपेंडर्स और स्पेक्ट्रल एक्सपेंडर्स, जैसा कि नीचे परिभाषित किया गया है।
+सहज रूप से, विस्तारक ग्राफ परिमित अप्रत्यक्ष [[मल्टीग्राफ]] रूप में होते है, जिसमें कोने के प्रत्येक उपसमुच्चय जो बहुत बड़े नहीं होते है, उनकी बड़ी [[सीमा (ग्राफ सिद्धांत)]] के रूप में होती है। इन धारणाओं की विभिन्न औपचारिकताएं विस्तारकों की विभिन्न धारणाओं को जन्म देती हैं, जैसे किनारे एक्सपेंडर्स, वर्टेक्स एक्सपेंडर्स और वर्णक्रमीय एक्सपेंडर्स, जैसा कि नीचे परिभाषित किया गया है।
-एक डिस्कनेक्टेड ग्राफ एक विस्तारक नहीं है, क्योंकि एक [[घटक (ग्राफ सिद्धांत)]] की सीमा खाली है। प्रत्येक जुड़ा हुआ ग्राफ एक विस्तारक है; हालाँकि, अलग-अलग जुड़े ग्राफ़ में अलग-अलग विस्तार पैरामीटर हैं। पूर्ण ग्राफ में सबसे अच्छा विस्तार गुण है, लेकिन इसकी सबसे बड़ी संभव [[डिग्री (ग्राफ सिद्धांत)]] है। अनौपचारिक रूप से, एक ग्राफ एक अच्छा विस्तारक होता है यदि इसमें कम डिग्री और उच्च विस्तार पैरामीटर होते हैं।
+एक डिस्कनेक्ट किया गया ग्राफ़ एक विस्तारक नहीं होते है क्योंकि कनेक्टेड [[घटक]] की सीमा रिक्त होती है। प्रत्येक जुड़ा हुआ ग्राफ एक विस्तारक रूप में होता है चूँकि, जुड़े ग्राफों के भिन्न -भिन्न विस्तार पैरामीटर होते हैं। जो पूर्ण ग्राफ में सबसे अच्छा विस्तार गुण के रूप में होते है लेकिन इसकी सबसे बड़ी संभव [[डिग्री (ग्राफ सिद्धांत)]] के रूप में होती है। अनौपचारिक रूप से ग्राफ एक अच्छा विस्तारक है यदि इसमें कम डिग्री और उच्च विस्तार पैरामीटर होते हैं।
 ===किनारे का विस्तार===
-किनारे का विस्तार (आइसोपेरिमेट्रिक संख्या या चीजर स्थिरांक (ग्राफ सिद्धांत)) {{math|''h''(''G'')}} एक ग्राफ का {{mvar|G}} पर {{mvar|n}} शिखर के रूप में परिभाषित किया गया है
+किनारे का विस्तार भी आइसोपेरिमेट्रिक संख्या या चीजर स्थिरांक {{math|''h''(''G'')}} एक ग्राफ सिद्धांत का {{mvar|G}} पर {{mvar|n}} शिखर के रूप में परिभाषित किया गया है।
 : <math>h(G) = \min_{0 < |S| \le \frac{n}{2} } \frac{|\partial S|}{|S|},</math>
-:कहाँ <math>\partial S := \{ \{ u, v \} \in E(G) \ : \ u \in S, v \in V(G) \setminus S \},</math>
+:जहाँ <math>\partial S := \{ \{ u, v \} \in E(G) \ : \ u \in S, v \in V(G) \setminus S \},</math>
 जिसे इस रूप में भी लिखा जा सकता है {{math|1=∂''S'' = ''E''(''S'', {{overline|''S''}})}} साथ {{math|1={{overline|''S''}} := ''V''(''G'') \ ''S''}} का पूरक {{mvar|S}} और
 :<math> E(A,B) = \{ \{ u, v \} \in E(G) \ : \ u \in A , v \in B \}</math> शीर्षों के उपसमुच्चय के बीच के किनारे {{math|''A'',''B'' ⊆ ''V''(''G'')}}.
-समीकरण में, न्यूनतम सभी गैर-खाली सेटों पर है {{mvar|S}} अधिक से अधिक {{math|{{frac|''n''|2}}}} शिखर और {{math|∂''S''}} की किनारा सीमा है {{mvar|S}}, यानी, ठीक एक समापन बिंदु के साथ किनारों का सेट {{mvar|S}}.<ref>Definition 2.1 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+समीकरण में, न्यूनतम सभी गैर-रिक्त सेटों पर होती है {{mvar|S}} अधिक से अधिक {{math|{{frac|''n''|2}}}} शिखर और {{math|∂''S''}} की किनारा सीमा {{mvar|S}} है अर्थात, किनारों का सेट {{mvar|S}} में ठीक एक समापन बिंदु के साथ है।.<ref>Definition 2.1 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
 सहज रूप से,
 : <math>\min {|\partial S|} = \min E({S}, \overline{S})</math>
-किनारों की वह न्यूनतम संख्या है जिसे ग्राफ़ को दो भागों में विभाजित करने के लिए काटने की आवश्यकता है।
+ग्राफ़ को दो भागों में विभाजित करने के लिए किनारों की न्यूनतम संख्या को काटने की आवश्यकता होती है। किनारे का विस्तार इस अवधारणा को दो भागों में सबसे छोटी संख्या के साथ विभाजित करके सामान्य करता है। यह देखने के लिए कि कैसे सामान्यीकरण मूल्य को अत्यधिक बदल सकता है, निम्नलिखित उदाहरण पर अवधारणा करते है। तो n शीर्षों की समान संख्या वाले दो पूर्ण ग्राफ़ और उनके शीर्षों को एक से जोड़कर दोनों ग्राफ़ों के बीच n किनारों के रूप में उपयोग करते है। न्यूनतम कटौती n रूप में होती है लेकिन किनारे का विस्तार 1 होता है।
-किनारे का विस्तार इस अवधारणा को दो भागों में सबसे छोटी संख्या के साथ विभाजित करके सामान्य करता है।
-यह देखने के लिए कि कैसे सामान्यीकरण मूल्य को काफी हद तक बदल सकता है, निम्नलिखित उदाहरण पर विचार करें।
-शीर्षों की समान संख्या वाले दो पूर्ण ग्राफ़ लें {{mvar|n}} और जोड़ {{mvar|n}} दो ग्राफ़ के बीच किनारों को उनके शीर्षों को एक-से-एक करके जोड़कर।
-न्यूनतम कटौती होगी {{mvar|n}} लेकिन किनारे का विस्तार 1 होगा।
-ध्यान दें कि में {{math|min {{abs|∂''S''}}}}, ऑप्टिमाइज़ेशन या तो अधिक समान रूप से किया जा सकता है {{math|0 ≤ {{abs|''S''}} ≤ {{frac|''n''|2}}}} या किसी गैर-खाली सबसेट पर, चूंकि  <math>E(S, \overline{S}) = E(\overline{S}, S)</math>. के लिए सही नहीं है {{math|''h''(''G'')}} द्वारा सामान्यीकरण के कारण {{math|{{abs|''S''}}}}.
+ध्यान दें कि में {{math|min {{abs|∂''S''}}}}, ऑप्टिमाइज़ेशन या तो अधिक समान रूप से किया जा सकता है {{math|0 ≤ {{abs|''S''}} ≤ {{frac|''n''|2}}}} या किसी गैर-रिक्त सबसेट पर, चूंकि <math>E(S, \overline{S}) = E(\overline{S}, S)</math>. के लिए सही नहीं है {{math|''h''(''G'')}} द्वारा सामान्यीकरण के कारण {{math|{{abs|''S''}}}}.यदि हम {{math|''h''(''G'')}} को सभी गैर-रिक्त सबसेट पर एक अनुकूलन के साथ लिखना चाहते हैं तो हम इसे फिर से लिख सकते हैं
-अगर हम लिखना चाहते हैं {{math|''h''(''G'')}} सभी गैर-खाली सबसेट पर अनुकूलन के साथ, हम इसे फिर से लिख सकते हैं
 : <math>h(G) = \min_{\emptyset \subsetneq S\subsetneq V(G) } \frac{E({S}, \overline{S})}{\min\{|S|, |\overline{S}|\}}.</math>
 === वर्टेक्स विस्तार ===
-शीर्ष isoperimetric संख्या {{math|''h''{{sub|out}}(''G'')}} एक ग्राफ का (शीर्ष विस्तार या आवर्धन भी)। {{mvar|G}} परिभाषित किया जाता है
+वर्टेक्स आइसोपेरिमेट्रिक संख्या {{math|''h''{{sub|out}}(''G'')}} वर्टेक्स विस्तरण या ग्राफ {{mvar|G}} का आवर्धन इस रूप में परिभाषित किया गया है।
 : <math>h_{\text{out}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{out}}(S)|}{|S|},</math>
-कहाँ {{math|∂{{sub|out}}(''S'')}} की बाहरी सीमा है {{mvar|S}}, यानी, शीर्षों का सेट {{math|''V''(''G'') \ ''S''}} कम से कम एक पड़ोसी के साथ {{mvar|S}}.<ref name="BobkovHoudre">{{harvtxt|Bobkov|Houdré|Tetali|2000}}</ref> इस परिभाषा के एक प्रकार में (अद्वितीय पड़ोसी विस्तार कहा जाता है) {{math|∂{{sub|out}}(''S'')}} में वर्टिकल के सेट द्वारा प्रतिस्थापित किया जाता है {{mvar|V}} ठीक एक पड़ोसी के साथ {{mvar|S}}.<ref name="AlonCapalbo">{{harvtxt|Alon|Capalbo|2002}}</ref>
+जहाँ {{math|∂{{sub|out}}(''S'')}} की बाहरी सीमा {{mvar|S}} है अर्थात शीर्षों का सेट {{math|''V''(''G'') \ ''S''}} कम से कम एक निकटतम के साथ {{mvar|S}} के रूप में होते है.<ref name="BobkovHoudre">{{harvtxt|Bobkov|Houdré|Tetali|2000}}</ref> इस परिभाषा के एक अनुसार जिसे अद्वितीय निकटतम विस्तार कहा जाता है {{math|∂{{sub|out}}(''S'')}} को {{mvar|V}} में शीर्षों के सेट द्वारा {{mvar|S}} में ठीक एक निकटतम के साथ प्रतिस्थापित किया जाता है।.<ref name="AlonCapalbo">{{harvtxt|Alon|Capalbo|2002}}</ref>
-शीर्ष isoperimetric संख्या {{math|''h''{{sub|in}}(''G'')}} एक ग्राफ का {{mvar|G}} परिभाषित किया जाता है
+शीर्ष आइसोपेरिमेट्रिक संख्या {{math|''h''{{sub|in}}(''G'')}} एक ग्राफ का {{mvar|G}} द्वारा परिभाषित किया जाता है।
 : <math>h_{\text{in}}(G) = \min_{0 < |S|\le \frac{n}{2}} \frac{|\partial_{\text{in}}(S)|}{|S|},</math>
-कहाँ <math>\partial_{\text{in}}(S)</math> की भीतरी सीमा है {{mvar|S}}, यानी, शीर्षों का सेट {{mvar|S}} कम से कम एक पड़ोसी के साथ {{math|''V''(''G'') \ ''S''}}.<ref name="BobkovHoudre" />
+जहाँ <math>\partial_{\text{in}}(S)</math> की भीतरी सीमा {{mvar|S}} है, अर्थात शीर्षों का सेट {{mvar|S}} कम से कम एक निकटतम के साथ {{math|''V''(''G'') \ ''S''}} के रूप में होता है.<ref name="BobkovHoudre" />
+=== वर्णक्रमीय विस्तार ===
+जब {{mvar|G}} नियमित ग्राफ के रूप में होता है, तो विस्तार की एक रेखीय बीजगणितीय परिभाषा {{mvar|d}} के [[आसन्न आव्यूह]] {{math|1=''A'' = ''A''(''G'')}} का {{mvar|G}}, के अभिलक्षणिक मान के आधार पर संभव होता है, जहाँ {{mvar|A{{sub|ij}}}} शीर्षों {{mvar|i}} और {{mvar|j}} के बीच किनारों की संख्या के रूप में होती है।.<ref>cf. Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> क्योंकि {{mvar|A}} [[सममित मैट्रिक्स|सममित]] आव्यूह है, [[वर्णक्रमीय प्रमेय]] का तात्पर्य है {{mvar|A}} में {{mvar|n}} वास्तविक मूल्यवान अभिलक्षणिक मान {{math|λ{{sub|1}} ≥ λ{{sub|2}} ≥ … ≥ λ{{sub|''n''}}}}. के रूप में हैं यह ज्ञात है कि ये सभी अभिलक्षणिक मान  {{math|[−''d'', ''d'']}} में हैं और अधिक विशेष रूप से यह ज्ञात है कि {{math|1=λ{{sub|''n''}} = −''d''}} यदि और केवल यदि {{mvar|G}} द्विपक्षीय रूप में है।
-=== वर्णक्रमीय विस्तार ===
+अधिक औपचारिक रूप से, हम एक n वर्टेक्स {{mvar|d}}-नियमित ग्राफ़ को संदर्भित करते हैं
-कब {{mvar|G}} नियमित ग्राफ है|{{mvar|d}}-नियमित, विस्तार की एक रेखीय बीजगणितीय परिभाषा Eigenvalue#Eigenvalues of the matrices of the [[adjacency matrix]] के आधार पर संभव है {{math|1=''A'' = ''A''(''G'')}} का {{mvar|G}}, कहाँ {{mvar|A{{sub|ij}}}} शीर्षों के बीच किनारों की संख्या है {{mvar|i}} और {{mvar|j}}.<ref>cf. Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> क्योंकि {{mvar|A}} [[सममित मैट्रिक्स]] है, [[वर्णक्रमीय प्रमेय]] का अर्थ है {{mvar|A}} है {{mvar|n}} वास्तविक मूल्यवान eigenvalues {{math|λ{{sub|1}} ≥ λ{{sub|2}} ≥ … ≥ λ{{sub|''n''}}}}. यह ज्ञात है कि ये सभी eigenvalues में हैं {{math|[−''d'', ''d'']}} और अधिक विशेष रूप से, यह ज्ञात है कि {{math|1=λ{{sub|''n''}} = −''d''}} अगर और केवल अगर {{mvar|G}} द्विपक्षीय है।
+:<math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math> एक के रूप में {{math|(''n'', ''d'', λ)}}-ग्राफ द्वारा दी गई सीमा {{math|(''n'', ''d'', λ)}}-ग्राफ {{math|λ{{sub|''i''}}}} के लिए {{math|''i'' ≠ 1}} [[विस्तारक मिश्रण लेम्मा]] सहित कई संदर्भों में उपयोगी रूप में होते है।
-अधिक औपचारिक रूप से, हम एक का उल्लेख करते हैं {{mvar|n}}-वर्टेक्स, {{mvar|d}}-नियमित ग्राफ के साथ
+क्योंकि {{mvar|G}} नियमित है, समान वितरण <math>u\in\R^n</math> साथ {{math|1=''u{{sub|i}}'' = {{frac|1|''n''}}}} सभी के लिए {{math|1=''i'' = 1, …, ''n''}} का [[स्थिर वितरण]] {{mvar|G}}.रूप में होते है अर्थात हमारे पास है {{math|1=''Au'' = ''du''}}, और {{mvar|u}} का [[आइजन्वेक्टर|अभिलक्षणिक सदिश]] {{mvar|A}} है अभिलक्षणिक मान {{math|1=λ{{sub|1}} = ''d''}} है, जहाँ {{mvar|d}}, {{mvar|G}} के शीर्षों की डिग्री (ग्राफ़ सिद्धांत) है।.{{mvar|G}} का [[वर्णक्रमीय अंतर]] को {{math|''d'' − λ{{sub|2}}}} के रूप में परिभाषित किया गया है और यह वर्णक्रमीय विस्तार को मापता है ग्राफ {{mvar|G}} का।.<ref>This definition of the spectral gap is from Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
-:<math>\max_{i \neq 1}|\lambda_i| \leq \lambda</math> एक के रूप में {{math|(''n'', ''d'', λ)}}-ग्राफ। एक द्वारा दी गई सीमा {{math|(''n'', ''d'', λ)}}-ग्राफ ऑन {{math|λ{{sub|''i''}}}} के लिए {{math|''i'' ≠ 1}} [[विस्तारक मिश्रण लेम्मा]] सहित कई संदर्भों में उपयोगी है।
-क्योंकि {{mvar|G}} नियमित है, समान वितरण <math>u\in\R^n</math> साथ {{math|1=''u{{sub|i}}'' = {{frac|1|''n''}}}} सभी के लिए {{math|1=''i'' = 1, …, ''n''}} का [[स्थिर वितरण]] है {{mvar|G}}. यानी हमारे पास है {{math|1=''Au'' = ''du''}}, और {{mvar|u}} का [[आइजन्वेक्टर]] है {{mvar|A}} आइगेनवैल्यू के साथ {{math|1=λ{{sub|1}} = ''d''}}, कहाँ {{mvar|d}} के शीर्षों की डिग्री (ग्राफ़ सिद्धांत) है {{mvar|G}}. का [[वर्णक्रमीय अंतर]] {{mvar|G}} होना परिभाषित किया गया है {{math|''d'' − λ{{sub|2}}}}, और यह ग्राफ के वर्णक्रमीय विस्तार को मापता है {{mvar|G}}.<ref>This definition of the spectral gap is from Section 2.3 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+यदि हम सेट बनाते हैं तो,
-अगर हम सेट करते हैं
 :<math>\lambda=\max\{|\lambda_2|, |\lambda_n|\}</math>
-क्योंकि यह एक ईजेनवेक्टर [[ओर्थोगोनल]] के अनुरूप सबसे बड़ा आइगेनवैल्यू है {{mvar|u}}, इसे [[रेले भागफल]] का उपयोग करके समान रूप से परिभाषित किया जा सकता है:
+क्योंकि यह एक अभिलक्षणिक सदिश [[ओर्थोगोनल]] के अनुरूप सबसे बड़ा अभिलक्षणिक मान है {{mvar|u}}, इसे [[रेले भागफल|रेलेइग़ भागफल]] का उपयोग करके समान रूप से परिभाषित किया जा जाता है
 :<math>\lambda=\max_{v \perp u , v \neq 0} \frac{\|Av\|_2}{\|v\|_2},</math>
-कहाँ
+जहाँ
-:<math>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</math> वेक्टर का 2-मानक है <math>v\in\R^n</math>.
+:<math>\|v\|_2=\left(\sum_{i=1}^n v_i^2\right)^{1/2}</math> सदिश का 2-मानक <math>v\in\R^n</math> के रूप में होता है।
-इन परिभाषाओं के सामान्यीकृत संस्करण भी व्यापक रूप से उपयोग किए जाते हैं और कुछ परिणामों को बताते हुए अधिक सुविधाजनक होते हैं। यहाँ एक मैट्रिक्स पर विचार करता है {{math|{{sfrac|1|''d''}}''A''}}, जो ग्राफ का [[मार्कोव संक्रमण मैट्रिक्स]] है {{mvar|G}}. इसके eigenvalues -1 और 1 के बीच हैं। जरूरी नहीं कि नियमित ग्राफ़ के लिए, ग्राफ़ के स्पेक्ट्रम को [[लाप्लासियन मैट्रिक्स]] के eigenvalues का उपयोग करके इसी तरह परिभाषित किया जा सकता है। निर्देशित रेखांकन के लिए, आसन्न मैट्रिक्स के [[विलक्षण मूल्य]]ों पर विचार किया जाता है {{mvar|A}}, जो सममित मैट्रिक्स के eigenvalues की जड़ों के बराबर हैं {{math|''A''{{sup|T}}''A''}}.
+इन परिभाषाओं के सामान्यीकृत संस्करण भी व्यापक रूप से उपयोग किए जाते हैं और कुछ परिणामों को बताते हुए अधिक सुविधाजनक होते हैं। यहाँ एक आव्यूह {{math|{{sfrac|1|''d''}}''A''}} पर अवधारणा के रूप में होता है, जो कि ग्राफ {{mvar|G}}. का [[मार्कोव संक्रमण मैट्रिक्स|मार्कोव ट्रांज़िशन]] आव्यूह होता है इसके अभिलक्षणिक मान -1 और 1 के बीच होते है। जरूरी नहीं कि नियमित ग्राफ़ के लिए, ग्राफ़ के स्पेक्ट्रम को [[लाप्लासियन]] मैट्रिक्स के अभिलक्षणिक मान का उपयोग करके इसी प्रकार  परिभाषित किया जा सकता है। निर्देशित रेखांकन के लिए, आसन्न आव्यूह {{mvar|A}} के [[विलक्षण मूल्य]] पर अवधारणा किया जाता है, जो सममित आव्यूह {{math|''A''{{sup|T}}''A''}}.के अभिलक्षणिक मान की रूट्स के बराबर होते है।
 == विभिन्न विस्तार गुणों के बीच संबंध ==
-ऊपर परिभाषित विस्तार पैरामीटर एक दूसरे से संबंधित हैं। विशेष रूप से, किसी के लिए {{mvar|d}}-नियमित ग्राफ {{mvar|G}},
+ऊपर परिभाषित विस्तार पैरामीटर एक दूसरे से संबंधित हैं। विशेष रूप से, किसी के लिए {{mvar|d}}-नियमित ग्राफ {{mvar|G}},के लिए इस प्रकार से होते है।
 :<math>h_{\text{out}}(G) \le h(G) \le d \cdot h_{\text{out}}(G).</math>
-नतीजतन, निरंतर डिग्री ग्राफ के लिए, वर्टेक्स और एज एक्सपेंशन गुणात्मक रूप से समान हैं।
+परिणामस्वरुप, निरंतर डिग्री ग्राफ के लिए, वर्टेक्स और किनारे एक्सपेंशन गुणात्मक रूप से समान होते है।
 === चीजर असमानताएं ===
-कब {{mvar|G}} है {{mvar|d}}-नियमित, जिसका अर्थ है कि प्रत्येक शीर्ष डिग्री का है {{mvar|d}}, isoperimetric स्थिरांक के बीच एक संबंध है {{math|''h''(''G'')}} और अंतराल {{math|''d'' − λ{{sub|2}}}} के आसन्न ऑपरेटर के स्पेक्ट्रम में {{mvar|G}}. मानक वर्णक्रमीय ग्राफ सिद्धांत द्वारा, a के आसन्न संचालिका का तुच्छ eigenvalue {{mvar|d}}-नियमित ग्राफ है {{math|1=λ{{sub|1}} = ''d''}} और पहला गैर-तुच्छ eigenvalue है {{math|λ{{sub|2}}}}. अगर {{mvar|G}} जुड़ा हुआ है, तो {{math|λ{{sub|2}} < ''d''}}. डोडिज़ुक के कारण एक असमानता{{Sfn|Dodziuk|1984}} और स्वतंत्र रूप से [[सावधान अलोन]] और [[विटाली मिलमैन]]{{Sfn|Alon|Spencer|2011}} बताता है<ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+कब {{mvar|G}}, {{mvar|d}}-नियमित होता है, जिसका अर्थ है कि प्रत्येक शीर्ष डिग्री {{mvar|d}} का है, तो आइसोपेरिमेट्रिक स्थिरांक {{math|''h''(''G'')}} और {{mvar|G}}. के आसन्न ऑपरेटर के स्पेक्ट्रम में अंतराल {{math|''d'' − λ{{sub|2}}}} के बीच संबंध होता है। {{mvar|d}}-नियमित ग्राफ का आसन्न ऑपरेटर λ1 = d है और पहला गैर-तुच्छ अभिलक्षणिक मान {{math|λ{{sub|2}}}}.है यदि {{mvar|G}} से जुड़ा हुआ है, तो {{math|λ{{sub|2}} < ''d''}}. डोडिज़ुक के कारण एक असमानता{{Sfn|Dodziuk|1984}} और स्वतंत्र रूप से [[सावधान अलोन]] और [[विटाली मिलमैन]]{{Sfn|Alon|Spencer|2011}} बताता है कि <ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
 : <math>\tfrac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.</math>
-वास्तव में, निचला बाउंड तंग है। [[हाइपरक्यूब ग्राफ]] के लिए सीमा में निचली सीमा हासिल की जाती है {{mvar|Q{{sub|n}}}}, कहाँ {{math|1=''h''(''G'') = 1}} और {{math|1=''d'' – λ = 2}}. ऊपरी सीमा एक चक्र के लिए (असामयिक रूप से) हासिल की जाती है, जहां {{math|1=''H''(''C{{sub|n}}'') = 4/''n''= Θ(1/''n'')}} और {{math|1=''d'' – λ = 2-2cos(2<math>\pi</math>/''n'') ≈ (2<math>\pi</math>/''n'')^2= Θ(1/''n''{{sup|2}})}}.<ref name="Hoory 2006"/>में एक बेहतर बाउंड दिया गया है <ref>B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291,
+वास्तव में, निचला बाउंड घना है। [[हाइपरक्यूब ग्राफ]] के लिए सीमा में निचली सीमा {{mvar|Q{{sub|n}}}},प्राप्त की जाती है, जहाँ {{math|1=''h''(''G'') = 1}} और {{math|1=''d'' – λ = 2}}. ऊपरी सीमा एक चक्र के लिए असामयिक रूप से प्राप्त की जाती है, जहां {{math|1=''H''(''C{{sub|n}}'') = 4/''n''= Θ(1/''n'')}} और {{math|1=''d'' – λ = 2-2cos(2<math>\pi</math>/''n'') ≈ (2<math>\pi</math>/''n'')^2= Θ(1/''n''{{sup|2}})}}.<ref name="Hoory 2006" /> में एक अच्छा बाउंड दिया गया है <ref>B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. B, 47(3):274–291,
-.</ref> जैसा
+.</ref> जैसा,
 : <math> h(G) \le \sqrt{d^2 - \lambda_2^2}.</math>
-ये असमानताएँ मार्कोव श्रृंखलाओं के लिए बाध्य चीजर से निकटता से संबंधित हैं और इन्हें चीगर स्थिरांक#चीगर.27s असमानता|रीमैनियन ज्यामिति में चीगर की असमानता के असतत संस्करण के रूप में देखा जा सकता है।
+ये असमानताएँ मार्कोव श्रृंखलाओं के लिए बाध्य चीगर से निकटता से संबंधित होती है और इन्हें रीमैनियन ज्यामिति में चीगर की असमानता के असतत संस्करण के रूप में देखा जा सकता है।
-वर्टेक्स आइसोपेरिमेट्रिक नंबर और स्पेक्ट्रल गैप के बीच समान कनेक्शन का भी अध्ययन किया गया है:<ref>See Theorem 1 and p.156, l.1 in {{harvtxt|Bobkov|Houdré|Tetali|2000}}. Note that {{math|λ{{sub|2}}}} there corresponds to {{math|2(''d'' − λ{{sub|2}})}} of the current article (see p.153, l.5)</ref>
+वर्टेक्स आइसोपेरिमेट्रिक नंबर और वर्णक्रमीय गैप के बीच समान कनेक्शन का भी अध्ययन किया जाता है:<ref>See Theorem 1 and p.156, l.1 in {{harvtxt|Bobkov|Houdré|Tetali|2000}}. Note that {{math|λ{{sub|2}}}} there corresponds to {{math|2(''d'' − λ{{sub|2}})}} of the current article (see p.153, l.5)</ref>
 : <math>h_{\text{out}}(G)\le \left(\sqrt{4 (d-\lambda_2)} + 1\right)^2 -1</math>
 : <math>h_{\text{in}}(G) \le \sqrt{8(d-\lambda_2)}.</math>
-असम्बद्ध रूप से बोलना, मात्राएँ {{math|{{frac|''h''{{sup|2}}|''d''}}}}, {{math|''h''{{sub|out}}}}, और {{math|''h''{{sub|in}}{{sup|2}}}} सभी वर्णक्रमीय अंतर से ऊपर बंधे हैं {{math|''O''(''d'' – λ{{sub|2}})}}.
+समान रूप से बोलते हुए, मात्रा {{math|{{frac|''h''{{sup|2}}|''d''}}}}, {{math|''h''{{sub|out}}}}, और {{math|''h''{{sub|in}}{{sup|2}}}} सभी ऊपर वर्णक्रमीय अंतराल {{math|''O''(''d'' – λ{{sub|2}})}}.से घिरी हुई हैं।
 == निर्माण ==
-विस्तारक रेखांकन के स्पष्ट रूप से परिवारों के निर्माण के लिए तीन सामान्य रणनीतियाँ हैं।<ref>see, e.g., {{harvtxt|Yehudayoff|2012}}</ref> पहली रणनीति बीजगणितीय और समूह-सैद्धांतिक है, दूसरी रणनीति विश्लेषणात्मक है और [[योगात्मक संयोजक]] का उपयोग करती है, और तीसरी रणनीति कॉम्बिनेटरियल है और ज़िग-ज़ैग उत्पाद | ज़िग-ज़ैग और संबंधित ग्राफ़ उत्पादों का उपयोग करती है। नोगा अलोन ने दिखाया कि [[परिमित ज्यामिति]] से निर्मित कुछ ग्राफ़ अत्यधिक विस्तार वाले ग्राफ़ के सबसे दुर्लभ उदाहरण हैं।<ref>{{cite journal | doi=10.1007/BF02579382 | volume=6 |issue = 3| title=Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory | journal=Combinatorica | pages=207–219 | year=1986 | last1 = Alon | first1 = Noga| citeseerx=10.1.1.300.5945 | s2cid=8666466 }}</ref>
+विस्तारक ग्राफ़ के समूहों को स्पष्ट रूप से बनाने के लिए तीन सामान्य रणनीतियाँ हैं।<ref>see, e.g., {{harvtxt|Yehudayoff|2012}}</ref> पहली रणनीति बीजगणितीय और समूह सिद्धांत है, दूसरी रणनीति विश्लेषणात्मक है और [[योगात्मक संयोजक]] का उपयोग करती है और तीसरी रणनीति कॉम्बिनेटरियल है और ज़िग ज़ैग और संबंधित ग्राफ़ उत्पादों का उपयोग करती है। नोगा अलोन ने दिखाया कि [[परिमित ज्यामिति]] से निर्मित कुछ ग्राफ़ अत्यधिक विस्तार वाले ग्राफ़ के सबसे दुर्लभ उदाहरण के रूप में हैं।<ref>{{cite journal | doi=10.1007/BF02579382 | volume=6 |issue = 3| title=Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory | journal=Combinatorica | pages=207–219 | year=1986 | last1 = Alon | first1 = Noga| citeseerx=10.1.1.300.5945 | s2cid=8666466 }}</ref>
 === मार्गुलिस-गैबर-गैलिल ===
-[[केली ग्राफ]]़ पर आधारित [[सार बीजगणित]] निर्माण विस्तारक ग्राफ़ के विभिन्न रूपों के लिए जाने जाते हैं। निम्नलिखित निर्माण मार्गुलिस के कारण है और गैबर और गैलिल द्वारा इसका विश्लेषण किया गया है।<ref>see, e.g., p.9 of {{harvtxt|Goldreich|2011}}</ref> प्रत्येक प्राकृतिक संख्या के लिए {{mvar|n}}, एक ग्राफ पर विचार करता है {{mvar|G{{sub|n}}}} वर्टेक्स सेट के साथ <math>\mathbb Z_n \times \mathbb Z_n</math>, कहाँ <math>\mathbb Z_n=\mathbb Z/n\mathbb Z</math>: प्रत्येक शीर्ष के लिए <math>(x,y)\in\mathbb Z_n \times \mathbb Z_n</math>, इसके आठ आसन्न शीर्ष हैं
+[[केली ग्राफ]] पर आधारित [[सार बीजगणित]] निर्माण विस्तारक ग्राफ़ के विभिन्न रूपों के लिए जाने जाते हैं। निम्नलिखित निर्माण मार्गुलिस के कारण है और गैबर और गैलिल द्वारा इसका विश्लेषण किया गया है।<ref>see, e.g., p.9 of {{harvtxt|Goldreich|2011}}</ref> प्रत्येक प्राकृतिक संख्या के लिए {{mvar|n}}, एक ग्राफ {{mvar|G{{sub|n}}}} पर अवधारणा करता है, वर्टेक्स सेट के साथ <math>\mathbb Z_n \times \mathbb Z_n</math>, जहाँ <math>\mathbb Z_n=\mathbb Z/n\mathbb Z</math>: प्रत्येक शीर्ष के लिए <math>(x,y)\in\mathbb Z_n \times \mathbb Z_n</math>, इसके आठ आसन्न शीर्ष हैं
 :<math>(x \pm 2y,y), (x \pm (2y+1),y), (x,y \pm 2x), (x,y \pm (2x+1)).</math>
-फिर निम्नलिखित धारण करता है:
+फिर निम्नलिखित धारण करता है
-<ब्लॉककोट>प्रमेय। सभी के लिए {{mvar|n}}, लेखाचित्र {{mvar|G{{sub|n}}}} का दूसरा सबसे बड़ा eigenvalue है <math>\lambda(G)\leq 5 \sqrt{2}</math></ब्लॉककोट>
+प्रमेय सभी के लिए {{mvar|n}}, लेखाचित्र {{mvar|G{{sub|n}}}} का दूसरा सबसे बड़ा <math>\lambda(G)\leq 5 \sqrt{2}</math> अभिलक्षणिक मान है
 ===रामनुजन ग्राफ्स===
-{{main article|Ramanujan graph}}
+{{main article|रामनुजन ग्राफ्स}}
-एक [[अलोन-बोपना बाउंड]] द्वारा, सभी पर्याप्त रूप से बड़े {{mvar|d}}-नियमित रेखांकन संतुष्ट करते हैं <math>\lambda_2 \ge 2\sqrt{d-1} - o(1)</math>, कहाँ {{math|λ{{sub|2}}}} निरपेक्ष मान में दूसरा सबसे बड़ा eigenvalue है।<ref>Theorem 2.7 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> प्रत्यक्ष परिणाम के रूप में, हम जानते हैं कि प्रत्येक निश्चित के लिए {{mvar|d}} और <math>\lambda< 2 \sqrt{d-1}</math> , निश्चित रूप से अनेक हैं {{math|(''n'', ''d'', λ)}}-ग्राफ। [[रामानुजन ग्राफ]] हैं {{mvar|d}}-नियमित रेखांकन जिसके लिए यह सीमा कड़ी है, संतोषजनक है <ref>Definition 5.11 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> :<math>\lambda = \max_{|\lambda_i| < d} |\lambda_i| \le 2\sqrt{d-1}.</math>
+एक [[अलोन-बोपना बाउंड]] द्वारा, सभी पर्याप्त रूप से बड़े {{mvar|d}}-नियमित रेखांकन संतुष्ट करते हैं <math>\lambda_2 \ge 2\sqrt{d-1} - o(1)</math>, जहाँ {{math|λ{{sub|2}}}} निरपेक्ष मान में दूसरा सबसे बड़ा अभिलक्षणिक मान है।<ref>Theorem 2.7 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> प्रत्यक्ष परिणाम के रूप में, हम जानते हैं कि प्रत्येक निश्चित के लिए {{mvar|d}} और <math>\lambda< 2 \sqrt{d-1}</math> , निश्चित रूप से अनेक हैं {{math|(''n'', ''d'', λ)}}-ग्राफ [[रामानुजन ग्राफ]] हैं, {{mvar|d}}-नियमित रेखांकन जिसके लिए यह सीमा घनी संतोषजनक है <ref>Definition 5.11 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref> :<math>\lambda = \max_{|\lambda_i| < d} |\lambda_i| \le 2\sqrt{d-1}.</math>
-इसलिए रामानुजन के रेखांकन का एक विषम रूप से सबसे छोटा संभव मान है {{math|λ{{sub|2}}}}. यह उन्हें उत्कृष्ट वर्णक्रमीय विस्तारक बनाता है।
-[[अलेक्जेंडर लुबोत्ज़की]], फिलिप्स, और [[पीटर इतिहास]] (1988), मार्गुलिस (1988), और मॉर्गनस्टर्न (1994) दिखाते हैं कि रामानुजन ग्राफ को स्पष्ट रूप से कैसे बनाया जा सकता है।<ref>Theorem 5.12 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+इसलिए रामानुजन के रेखांकन {{math|λ{{sub|2}}}}.का एक विषम रूप से सबसे छोटा संभव मान है यह उन्हें उत्कृष्ट वर्णक्रमीय विस्तारक बनाता है।
-में, एलोन ने सबसे अधिक अनुमान लगाया {{mvar|d}}-नियमित रेखांकन पर {{mvar|n}} कोने, पर्याप्त रूप से बड़े के लिए {{mvar|n}}, लगभग रामानुजन हैं।<ref>{{Cite journal|last=Alon|first=Noga|date=1986-06-01|title=Eigenvalues and expanders|url=https://doi.org/10.1007/BF02579166|journal=Combinatorica|language=en|volume=6|issue=2|pages=83–96|doi=10.1007/BF02579166|s2cid=41083612|issn=1439-6912}}</ref> यानी के लिए {{math|''φ'' > 0}}, वे संतुष्ट हैं
-:<math>\lambda \le 2\sqrt{d-1}+\varepsilon</math>.
+[[अलेक्जेंडर लुबोत्ज़की]], फिलिप्स और [[पीटर इतिहास]] (1988), मार्गुलिस (1988), और मॉर्गनस्टर्न (1994) दिखाते हैं कि रामानुजन ग्राफ को स्पष्ट रूप से कैसे बनाया जा सकता है।<ref>Theorem 5.12 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
-में, जोएल फ्रीडमैन दोनों ने अनुमान को साबित किया और निर्दिष्ट किया कि अधिकांश का क्या मतलब है {{mvar|d}}-रेगुलर ग्राफ़ दिखाकर कि रैंडम रेगुलर ग्राफ़ | रैंडम {{mvar|d}}-नियमित रेखांकन है <math>\lambda \le 2\sqrt{d-1}+\varepsilon</math> हरएक के लिए {{math|''φ'' > 0}} संभावना के साथ {{math|1 – ''O''(''n''{{sup|τ}})}}, कहाँ<ref>{{cite arXiv|last=Friedman|first=Joel|date=2004-05-05|title=A proof of Alon's second eigenvalue conjecture and related problems|eprint=cs/0405020}}</ref><ref>Theorem 7.10 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+में, एलोन ने सबसे अधिक अनुमान लगाया {{mvar|d}}-नियमित रेखांकन पर {{mvar|n}} कोने पर्याप्त रूप से बड़े के लिए {{mvar|n}}, लगभग रामानुजन हैं।<ref>{{Cite journal|last=Alon|first=Noga|date=1986-06-01|title=Eigenvalues and expanders|url=https://doi.org/10.1007/BF02579166|journal=Combinatorica|language=en|volume=6|issue=2|pages=83–96|doi=10.1007/BF02579166|s2cid=41083612|issn=1439-6912}}</ref> अर्थात के लिए {{math|''φ'' > 0}}, वे
-:<math>\tau = \left\lceil\frac{\sqrt{d-1} +1}{2} \right\rceil.</math>
+:<math>\lambda \le 2\sqrt{d-1}+\varepsilon</math>.को संतुष्ट हैं
+में, जोएल फ्रीडमैन दोनों ने अनुमान को सिद्ध किया और निर्दिष्ट किया कि अधिकांश {{mvar|d}} नियमित ग्राफ़ का क्या मतलब है यह दिखाते हुए कि यादृच्छिक {{mvar|d}} नियमित ग्राफ़ में <math>\lambda \le 2\sqrt{d-1}+\varepsilon</math> हर {{math|''φ'' > 0}} के लिए प्रायिकता {{math|1 – ''O''(''n''{{sup|τ}})}}, के साथ हैं जहाँ <ref>{{cite arXiv|last=Friedman|first=Joel|date=2004-05-05|title=A proof of Alon's second eigenvalue conjecture and related problems|eprint=cs/0405020}}</ref><ref>Theorem 7.10 of {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>
+:<math>\tau = \left\lceil\frac{\sqrt{d-1} +1}{2} \right\rceil.</math><br />
 === ज़िग-ज़ैग उत्पाद ===
-{{Main articles|Zig-zag product}}
+{{Main articles|ज़िग-ज़ैग उत्पाद}}
-में [[ओमर रीनॉल्ड]], [[सलिल वधान]] और [[एवी विगडरसन]] ने ज़िग-ज़ैग उत्पाद पेश किया।<ref name=":0">{{Cite journal|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors|url=http://dx.doi.org/10.1109/sfcs.2000.892006|journal=Proceedings 41st Annual Symposium on Foundations of Computer Science|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref> मोटे तौर पर बोलते हुए, दो विस्तारक ग्राफों का ज़िग-ज़ैग उत्पाद केवल थोड़ा खराब विस्तार वाला ग्राफ बनाता है। इसलिए, विस्तारक ग्राफ के परिवारों के निर्माण के लिए एक ज़िग-ज़ैग उत्पाद का भी उपयोग किया जा सकता है। अगर {{mvar|G}} एक है {{math|(''n'', ''m'', λ{{sub|1}})}}-ग्राफ और {{mvar|H}} एक {{math|(''m'', ''d'', λ{{sub|1}})}}-ग्राफ, फिर ज़िग-ज़ैग उत्पाद {{math|''G'' ◦ ''H''}} एक है {{math|(''nm'', ''d''{{sup|2}}, ''φ''(λ{{sub|1}}, λ{{sub|2}}))}}-ग्राफ जहां {{mvar|φ}} निम्नलिखित गुण हैं।
+में [[ओमर रीनॉल्ड]], [[सलिल वधान]] और [[एवी विगडरसन]] ने ज़िग-ज़ैग उत्पाद प्रस्तुत किया।<ref name=":0">{{Cite journal|last1=Reingold|first1=O.|last2=Vadhan|first2=S.|last3=Wigderson|first3=A.|title=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors|url=http://dx.doi.org/10.1109/sfcs.2000.892006|journal=Proceedings 41st Annual Symposium on Foundations of Computer Science|year=2000|pages=3–13|publisher=IEEE Comput. Soc|doi=10.1109/sfcs.2000.892006|isbn=0-7695-0850-2|s2cid=420651}}</ref> मोटे तौर पर बोलते हुए, दो विस्तारक ग्राफों का ज़िग-ज़ैग उत्पाद केवल थोड़ा खराब विस्तार वाला ग्राफ बनाता है। इसलिए, विस्तारक ग्राफ के समूहों के निर्माण के लिए एक ज़िग-ज़ैग उत्पाद का भी उपयोग किया जा सकता है। यदि {{mvar|G}} एक है {{math|(''n'', ''m'', λ{{sub|1}})}}-ग्राफ और {{mvar|H}} एक {{math|(''m'', ''d'', λ{{sub|1}})}}-ग्राफ, फिर ज़िग-ज़ैग उत्पाद {{math|''G'' ◦ ''H''}} एक है {{math|(''nm'', ''d''{{sup|2}}, ''φ''(λ{{sub|1}}, λ{{sub|2}}))}}-ग्राफ जहां {{mvar|φ}} निम्नलिखित गुण के रूप में होते है।
-# अगर {{math|λ{{sub|1}} < 1}} और {{math|λ{{sub|2}} < 1}}, तब {{math|''φ''(λ{{sub|1}}, λ{{sub|2}}) < 1}};
+# यदि {{math|λ{{sub|1}} < 1}} और {{math|λ{{sub|2}} < 1}}, तब {{math|''φ''(λ{{sub|1}}, λ{{sub|2}}) < 1}};
 # {{math|''φ''(λ{{sub|1}}, λ{{sub|2}}) ≤  λ{{sub|1}} + λ{{sub|2}}}}.
 विशेष रूप से,<ref name=":0" />:<math>f(\lambda_1, \lambda_2)=\frac{1}{2}(1-\lambda^2_2)\lambda_2 +\frac{1}{2}\sqrt{(1-\lambda^2_2)^2\lambda_1^2 +4\lambda^2_2}.</math>
-ध्यान दें कि संपत्ति (1) का तात्पर्य है कि दो विस्तारक ग्राफों का ज़िग-ज़ैग उत्पाद भी एक विस्तारक ग्राफ है, इस प्रकार ज़िग-ज़ैग उत्पादों का उपयोग विस्तारक ग्राफों के एक परिवार को बनाने के लिए किया जा सकता है।
-सहज रूप से, ज़िग-ज़ैग उत्पाद के निर्माण के बारे में निम्नलिखित तरीके से सोचा जा सकता है। का प्रत्येक शीर्ष {{mvar|G}} के बादल तक उड़ा दिया जाता है {{mvar|m}} कोने, प्रत्येक शीर्ष से जुड़े एक अलग किनारे से जुड़ा हुआ है। प्रत्येक शीर्ष को अब के रूप में लेबल किया गया है {{math|(''v'', ''k'')}} कहाँ {{mvar|v}} के एक मूल शीर्ष को संदर्भित करता है {{mvar|G}} और {{mvar|k}} यह आपकी जानकारी के लिए है {{mvar|k}}इसका किनारा {{mvar|v}}. दो शिखर, {{math|(''v'', ''k'')}} और {{math|(''w'',''l'')}} जुड़े हुए हैं यदि से प्राप्त करना संभव है {{math|(''v'', ''k'')}} को {{math|(''w'', ''l'')}} चालों के निम्नलिखित क्रम के माध्यम से।
+ध्यान दें कि गुण (1) का तात्पर्य है कि दो विस्तारक ग्राफों का ज़िग-ज़ैग उत्पाद भी एक विस्तारक ग्राफ के रूप में होता है, इस प्रकार ज़िग-ज़ैग उत्पादों का उपयोग विस्तारक ग्राफों के एक समूह को बनाने के लिए किया जाता है।
+सहज रूप से, ज़िग-ज़ैग उत्पाद के निर्माण के बारे में निम्नलिखित विधि से सोचा जा सकता है। {{mvar|G}} के प्रत्येक शीर्ष को m शीर्षों के एक बादल तक उड़ाया जाता है, प्रत्येक शीर्ष से जुड़े एक अलग किनारे से जुड़ा होता है। प्रत्येक शीर्ष को अब {{math|(''v'', ''k'')}} के रूप में लेबल किया गया है जहाँ {{mvar|v}}, {{mvar|G}} के मूल शीर्ष को संदर्भित करता है और {{mvar|k}} इसका किनारा {{mvar|v}}. दो शिखर, {{math|(''v'', ''k'')}} और {{math|(''w'',''l'')}} जुड़े हुए हैं। निम्नलिखित अनुक्रम के माध्यम से {{math|(''v'', ''k'')}} को {{math|(''w'', ''l'')}} तक जाने के लिए उपयोग करते है।
-# ज़िग - से हटो {{math|(''v'', ''k'')}} को {{math|(''v'', ''k' '')}}, के किनारे का उपयोग करना {{mvar|H}}.
+# ज़िग - {{mvar|H}} के किनारे का उपयोग करके {{math|(''v'', ''k'')}} को {{math|(''v'', ''k' '')}} पर जाते है।
-# किनारे का उपयोग करके बादलों में कूदें {{mvar|k'}} में {{mvar|G}} को पाने के लिए {{math|(''w'', ''l' '')}}.
+#{{math|(''w'', ''l' '')}}. पर जाने के लिए {{mvar|G}} में किनारे {{mvar|k'}}' का उपयोग करके घन पर जाते है।
-# ज़ग - से हटो {{math|(''w'', ''l' '')}} को {{math|(''w'', ''l'')}} के किनारे का उपयोग करना {{mvar|H}}.<ref name=":0" />
+# ज़ैग - {{mvar|H}}. के किनारे का उपयोग करके{{math|(''w'', ''l' '')}} को {{math|(''w'', ''l'')}} पर जाते है।.<ref name=":0" />
 ===यादृच्छिक निर्माण===
-ऐसे कई परिणाम हैं जो संभाव्य तर्कों के माध्यम से अच्छे विस्तार गुणों वाले ग्राफ़ के अस्तित्व को दर्शाते हैं। वास्तव में, विस्तारकों के अस्तित्व को सबसे पहले पिंस्कर ने सिद्ध किया था<ref>{{Cite journal|last=Pinkser|first=M.|title=On the Complexity of a Concentrator|journal=[[SIAM Journal on Computing]]|year=1973|publisher=SIAM|citeseerx=10.1.1.393.1430}}</ref> जिसने दिखाया कि एक यादृच्छिक रूप से चुने गए के लिए {{mvar|n}} शीर्ष छोड़ दिया {{mvar|d}} नियमित [[द्विपक्षीय ग्राफ]],  {{math|{{abs|''N''(''S'')}} ≥ (''d'' – 2){{abs|''S''}}}} कोने के सभी सबसेट के लिए {{math|{{abs|''S''}} ≤ ''c{{sub|d}}n''}} उच्च संभावना के साथ, कहाँ {{mvar|c{{sub|d}}}} पर निर्भर करता है {{mvar|d}} वह है {{math|''O''(''d''{{sup|-4}})}}. अलोन और रोचमैन <ref>{{Cite journal|last1=Alon|first1=N.|last2=Roichman|first2=Y.|title=Random Cayley graphs and Expanders|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203|journal=Random Structures and Algorithms|year=1994|volume=5|issue=2|pages=271–284|publisher=Wiley Online Library|doi=10.1002/rsa.3240050203}}</ref> दिखाया कि हर समूह के लिए {{mvar|G}} आदेश की {{mvar|n}} और हर {{math|1 > ''ε'' > 0}}, वहाँ कुछ {{math|''c''(''ε'') > 0}} ऐसा है कि केली ग्राफ पर {{mvar|G}} साथ {{math|''c''(''ε'') log{{sub|2}} ''n''}} जनरेटर एक है {{mvar|ε}} विस्तारक, यानी इसका दूसरा ईगेनवैल्यू से कम है {{math|1 – ''ε'' }}, उच्च संभावना के साथ।
+ऐसे कई परिणाम हैं जो संभाव्य तर्कों के माध्यम से अच्छे विस्तार गुणों वाले ग्राफ़ के अस्तित्व को दर्शाते हैं। वास्तव में, विस्तारकों के अस्तित्व को सबसे पहले पिंस्कर ने सिद्ध किया था<ref>{{Cite journal|last=Pinkser|first=M.|title=On the Complexity of a Concentrator|journal=[[SIAM Journal on Computing]]|year=1973|publisher=SIAM|citeseerx=10.1.1.393.1430}}</ref> जिसने दिखाया कि एक यादृच्छिक रूप से चुने गए के लिए {{mvar|n}} शीर्ष छोड़ दिया {{mvar|d}} नियमित [[द्विपक्षीय ग्राफ]], {{math|{{abs|''N''(''S'')}} ≥ (''d'' – 2){{abs|''S''}}}} कोने के सभी सबसेट के लिए {{math|{{abs|''S''}} ≤ ''c{{sub|d}}n''}} उच्च संभावना के साथ, जहाँ {{mvar|c{{sub|d}}}} एक स्थिरांक है जो {{mvar|d}} पर निर्भर करता है जो कि {{math|''O''(''d''{{sup|-4}})}}.है। अलोन और रोचमैन <ref>{{Cite journal|last1=Alon|first1=N.|last2=Roichman|first2=Y.|title=Random Cayley graphs and Expanders|url=https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240050203|journal=Random Structures and Algorithms|year=1994|volume=5|issue=2|pages=271–284|publisher=Wiley Online Library|doi=10.1002/rsa.3240050203}}</ref> ने दिखाया कि क्रम n के प्रत्येक समूह G के लिए और प्रत्येक {{math|1 > ''ε'' > 0}}, में कुछ {{math|''c''(''ε'') > 0}} होता है जैसे कि {{mvar|G}} साथ {{math|''c''(''ε'') log{{sub|2}} ''n''}} जनरेटर के साथ {{mvar|G}} पर केली ग्राफ एक ε विस्तारक है अर्थात  उच्च संभावना के साथ {{math|1 – ''ε'' }}, से कम दूसरा अभिलक्षणिक मान है।।
 == अनुप्रयोग और उपयोगी गुण ==
-विस्तारकों के लिए मूल प्रेरणा आर्थिक रूप से मजबूत नेटवर्क (फोन या कंप्यूटर) का निर्माण करना है: सीमाबद्ध डिग्री वाला एक विस्तारक सभी उपसमुच्चयों के लिए आकार (कोने की संख्या) के साथ रैखिक रूप से बढ़ने वाले किनारों की संख्या के साथ एक स्पर्शोन्मुख मजबूत ग्राफ है।
+विस्तारकों के लिए मूल प्रेरणा आर्थिक रूप से प्रबल नेटवर्क (फोन या कंप्यूटर) का निर्माण करना है: सीमाबद्ध डिग्री वाला एक विस्तारक सभी उपसमुच्चयों के लिए आकार (कोने की संख्या) के साथ रैखिक रूप से बढ़ने वाले किनारों की संख्या के साथ एक स्पर्शोन्मुख प्रबल ग्राफ है।
-एक्सपैंडर ग्राफ़ को [[कंप्यूटर विज्ञान]] में [[कलन विधि]], [[विस्तारक कोड]], एक्सट्रैक्टर (गणित), [[छद्म यादृच्छिक जनरेटर]], [[छँटाई नेटवर्क]] डिजाइन करने में व्यापक अनुप्रयोग मिले हैं।{{harvtxt|Ajtai|Komlós|Szemerédi|1983}}) और मजबूत कंप्यूटर नेटवर्क। कम्प्यूटेशनल जटिलता सिद्धांत में कई महत्वपूर्ण परिणामों के प्रमाण में भी उनका उपयोग किया गया है, जैसे एस[[एल (जटिलता)]] = एल (जटिलता) ({{harvtxt|Reingold|2008}}) और [[पीसीपी प्रमेय]] ({{harvtxt|Dinur|2007}}). [[क्रिप्टोग्राफी]] में, विस्तारक ग्राफ़ का उपयोग [[हैश फंकशन]] के निर्माण के लिए किया जाता है।
+एक्सपैंडर ग्राफ़ को [[कंप्यूटर विज्ञान]] में [[कलन विधि]], [[विस्तारक कोड]], एक्सट्रैक्टर (गणित), [[छद्म यादृच्छिक जनरेटर]], [[छँटाई नेटवर्क]] डिजाइन करने में व्यापक अनुप्रयोग मिले हैं।{{harvtxt|Ajtai|Komlós|Szemerédi|1983}}) और प्रबल कंप्यूटर नेटवर्क। कम्प्यूटेशनल जटिलता सिद्धांत में कई महत्वपूर्ण परिणामों के प्रमाण में भी उनका उपयोग किया गया है, जैसे एस[[एल (जटिलता)]] = एल (जटिलता) ({{harvtxt|Reingold|2008}}) और [[पीसीपी प्रमेय]] [[(दिनूर (2007)|दिनूर (2007)]] [[क्रिप्टोग्राफी]] में, विस्तारक ग्राफ़ का उपयोग [[हैश फंकशन|है फलन]] के निर्माण के लिए किया जाता है।
-एक [https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ 2006 एक्सपैंडर ग्राफ़ के सर्वेक्षण] में, हूरी, लिनियल, और विगडरसन ने निम्न के अध्ययन को विभाजित किया विस्तारक ग्राफ को चार श्रेणियों में विभाजित करता है: [[चरम ग्राफ सिद्धांत]], विशिष्ट व्यवहार, स्पष्ट निर्माण और एल्गोरिदम। चरम समस्याएं विस्तार पैरामीटरों की सीमा पर ध्यान केंद्रित करती हैं, जबकि विशिष्ट व्यवहार समस्याएं यह बताती हैं कि [[यादृच्छिक ग्राफ]] पर विस्तार पैरामीटर कैसे वितरित किए जाते हैं। स्पष्ट निर्माण ग्राफ़ के निर्माण पर ध्यान केंद्रित करते हैं जो कुछ मापदंडों का अनुकूलन करते हैं, और एल्गोरिथम प्रश्न मापदंडों के मूल्यांकन और अनुमान का अध्ययन करते हैं।
+एक [https://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ 2006 एक्सपैंडर ग्राफ़ के सर्वेक्षण] में, हूरी, लिनियल, और विगडरसन ने निम्न के अध्ययन को विभाजित किया विस्तारक ग्राफ को चार श्रेणियों में विभाजित करता है: [[चरम ग्राफ सिद्धांत]], विशिष्ट व्यवहार, स्पष्ट निर्माण और कलन विधि । चरम समस्याएं विस्तार पैरामीटरों की सीमा पर ध्यान केंद्रित करती हैं, जबकि विशिष्ट व्यवहार समस्याएं यह बताती हैं कि [[यादृच्छिक ग्राफ]] पर विस्तार पैरामीटर कैसे वितरित किए जाते हैं। स्पष्ट निर्माण ग्राफ़ के निर्माण पर ध्यान केंद्रित करते हैं जो कुछ मापदंडों का अनुकूलन करते हैं, और एल्गोरिथम प्रश्न मापदंडों के मूल्यांकन और अनुमान का अध्ययन करते हैं।
 === एक्सपैंडर मिक्सिंग लेम्मा ===
-{{Main article|Expander mixing lemma}}
+{{Main article|एक्सपैंडर मिक्सिंग लेम्मा}}
-लेम्मा को मिलाने वाला विस्तारक बताता है कि एक के लिए {{math|(''n'', ''d'', λ)}}-ग्राफ़, किसी भी दो उपसमूहों के लिए {{math|''S'', ''T'' ⊆ ''V''}}, बीच किनारों की संख्या {{mvar|S}} और {{mvar|T}} लगभग वह है जो आप यादृच्छिक रूप से अपेक्षा करेंगे {{mvar|d}}-नियमित ग्राफ। सन्निकटन बेहतर छोटा है {{math|λ}} है। एक यादृच्छिक में {{mvar|d}}-रेगुलर ग्राफ़, साथ ही एक एर्दोस-रेनी मॉडल में|एर्डोस-रेनी रैंडम ग्राफ़ एज प्रायिकता के साथ {{math|{{frac|''d''|''n''}}}}, हमें उम्मीद है {{math|{{frac|''d''|''n''}} • {{abs|''S''}} • {{abs|''T''}}}} किनारों के बीच {{mvar|S}} और {{mvar|T}}.
+लेम्मा को मिलाने वाला विस्तारक बताता है कि एक के लिए {{math|(''n'', ''d'', λ)}}-ग्राफ़, किसी भी दो उपसमूहों के लिए {{math|''S'', ''T'' ⊆ ''V''}}, बीच किनारों की संख्या {{mvar|S}} और {{mvar|T}} लगभग वह है जो आप यादृच्छिक रूप से अपेक्षा करेंगे {{mvar|d}}-नियमित ग्राफ। सन्निकटन अच्छा छोटा है {{math|λ}} है। एक यादृच्छिक में {{mvar|d}}-रेगुलर ग्राफ़, साथ ही एक एर्दोस-रेनी मॉडल में|एर्डोस-रेनी रैंडम ग्राफ़ किनारे प्रायिकता के साथ {{math|{{frac|''d''|''n''}}}}, हमें उम्मीद है {{math|{{frac|''d''|''n''}} • {{abs|''S''}} • {{abs|''T''}}}} किनारों के बीच {{mvar|S}} और {{mvar|T}}.
-अधिक औपचारिक रूप से, चलो {{math|''E''(''S'', ''T'')}} के बीच किनारों की संख्या को निरूपित करें {{mvar|S}} और {{mvar|T}}. यदि दो सेट अलग नहीं होते हैं, तो उनके चौराहे के किनारों को दो बार गिना जाता है, अर्थात
+अधिक औपचारिक रूप से, चलो {{math|''E''(''S'', ''T'')}} के बीच किनारों की संख्या को निरूपित करें {{mvar|S}} और {{mvar|T}}. यदि दो सेट भिन्न नहीं होते हैं, तो उनके चौराहे के किनारों को दो बार गिना जाता है, अर्थात
 : <math>E(S,T)=2|E(G[S\cap T])| + E(S\setminus T,T) + E(S,T\setminus S). </math>
@@ Line 135: / Line 134: @@
 :<math>\left|E(S, T) - \frac{d \cdot |S| \cdot |T|}{n}\right| \leq \lambda  \sqrt{|S| \cdot |T|}.</math>
-के अनेक गुण {{math|(''n'', ''d'', λ)}}-ग्राफ विस्तारक मिश्रण लेम्मा के परिणाम हैं, जिनमें निम्नलिखित शामिल हैं।<ref name="Hoory 2006"/>
+के अनेक गुण {{math|(''n'', ''d'', λ)}}-ग्राफ विस्तारक मिश्रण लेम्मा के परिणाम हैं, जिनमें निम्नलिखित सम्मलित हैं।<ref name="Hoory 2006"/>
 * एक ग्राफ का एक [[स्वतंत्र सेट (ग्राफ सिद्धांत)]] शीर्षों का एक उपसमुच्चय होता है जिसमें दो आसन्न कोने नहीं होते हैं। एक में {{math|(''n'', ''d'', λ)}}-ग्राफ, एक स्वतंत्र सेट का आकार अधिकतम होता है {{math|{{frac|λ''n''|''d''}}}}.
-* ग्राफ का [[ग्राफ रंगना]] {{mvar|G}}, {{math|χ(''G'')}}, आवश्यक रंगों की न्यूनतम संख्या है, ताकि आसन्न शीर्षों के अलग-अलग रंग हों। हॉफमैन ने दिखाया {{math|{{frac|''d''|λ}} ≤ χ(''G'')}},<ref>{{Cite journal|last1=Hoffman|first1=A. J.|last2=Howes|first2=Leonard|date=1970|title=On Eigenvalues and Colorings of Graphs, Ii|url=https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1749-6632.1970.tb56474.x|journal=Annals of the New York Academy of Sciences|language=en|volume=175|issue=1|pages=238–242|doi=10.1111/j.1749-6632.1970.tb56474.x|bibcode=1970NYASA.175..238H|s2cid=85243045|issn=1749-6632}}</ref> जबकि अलोन, क्रिवेलेविच और सुदाकोव ने दिखाया कि अगर {{math|''d'' < {{frac|2''n''|3}}}}, तब<ref>{{Cite journal|last1=Alon|first1=Noga|authorlink1=Noga Alon|last2=Krivelevich|first2=Michael|authorlink2=Michael Krivelevich|last3=Sudakov|first3=Benny|authorlink3=Benny Sudakov|date=1999-09-01|title=Coloring Graphs with Sparse Neighborhoods|journal=[[Journal of Combinatorial Theory]] | series=Series B |language=en|volume=77|issue=1|pages=73–82|doi=10.1006/jctb.1999.1910|doi-access=free|issn=0095-8956}}</ref><p><math>\chi(G) \leq O \left( \frac{d}{\log(1+d/\lambda)} \right).</math></p>
+* ग्राफ का [[ग्राफ रंगना]] {{mvar|G}}, {{math|χ(''G'')}}, आवश्यक रंगों की न्यूनतम संख्या है, जिससे कि आसन्न शीर्षों के भिन्न -भिन्न रंग हों। हॉफमैन ने दिखाया {{math|{{frac|''d''|λ}} ≤ χ(''G'')}},<ref>{{Cite journal|last1=Hoffman|first1=A. J.|last2=Howes|first2=Leonard|date=1970|title=On Eigenvalues and Colorings of Graphs, Ii|url=https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1749-6632.1970.tb56474.x|journal=Annals of the New York Academy of Sciences|language=en|volume=175|issue=1|pages=238–242|doi=10.1111/j.1749-6632.1970.tb56474.x|bibcode=1970NYASA.175..238H|s2cid=85243045|issn=1749-6632}}</ref> जबकि अलोन, क्रिवेलेविच और सुदाकोव ने दिखाया कि यदि {{math|''d'' < {{frac|2''n''|3}}}}, तब<ref>{{Cite journal|last1=Alon|first1=Noga|authorlink1=Noga Alon|last2=Krivelevich|first2=Michael|authorlink2=Michael Krivelevich|last3=Sudakov|first3=Benny|authorlink3=Benny Sudakov|date=1999-09-01|title=Coloring Graphs with Sparse Neighborhoods|journal=[[Journal of Combinatorial Theory]] | series=Series B |language=en|volume=77|issue=1|pages=73–82|doi=10.1006/jctb.1999.1910|doi-access=free|issn=0095-8956}}</ref><p><math>\chi(G) \leq O \left( \frac{d}{\log(1+d/\lambda)} \right).</math></p>
 * किसी ग्राफ़ की दूरी (ग्राफ़ सिद्धांत) दो शीर्षों के बीच की अधिकतम दूरी होती है, जहाँ दो शीर्षों के बीच की दूरी को उनके बीच का सबसे छोटा पथ परिभाषित किया जाता है। चुंग ने दिखाया कि एक का व्यास {{math|(''n'', ''d'', λ)}}-ग्राफ अधिकतम है<ref>{{Cite journal|last=Chung|first=F. R. K.|date=1989|title=Diameters and eigenvalues|url=https://www.ams.org/jams/1989-02-02/S0894-0347-1989-0965008-X/|journal=Journal of the American Mathematical Society|language=en|volume=2|issue=2|pages=187–196|doi=10.1090/S0894-0347-1989-0965008-X|issn=0894-0347|doi-access=free}}</ref><p><math>\left\lceil \log \frac{n}{ \log(d/\lambda)} \right\rceil.</math></p>
 === एक्सपैंडर वॉक सैंपलिंग ===
-{{Main article|Expander walk sampling}}
+{{Main article|एक्सपैंडर वॉक सैंपलिंग}}
-[[Chernoff बाध्य]] बताता है कि, रेंज में एक यादृच्छिक चर से कई स्वतंत्र नमूनों का नमूना लेते समय {{math|[−1, 1]}}, उच्च संभावना के साथ हमारे नमूनों का औसत यादृच्छिक चर की अपेक्षा के करीब है। एक्सपैंडर वॉक सैंपलिंग लेम्मा, के कारण {{harvtxt|Ajtai|Komlós|Szemerédi|1987}} और {{harvtxt|Gillman|1998}}, बताता है कि विस्तारक ग्राफ पर चलने से नमूना लेने पर भी यह सच होता है। यह विशेष रूप से [[derandomization]] के सिद्धांत में उपयोगी है, क्योंकि एक्सपैंडर वॉक के अनुसार सैंपलिंग स्वतंत्र रूप से सैंपलिंग की तुलना में बहुत कम रैंडम बिट्स का उपयोग करता है।
+[[Chernoff बाध्य|चेरनॉफ़बाध्य]] बताता है कि, रेंज में एक यादृच्छिक चर से कई स्वतंत्र नमूनों का नमूना लेते समय {{math|[−1, 1]}}, उच्च संभावना के साथ हमारे नमूनों का औसत यादृच्छिक चर की अपेक्षा के करीब है। एक्सपैंडर वॉक सैंपलिंग लेम्मा, के कारण [[अजताई, कोमलोस और ज़ेमेरेडी (1987)]] और गिलमैन (1998), बताता है कि विस्तारक ग्राफ पर चलने से नमूना लेने पर भी यह सच होता है। यह विशेष रूप से [[derandomization|यादृच्छिकीकरण]] के सिद्धांत में उपयोगी है, क्योंकि एक्सपैंडर वॉक के अनुसार सैंपलिंग स्वतंत्र रूप से सैंपलिंग की तुलना में बहुत कम रैंडम बिट्स का उपयोग करता है।
 === एकेएस सॉर्टिंग नेटवर्क और अनुमानित पड़ाव ===
 {{Main article|Sorting network}}
-सॉर्टिंग नेटवर्क इनपुट्स का एक सेट लेते हैं और इनपुट्स को सॉर्ट करने के लिए समानांतर चरणों की एक श्रृंखला करते हैं। एक समानांतर कदम में किसी भी संख्या में असंबद्ध तुलना और संभावित रूप से जोड़े गए इनपुट की अदला-बदली करना शामिल है। एक नेटवर्क की गहराई उसके द्वारा उठाए जाने वाले समानांतर कदमों की संख्या से दी जाती है। विस्तारक रेखांकन एकेएस छँटाई नेटवर्क में एक महत्वपूर्ण भूमिका निभाते हैं, जो गहराई तक पहुँचता है {{math|''O''(log ''n'')}}. हालांकि यह एक छँटाई नेटवर्क के लिए असम्बद्ध रूप से सबसे अच्छी ज्ञात गहराई है, विस्तारकों पर निर्भरता व्यावहारिक उपयोग के लिए स्थिर सीमा को बहुत बड़ा बना देती है।
+सॉर्टिंग नेटवर्क इनपुट्स का एक सेट लेते हैं और इनपुट्स को सॉर्ट करने के लिए समानांतर चरणों की एक श्रृंखला करते हैं। एक समानांतर कदम में किसी भी संख्या में असंबद्ध तुलना और संभावित रूप से जोड़े गए इनपुट की अदला-बदली करना  सम्मिलित  है। एक नेटवर्क की गहराई उसके द्वारा उठाए जाने वाले समानांतर कदमों की संख्या से दी जाती है। विस्तारक ग्राफ एकेएस सॉर्टिंग नेटवर्क में एक महत्वपूर्ण भूमिका निभाते हैं जो गहराई {{math|''O''(log ''n'')}}.प्राप्त करता है। चूंकि, यह एक छँटाई नेटवर्क के लिए सबसे अच्छी प्रकार  से ज्ञात गहराई है, लेकिन विस्तारकों पर निर्भरता व्यावहारिक उपयोग के लिए स्थिर सीमा को बहुत बड़ा बना देती है।
-एकेएस सॉर्टिंग नेटवर्क के भीतर, विस्तृत गहराई का निर्माण करने के लिए विस्तारक ग्राफ का उपयोग किया जाता है {{mvar|ε}}-आधा. एक {{mvar|ε}}-halver इनपुट के रूप में लंबाई लेता है {{mvar|n}} का क्रमपरिवर्तन {{math|(1, …, ''n'')}} और इनपुट्स को दो असम्बद्ध सेटों में आधा कर देता है {{mvar|A}} और {{mvar|B}} जैसे कि प्रत्येक पूर्णांक के लिए {{math|''k'' ≤ {{frac|''n''|2}}}} अधिक से अधिक {{mvar|εk}} की {{mvar|k}} सबसे छोटे इनपुट में हैं {{mvar|B}} और अधिक से अधिक {{mvar|εk}} की {{mvar|k}} सबसे बड़े इनपुट हैं {{mvar|A}}. सेट {{mvar|A}} और {{mvar|B}} एक हैं {{mvar|ε}}आधा करना।
+एकेएस सॉर्टिंग नेटवर्क के भीतर, विस्तारक रेखांकन का उपयोग बंधी हुई गहराई ε-आधा करने के लिए किया जाता है। एक ε-हॉल्वर इनपुट के रूप में (1, …, n) की लंबाई n क्रमचय लेता है और इनपुट को दो अलग-अलग सेटों A और B में आधा कर देता है जैसे कि प्रत्येक पूर्णांक k ≤ n⁄2 के लिए k के सबसे छोटे इनपुट में सबसे अधिक εk होता है बी और सबसे अधिक εk के सबसे बड़े इनपुट {{mvar|A}}.में हैं। सेट {{mvar|A}} और {{mvar|B}} एक हैं {{mvar|ε}}आधा करते हैं।
-अगले {{harvtxt|Ajtai|Komlós|Szemerédi|1983}}, गहराई {{mvar|d}} {{mvar|ε}}-हॉल्वर का निर्माण निम्नानुसार किया जा सकता है। एक लें {{mvar|n}} शिखर, डिग्री {{mvar|d}} भागों के साथ द्विदलीय विस्तारक {{mvar|X}} और {{mvar|Y}} समान आकार के ऐसे कि अधिकतम आकार के शीर्षों का प्रत्येक उपसमुच्चय {{mvar|εn}} कम से कम है {{math|{{sfrac|1 – ''ε''|''ε''}}}} पड़ोसियों।
+अजताई, [[कोमलोस और ज़ेमेरेडी 1983]] के बाद एक गहराई {{mvar|d}} {{mvar|ε}}- हॉल्वर का निर्माण निम्नानुसार किया जाता है। समान आकार के भागों X और Y के साथ एक {{mvar|n}} शीर्ष, डिग्री {{mvar|d}} द्विदलीय विस्तारक लें, जैसे कि अधिकतम εn आकार के शीर्षों के प्रत्येक उपसमुच्चय में कम से कम {{math|{{sfrac|1 – ''ε''|''ε''}}}} निकटतम रूप में होता है।
-ग्राफ़ के कोने को उन रजिस्टरों के रूप में माना जा सकता है जिनमें इनपुट होते हैं और किनारों को तारों के रूप में माना जा सकता है जो दो रजिस्टरों के इनपुट की तुलना करते हैं। प्रारंभ में, मनमाने ढंग से आधा इनपुट अंदर रखें {{mvar|X}} और आधे इनपुट में {{mvar|Y}} और किनारों को विघटित करें {{mvar|d}} सही मिलान। के साथ समाप्त करने का लक्ष्य है {{mvar|X}} मोटे तौर पर इनपुट के छोटे आधे हिस्से से युक्त और {{mvar|Y}} मोटे तौर पर इनपुट का बड़ा आधा हिस्सा होता है। इसे प्राप्त करने के लिए, इस मिलान के किनारों द्वारा जोड़े गए रजिस्टरों की तुलना करके प्रत्येक मिलान को क्रमिक रूप से संसाधित करें और किसी भी इनपुट को ठीक करें जो क्रम से बाहर हैं। विशेष रूप से, मिलान के प्रत्येक किनारे के लिए, यदि बड़ा इनपुट रजिस्टर में है {{mvar|X}} और छोटा इनपुट रजिस्टर में है {{mvar|Y}}, फिर दो इनपुटों की अदला-बदली करें ताकि छोटा इनपुट अंदर आ जाए {{mvar|X}} और बड़ा अंदर है {{mvar|Y}}. यह स्पष्ट है कि इस प्रक्रिया के होते हैं {{mvar|d}} समानांतर कदम।
+ग्राफ़ के कोने को उन रजिस्टरों के रूप में माना जा सकता है जिनमें इनपुट होते हैं और किनारों को तारों के रूप में माना जा सकता है जो दो रजिस्टरों के इनपुट की तुलना करते हैं। प्रारंभ में, मनमाने ढंग से आधे इनपुट को X में और आधे इनपुट को Y में रखें और किनारों को d पूर्ण मिलान में विघटित करें। लक्ष्य X के साथ समाप्त होना है जिसमें मोटे तौर पर इनपुट का छोटा आधा भाग  होता है और Y में इनपुट का बड़ा आधा भाग  होता है। इसे प्राप्त करने के लिए इस मिलान के किनारों द्वारा जोड़े गए रजिस्टरों की तुलना करके प्रत्येक मिलान को क्रमिक रूप से संसाधित करें और किसी भी इनपुट को ठीक करें जो क्रम से बाहर हैं। विशेष रूप से, मिलान के प्रत्येक किनारे के लिए, यदि बड़ा इनपुट एक्स में रजिस्टर में है और छोटा इनपुट वाई में रजिस्टर में है तो दो इनपुट स्वैप करें ताकि छोटा एक्स में हो और बड़ा वाई में हो। यह स्पष्ट है कि इस प्रक्रिया में d समानांतर चरण के रूप में होते हैं
-आख़िरकार {{mvar|d}} चक्कर लगाओ, लो {{mvar|A}} रजिस्टरों में इनपुट का सेट होना {{mvar|X}} और {{mvar|B}} रजिस्टरों में इनपुट का सेट होना {{mvar|Y}} एक प्राप्त करने के लिए {{mvar|ε}}आधा करना। इसे देखने के लिए ध्यान दें कि यदि कोई register {{mvar|u}} में {{mvar|X}} और {{mvar|v}} में {{mvar|Y}} किनारे से जुड़े हुए हैं {{mvar|uv}} फिर इस किनारे से मिलान करने के बाद संसाधित किया जाता है, इनपुट में {{mvar|u}} से कम है {{mvar|v}}. इसके अलावा, यह संपत्ति बाकी प्रक्रिया के दौरान सही रहती है। अब, कुछ के लिए मान लीजिए {{math|''k'' ≤ {{frac|''n''|2}}}} इससे ज्यादा {{mvar|εk}} इनपुट्स का {{math|(1, …, ''k'')}} में हैं {{mvar|B}}. फिर ग्राफ के विस्तार गुणों द्वारा, इन इनपुटों के रजिस्टरों में {{mvar|Y}} कम से जुड़े हुए हैं {{math|{{sfrac|1 – ''ε''|''ε''}}''k''}} में दर्ज करता है {{mvar|X}}. कुल मिलाकर, यह से अधिक बनता है {{mvar|k}} रजिस्टर इसलिए कुछ रजिस्टर होना चाहिए {{mvar|A}} में {{mvar|X}} किसी रजिस्टर से जुड़ा है {{mvar|B}} में {{mvar|Y}} जैसे कि अंतिम इनपुट {{mvar|A}} इसमें नहीं है {{math|(1, …, ''k'')}}, जबकि का अंतिम इनपुट {{mvar|B}} है। हालांकि यह पिछली संपत्ति का उल्लंघन करता है, और इस प्रकार आउटपुट सेट करता है  {{mvar|A}} और {{mvar|B}} एक होना चाहिए {{mvar|ε}}आधा करना।
+सभी {{mvar|d}} राउंड के बाद {{mvar|A}} को {{mvar|X}} और {{mvar|B}} में रजिस्टरों में इनपुट का सेट होने के लिए {{mvar|Y}} में रजिस्टरों में इनपुट का सेट होने के लिए {{mvar|ε}} आधा करते है। इसे देखने के लिए, ध्यान दें कि यदि X में कोई रजिस्टर u और Y में v एक किनारे uv से जुड़ा है तो इस किनारे के साथ मिलान करने के बाद संसाधित किया जाता है, u में इनपुट v से कम होता है। इसके अतिरिक्त, यह गुण बाकी प्रक्रिया के दौरान सही रहती है। अब मान लीजिए कि कुछ {{math|''k'' ≤ {{frac|''n''|2}}}} के लिए इनपुट {{math|(1, …, ''k'')}} के εk से अधिक B में हैं। फिर ग्राफ के विस्तार गुणों द्वारा, Y में इन इनपुट के रजिस्टर कम से कम जुड़े हुए हैं {{math|{{sfrac|1 – ''ε''|''ε''}}''k''}} में अंकित करता है, {{mvar|X}}. कुल मिलाकर, यह k से अधिक रजिस्टर का गठन करता है, इसलिए X में कुछ रजिस्टर A होना चाहिए, जो Y में कुछ रजिस्टर B से जुड़ा हो, जैसे कि A का अंतिम इनपुट (1, ..., k) में नहीं है, जबकि अंतिम बी का इनपुट है।चूँकि  यह पिछली संपत्ति का उल्लंघन करता है और इस प्रकार आउटपुट सेट ए और बी को ε-आधा होना चाहिए।
 == यह भी देखें ==
@@ Line 161: / Line 160: @@
 * ज़िग-ज़ैग उत्पाद
 * [[सुपरस्ट्रॉन्ग सन्निकटन]]
-*स्पेक्ट्रल ग्राफ सिद्धांत
+*वर्णक्रमीय ग्राफ सिद्धांत
 ==टिप्पणियाँ==
@@ Line 260: / Line 259: @@
 * [http://ttic.uchicago.edu/~prahladh/teaching/spring05/index.html Lecture notes from a course on expanders (by Prahladh Harsha)]
 *[https://web.archive.org/web/20070523090323/http://www.yann-ollivier.org/specgraph/specgraph.html Definition and application of spectral gap]
-[[Category: ग्राफ परिवार]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 13/02/2023]]
+[[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:ग्राफ परिवार]]

Anonymous

Search

विस्तारक ग्राफ: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:42, 21 February 2023

Contents

परिभाषाएँ

किनारे का विस्तार

वर्टेक्स विस्तार

वर्णक्रमीय विस्तार

विभिन्न विस्तार गुणों के बीच संबंध

चीजर असमानताएं

निर्माण

मार्गुलिस-गैबर-गैलिल

रामनुजन ग्राफ्स

ज़िग-ज़ैग उत्पाद

यादृच्छिक निर्माण

अनुप्रयोग और उपयोगी गुण

एक्सपैंडर मिक्सिंग लेम्मा

एक्सपैंडर वॉक सैंपलिंग

एकेएस सॉर्टिंग नेटवर्क और अनुमानित पड़ाव

यह भी देखें

टिप्पणियाँ

संदर्भ

पाठ्यपुस्तकें और सर्वेक्षण

शोध लेख

हाल के अनुप्रयोग

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

विस्तारक ग्राफ: Difference between revisions

Latest revision as of 10:42, 21 February 2023

परिभाषाएँ

किनारे का विस्तार

वर्टेक्स विस्तार

वर्णक्रमीय विस्तार

विभिन्न विस्तार गुणों के बीच संबंध

चीजर असमानताएं

निर्माण

मार्गुलिस-गैबर-गैलिल

रामनुजन ग्राफ्स

ज़िग-ज़ैग उत्पाद

यादृच्छिक निर्माण

अनुप्रयोग और उपयोगी गुण

एक्सपैंडर मिक्सिंग लेम्मा

एक्सपैंडर वॉक सैंपलिंग

एकेएस सॉर्टिंग नेटवर्क और अनुमानित पड़ाव

यह भी देखें

टिप्पणियाँ

संदर्भ

पाठ्यपुस्तकें और सर्वेक्षण

शोध लेख

हाल के अनुप्रयोग

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories