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

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

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