Polyhedral combinatorics
पॉलीहेड्रल कॉम्बिनेटोरिक्स, कॉम्बिनेटोरिक्स और असतत ज्यामिति के भीतर गणित की एक शाखा है, जो उत्तल पॉलीहेड्रा और उच्च-आयामी उत्तल पॉलीटोप के चेहरों की गिनती और वर्णन करने की समस्याओं का अध्ययन करती है। पॉलीहेड्रल संयोजन विज्ञान में अनुसंधान दो अलग-अलग क्षेत्रों में होता है। इस क्षेत्र के गणितशास्त्री पॉलीटोप के संयोजन का अध्ययन करते हैं; उदाहरण के लिए, वे ऐसी असमानताओं की तलाश करते हैं जो मनमाने पॉलीटोप में या पॉलीटोप के कुछ महत्वपूर्ण उपवर्गों में शीर्षों, किनारों और उच्च आयामों के चेहरों की संख्या के बीच संबंधों का वर्णन करती हैं, और पॉलीटोप के अन्य संयोजन गुणों का अध्ययन करते हैं जैसे कि उनकी कनेक्टिविटी और व्यास (किसी भी अन्य शीर्ष से किसी भी शीर्ष तक पहुंचने के लिए आवश्यक चरणों की संख्या)। इसके अतिरिक्त, कई कंप्यूटर वैज्ञानिक पूर्णांक प्रोग्रामिंग समस्याओं से उत्पन्न होने वाले कुछ विशिष्ट पॉलीटोप (विशेष रूप से 0-1 पॉलीटोप, जिनके शीर्ष एक हाइपरक्यूब के सबसेट हैं) के चेहरों के सटीक विवरण में अनुसंधान का वर्णन करने के लिए "पॉलीहेड्रल संयोजन" वाक्यांश का उपयोग करते हैं। चेहरे और चेहरे की गिनती करने वाले वैक्टर एक उत्तल पॉलीटोप पी के एक चेहरे को पी और एक बंद अर्ध-स्थान एच के प्रतिच्छेदन के रूप में परिभाषित किया जा सकता है जैसे कि एच की सीमा में पी का कोई आंतरिक बिंदु न हो। 0-आयामी चेहरे स्वयं शीर्ष हैं, और 1-आयामी चेहरे (जिन्हें किनारे कहा जाता है) शीर्षों के जोड़े को जोड़ने वाले रेखा खंड हैं। ध्यान दें कि इस परिभाषा में खाली समुच्चय और संपूर्ण पॉलीटोप पी के चेहरे भी शामिल हैं। यदि पी का आयाम डी है, तो आयाम डी-1 वाले पी के चेहरे को पी के पहलू कहा जाता है और आयाम डी-2 वाले चेहरे को कटक कहा जाता है। पी के चेहरों को आंशिक रूप से समावेश द्वारा क्रमबद्ध किया जा सकता है, जिससे एक चेहरे की जाली बनती है जिसमें इसका शीर्ष तत्व पी स्वयं होता है और इसके निचले तत्व के रूप में खाली सेट होता है। पॉलीहेड्रल संयोजन विज्ञान में एक प्रमुख उपकरण एक पॉलीटोप का f-वेक्टर है, वेक्टर (f0, f1,., fd−1) जहां फाई पॉलीटोप की i-आयामी विशेषताओं की संख्या है। उदाहरण के लिए, एक घन में आठ शीर्ष, बारह किनारे और छह पहलू होते हैं, इसलिए इसका f-वेक्टर (8,12,6) है। दोहरे पॉलीटोप में विपरीत क्रम में समान संख्याओं के साथ एक f-वेक्टर होता है; इस प्रकार, उदाहरण के लिए, नियमित ऑक्टाहेड्रॉन, जो एक घन के लिए दोहरे होते हैं, में f-वेक्टर (6,12,8) होता है। विन्यास मैट्रिक्स में विकर्ण तत्वों के रूप में नियमित पॉलीटोप के एफ-वेक्टर शामिल हैं। विस्तारित f-वेक्टर का गठन f-वेक्टर के प्रत्येक छोर पर संख्या एक को जोड़कर, चेहरे की जाली के सभी स्तरों पर वस्तुओं की संख्या की गिनती करके किया जाता है; वेक्टर के बाईं ओर, f−1 = 1 खाली सेट को एक चेहरे के रूप में गिनता है, जबकि दाईं ओर, fd = 1 खुद P को गिनता है। घन के लिए विस्तारित f-वेक्टर (1,8,12,6,1) है और ऑक्टाहेड्रॉन के लिए यह (1,6,12,8,1) है। यद्यपि इन उदाहरण पॉलीहेड्रा के लिए वैक्टर एक-आयामी हैं (गुणांक, बाएं से दाएं क्रम में लिए जाते हैं, अधिकतम तक बढ़ते हैं और फिर घटते हैं), ऐसे उच्च-आयामी पॉलीटोप हैं जिनके लिए यह सच नहीं है। सरल पॉलीटोप (पॉलीटोप जिसमें प्रत्येक पहलू एक सिंप्लेक्स होता है) के लिए, इन वैक्टरों को बदलना अक्सर सुविधाजनक होता है, जिससे एच-वेक्टर नामक एक अलग वेक्टर का उत्पादन होता है। यदि हम f-वेक्टर (अंतिम 1 को छोड़कर) के शब्दों की व्याख्या एक बहुपद के गुणांक के रूप में करते हैं (उदाहरण के लिए, ऑक्टाहेड्रॉन के लिए यह बहुपद f (x) = x3 + 6x2 + 12x + 8 देता है), तो h-वेक्टर बहुपद h (x) = f (x−1) (फिर से, ऑक्टाहेड्रॉन के लिए, h (x) = x3 + 3x2 + 3x + 1) के गुणांक को सूचीबद्ध करता है। जैसा कि ज़िगलर लिखते हैं, "सरल पॉलीटोप के बारे में विभिन्न समस्याओं के लिए, एच-वेक्टर चेहरे की संख्याओं के बारे में जानकारी को एन्कोड करने के लिए एफ-वेक्टर की तुलना में बहुत अधिक सुविधाजनक और संक्षिप्त तरीका है।" समानताएं और असमानताएं एक पॉलीटोप के एफ-वेक्टर के गुणांकों के बीच सबसे महत्वपूर्ण संबंध यूलर का सूत्र एस (−1) आई. एफ. आई = 0 है, जहां विस्तारित एफ-वेक्टर के गुणांक पर योग सीमा की शर्तें हैं। तीन आयामों में, विस्तारित f-वेक्टर (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-आयामी पूर्णांक सदिश जो इन समानताओं और असमानताओं को संतुष्ट करता है, एक उत्तल पॉलीहेड्रॉन का f-सदिश है। उच्च आयामों में, एक पॉलीटोप के चेहरों की संख्या के बीच अन्य संबंध भी महत्वपूर्ण हो जाते हैं, जिसमें डेहन-सोमरविले समीकरण शामिल हैं, जिन्हें सरल पॉलीटोप के एच-वेक्टर के संदर्भ में व्यक्त किया जाता है, सभी के के लिए सरल रूप एचके = एचडी-के लेते हैं। के = 0 के साथ इन समीकरणों का उदाहरण यूलर के सूत्र के बराबर है लेकिन डी> 3 के लिए इन समीकरणों के अन्य उदाहरण एक दूसरे से रैखिक रूप से स्वतंत्र हैं और एच-वेक्टर (और इसलिए एफ-वेक्टर) को अतिरिक्त तरीकों से बाधित करते हैं। पॉलीटोप फेस काउंट पर एक और महत्वपूर्ण असमानता ऊपरी बाध्य प्रमेय द्वारा दी गई है, जो पहले द्वारा सिद्ध की गई है, जिसमें कहा गया है कि n शीर्षों के साथ एक डी-आयामी पॉलीटोप में किसी भी अन्य आयाम के उतने ही चेहरे हो सकते हैं जितने एक पड़ोसी पॉलीटोप में समान संख्या में शीर्ष हो सकते हैंः जहां तारांकन का अर्थ है कि योग का अंतिम पद तब आधा किया जाना चाहिए जब d सम हो। लक्षणहीन रूप से, इसका तात्पर्य है कि सभी आयामों के अधिकांश चेहरे हैं। यहाँ तक कि चार आयामों में भी, उत्तल बहुपदों के संभावित f-सदिशों का समूह चार-आयामी पूर्णांक जाली का उत्तल उपसमुच्चय नहीं बनाता है, और इन सदिशों के संभावित मूल्यों के बारे में बहुत कुछ अज्ञात है। ग्राफ-सैद्धांतिक गुण पॉलीटोप के चेहरों की संख्या की जांच करने के साथ-साथ, शोधकर्ताओं ने उनके अन्य संयुक्त गुणों का अध्ययन किया है, जैसे कि पॉलीटोप के शीर्ष और किनारों (उनके 1-कंकाल) से प्राप्त ग्राफ का विवरण। बालिंस्की के प्रमेय में कहा गया है कि किसी भी डी-आयामी उत्तल पॉलीटोप से इस तरह से प्राप्त ग्राफ डी-वर्टेक्स से जुड़ा हुआ है। त्रि-आयामी पॉलीहेड्रा के मामले में, इस गुण और समतलीयता का उपयोग पॉलीहेड्रा के ग्राफ को सटीक रूप से चिह्नित करने के लिए किया जा सकता हैः स्टेनिट्ज़ के प्रमेय में कहा गया है कि जी एक त्रि-आयामी पॉलीहेड्रॉन का कंकाल है यदि और केवल तभी जब जी एक 3-वर्टेक्स से जुड़ा समतलीय ग्राफ है। एक प्रमेय (पहले माइक पेरल्स द्वारा अनुमानित) में कहा गया है कि कोई भी अपने ग्राफ से एक साधारण पॉलीटोप की चेहरे की संरचना का पुनर्निर्माण कर सकता है। अर्थात्, यदि दिया गया दिशाहीन ग्राफ एक साधारण पॉलीटोप का कंकाल है, तो केवल एक पॉलीटोप (संयोजन समतुल्यता तक) है जिसके लिए यह सच है। यह (गैर-सरल) पड़ोसी पॉलीटोप के विपरीत है जिसका ग्राफ एक पूर्ण ग्राफ है; एक ही ग्राफ के लिए कई अलग-अलग पड़ोसी पॉलीटोप हो सकते हैं। अद्वितीय सिंक अभिविन्यास पर आधारित इस प्रमेय का एक और प्रमाण उनके द्वारा दिया गया था, और दिखाया गया था कि इस प्रमेय का उपयोग उनके ग्राफ से सरल पॉलीटोप के चेहरे के जाली के पुनर्निर्माण के लिए एक बहुपद समय एल्गोरिथ्म प्राप्त करने के लिए कैसे किया जाए। हालांकि, यह परीक्षण करना कि क्या किसी दिए गए ग्राफ या जाली को एक साधारण पॉलीटोप के चेहरे की जाली के रूप में महसूस किया जा सकता है, सरल पॉलीटोप की प्राप्ति के बराबर (ध्रुवीयता द्वारा) है, जिसे वास्तविक रूप से अस्तित्व के सिद्धांत के लिए पूर्ण दिखाया गया था। रैखिक प्रोग्रामिंग के लिए सिम्प्लेक्स विधि के संदर्भ में, एक पॉलीटोप के व्यास को समझना महत्वपूर्ण है, किसी भी अन्य शीर्ष से पथ द्वारा किसी भी शीर्ष तक पहुंचने के लिए आवश्यक किनारों की न्यूनतम संख्या। एक रैखिक कार्यक्रम की रैखिक असमानताओं की प्रणाली एक पॉलीटोप के पहलुओं को परिभाषित करती है जो कार्यक्रम के सभी व्यवहार्य समाधानों का प्रतिनिधित्व करती है, और सिम्प्लेक्स विधि इस पॉलीटोप में एक पथ का पालन करके इष्टतम समाधान पाती है। इस प्रकार, व्यास इस विधि के लिए आवश्यक चरणों की संख्या पर एक निचली सीमा प्रदान करता है। हिर्श अनुमान, जिसे अब अस्वीकार कर दिया गया है, ने एक मजबूत (रैखिक) सीमा का सुझाव दिया कि निश्चित आयाम और पहलुओं की संख्या के साथ एक पॉलीटोप का व्यास कितना बड़ा हो सकता है। उनके व्यास पर कमजोर (अर्ध-बहुपद और) ऊपरी सीमाएँ ज्ञात हैं, साथ ही पॉलीटोप के विशेष वर्गों के लिए हिर्श अनुमान के प्रमाण भी ज्ञात हैं। कम्प्यूटेशनल गुण यह तय करना कि क्या किसी दिए गए पॉलीटोप के शीर्षों की संख्या कुछ प्राकृतिक संख्या k से घिरी हुई है, एक कम्प्यूटेशनल रूप से कठिन समस्या है और जटिलता वर्ग पीपी के लिए पूर्ण है। 0-1 पॉलीटोप के पहलू पूर्णांक प्रोग्रामिंग के लिए कटिंग-प्लेन विधियों के संदर्भ में यह महत्वपूर्ण है कि वे पॉलीटोप के पहलुओं का सटीक वर्णन करने में सक्षम हों जिनमें संयोजन अनुकूलन समस्याओं के समाधान के अनुरूप शीर्ष हों। अक्सर, इन समस्याओं के समाधान होते हैं जिन्हें द्विआधारी वैक्टर द्वारा वर्णित किया जा सकता है, और संबंधित पॉलीटोप में शीर्ष निर्देशांक होते हैं जो सभी शून्य या एक होते हैं। एक उदाहरण के रूप में, बिरखॉफ पॉलीटोप पर विचार करें, एन × एन मैट्रिक्स का सेट जो क्रमपरिवर्तन मैट्रिक्स के उत्तल संयोजन से बनाया जा सकता है। समान रूप से, इसके शीर्षों को एक पूर्ण द्विदलीय ग्राफ में सभी सही मिलानों का वर्णन करने के रूप में सोचा जा सकता है, और इस पॉलीटोप पर एक रैखिक अनुकूलन समस्या को द्विदलीय न्यूनतम वजन सही मिलान समस्या के रूप में व्याख्या की जा सकती है। बिरखॉफ-वॉन न्यूमैन प्रमेय बताता है कि इस पॉलीटोप को दो प्रकार की रैखिक असमानता या समानता द्वारा वर्णित किया जा सकता है। सबसे पहले, प्रत्येक मैट्रिक्स सेल के लिए, एक बाधा है कि इस सेल का एक गैर-नकारात्मक मूल्य है। और दूसरा, मैट्रिक्स की प्रत्येक पंक्ति या कॉलम के लिए, एक बाधा है कि उस पंक्ति या कॉलम में कोशिकाओं का योग एक के बराबर है। पंक्ति और स्तंभ बाधाएं आयाम n2−2n + 1 के एक रैखिक उपक्षेत्र को परिभाषित करती हैं जिसमें बिरखॉफ पॉलीटोप स्थित होता है, और गैर-नकारात्मकता बाधाएं उस उपक्षेत्र के भीतर बिरखॉफ पॉलीटोप के पहलुओं को परिभाषित करती हैं। हालांकि, बिरखॉफ पॉलीटोप असामान्य है क्योंकि इसके पहलुओं का पूरा विवरण उपलब्ध है। कई अन्य 0-1 पॉलीटोप के लिए, तेजी से कई या सुपरएक्सपोनेंशियल रूप से कई पहलू हैं, और उनके पहलुओं का केवल आंशिक विवरण उपलब्ध है। एब्स्ट्रैक्ट पॉलीटोप कॉम्बिनेटरियल कम्यूटेटिव अलजेब्रा मैट्रोइड पॉलीटोप ऑर्डर पॉलीटोप सिम्प्लिसियल स्फीयर स्टेबल मैचिंग पॉलीटोप नोट्स संदर्भ भी देखें। .. .. .. .. .. .. .. .. .. .. .. .. .. .. बाहरी लिंक।