विस्तारक ग्राफ

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

परिभाषाएँ

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

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

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

किनारे का विस्तार (आइसोपेरिमेट्रिक संख्या या चीजर स्थिरांक (ग्राफ सिद्धांत)) 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\},$

जिसे इस रूप में भी लिखा जा सकता है ∂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 ⊆ V(G).

समीकरण में, न्यूनतम सभी गैर-खाली सेटों पर है S अधिक से अधिक n⁄2 शिखर और ∂S की किनारा सीमा है S, अर्थात , ठीक एक समापन बिंदु के साथ किनारों का सेट S. सहज रूप से,

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

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

ध्यान दें कि में min |∂S|, ऑप्टिमाइज़ेशन या तो अधिक समान रूप से किया जा सकता है 0 ≤ |S| ≤ 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}}|\}}}.$

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

शीर्ष isoperimetric संख्या h_out(G) एक ग्राफ का (शीर्ष विस्तार या आवर्धन भी)। G परिभाषित किया जाता है

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

कहाँ ∂_out(S) की बाहरी सीमा है S, अर्थात , शीर्षों का सेट V(G) \ S कम से कम एक निकटतम के साथ S. इस परिभाषा के एक प्रकार में (अद्वितीय निकटतम विस्तार कहा जाता है) ∂_out(S) में वर्टिकल के सेट द्वारा प्रतिस्थापित किया जाता है V ठीक एक निकटतम के साथ S. शीर्ष isoperimetric संख्या 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.

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

कब G नियमित ग्राफ है|d-नियमित, विस्तार की एक रेखीय बीजगणितीय परिभाषा Eigenvalue#Eigenvalues ​​of the matrices of the adjacency matrix के आधार पर संभव है A = A(G) का G, कहाँ A_ij शीर्षों के बीच किनारों की संख्या है i और j. क्योंकि A सममित मैट्रिक्स है, वर्णक्रमीय प्रमेय का अर्थ है A है n वास्तविक मूल्यवान eigenvalues λ₁ ≥ λ₂ ≥ … ≥ λ_n. यह ज्ञात है कि ये सभी eigenvalues ​​​​में हैं [−d, d] और अधिक विशेष रूप से, यह ज्ञात है कि λ_n = −d यदि और केवल यदि G द्विपक्षीय है।

अधिक औपचारिक रूप से, हम एक का उल्लेख करते हैं n-वर्टेक्स, d-नियमित ग्राफ के साथ

$\max _{i\neq 1}|\lambda _{i}|\leq \lambda$ एक के रूप में (n, d, λ)-ग्राफ। एक द्वारा दी गई सीमा (n, d, λ)-ग्राफ ऑन λ_i के लिए i ≠ 1 विस्तारक मिश्रण लेम्मा सहित कई संदर्भों में उपयोगी है।

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

$\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}$.

इन परिभाषाओं के सामान्यीकृत संस्करण भी व्यापक रूप से उपयोग किए जाते हैं और कुछ परिणामों को बताते हुए अधिक सुविधाजनक होते हैं। यहाँ एक मैट्रिक्स पर विचार करता है 1/dA, जो ग्राफ का मार्कोव संक्रमण मैट्रिक्स है G. इसके eigenvalues ​​-1 और 1 के बीच हैं। आवश्यक नहीं कि नियमित ग्राफ़ के लिए, ग्राफ़ के स्पेक्ट्रम को लाप्लासियन मैट्रिक्स के eigenvalues ​​​​का उपयोग करके इसी तरह परिभाषित किया जा सकता है। निर्देशित रेखांकन के लिए, आसन्न मैट्रिक्स के विलक्षण मूल्यों पर विचार किया जाता है A, जो सममित मैट्रिक्स के eigenvalues ​​​​की जड़ों के बराबर हैं A^TA.

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

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

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

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

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

कब G है d-नियमित, जिसका अर्थ है कि प्रत्येक शीर्ष डिग्री का है d, isoperimetric स्थिरांक के बीच एक संबंध है h(G) और अंतराल d − λ₂ के आसन्न ऑपरेटर के स्पेक्ट्रम में G. मानक वर्णक्रमीय ग्राफ सिद्धांत द्वारा, a के आसन्न संचालिका का तुच्छ eigenvalue d-नियमित ग्राफ है λ₁ = d और पहला गैर-तुच्छ eigenvalue है λ₂. यदि G जुड़ा हुआ है, तो λ₂ < d. डोडिज़ुक के कारण एक असमानता और स्वतंत्र रूप से सावधान अलोन और विटाली मिलमैन बताता है

${\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) और d – λ = 2-2cos(2$\pi$/n) ≈ (2$\pi$/n)^2= Θ(1/n²).में एक बेहतर बाउंड दिया गया है जैसा

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

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

वर्टेक्स आइसोपेरिमेट्रिक नंबर और स्पेक्ट्रल गैप के बीच समान कनेक्शन का भी अध्ययन किया गया है:

$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²⁄d, h_out, और h_in² सभी वर्णक्रमीय अंतर से ऊपर बंधे हैं O(d – λ₂).

निर्माण

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

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

केली ग्राफ़ पर आधारित सार बीजगणित निर्माण विस्तारक ग्राफ़ के विभिन्न रूपों के लिए जाने जाते हैं। निम्नलिखित निर्माण मार्गुलिस के कारण है और गैबर और गैलिल द्वारा इसका विश्लेषण किया गया है। प्रत्येक प्राकृतिक संख्या के लिए 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 का दूसरा सबसे बड़ा eigenvalue है $\lambda (G)\leq 5{\sqrt {2}}$</ब्लॉककोट>

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

Main article: Ramanujan graph

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

अलेक्जेंडर लुबोत्ज़की, फिलिप्स, और पीटर इतिहास (1988), मार्गुलिस (1988), और मॉर्गनस्टर्न (1994) दिखाते हैं कि रामानुजन ग्राफ को स्पष्ट रूप से कैसे बनाया जा सकता है। 1985 में, एलोन ने सबसे अधिक अनुमान लगाया d-नियमित रेखांकन पर n कोने, पर्याप्त रूप से बड़े के लिए n, लगभग रामानुजन हैं। अर्थात के लिए φ > 0, वे संतुष्ट हैं

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

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

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

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

Main article: Zig-zag product

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

1. यदि λ₁ < 1 और λ₂ < 1, तब φ(λ₁, λ₂) < 1;
2. φ(λ₁, λ₂) ≤ λ₁ + λ₂.

विशेष रूप से,:$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 यह आपकी जानकारी के लिए है kइसका किनारा v. दो शिखर, (v, k) और (w,l) जुड़े हुए हैं यदि से प्राप्त करना संभव है (v, k) को (w, l) चालों के निम्नलिखित क्रम के माध्यम से।

1. ज़िग - से हटो (v, k) को (v, k' ), के किनारे का उपयोग करना H.
2. किनारे का उपयोग करके बादलों में कूदें k' में G को पाने के लिए (w, l' ).
3. ज़ग - से हटो (w, l' ) को (w, l) के किनारे का उपयोग करना H.

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

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

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

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

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

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

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

Main article: Expander mixing lemma

लेम्मा को मिलाने वाला विस्तारक बताता है कि एक के लिए (n, d, λ)-ग्राफ़, किसी भी दो उपसमूहों के लिए S, T ⊆ 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, λ)-ग्राफ विस्तारक मिश्रण लेम्मा के परिणाम हैं, जिनमें निम्नलिखित सम्मलित हैं।

• एक ग्राफ का एक स्वतंत्र सेट (ग्राफ सिद्धांत) शीर्षों का एक उपसमुच्चय होता है जिसमें दो आसन्न कोने नहीं होते हैं। एक में (n, d, λ)-ग्राफ, एक स्वतंत्र सेट का आकार अधिकतम होता है λn⁄d.
• ग्राफ का ग्राफ रंगना G, χ(G), आवश्यक रंगों की न्यूनतम संख्या है, जिससे कि आसन्न शीर्षों के भिन्न -भिन्न रंग हों। हॉफमैन ने दिखाया d⁄λ ≤ χ(G), जबकि अलोन, क्रिवेलेविच और सुदाकोव ने दिखाया कि यदि d < 2n⁄3, तब

  $\chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).$

• किसी ग्राफ़ की दूरी (ग्राफ़ सिद्धांत) दो शीर्षों के बीच की अधिकतम दूरी होती है, जहाँ दो शीर्षों के बीच की दूरी को उनके बीच का सबसे छोटा पथ परिभाषित किया जाता है। चुंग ने दिखाया कि एक का व्यास (n, d, λ)-ग्राफ अधिकतम है

  $\left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .$

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

Main article: Expander walk sampling

Chernoff बाध्य बताता है कि, रेंज में एक यादृच्छिक चर से कई स्वतंत्र नमूनों का नमूना लेते समय [−1, 1], उच्च संभावना के साथ हमारे नमूनों का औसत यादृच्छिक चर की अपेक्षा के करीब है। एक्सपैंडर वॉक सैंपलिंग लेम्मा, के कारण Ajtai, Komlós & Szemerédi (1987) और Gillman (1998), बताता है कि विस्तारक ग्राफ पर चलने से नमूना लेने पर भी यह सच होता है। यह विशेष रूप से derandomization के सिद्धांत में उपयोगी है, क्योंकि एक्सपैंडर वॉक के अनुसार सैंपलिंग स्वतंत्र रूप से सैंपलिंग की तुलना में बहुत कम रैंडम बिट्स का उपयोग करता है।

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

Main article: Sorting network

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

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

अगले Ajtai, Komlós & Szemerédi (1983), गहराई d ε-हॉल्वर का निर्माण निम्नानुसार किया जा सकता है। एक लें n शिखर, डिग्री d भागों के साथ द्विदलीय विस्तारक X और Y समान आकार के ऐसे कि अधिकतम आकार के शीर्षों का प्रत्येक उपसमुच्चय εn कम से कम है 1 – ε/ε पड़ोसियों।

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

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

यह भी देखें

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

संदर्भ

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

• 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)

बाहरी संबंध

• Brief introduction in Notices of the American Mathematical Society
• Introductory paper by Michael Nielsen
• Lecture notes from a course on expanders (by Nati Linial and Avi Wigderson)
• Lecture notes from a course on expanders (by Prahladh Harsha)
• Definition and application of spectral gap