क्लिक कॉम्प्लेक्स

एक ग्राफ का समूह प्रणाली। आकार एक के समूह छोटे लाल डिस्क के रूप में दिखाए जाते हैं; आकार दो के समूहों को काली रेखा खंडों के रूप में दिखाया गया है; आकार तीन के समूहों को हल्के नीले त्रिकोण के रूप में दिखाया गया है; और आकार चार के समूहों को गहरे नीले रंग के टेट्राहेड्रा के रूप में दिखाया गया है।

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

समूह प्रणाली

अप्रत्यक्ष ग्राफ G की समूह प्रणाली X(G) एक संक्षिप्त सरल प्रणाली है (अर्थात, उपसमुच्चय संचालन के अंतर्गत परिमित समुच्चय की एक श्रेणी) जो G के समूहों में शीर्ष (ग्राफ सिद्धांत) के समुच्चय द्वारा निर्मित है। समूह का कोई भी उपसमुच्चय अपने आप में समूह है, इसलिए उपसमुच्चय की यह श्रेणी एक संक्षिप्त सरल प्रणाली की आवश्यकता को पूरा करता है कि श्रेणी में एक समुच्चय प्रत्येक श्रेणी में होना चाहिए।

समूह प्रणाली को एक रेखागणितीय स्पेस के रूप में भी देखा जा सकता है जिसमें प्रत्येक समूह शीर्ष k को आकार k – 1 के संकेतन द्वारा दर्शाया गया है। X(G) जिसे प्रणाली के अंतर्निहित ग्राफ के रूप में भी जाना जाता है वो 1- रूप-रेखा श्रेणी में प्रत्येक 1-तत्व समुच्चय के लिए एक शीर्ष के साथ एक अप्रत्यक्ष ग्राफ है और श्रेणी में प्रत्येक 2-तत्व समुच्चय के लिए परिधि है जहाँ G समरूप है।

नकारात्मक उदाहरण

प्रत्येक समूह प्रणाली एक संक्षिप्त सरल प्रणाली है, लेकिन विपरीत सच नहीं है। उदाहरण के लिए, अधिकतम समुच्चय {1,2,3}, {2,3,4}, {4,1} के साथ {1,2,3,4} संक्षिप्त सरल प्रणाली पर विचार करें। यदि यह किसी ग्राफ़ G का X ( G ) होता तो G के शीर्ष {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {4,1} होते इसलिए X ( G ) में भी समूह {1,2,3,4} होना चाहिए।

स्वतंत्र प्रणाली

अप्रत्यक्ष ग्राफ G की स्वतंत्र प्रणाली I(G) है जो स्वतंत्र समुच्चयों G के शीर्ष (ग्राफ सिद्धांत) के समुच्चय द्वारा निर्मित एक संक्षिप्त सरल प्रणाली है। समूह प्रणाली का G पूरक ग्राफ के स्वतंत्रता प्रणाली G के बराबर होता है।

संकेत प्रणाली

संकेत प्रणाली "2-निर्धारित" नामक एक अतिरिक्त गुण के साथ एक संक्षिप्त सरल प्रणाली है। प्रत्येक उपसमूह S के शीर्ष के लिए, यदि S में शीर्ष की प्रत्येक जोड़ी प्रणाली में है, तो S स्वयं भी प्रणाली में है।

प्रत्येक समूह प्रणाली एक संकेत प्रणाली है: यदि S में प्रत्येक जोड़ी का आकार 2 का एक समूह है, तो उनके बीच एक शीर्ष है, इसलिए S एक समूह है।

प्रत्येक संकेत प्रणाली एक समूह प्रणाली है: एक संकेत प्रणाली दिया गया है, ग्राफ़ G को सभी शीर्ष के समुच्चय पर परिभाषित करें, जहाँ दो शीर्ष u,v G iff {u,v} में आसन्न हैं (इस ग्राफ को प्रणाली का 1-रूप-रेखा  कहा जाता है)। संकेत प्रणाली की परिभाषा के अनुसार, वर्टिकल का प्रत्येक समुच्चय जो जोड़े से जुड़ा हुआ है, प्रणाली में है। इसलिए, संकेत प्रणाली 'G' पर समूह प्रणाली के बराबर है।

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

मिखाइल लियोनिदोविच ग्रोमोव ने संकेत प्रणाली होने की स्थिति के रूप में नो-Δ (शुन्य परिवर्तन) स्थिति को परिभाषित किया था।

व्हिटनी प्रणाली

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

अनुरूप हाइपरग्राफ

हाइपरग्राफ का प्राथमिक ग्राफ G (H) एक ही शीर्ष समुच्चय पर ग्राफ है, जिसके किनारों के रूप में एक ही अत्यंत किनारें में एक साथ दिखाई देने वाले जोड़े हैं। एक हाइपरग्राफ को 'अनुरूप' कहा जाता है, यदि इसके प्राथमिक ग्राफ का प्रत्येक अधिकतम समूह एक अत्यंत किनारा है या समकक्ष है यदि इसके प्राथमिक ग्राफ का प्रत्येक समूह कुछ अत्यंत किनारें में समाहित है। यदि हाइपरग्राफ को नीचे की ओर बंद करने की आवश्यकता होती है तो हाइपरग्राफ सटीक रूप से अनुरूप होता है तब यह एक संकेत प्रणाली होता है। यह हाइपरग्राफ की भाषा को सरल प्रणालियों की भाषा से संबंधित करता है।

उदाहरण और अनुप्रयोग

किसी भी कोशिका प्रणाली C का बैरीसेंट्रिक उपखंड एक संकेत प्रणाली है जिसमें C की प्रति कोशिका में एक शीर्ष होता है। बेरिसेंट्रिक उपखंड के शीर्ष का एक संग्रह एक संकेतन बनाता है अगर और केवल अगर C की कोशिकाओं का संबंधित संग्रह एक संकेत (कोशिकाओं के समावेशन क्रम में श्रृंखला) बनाता हो।विशेष रूप से, 2-बहुखण्ड पर एक कोशिका प्रणाली का बैरीसेंट्रिक उपखंड बहुखण्ड के व्हिटनी त्रिभुज को निर्मित करता है।

आंशिक रूप से अनुक्रम किए गए समुच्चय के अनुक्रम प्रणाली में आंशिक अनुक्रम की श्रृंखला (कुल अनुक्रम उपसमुच्चय) होती हैं। यदि कुछ उपसमुच्चय की प्रत्येक जोड़ी स्वयं अनुक्रमित है, तो संपूर्ण उपसमुच्चय एक श्रृंखला है, इसलिए क्रम प्रणाली नो-Δ स्थिति को संतुष्ट करता है। इसे आंशिक क्रम के तुलनात्मक ग्राफ के समूह प्रणाली के रूप में व्याख्या किया जा सकता है।

एक ग्राफ़ के मिलान प्रणाली में कोई भी दो किनारों के समुच्चय होते हैं जो एक समापन बिंदु साझा नहीं करते हैं। फिर से, समुच्चय की यह श्रेणी नो-Δ शर्त को पूरा करता है। इसे दिए गए ग्राफ के रैखिक ग्राफ के पूरक ग्राफ के समूह प्रणाली के रूप में देखा जा सकता है। जब मिलान प्रणाली को बिना किसी विशेष ग्राफ के संदर्भ के रूप में संदर्भित किया जाता है, तो इसका मतलब है कि यह एक पूर्ण ग्राफ की मिलान प्रणाली है। एक पूर्ण द्विदलीय ग्राफ K_m,n का मिलान प्रणाली शतरंज की बिसात के रूप में जाना जाता है। यह एक शतरंज के हाथी के ग्राफ के पूरक ग्राफ का समूह ग्राफ है, और इसका प्रत्येक सरलीकरण m × n शतरंज की बिसात पर हाथी की नियुक्ति का प्रतिनिधित्व करता है जैसे कि कोई भी दो हाथी एक दूसरे पर हमला नहीं करते हैं। तब m = n ± 1, शतरंज की बिसात पर एक आभासी-बहुखण्ड बनाता है।

मीट्रिक स्थान में बिंदुओं के एक समूह का विएटोरिस-रिप्स प्रणाली समूह प्रणाली की एक विशेष स्तिथि है, जो बिंदुओं के यूनिट डिस्क ग्राफ से बनता है; हालांकि, प्रत्येक समूह प्रणाली X(G) को अंतर्निहित ग्राफ G पर सबसे कम पथ मीट्रिक के वीटोरिस-रिप्स प्रणाली के रूप में व्याख्या किया जा सकता है।

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

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

समरूपता समूह

मेशुलम समूह प्रणाली के समरूप पर निम्नलिखित सिद्धांत को सिद्ध करता है। मान लीजिए कि दिए गए पूर्णांक $l\geq 1,t\geq 0$, में ग्राफ G $P(l,t)$ नामक गुणों को संतुष्ट करता है, जिसका अर्थ है कि:

• शीर्षों $l$ के प्रत्येक समुच्चय G में एक सामान्य आसन्न है;
• शीर्षों का एक समुच्चय A उपलब्ध है, जिसमें शीर्षों $l$ के प्रत्येक समुच्चय के लिए एक सामान्य आसन्न होता है, और इसके अतिरिक्त, प्रेरित ग्राफ G[A] में एक प्रेरित उपग्राफ के रूप में, टी-आकारीय अष्टभुजाकार वृत्त के 1-रूप-रेखा की प्रति उपलब्ध नहीं है।

फिर समूह प्रणाली X(G) की जे-वें कम होमोलोजी j के बीच 0 और $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ के लिए निम्न है।

यह भी देखें

• सिम्पलेक्स ग्राफ, एक प्रकार का ग्राफ जिसमें अंतर्निहित ग्राफ के प्रत्येक समूह के लिए एक नोड होता है
• विभाजन मेट्रॉइड#समूह प्रणाली, एक प्रकार का मैट्रोइड जिसका [[matroid चौराहा]] समूह प्रणाली बना सकता है

संदर्भ

• Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, vol. 453, Providence, RI: AMS, pp. 49–86.
• Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
• Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation, 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669, S2CID 2786607.
• Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B. (eds.), Handbook of Geometric Topology, Elsevier, pp. 373–422.
• Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17, doi:10.37236/1634.
• Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358, S2CID 28144260.
• Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic, 9 (3): 387–405, CiteSeerX 10.1.1.107.5000, doi:10.2178/bsl/1058448678.
• Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258 (1–3): 123–135, doi:10.1016/S0012-365X(02)00266-2.
• Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.