ग्राफॉन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 181: Line 181:
यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है <math>G</math> और <math>H</math> समान रेखांकन हैं।
यदि ये संख्याएँ उपसमुच्चयों की प्रत्येक जोड़ी के लिए समान हैं (वर्टेक्स की कुल संख्या के सापेक्ष), तो यह सुझाव देता है <math>G</math> और <math>H</math> समान रेखांकन हैं।


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


  d_\square(G, H) = \frac 1{n^2} \max_{X, Y\subseteq V}\left|e_G(X,Y) - e_H(X,Y)\right|.</math>
  d_\square(G, H) = \frac 1{n^2} \max_{X, Y\subseteq V}\left|e_G(X,Y) - e_H(X,Y)\right|.</math>
दूसरे शब्दों में, लेबल की गई कट दूरी बीच के शीर्ष घनत्व की अधिकतम विसंगति को कूटबद्ध करती है <math>G</math> और <math>H</math>.
दूसरे शब्दों में, लेबल की गई कट दूरी बीच के शीर्ष घनत्व की अधिकतम विसंगति को <math>G</math> और <math>H</math> कूटबद्ध करती है। हम शीर्ष के घनत्व को व्यक्त करके इस अवधारणा को ग्राफॉन के लिए सामान्यीकृत कर सकते हैं <math> \tfrac 1{n^2} e_G(X, Y) </math> संबंधित ग्राफॉन के संदर्भ में <math>W_G</math>, समानता दे रहा है:
हम शीर्ष के घनत्व को व्यक्त करके इस अवधारणा को ग्राफॉन के लिए सामान्यीकृत कर सकते हैं <math> \tfrac 1{n^2} e_G(X, Y) </math> संबंधित ग्राफॉन के संदर्भ में <math>W_G</math>, समानता दे रहा है


<math display=block> d_\square(G, H) = \max_{X, Y\subseteq V} \left| \int_{I_X} \int_{I_Y} W_G(x, y) - W_H(x, y) \; \mathrm{d}x \, \mathrm{d}y \right| </math>
<math display=block> d_\square(G, H) = \max_{X, Y\subseteq V} \left| \int_{I_X} \int_{I_Y} W_G(x, y) - W_H(x, y) \; \mathrm{d}x \, \mathrm{d}y \right| </math>
कहाँ <math>I_X, I_Y \subseteq [0, 1]</math> में वर्टिकल के अनुरूप अंतराल के संघ हैं <math>X</math> और <math>Y</math>. ध्यान दें कि इस परिभाषा का तब भी उपयोग किया जा सकता है जब तुलना किए जा रहे ग्राफ़ एक शीर्ष सेट को साझा नहीं करते हैं।
जहाँ <math>I_X, I_Y \subseteq [0, 1]</math> में <math>X</math> और <math>Y</math> वर्टेक्स के अनुरूप अंतराल के संघ हैं। ध्यान दें कि इस परिभाषा का तब भी उपयोग किया जा सकता है जब तुलना किए जा रहे ग्राफ़ एक शीर्ष सेट को साझा नहीं करते हैं।
यह निम्नलिखित अधिक सामान्य परिभाषा को प्रेरित करता है।
यह निम्नलिखित अधिक सामान्य परिभाषा को प्रेरित करता है।


परिभाषा 1. किसी भी सममित, मापने योग्य कार्य के लिए <math>f : [0,1]^2 \to \mathbb{R}</math>, के कट मानदंड को परिभाषित करें <math>f</math> मात्रा होना
परिभाषा 1. किसी भी सममित, मापने योग्य कार्य के लिए <math>f : [0,1]^2 \to \mathbb{R}</math>, के कट मानदंड को <math>f</math> मात्रा परिभाषित करें:
<math display=block> \lVert f \rVert_\square = \sup_{S, T\subseteq [0,1]} \left| \int_{S} \int_{T} f(x,y) \; \mathrm{d}x \, \mathrm{d}y \right|</math>
<math display=block> \lVert f \rVert_\square = \sup_{S, T\subseteq [0,1]} \left| \int_{S} \int_{T} f(x,y) \; \mathrm{d}x \, \mathrm{d}y \right|</math>
सभी औसत दर्जे का सबसेट ले लिया <math>S, T</math> इकाई अंतराल का।{{r|Lovasz:2013}}
सभी औसत दर्जे का सबसेट ले लिया <math>S, T</math> इकाई अंतराल का।{{r|Lovasz:2013}}
Line 198: Line 197:
यह लेबल कट दूरी की हमारी पहले की धारणा को दर्शाता है, क्योंकि हमारे पास समानता है <math>\lVert W_G - W_H \rVert_\square = d_\square(G, H)</math>.
यह लेबल कट दूरी की हमारी पहले की धारणा को दर्शाता है, क्योंकि हमारे पास समानता है <math>\lVert W_G - W_H \rVert_\square = d_\square(G, H)</math>.


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


परिभाषा 2. ग्राफॉन के किसी भी जोड़े के लिए <math>U</math> और <math>W</math>, उनकी कट दूरी को परिभाषित करें
परिभाषा 2. ग्राफॉन के किसी भी जोड़े के लिए <math>U</math> और <math>W</math>, उनकी कट दूरी को परिभाषित करें
<math display=block> \delta_\square(U, W) = \inf_{\varphi} \lVert U - W^\varphi \rVert_\square</math>
<math display=block> \delta_\square(U, W) = \inf_{\varphi} \lVert U - W^\varphi \rVert_\square</math>
कहाँ <math>W^\varphi(x,y) = W(\varphi(x), \varphi(y))</math> की रचना है <math>W</math> नक्शे के साथ <math>\varphi</math>, और इन्फिमम को सभी अपरिवर्तनीय उपाय पर ले लिया जाता है माप-संरक्षण आक्षेपों को इकाई अंतराल से स्वयं में।{{r|whatis}}
जहाँ <math>W^\varphi(x,y) = W(\varphi(x), \varphi(y))</math> की रचना है <math>W</math> नक्शे के साथ <math>\varphi</math>, और न्यूनतम को सभी अपरिवर्तनीय उपाय पर ले लिया जाता है माप-संरक्षण आक्षेपों को इकाई अंतराल से स्वयं में।{{r|whatis}}
</ब्लॉककोट>
</ब्लॉककोट>


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


अब हम कहते हैं कि रेखांकन का एक क्रम <math>(G_n)</math> कट दूरी के तहत अभिसारी है अगर यह कट दूरी के तहत एक कॉची अनुक्रम है <math>\delta_\square</math>. हालांकि यह परिभाषा का सीधा परिणाम नहीं है, अगर ग्राफ का ऐसा क्रम कॉशी है, तो यह हमेशा किसी ग्राफॉन में परिवर्तित हो जाता है <math>W</math>.
अब हम कहते हैं कि रेखांकन का एक क्रम <math>(G_n)</math> कट दूरी के तहत अभिसारी है अगर यह कट दूरी के तहत एक कॉची अनुक्रम है <math>\delta_\square</math>. हालांकि यह परिभाषा का सीधा परिणाम नहीं है, अगर ग्राफ का ऐसा क्रम कॉची है, तो <math>W</math> हमेशा किसी ग्राफॉन में परिवर्तित हो जाता है।


[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
Line 220: Line 219:
==== अभिसरण की समानता ====
==== अभिसरण की समानता ====


जैसा कि यह निकला, रेखांकन के किसी भी क्रम के लिए <math>(G_n)</math>, बायाँ-अभिसरण कट दूरी के तहत अभिसरण के बराबर है, और इसके अलावा, सीमा रेखाचित्र <math>W</math> एक ही है। हम समान परिभाषाओं का उपयोग करके स्वयं ग्राफोन के अभिसरण पर भी विचार कर सकते हैं, और समान समानता सत्य है। वास्तव में, अभिसरण की दोनों धारणाएं काउंटिंग लेम्मा के माध्यम से अधिक मजबूती से संबंधित हैं।{{r|Lovasz:2013}}
जैसे ही यह पता चला कि रेखांकन के किसी भी क्रम के लिए <math>(G_n)</math>, बायाँ-अभिसरण कट दूरी के तहत अभिसरण के बराबर है, और इसके अलावा, सीमा रेखाचित्र <math>W</math> एक ही है। हम समान परिभाषाओं का उपयोग करके स्वयं ग्राफोन के अभिसरण पर भी विचार कर सकते हैं, और समान समानता सत्य है। वास्तव में, अभिसरण की दोनों धारणाएं काउंटिंग लेम्मा के माध्यम से अधिक मजबूती से संबंधित हैं।{{r|Lovasz:2013}}


<ब्लॉककोट>काउंटिंग लेम्मा। ग्राफॉन की किसी भी जोड़ी के लिए <math>U</math> और <math>W</math>, अपने पास
<ब्लॉककोट>काउंटिंग लेम्मा। ग्राफॉन की किसी भी जोड़ी के लिए <math>U</math> और <math>W</math>, अपने पास है:
<math display=block> |t(F, U) - t(F, W)| \le e(F) \delta_\square(U, W) </math>
<math display=block> |t(F, U) - t(F, W)| \le e(F) \delta_\square(U, W) </math>
सभी रेखांकन के लिए <math>F</math>.
सभी रेखांकन के लिए <math>F</math>.
</ब्लॉककोट>
</ब्लॉककोट>


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


उलटा काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक वास्तविक संख्या मौजूद है <math>\eta > 0</math> और एक सकारात्मक पूर्णांक <math>k</math> ऐसा कि किसी भी जोड़ी ग्राफोन के लिए <math>U</math> और <math>W</math> साथ
व्युत्क्रम काउंटिंग लेम्मा। प्रत्येक वास्तविक संख्या के लिए <math>\epsilon > 0</math>, एक वास्तविक संख्या मौजूद है <math>\eta > 0</math> और एक सकारात्मक पूर्णांक <math>k</math> ऐसा कि किसी भी जोड़ी ग्राफोन के लिए <math>U</math> और <math>W</math> साथ
<math display=block> |t(F, U) - t(F, W)| \le \eta </math>
<math display=block> |t(F, U) - t(F, W)| \le \eta </math>
सभी रेखांकन के लिए <math>F</math> संतुष्टि देने वाला <math>v(F) \le k</math>,
सभी रेखांकन के लिए <math>F</math> संतुष्टि देने वाला <math>v(F) \le k</math>,
Line 245: Line 244:


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


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


Line 255: Line 254:
</ब्लॉककोट>
</ब्लॉककोट>


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


[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
Line 268: Line 267:
=== नियमितता लेम्मा ===
=== नियमितता लेम्मा ===


ग्राफॉन के स्थान की सघनता <math>(\widetilde{\mathcal{W}}_0, \delta_{\square})</math> ज़ेमेरीडी नियमितता लेम्मा के विश्लेषणात्मक सूत्रीकरण के रूप में सोचा जा सकता है ज़ेमेरीडी की नियमितता लेम्मा; वास्तव में, मूल लेम्मा की तुलना में एक मजबूत परिणाम।<ref name="lovasz-szegedy">{{cite journal |last1=Lovász |first1=László |last2=Szegedy |first2=Balázs |title=Szemerédi's lemma for the analyst |journal=Geom. Funct. Anal. |date=2007 |volume=17 |pages=252–270 |doi=10.1007/s00039-007-0599-6 |s2cid=15201345 |url=https://link.springer.com/content/pdf/10.1007/s00039-007-0599-6.pdf |access-date=10 December 2021}}</ref>
ग्राफॉन के स्थान की सघनता <math>(\widetilde{\mathcal{W}}_0, \delta_{\square})</math> ज़ेमेरीडी नियमितता लेम्मा के विश्लेषणात्मक सूत्रीकरण के रूप में सोचा जा सकता है ज़ेमेरीडी की नियमितता लेम्मा; वास्तव में, मूल लेम्मा की तुलना में एक मजबूत परिणाम है।<ref name="lovasz-szegedy">{{cite journal |last1=Lovász |first1=László |last2=Szegedy |first2=Balázs |title=Szemerédi's lemma for the analyst |journal=Geom. Funct. Anal. |date=2007 |volume=17 |pages=252–270 |doi=10.1007/s00039-007-0599-6 |s2cid=15201345 |url=https://link.springer.com/content/pdf/10.1007/s00039-007-0599-6.pdf |access-date=10 December 2021}}</ref>
ज़ेमेरेडी की नियमितता लेम्मा को ग्राफोन की भाषा में निम्नानुसार अनुवादित किया जा सकता है। एक ग्राफॉन बनने के लिए एक स्टेपफंक्शन को परिभाषित करें <math>W</math> यह टुकड़े-टुकड़े स्थिर है, अर्थात कुछ विभाजन के लिए <math>\mathcal{P}</math> का <math>[0,1]</math>, <math>W</math> निरंतर चालू है <math>S \times T</math> सभी के लिए <math>S, T \in \mathcal{P}</math>. बयान है कि एक ग्राफ <math>G</math> एक नियमितता विभाजन यह कहने के बराबर है कि इससे संबंधित ग्राफॉन है <math>W_G</math> एक स्टेपफंक्शन के करीब है।
ज़ेमेरेडी की नियमितता लेम्मा को ग्राफोन की भाषा में निम्नानुसार अनुवादित किया जा सकता है। एक ग्राफॉन बनने के लिए एक स्टेपफंक्शन को परिभाषित करें <math>W</math> यह टुकड़े-टुकड़े स्थिर है, अर्थात कुछ विभाजन के लिए <math>\mathcal{P}</math> का <math>[0,1]</math>, <math>W</math> निरंतर चालू है <math>S \times T</math> सभी के लिए <math>S, T \in \mathcal{P}</math>. बयान है कि एक ग्राफ <math>G</math> एक नियमितता विभाजन यह कहने के बराबर है कि इससे संबंधित ग्राफॉन है <math>W_G</math> एक स्टेपफंक्शन के करीब है।


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


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


लेकिन इसका उपयोग मजबूत नियमितता परिणाम साबित करने के लिए किया जा सकता है, जैसे कि Szemerédi_regularity_lemma#Strong_regularity_lemma :
लेकिन इसका उपयोग मजबूत नियमितता परिणाम साबित करने के लिए किया जा सकता है, जैसे कि ज़ेमेरीडी नियमितता लेम्मा#मजबूत नियमितता लेम्मा :


ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए <math>\mathbf{\epsilon} = (\epsilon_0, \epsilon_1, \dots)</math> धनात्मक वास्तविक संख्याओं का, एक धनात्मक पूर्णांक होता है <math>S</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफन है <math>W'</math> और एक स्टेपफंक्शन <math>U</math> साथ <math>k < S</math> ऐसे कदम <math> \lVert W - W' \rVert_1 \le \epsilon_0 </math> और <math> \lVert W' - U \rVert_\square \le \epsilon_k.</math>
ग्राफों के लिए मजबूत नियमितता लेम्मा। हर क्रम के लिए <math>\mathbf{\epsilon} = (\epsilon_0, \epsilon_1, \dots)</math> धनात्मक वास्तविक संख्याओं का, एक धनात्मक पूर्णांक होता है <math>S</math> ऐसा है कि हर ग्राफॉन के लिए <math>W</math>, एक ग्राफन है <math>W'</math> और एक स्टेपफंक्शन <math>U</math> साथ <math>k < S</math> ऐसे कदम <math> \lVert W - W' \rVert_1 \le \epsilon_0 </math> और <math> \lVert W' - U \rVert_\square \le \epsilon_k.</math>
</ब्लॉककोट>
</ब्लॉककोट>


मजबूत नियमितता प्रमेयिका का प्रमाण ऊपर दिए गए परिणाम 1 की अवधारणा के समान है। यह पता चला है कि हर ग्राफॉन <math>W</math> एक स्टेपफंक्शन के साथ अनुमान लगाया जा सकता है <math>U</math> Lp_space#Lp_spaces_and_Lebesgue_integrals | में <math>L_1</math> मानदंड, दिखा रहा है कि गेंदों का सेट <math>B_1(U, \epsilon_0)</math> ढकना <math>\widetilde{\mathcal{W}}_0</math>. ये सेट में नहीं खुले हैं <math>\delta_\square</math> मीट्रिक, लेकिन खुले रहने के लिए उन्हें थोड़ा बड़ा किया जा सकता है। अब, हम एक परिमित उपकवर ले सकते हैं, और कोई यह दिखा सकता है कि वांछित स्थिति इस प्रकार है।
मजबूत नियमितता प्रमेयिका का प्रमाण ऊपर दिए गए परिणाम 1 की अवधारणा के समान है। यह पता चला है कि हर ग्राफॉन <math>W</math> एक स्टेपफंक्शन के साथ अनुमान लगाया जा सकता है <math>U</math> एलपी_स्पेस#एलपी_स्पेस_एंड_लेब्सग्यू_इंटीग्रल्स में <math>L_1</math> मानदंड, दिखा रहा है कि गेंदों का सेट <math>B_1(U, \epsilon_0)</math> ढकना <math>\widetilde{\mathcal{W}}_0</math>. ये सेट में नहीं खुले हैं <math>\delta_\square</math> मीट्रिक, लेकिन खुले रहने के लिए उन्हें थोड़ा बड़ा किया जा सकता है। अब, हम एक परिमित उपकवर ले सकते हैं, और कोई यह दिखा सकता है कि वांछित स्थिति इस प्रकार है।


[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
Line 290: Line 289:
[[Category:सिद्धांत संभावना]]
[[Category:सिद्धांत संभावना]]


=== सिदोरेंको का अनुमान ===
=== सिदोरेंको का अनुमान ===
{{Main|Sidorenko's conjecture}}
{{Main|सिदोरेंको का अनुमान}}


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


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


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


== सामान्यीकरण ==
== सामान्यीकरण ==


ग्राफोन स्वाभाविक रूप सेसघन सरल रेखांकन से जुड़े होते हैं।
ग्राफोन स्वाभाविक रूप से सघन सरल रेखांकन से जुड़े होते हैं।
सघन निर्देशित भारित रेखांकन के लिए इस मॉडल के विस्तार हैं, जिन्हें अक्सर अलंकृत ग्राफॉन कहा जाता है।{{r|decorate}} रेंडम ग्राफ मॉडल के दोनों दृष्टिकोणों से विरल ग्राफ शासन के हाल के विस्तार भी हैं <ref name=Veitch:Roy:2015 />और ग्राफ सीमा सिद्धांत।<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc1 /><ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc2 />
सघन निर्देशित भारित रेखांकन के लिए इस मॉडल के विस्तार हैं, जिन्हें अक्सर अलंकृत ग्राफॉन कहा जाता है।{{r|decorate}} रेंडम ग्राफ मॉडल के दोनों दृष्टिकोणों से विरल ग्राफ शासन के हाल के विस्तार भी हैं <ref name=Veitch:Roy:2015 />और ग्राफ सीमा सिद्धांत भी है।<ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc1 /><ref name=Borgs:Chayes:Cohn:Zhao:2014:sgc2 />




Revision as of 15:22, 18 May 2023

एक ग्राफॉन द्वारा परिभाषित विनिमेय यादृच्छिक ग्राफ का अहसास। ग्राफॉन को मैजेंटा हीटमैप (निचले दाएं) के रूप में दिखाया गया है। आकार का एक यादृच्छिक ग्राफ स्वतंत्र रूप से प्रत्येक शीर्ष को असाइन करके उत्पन्न होता है एक अव्यक्त यादृच्छिक चर (ऊर्ध्वाधर अक्ष के साथ मान) और प्रत्येक शीर्ष सहित संभावना के साथ स्वतंत्र रूप से . उदाहरण के लिए, किनारा (हरा, बिंदीदार) संभावना के साथ मौजूद है ; दाहिने वर्ग में हरे बक्से का प्रतिनिधित्व करते हैं के मूल्य और . ऊपरी बाएँ पैनल ग्राफ प्राप्ति को आसन्न आव्यूह के रूप में दिखाता है।

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