पॉलीहेड्रल कॉम्बिनेटरिक्स

पॉलीहेड्रल साहचर्य, कॉम्बिनेटरिक्स और असतत ज्यामिति के भीतर गणित की शाखा है जो उत्तल पॉलीहेड्रॉन और उच्च-आयामी उत्तल पॉलीटोप्स के फलकों की गिनती और वर्णन करने की समस्याओं का अध्ययन करती है।

पॉलीहेड्रल कॉम्बिनेटरिक्स में अनुसंधान दो अलग-अलग क्षेत्रों में किया जाता है। इस क्षेत्र के गणितज्ञ पॉलीटॉप्स के संयोजन विज्ञान का अध्ययन करते हैं; उदाहरण के लिए वे असमानता (गणित) की खोज करते हैं जो वर्टेक्स (ज्यामिति), किनारे (ज्यामिति) की संख्या के बीच संबंधों का वर्णन करती है और स्वेच्छाचारी पॉलीटोप्स या पॉलीटोप्स के कुछ महत्वपूर्ण उपवर्गों में उच्च आयामों के फलकों और पॉलीटोप्स के अन्य दहनशील गुणों का अध्ययन करती है। जैसे कि उनकी संयोजकता (ग्राफ़ सिद्धांत) और व्यास (किसी अन्य शीर्ष से किसी शीर्ष तक पहुँचने के लिए आवश्यक चरणों की संख्या)। इसके अतिरिक्त कई कंप्यूटर वैज्ञानिक पूर्णांक प्रोग्रामिंग समस्याओं से उत्पन्न होने वाले कुछ विशिष्ट पॉलीटॉप्स (विशेष रूप से 0-1 पॉलीटोप्स जिनके किनारे अतिविम के सबसेट हैं) के सटीक विवरणों में अनुसंधान का वर्णन करने के लिए "पॉलीहेड्रल कॉम्बिनेटरिक्स" वाक्यांश का उपयोग करते हैं।

फलक और फलकों की गिनती करने वाले वैक्टर

उत्तल पॉलीटॉप की फेस जाली।

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

पॉलीहेड्रल कॉम्बिनेटरिक्स में एक महत्वपूर्ण उपकरण पॉलीटॉप का ƒ-वेक्टर है तथा वेक्टर (ƒ₀, ƒ₁, ..., ƒ_d−1) जहां ƒ_i पॉलीटोप की आई-डायमेंशनल विशेषताओं की संख्या है। उदाहरण के लिए एक घन में आठ कोने, बारह किनारे और छह फलक होते हैं इसलिए इसका ƒ-वेक्टर (8,12,6) है। दोहरे पॉलीहेड्रॉन में एक ƒ-वेक्टर होता है जिसमें विपरीत क्रम में समान संख्याएं होती हैं; इस प्रकार उदाहरण के लिए नियमित ऑक्टाहेड्रोन, घन के लिए दोहरी, में ƒ-वेक्टर (6,12,8) है। कॉन्फ़िगरेशन मेट्रिसेस में विकर्ण तत्वों के रूप में नियमित पॉलीटोप्स के f-वैक्टर सम्मिलित हैं।

विस्तारित ƒ-वेक्टर इसके प्रत्येक छोर पर नंबर एक को जोड़कर बनाया जाता है एवं फलकों की जाली के सभी स्तरों पर वस्तुओं की संख्या की गणना करता है; वेक्टर के बाईं ओर f₋₁= 1 रिक्त सेट को फलकों के रूप में गिनता है जबकि दाईं ओर f_d= 1, P को ही गिनता है।

घन के लिए विस्तारित ƒ-वेक्टर (1,8,12,6,1) है और अष्टफलक के लिए यह (1,6,12,8,1) है। यद्यपि उदाहरणार्थ पॉलीहेड्रा के लिए वैक्टर असमान हैं (गुणांक बाएं से दाएं क्रम में लिए जाते हैं, अधिकतम तक बढ़ते हैं और फिर घटते हैं) तथा ये उच्च-आयामी पॉलीटोप्स हैं जिनके लिए यह सत्य नहीं है।

साधारण पॉलीटोप्स के लिए (पॉलीटोप्स जिसमें हर पहलू सरल है) इन वैक्टरों को परिवर्तित करना अधिकतर सुविधाजनक होता है जो अलग वेक्टर का निर्माण करता है जिसे एच-वेक्टर कहा जाता है। यदि हम ƒ-वेक्टर (अंतिम 1 को छोड़कर) के नियमों को बहुपद ƒ(x) = Σf के गुणांक _ix^{d − i − 1} के रूप में समझते हैं (उदाहरण के लिए अष्टफलक के लिए यह बहुपद ƒ(x) = x देता है³ + 6x² + 12x + 8) तो h-वेक्टर बहुपद h(x) = ƒ(x − 1) के गुणांकों को सूचीबद्ध करता है (पुनः अष्टफलक के लिए h(x) = x³ + 3x² + 3x + 1). जैसा कि ज़िग्लर लिखते हैं कि "सरल पॉलीटोप्स के विषय में विभिन्न समस्याओं के लिए h-वैक्टर, ƒ-वैक्टर की तुलना में फलकों की संख्या के बारे में जानकारी को एन्कोड करने का अधिक सुविधाजनक और संक्षिप्त तरीका है।"

समानताएं और असमानताएं

पॉलीटॉप के ƒ-वेक्टर के गुणांकों के बीच सबसे महत्वपूर्ण संबंध यूलर का सूत्र Σ(-1)ⁱf_i = 0 है जहां योग के नियम विस्तारित ƒ-वेक्टर के गुणांकों पर होते हैं। तीन आयामों में विस्तारित ƒ-वेक्टर (1, v, e, f, 1) के बाएँ और दाएँ सिरों पर दो 1 को समीकरण के दाएँ हाथ की ओर ले जाने से यह पहचान अधिक परिचित रूप v - e में बदल जाती है + f = 2, इस तथ्य से कि त्रि-आयामी बहुफलक के प्रत्येक फलक में कम से कम तीन किनारे होते हैं इसके बाद 2e ≥ 3f की दोहरी गणना होती है और यूलर के सूत्र से e और f को हटाने के लिए इस असमानता का उपयोग करने से और भी असमानताएं e ≤ 3v - 6 और f ≤ 2v − 4 हो जाती हैं। e ≤ 3f − 6 और v ≤ 2f − 4 द्वैत से यह स्टीनिट्ज़ के प्रमेय से अनुसरण करता है कि कोई भी 3-आयामी पूर्णांक वेक्टर जो इन समानताओं और असमानताओं को संतुष्ट करता है एक उत्तल पॉलीहेड्रॉन का ƒ-वेक्टर होता है। [5]

उच्च आयामों में पॉलीटॉप के फलकों की संख्या के बीच अन्य संबंध भी महत्वपूर्ण हो जाते हैं जिसमें देह्न-सोमरविले समीकरण भी सम्मिलित हैं जो साधारण पॉलीटोप्स के एच-वेक्टरों के संदर्भ में व्यक्त किए जाते हैं एवं सभी के लिए सरल रूप h_k = h_{d − k} लेते हैं। k = 0 के साथ इन समीकरणों का उदाहरण यूलर के सूत्र के बराबर है परन्तु d> 3 के लिए इन समीकरणों के अन्य उदाहरण एक दूसरे से रैखिक रूप से स्वतंत्र हैं और अतिरिक्त तरीकों से h-वेक्टर (और इसलिए ƒ-वैक्टर भी) को बाधित करते हैं। [4]

पॉलीटॉप फेस काउंट्स पर एक और महत्वपूर्ण असमानता ऊपरी सीमा प्रमेय द्वारा दी गई है जिसे पूर्व में McMullen (1970) द्वारा सिद्ध किया गया था जिसमें कहा गया है कि n कोने वाले एक d-आयामी पॉलीटॉप में किसी भी अन्य आयाम के उतने ही फलक हो सकते हैं जितने कि समान संख्या वाले कोने वाले पड़ोसी पॉलीटॉप के रूप में होते हैं:

$f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {d-i}{k-i}}+{\binom {i}{k-d+i}}\right){\binom {n-d-1+i}{i}},$

जहाँ तारांकन का अर्थ है कि योग का अंतिम शब्द आधा होना चाहिए जब d सम हो। असम्बद्ध रूप से इसका तात्पर्य है कि सभी आयामों के फलक अधिकतम $\scriptstyle O(n^{\lfloor d/2\rfloor })$ हैं।

यहां तक ​​कि चार आयामों में उत्तल पॉलीटोप्स के संभावित ƒ-सदिशों का सेट चार-आयामी पूर्णांक जाली का उत्तल उपसमुच्चय नहीं बनाता है और इन वैक्टरों के संभावित मूल्यों के बारे में बहुत कुछ अज्ञात रहता है।

ग्राफ-सैद्धांतिक गुण

पॉलीटोप्स के फलकों की संख्या की जांच के साथ-साथ शोधकर्ताओं ने उनमें से अन्य कॉम्बीनेटरियल गुणों का अध्ययन किया है जैसे पॉलीटोप्स के कोने और किनारों से प्राप्त अप्रत्यक्ष ग्राफ के विवरण (उनके 1-कंकाल)।

बालिंस्की के प्रमेय में कहा गया है कि किसी भी डी-डायमेंशनल कॉन्वेक्स पॉलीटोप से इस तरह से प्राप्त ग्राफ डी-वर्टेक्स-कनेक्टेड है। त्रि-आयामी पॉलीहेड्रा के सम्बन्ध में इस संपत्ति और प्लेनर ग्राफ का उपयोग पॉलीहेड्रा के ग्राफों को सटीक रूप से चित्रित करने के लिए किया जा सकता है: स्टीनिट्ज़ के प्रमेय में कहा गया है कि G एक त्रि-आयामी पॉलीहेड्रॉन का ढांचा है यदि G केवल एक 3-वर्टेक्स-कनेक्टेड प्लानर ग्राफ है।

ब्लाइंड & मानी-लेविटस्कॉ (1987) ने एक प्रमेय (पहले मीका मोती द्वारा अनुमान लगाया गया था) में कहा गया है कि साधारण पॉलीटॉप के फलकों की संरचना को उनके ग्राफ से पुनः से बनाया जा सकता है। यदि दिया गया अप्रत्यक्ष ग्राफ साधारण पॉलीटॉप का ढांचा है तो केवल पॉलीटॉप (कॉम्बिनेटरियल समतुल्यता तक) है जिसके लिए यह सच है। यह (गैर-सरल) पड़ोसी पॉलीटोप्स के साथ तीव्र विपरीत है जिसका ग्राफ पूर्ण ग्राफ है; एक ही ग्राफ के लिए कई अलग-अलग पड़ोसी पॉलीटोप्स हो सकते हैं। अद्वितीय अद्वितीय सिंक अभिविन्यास आधारित इस प्रमेय का एक अन्य प्रमाण Kalai (1988), और Friedman (2009) द्वारा दिया गया था जिन्होंने दिखाया कि कैसे इस प्रमेय का उपयोग करके उनके ग्राफ़ से साधारण पॉलीटोप्स के फलकों के जाली के पुनर्निर्माण के लिए बहुपद समय एल्गोरिथ्म प्राप्त किया जा सकता है। जबकि यह परीक्षण करना कि क्या किसी दिए गए ग्राफ़ या जाली को साधारण पॉलीटॉप के फलकों की जाली के रूप में अनुभव किया जा सकता है एवं यह सरलीकृत पॉलीटोप्स की प्राप्ति के बराबर (ध्रुवीयता द्वारा) है जो Adiprasito & Padrol (2014) द्वारा वास्तविक के अस्तित्व सिद्धांत के लिए पूर्ण होना दिखाया गया था।

रैखिक प्रोग्रामिंग के लिए सिंप्लेक्स विधि के संदर्भ में पॉलीटॉप के व्यास को समझना और किसी भी शीर्ष से पथ द्वारा किसी शीर्ष तक पहुंचने के लिए आवश्यक किनारों की न्यूनतम संख्या को समझना महत्वपूर्ण है। रेखीय कार्यक्रम की रैखिक असमानता की प्रणाली कार्यक्रम के सभी व्यवहार्य समाधानों का प्रतिनिधित्व करने वाले पॉलीटॉप के पहलुओं को परिभाषित करती है और सिंप्लेक्स विधि इस पॉलीटॉप में एक पथ का अनुसरण करके इष्टतम समाधान ढूंढती है। इस प्रकार व्यास इस विधि के लिए आवश्यक चरणों की संख्या पर एक निचली सीमा प्रदान करता है। हिर्श अनुमान जो अब अप्रमाणित हो चुका है, ने निश्चित आयाम के साथ पॉलीटॉप के व्यास पर मजबूत (रैखिक) बंधन का सुझाव दिया कि $d$ और फलक की संख्या (ज्यामिति) $n$ हो सकती है। शक्तिहीन (अर्ध-बहुपद में $d$ और $n$) व्यास पर ऊपरी सीमाएं ज्ञात हैं साथ ही पॉलीटोप्स के विशेष वर्गों के लिए हिर्श अनुमान के प्रमाण भी हैं।

कम्प्यूटेशनल गुण

कम्प्यूटेशनल रूप से कठिन समस्या यह निर्धारित करना है कि किसी दिए गए पॉलीटॉप के शीर्षों की संख्या कुछ प्राकृतिक संख्या k से बंधी है या नहीं और यह जटिलता वर्ग PP (जटिलता) के लिए पूर्ण है।

0-1 पॉलीटोप्स के तथ्य

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

उदाहरण के रूप में ब्रिकहॉफ पॉलीटॉप पर विचार करें, n × n मैट्रिक्स का सेट जो क्रमपरिवर्तन मैट्रिक्स के उत्तल संयोजनों से बनाया जा सकता है। समान रूप से इसके शीर्षों को पूर्ण द्विदलीय ग्राफ में सभी पूर्ण मिलानों के वर्णन करने के बारे में सोचा जा सकता है और इस पॉलीटॉप पर रैखिक अनुकूलन समस्या को द्विदलीय न्यूनतम भार पूर्ण मिलान समस्या के रूप में व्याख्या की जा सकता है। ब्रिकहॉफ-वॉन न्यूमैन प्रमेय कहता है कि इस पॉलीटोप को दो प्रकार की रैखिक असमानता या समानता द्वारा वर्णित किया जा सकता है। सबसे पहले प्रत्येक मैट्रिक्स सेल के लिए बाधा इस सेल का गैर-ऋणात्मक मान है और दूसरा मैट्रिक्स की प्रत्येक पंक्ति या स्तंभ के लिए बाधा है कि उस पंक्ति या स्तंभ में कोशिकाओं का योग एक के बराबर है। पंक्ति और स्तंभ प्रतिबंध आयाम n² − 2n + 1 के रेखीय उप-स्थान को परिभाषित करते हैं जिसमें ब्रिकहॉफ पॉलीटोप निहित है और गैर-नकारात्मक बाधाएं उस उप-स्थान के भीतर ब्रिकहॉफ पॉलीटॉप के पहलुओं को परिभाषित करती हैं।

जबकि ब्रिकहॉफ पॉलीटोप असामान्य है क्योंकि इसके पहलुओं का पूरा विवरण उपलब्ध है। कई अन्य पॉलीटॉप्स के लिए 0-1 घातीय रूप से कई या सुपरएक्सपोनेंशियल रूप से कई पहलू हैं और उनके पहलुओं का केवल आंशिक विवरण उपलब्ध है।

यह भी देखें

• एब्स्ट्रैक्ट पॉलीटॉप
• कॉम्बिनेटरियल कम्यूटेटिव बीजगणित
• मैट्रॉइड पॉलीटोप
• ऑर्डर पॉलीटॉप
• साधारण क्षेत्र
• स्थिर मिलान पॉलीटॉप

संदर्भ

• Adiprasito, Karim A.; Padrol, Arnau (2017), "The universality theorem for neighborly polytopes", Combinatorica, 37: 129–136, arXiv:1402.7207, Bibcode:2014arXiv1402.7207A, doi:10.1007/s00493-016-3253-9.
• Balinski, Michel L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics, 11: 431–434, doi:10.2140/pjm.1961.11.431.
• Blind, Roswitha; Mani-Levitska, Peter (1987), "Puzzles and polytope isomorphisms", Aequationes Mathematicae, 34 (2–3): 287–297, doi:10.1007/BF01830678, MR 0921106.
• Cook, William; Seymour, Paul D. (1989), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, ISBN 978-0-8218-6591-0.
• Friedman, Eric J. (2009), "Finding a simple polytope from its graph in polynomial time", Discrete & Computational Geometry, 41 (2): 249–256, doi:10.1007/s00454-008-9121-7, MR 2471873.
• Haase, Christoph; Kiefer, Stefan (2016), "The complexity of the Kth largest subset problem and related problems", Information Processing Letters, 116 (2): 111–115, arXiv:1501.06729, doi:10.1016/j.ipl.2015.09.015
• Höppner, Andrea; Ziegler, Günter M. (2000), "A census of flag-vectors of 4-polytopes", in Kalai, Gil; Ziegler, Günter M. (eds.), Polytopes — Combinatorics and Computation, DMV Seminar, vol. 29, pp. 105–110, doi:10.1007/978-3-0348-8438-9_4.
• Kalai, Gil (1988), "A simple way to tell a simple polytope from its graph", Journal of Combinatorial Theory, Series A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7, MR 0964396.
• Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society, 26 (2): 315–316, arXiv:math/9204233, doi:10.1090/S0273-0979-1992-00285-9, MR 1130448.
• Kalai, Gil; Ziegler, Günter M., eds. (2000), Polytopes — Combinatorics and Computation, DMV Seminar, vol. 29, Birkhäuser, doi:10.1007/978-3-0348-8438-9, ISBN 978-3-7643-6351-2.
• McMullen, Peter (1970), "The maximum numbers of faces of a convex polytope", Mathematika, 17: 179–184, doi:10.1112/S0025579300002850.
• Naddef, Denis (1989), "The Hirsch conjecture is true for (0,1)-polytopes", Mathematical Programming, 45 (1): 109–110, doi:10.1007/BF01589099, MR 1017214.
• Santos, Francisco (2012), "A counterexample to the Hirsch conjecture", Annals of Mathematics, Princeton University and Institute for Advanced Study, 176 (1): 383–412, arXiv:1006.2814, doi:10.4007/annals.2012.176.1.7, MR 2925387
• Schrijver, Alexander (1987), Polyhedral Combinatorics, Centrum voor Wiskunde en Informatica.
• Steinitz, Ernst (1906), "Über die Eulerschen Polyederrelationen", Archiv für Mathematik und Physik, 11: 86–88.
• Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, doi:10.1007/978-1-4613-8431-1, ISBN 0-387-94365-X.
• Ziegler, Günter M. (2000), "Lectures on 0-1 polytopes", in Kalai, Gil; Ziegler, Günter M. (eds.), Polytopes — Combinatorics and Computation, DMV Seminar, vol. 29, pp. 1–41, doi:10.1007/978-3-0348-8438-9_1.

बाहरी संबंध

• Kalai, Gil (2008), Five Open Problems Regarding Convex Polytopes.