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

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

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

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

उत्तल पॉलीटॉप का चेहरा जाली।

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

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

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

घन के लिए विस्तारित ƒ-वेक्टर (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). जैसा कि ज़िग्लर लिखते हैं कि "सरल पॉलीटोप्स के विषय में विभिन्न समस्याओं के लिए एच-वैक्टर ƒ-वैक्टर की तुलना में फलकों की संख्या के बारे में जानकारी को एन्कोड करने का एक अधिक सुविधाजनक और संक्षिप्त तरीका है।"

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

पॉलीटॉप के ƒ-वेक्टर के गुणांकों के बीच सबसे महत्वपूर्ण संबंध यूलर का सूत्र Σ(-1)ifi = 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]

उच्च आयामों में, पॉलीटॉप के चेहरों की संख्या के बीच अन्य संबंध भी महत्वपूर्ण हो जाते हैं, जिसमें देह्न-सोमरविले समीकरण भी शामिल हैं, जो साधारण पॉलीटोप्स के एच-वेक्टरों के संदर्भ में व्यक्त किए जाते हैं, सभी के लिए सरल रूप एचके = एचडी - के लेते हैं। k = 0 के साथ इन समीकरणों का उदाहरण यूलर के सूत्र के बराबर है, लेकिन d> 3 के लिए इन समीकरणों के अन्य उदाहरण एक दूसरे से रैखिक रूप से स्वतंत्र हैं और अतिरिक्त तरीकों से एच-वेक्टर (और इसलिए ƒ-वैक्टर भी) को बाधित करते हैं। [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-स्केलेटा)।

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

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

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

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

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

एक उदाहरण के रूप में, Birkhoff polytope पर विचार करें, 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.