हिर्श अनुमान: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(17 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[File:Icosidodecahedral graph.png|thumb|एक [[इकोसिडोडेकाहेड्रॉन]] का ग्राफ, एक उदाहरण जिसके लिए अनुमान सत्य है।]][[गणितीय प्रोग्रामिंग|गणितीय निर्माण]] और [[पॉलीहेड्रल कॉम्बिनेटरिक्स|बहुफलकीय साहचर्य]] में हिर्श अनुमान यह कथन है कि आयामी   यूक्लिड के नियमों के अनुरूप अंतरिक्ष में एन-स्वरूप पॉलीटॉप के किनारा-शिखर लेखाचित्र का व्यास n - d से अधिक नहीं है''अर्थात् पॉलीटॉप के किन्हीं भी दो शीर्षों को  n-d लंबाई के पथ द्वारा एक-दूसरे से जोड़ा जाना चाहिए अनुमान पहली  बार 1957 में वॉरेन एम हिर्श द्वारा तथा डेंटजिंग को जॉर्ज बी द्वारा एक पत्र में प्रस्तुत किया गया था <ref name="z84" /><ref>{{harvtxt|Dantzig|1963}}, pp. 160 and 168.</ref> [[रैखिक प्रोग्रामिंग|रैखिक निर्माण]] संकेतन विधि के विश्लेषण से प्रेरित था क्योंकि पॉलीटॉप एक व्यास के रूप में संकेतन विधि द्वारा आवश्यक चरणों की संख्या पर एक निचली सीमा प्रदान करता है अब यह अनुमान सामान्य रूप से झूठा माना जाता है।''
[[File:Icosidodecahedral graph.png|thumb|एक [[इकोसिडोडेकाहेड्रॉन]] का ग्राफ, एक उदाहरण जिसके लिए अनुमान सत्य है।]][[गणितीय प्रोग्रामिंग|गणितीय निर्माण]] और [[पॉलीहेड्रल कॉम्बिनेटरिक्स|बहुफलकीय साहचर्य]] में हिर्श अनुमान यह कथन यह है कि आयामी यूक्लिड के नियमों के अनुरूप अंतरिक्ष में एन-स्वरूप बहुशीर्ष के किनारे-शिखर लेखाचित्र का व्यास n - d से अधिक नहीं है''अर्थात् बहुशीर्ष के किन्हीं दो सिरों को  n-d लंबाई के पथ द्वारा एक-दूसरे से जोड़ा जाना चाहिए तथा पहली  बार 1957 में वॉरेन एम हिर्श द्वारा तथा काट के निशान को को जॉर्ज बी द्वारा एक पत्र में प्रस्तुत किया गया था <ref name="z84" /><ref>{{harvtxt|Dantzig|1963}}, pp. 160 and 168.</ref>जो [[रैखिक प्रोग्रामिंग|रैखिक निर्माण]] संकेतन विधि के विश्लेषण से प्रेरित था क्योंकि इसमें बहुशीर्ष एक व्यास के रूप में संकेतन विधि द्वारा आवश्यक चरणों की संख्या पर एक निचली सीमा प्रदान करता है और यह अनुमान सामान्य रूप से गलत माना जाता है।''


हिर्श अनुमान डी विशेष मामलों के लिए सिद्ध किया गया था<ref>E.g. see {{harvtxt|Naddef|1989}} for 0-1 polytopes.</ref> जबकि व्यास पर ज्ञात की गईं ऊपरी सीमाएं n और d उप-घातीय हैं<ref>{{harvtxt|Kalai|Kleitman|1992}}.</ref> पचास से अधिक वर्षों के बाद कैंटब्रिया विश्वविद्यालय से [[फ्रांसिस्को सैंटोस लील]] द्वारा मई 2010 में एक प्रति-उदाहरण की घोषणा की गई <ref name=disproved>{{harvtxt|Santos|2011}}.</ref><ref name=Kalai-blog-Hirsch>{{harvtxt|Kalai|2010}}.</ref><ref>{{citation|url=http://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refuta-la-conjetura-de-hirsch/|title=Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch|website=Gaussianos|date=May 24, 2010}}</ref> जिसका परिणाम सिएटल में 100 साल के सम्मेलन में प्रस्तुत किया गया था [[विक्टर क्ले]] और ब्रैंको ग्रुनबाम का गणित, [[गणित के इतिहास]] में दिखाई दिया<ref>{{harvtxt|Santos|2011}}</ref> संकेतन विधि के विश्लेषण के लिए कोई सीधा परिणाम नहीं है क्योंकि यह बड़े लेकिन फिर भी रैखिक या बहुपद चरणों की संभावना से इंकार नहीं करता।
हिर्श अनुमान डी विशेष घटनाओं के लिए सिद्ध किया गया था<ref>E.g. see {{harvtxt|Naddef|1989}} for 0-1 polytopes.</ref> जबकि व्यास पर ज्ञात की गईं ऊपरी सीमाएं n और d उप-घातीय हैं<ref>{{harvtxt|Kalai|Kleitman|1992}}.</ref> तथा पचास वर्षों के बाद कैंटब्रिया विश्वविद्यालय से [[फ्रांसिस्को सैंटोस लील]] द्वारा मई 2010 में एक प्रति-उदाहरण की घोषणा की गई <ref name=disproved>{{harvtxt|Santos|2011}}.</ref><ref name=Kalai-blog-Hirsch>{{harvtxt|Kalai|2010}}.</ref><ref>{{citation|url=http://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refuta-la-conjetura-de-hirsch/|title=Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch|website=Gaussianos|date=May 24, 2010}}</ref> जिसका परिणाम सिएटल में 100 साल के सम्मेलन में प्रस्तुत किया गया था [[विक्टर क्ले|सदिश राशि]] और ब्रैंको ग्रुनबाम का [[गणित के इतिहास|गणित इतिहास]] में दिखाई दिया<ref>{{harvtxt|Santos|2011}}</ref> जो संकेतन विधि के विश्लेषण के लिए सीधा परिणाम नहीं है क्योंकि यह रैखिक या बहुपद चरणों की संभावना से पीछे नहीं हटता।


समस्या के समान सूत्र दिए गए थे जैसे कि डी-सीढ़ी जिसमें कहा गया है कि डी-आयामी यूक्लिड के नियमों के अनुरूप अंतरिक्ष में किसी भी 2डी-स्वरूप पॉलीटॉप का व्यास डी से अधिक नहीं है सैंटोस लील का प्रत्युत्तर भी इस अनुमान का खंडन करता है।<ref name="z84">{{harvtxt|Ziegler|1994}}, p. 84.</ref><ref name="d-step">{{harvtxt|Klee|Walkup|1967}}.</ref>
इसमें समस्या के समान सूत्र दिए गए थे जैसे कि डी-सीढ़ी जिसमें कहा गया है कि डी-आयामी यूक्लिड के नियमों के अनुरूप अंतरिक्ष में किसी भी 2 डी-स्वरूप ''बहुशीर्ष'' का व्यास डी से अधिक नहीं है सैंटोस लील का प्रत्युत्तर भी इस अनुमान का खंडन करता है।<ref name="z84">{{harvtxt|Ziegler|1994}}, p. 84.</ref><ref name="d-step">{{harvtxt|Klee|Walkup|1967}}.</ref>




== अनुमान का कथन ==
== अनुमान का कथन ==


उत्तल पॉलीटोप का एक ग्राफ <math>P</math> है जिसमें <math>P</math> के किन्हीं दो शीर्षों को एक किनारे से जोड़ा जाता है और यदि दो संगत शीर्ष <math>P</math> पॉलीटॉप के किनारे से जुड़े हुए हैं तो उनका व्यास <math>P</math> निरूपित होता है <math>\delta(P)</math> भी एक ग्राफ का व्यास है ये परिभाषाएँ [[अच्छी तरह से परिभाषित]] हैं क्योंकि एक ही पॉलीटॉप के किसी भी दो ग्राफ को ग्राफ के रूप में आइसोमोर्फिज़्म होना चाहिए हम तब हिर्श अनुमान को इस प्रकार बता सकते हैं
उत्तल ''बहुशीर्ष'' का एक ग्राफ <math>P</math> है जिसमें <math>P</math> के किन्हीं दो सिरों को एक सिरे से जोड़ा जाता है और यदि दो संगत सिरे <math>P</math> बहुशीर्ष के सिरे से जुड़े हुए हैं तो उनका व्यास <math>P</math> निरूपित होता है <math>\delta(P)</math> भी एक ग्राफ का व्यास है ये परिभाषाएँ [[अच्छी तरह से परिभाषित]] हैं क्योंकि एक ही ''बहुशीर्ष'' के किसी भी दो ग्राफ को ग्राफ के रूप में समरूपतावादी होना चाहिए तब हम हिर्श के अनुमान को इस प्रकार बता सकते हैं


अनुमान <math>P</math> एन स्वरूपों के साथ एक डी-आयामी उत्तल पॉलीटॉप हो तब <math>\delta(P)\leq n-d</math>
अनुमान <math>P</math> एन स्वरूपों के साथ एक डी-आयामी उत्तल ''बहुशीर्ष'' हो तब <math>\delta(P)\leq n-d</math>


उदाहरण के लिए तीन आयामों में एक घन के छह स्वरूप होते हैं हिर्श अनुमान तब संकेत करता है कि इस घन का व्यास तीन से अधिक नहीं हो सकता अनुमान को स्वीकार करने का अर्थ यह होगा कि घन के किन्हीं भी दो सिरों को अधिकतम तीन चरणों का उपयोग करके पथ द्वारा जोड़ा जा सकता है वास्तव में 8 आयाम वाले सभी पॉलीटॉप के लिए यह सीमा अनुकूल है आयाम का कोई पॉलिटॉप नहीं है <math>d\geq 8</math> का व्यास n-d से कम है n पहले की तरह इसके स्वरूपों की संख्या है<ref>{{harvtxt|Ziegler|1994}}</ref> सभी घटनाओं के लिए अनुमान अपने किनारों के साथ एक पथ द्वारा पॉलीटोप के किन्हीं दो सिरों को जोड़ने के लिए आवश्यक चरणों की न्यूनतम संख्या प्रदान करता है क्योंकि सरल विधि अनिवार्य रूप से व्यवहार्य क्षेत्र के अनुकूल बिंदु तक पथ का निर्माण करके संचालित होती है इसलिए हिर्श अनुमान खराब स्थिति भू-दृश्य में समाप्त करने के लिए एक सरल विधि के लिए निम्न सीमा प्रदान करेगा
उदाहरण के लिए तीन आयामों में एक घन के छह स्वरूप होते हैं हिर्श अनुमान तब संकेत करता है कि इस घन का व्यास तीन से अधिक नहीं हो सकता तथा अनुमान को स्वीकार करने का अर्थ यह होगा कि घन के किन्हीं दो सिरों को अधिकतम तीन चरणों का उपयोग करके पथ द्वारा जोड़ा जा सकता है वास्तव में 8 आयाम वाले सभी बहुशीर्ष के लिए यह सीमा अनुकूल है आयाम का कोई बहुशीर्ष नहीं है <math>d\geq 8</math> का व्यास n-d से कम है n पहले की तरह इसके स्वरूपों की संख्या है<ref>{{harvtxt|Ziegler|1994}}</ref> इसमें सभी घटनाओं के लिए अनुमान अपने किनारों के साथ एक पथ द्वारा बहुशीर्ष के किन्हीं दो सिरों को जोड़ने के लिए आवश्यक चरणों की न्यूनतम संख्या प्रदान करता है क्योंकि यह सरल विधि अनिवार्य रूप से व्यवहार क्षेत्र के अनुकूल बिंदु तक पथ का निर्माण करके संचालित होती है इसलिए हिर्श अनुमान खराब स्थिति भू-दृश्य में समाप्त करने के लिए एक सरल विधि के लिए निम्न सीमा प्रदान करता है।


हिर्श अनुमान बहुपद हिर्श अनुमान की एक विशेष घटना है जो दावा करता है कि कुछ सकारात्मक पूर्णांक k जो कि सभी बहुपदों के लिए <math>P</math> <math>\delta(P)=O(n^k)</math> जहाँ n, P के स्वरूपों की संख्या है।
हिर्श अनुमान बहुपद एक विशेष घटना है जो यह बताता है कि कुछ सकारात्मक पूर्णांक k जो कि सभी बहुपदों के लिए <math>P</math> <math>\delta(P)=O(n^k)</math> जहाँ n, P के स्वरूपों की संख्या है।


== प्रगति और मध्यवर्ती परिणाम ==
== प्रगति और मध्यवर्ती परिणाम ==


कई घटनाओं में हिर्श अनुमान सही सिद्ध हुआ है जैसे कि आयाम 3 या उससे कम के पॉलीटॉप अनुमान को संतुष्ट करता है एन स्वरूपों के साथ कोई भी डी-आयामी पॉलीटॉप जैसे कि <math> n-d\leq 6 </math> अनुमान को भी संतुष्ट करता है<ref>{{harvtxt|Ziegler|1994}}</ref>अनुमान को हल करने के दूसरे प्रयास को हिर्श अनुमान लागू करेगा  इसका एक महत्वपूर्ण उदाहरण डी-सीढ़ी अनुमान है हिर्श अनुमान का एक अवशेष जो वास्तविक रूप से इसके समरूप दिखाया गया है
कई घटनाओं में हिर्श अनुमान सही सिद्ध हुआ है जैसे कि आयाम 3 या उससे कम के बहुशीर्ष अनुमान को संतुष्ट करता है एन स्वरूपों के साथ कोई भी डी-आयामी बहुशीर्ष जैसे कि <math> n-d\leq 6 </math> अनुमान को भी संतुष्ट करता है<ref>{{harvtxt|Ziegler|1994}}</ref>अनुमान को हल करने के दूसरे प्रयास को हिर्श अनुमान लागू करेगा  इसका एक महत्वपूर्ण उदाहरण डी-सीढ़ी अनुमान है तथा हिर्श अनुमान का एक अवशेष जो वास्तविक रूप से इसके समरूप दिखाया गया है


'प्रमेय' निम्नलिखित कथन समतुल्य हैं
प्रमेय निम्नलिखित कथन समतुल्य हैं
# <math>\delta(P)\leq n-d </math> सभी डी-आयामी पॉलीटोप्स के लिए एन स्वरूपों के साथ P
# <math>\delta(P)\leq n-d </math> सभी डी-आयामी बहुशीर्षों के लिए एन स्वरूपों के साथ P है।
# <math>\delta(P)\leq d </math> सभी डी-आयामी पॉलीटोप्स के लिए 2d स्वरूपों के साथ P
# <math>\delta(P)\leq d </math> सभी डी-आयामी बहुशीर्षों के लिए 2d स्वरूपों के साथ P है।


दूसरे शब्दों में, हिर्श अनुमान को साबित करने या अस्वीकार करने के लिए, किसी को केवल पॉलीटोप्स पर विचार करने की जरूरत है, जो इसके आयाम के रूप में दो बार कई पहलुओं के साथ है। एक और महत्वपूर्ण छूट यह है कि हिर्श अनुमान सभी पॉलीटॉप्स के लिए है अगर और केवल अगर यह सभी सरल पॉलीटॉप्स के लिए है।<ref>{{harvtxt|Ziegler|1994}}</ref>
दूसरे शब्दों में हिर्श अनुमान को सिद्ध करने या अस्वीकार करने के लिए बहुशीर्षों पर विचार करने की जरूरत है जो कि इसके आयाम के रूप में कई स्वरूप सिद्ध हैं तथा इसमें एक महत्वपूर्ण तथ्य यह है कि हिर्श अनुमान सभी बहुशीर्षों के लिए मान्य है और यह सभी सरल बहुशीर्षों के लिए है।<ref>{{harvtxt|Ziegler|1994}}</ref>




== प्रति उदाहरण ==
== प्रति उदाहरण ==


[[File:Octahedron.jpg|thumb|[[अष्टफलक]] धुरी के सबसे प्रसिद्ध उदाहरणों में से एक है।]]दुर्भाग्य से, हिर्श अनुमान सभी मामलों में सही नहीं है, जैसा कि 2011 में फ्रांसिस्को सैंटोस द्वारा दिखाया गया था। सैंटोस का काउंटर उदाहरण का स्पष्ट निर्माण इस तथ्य से दोनों आता है कि अनुमान को केवल सरल पॉलीटोप्स पर विचार करने के लिए आराम दिया जा सकता है, और हिर्श के बीच समानता से और डी-स्टेप अनुमान।<ref>{{harvtxt|Santos|2011}}</ref> विशेष रूप से सैंटोस स्पिंडल नामक पॉलीटोप्स के एक विशेष वर्ग की जांच करके अपना प्रति उदाहरण प्रस्तुत करता है।
[[File:Octahedron.jpg|thumb|[[अष्टफलक]] धुरी के सबसे प्रसिद्ध उदाहरणों में से एक है।]]हिर्श अनुमान सभी घटनाओं में सही नहीं है जैसा कि 2011 में फ्रांसिस्को वितरण द्वारा दिखाया गया था कि वितरण का विरोध करना इसका मुख्य उदाहरण है तथा हिर्श अनुमान को केवल सरल बहुशीर्ष पर विचार करने के लिए आराम दिया जा सकता है अब हिर्श अनुमान के बीच समानता और डी-सीढ़ी <ref>{{harvtxt|Santos|2011}}</ref> विशेष रूप से वितरण धुरी नामक बहुशीर्षों के एक विशेष वर्ग की जांच करके अपना प्रति उदाहरण प्रस्तुत करता है।


'परिभाषा' एक डी-स्पिंडल एक डी-आयामी पॉलीटोप है <math>P</math> जिसके लिए अलग-अलग शीर्षों की एक जोड़ी मौजूद है जैसे कि हर पहलू <math>P</math> इन दो शीर्षों में से ठीक एक शामिल है।
परिभाषा में एक डी-धुरी और एक डी-आकार बहुशीर्ष हैं जिसमें <math>P</math> के लिए अलग-अलग सिरों की एक जोड़ी सम्मिलित है जैसे कि हर स्वरूप में <math>P</math> इन दो सिरों में से एक में सम्मिलित है


इन दो शीर्षों के बीच के सबसे छोटे पथ की लंबाई को धुरी की लंबाई कहा जाता है। हिर्श अनुमान का खंडन निम्नलिखित प्रमेय पर निर्भर करता है, जिसे स्पिंडल के लिए मजबूत डी-स्टेप प्रमेय कहा जाता है।
इन दो सिरों के बीच के सबसे छोटे पथ की लंबाई को धुरी की लंबाई कहा जाता है हिर्श अनुमान का निराकरण निम्नलिखित प्रमेय पर निर्भर करता है धुरी को मजबूत डी-सीढ़ी प्रमेय कहा जाता है।


'प्रमेय (सैंटोस)' चलो <math>P</math> एक डी-धुरी हो। मान लीजिए n इसके फलकों की संख्या है, और l इसकी लंबाई है। फिर एक मौजूद है <math>(n-d)</math>-धुरी, <math>P'</math>, साथ <math>2n-2d</math> पहलू और लंबाई नीचे से घिरी हुई है <math>l+n-2d</math>. विशेष रूप से, अगर <math>l>d</math>, तब <math>P'</math> डी-स्टेप अनुमान का उल्लंघन करता है।
माना <math>P</math> एक डी-धुरी हो n इसके फलकों की संख्या है और l इसकी लंबाई है तो <math>(n-d)</math>धुरी <math>P'</math> के साथ और <math>2n-2d</math> स्वरूप की लंबाई नीचे से घिरी हुई है <math>l+n-2d</math> विशेष रूप से अगर <math>l>d</math>, तब <math>P'</math> डी-सीढ़ी अनुमान का उल्लंघन करता है


सैंटोस फिर लंबाई 6 के साथ एक 5-आयामी धुरी का निर्माण करने के लिए आगे बढ़ता है, जिससे यह साबित होता है कि एक और धुरी मौजूद है जो हिर्श अनुमान के प्रतिरूप के रूप में कार्य करता है। इन दो तकुओं में से पहले में 48 पहलू और 322 कोने हैं, जबकि अनुमान को वास्तव में खारिज करने वाले तर्कु में 86 पहलू हैं और यह 43-आयामी है। यह प्रति उदाहरण बहुपद हिर्श अनुमान का खंडन नहीं करता है, जो एक खुली समस्या बनी हुई है।<ref>{{harvtxt|Santos|2011}}</ref>
वितरण लंबाई 6 के साथ एक 5-आयामी धुरी का निर्माण करने के लिए आगे बढ़ता है जिससे यह सिद्ध होता है कि एक और धुरी एकत्र है जो हिर्श अनुमान के प्रतिरूप के रूप में कार्य करती है इन दो धुरी में पहले 48 स्वरूप और 322 कोने हैं जबकि अनुमान को रद्द करने वाले तर्क में 86 स्वरूप हैं और 43-कोने हैं यह उदाहरण बहुपद हिर्श अनुमान का निराकरण नहीं करता है जो एक खुली समस्या बनी हुई है।<ref>{{harvtxt|Santos|2011}}</ref>




Line 58: Line 58:


{{Disproved conjectures}}
{{Disproved conjectures}}
[[Category: पॉलीहेड्रल कॉम्बिनेटरिक्स]] [[Category: अनुमान]] [[Category: अस्वीकृत अनुमान]] [[Category: रैखिक प्रोग्रामिंग]]


 
[[Category:Collapse templates]]
 
[[Category: Machine Translated Page]]
[[Category:Created On 01/05/2023]]
[[Category:Created On 01/05/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:अनुमान]]
[[Category:अस्वीकृत अनुमान]]
[[Category:पॉलीहेड्रल कॉम्बिनेटरिक्स]]
[[Category:रैखिक प्रोग्रामिंग]]

Latest revision as of 12:07, 18 May 2023

एक इकोसिडोडेकाहेड्रॉन का ग्राफ, एक उदाहरण जिसके लिए अनुमान सत्य है।

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

हिर्श अनुमान डी विशेष घटनाओं के लिए सिद्ध किया गया था[3] जबकि व्यास पर ज्ञात की गईं ऊपरी सीमाएं n और d उप-घातीय हैं[4] तथा पचास वर्षों के बाद कैंटब्रिया विश्वविद्यालय से फ्रांसिस्को सैंटोस लील द्वारा मई 2010 में एक प्रति-उदाहरण की घोषणा की गई [5][6][7] जिसका परिणाम सिएटल में 100 साल के सम्मेलन में प्रस्तुत किया गया था सदिश राशि और ब्रैंको ग्रुनबाम का गणित इतिहास में दिखाई दिया[8] जो संकेतन विधि के विश्लेषण के लिए सीधा परिणाम नहीं है क्योंकि यह रैखिक या बहुपद चरणों की संभावना से पीछे नहीं हटता।

इसमें समस्या के समान सूत्र दिए गए थे जैसे कि डी-सीढ़ी जिसमें कहा गया है कि डी-आयामी यूक्लिड के नियमों के अनुरूप अंतरिक्ष में किसी भी 2 डी-स्वरूप बहुशीर्ष का व्यास डी से अधिक नहीं है सैंटोस लील का प्रत्युत्तर भी इस अनुमान का खंडन करता है।[1][9]


अनुमान का कथन

उत्तल बहुशीर्ष का एक ग्राफ है जिसमें के किन्हीं दो सिरों को एक सिरे से जोड़ा जाता है और यदि दो संगत सिरे बहुशीर्ष के सिरे से जुड़े हुए हैं तो उनका व्यास निरूपित होता है भी एक ग्राफ का व्यास है ये परिभाषाएँ अच्छी तरह से परिभाषित हैं क्योंकि एक ही बहुशीर्ष के किसी भी दो ग्राफ को ग्राफ के रूप में समरूपतावादी होना चाहिए तब हम हिर्श के अनुमान को इस प्रकार बता सकते हैं

अनुमान एन स्वरूपों के साथ एक डी-आयामी उत्तल बहुशीर्ष हो तब

उदाहरण के लिए तीन आयामों में एक घन के छह स्वरूप होते हैं हिर्श अनुमान तब संकेत करता है कि इस घन का व्यास तीन से अधिक नहीं हो सकता तथा अनुमान को स्वीकार करने का अर्थ यह होगा कि घन के किन्हीं दो सिरों को अधिकतम तीन चरणों का उपयोग करके पथ द्वारा जोड़ा जा सकता है वास्तव में 8 आयाम वाले सभी बहुशीर्ष के लिए यह सीमा अनुकूल है आयाम का कोई बहुशीर्ष नहीं है का व्यास n-d से कम है n पहले की तरह इसके स्वरूपों की संख्या है[10] इसमें सभी घटनाओं के लिए अनुमान अपने किनारों के साथ एक पथ द्वारा बहुशीर्ष के किन्हीं दो सिरों को जोड़ने के लिए आवश्यक चरणों की न्यूनतम संख्या प्रदान करता है क्योंकि यह सरल विधि अनिवार्य रूप से व्यवहार क्षेत्र के अनुकूल बिंदु तक पथ का निर्माण करके संचालित होती है इसलिए हिर्श अनुमान खराब स्थिति भू-दृश्य में समाप्त करने के लिए एक सरल विधि के लिए निम्न सीमा प्रदान करता है।

हिर्श अनुमान बहुपद एक विशेष घटना है जो यह बताता है कि कुछ सकारात्मक पूर्णांक k जो कि सभी बहुपदों के लिए जहाँ n, P के स्वरूपों की संख्या है।

प्रगति और मध्यवर्ती परिणाम

कई घटनाओं में हिर्श अनुमान सही सिद्ध हुआ है जैसे कि आयाम 3 या उससे कम के बहुशीर्ष अनुमान को संतुष्ट करता है एन स्वरूपों के साथ कोई भी डी-आयामी बहुशीर्ष जैसे कि अनुमान को भी संतुष्ट करता है[11]अनुमान को हल करने के दूसरे प्रयास को हिर्श अनुमान लागू करेगा इसका एक महत्वपूर्ण उदाहरण डी-सीढ़ी अनुमान है तथा हिर्श अनुमान का एक अवशेष जो वास्तविक रूप से इसके समरूप दिखाया गया है

प्रमेय निम्नलिखित कथन समतुल्य हैं

  1. सभी डी-आयामी बहुशीर्षों के लिए एन स्वरूपों के साथ P है।
  2. सभी डी-आयामी बहुशीर्षों के लिए 2d स्वरूपों के साथ P है।

दूसरे शब्दों में हिर्श अनुमान को सिद्ध करने या अस्वीकार करने के लिए बहुशीर्षों पर विचार करने की जरूरत है जो कि इसके आयाम के रूप में कई स्वरूप सिद्ध हैं तथा इसमें एक महत्वपूर्ण तथ्य यह है कि हिर्श अनुमान सभी बहुशीर्षों के लिए मान्य है और यह सभी सरल बहुशीर्षों के लिए है।[12]


प्रति उदाहरण

अष्टफलक धुरी के सबसे प्रसिद्ध उदाहरणों में से एक है।

हिर्श अनुमान सभी घटनाओं में सही नहीं है जैसा कि 2011 में फ्रांसिस्को वितरण द्वारा दिखाया गया था कि वितरण का विरोध करना इसका मुख्य उदाहरण है तथा हिर्श अनुमान को केवल सरल बहुशीर्ष पर विचार करने के लिए आराम दिया जा सकता है अब हिर्श अनुमान के बीच समानता और डी-सीढ़ी [13] विशेष रूप से वितरण धुरी नामक बहुशीर्षों के एक विशेष वर्ग की जांच करके अपना प्रति उदाहरण प्रस्तुत करता है।

परिभाषा में एक डी-धुरी और एक डी-आकार बहुशीर्ष हैं जिसमें के लिए अलग-अलग सिरों की एक जोड़ी सम्मिलित है जैसे कि हर स्वरूप में इन दो सिरों में से एक में सम्मिलित है

इन दो सिरों के बीच के सबसे छोटे पथ की लंबाई को धुरी की लंबाई कहा जाता है हिर्श अनुमान का निराकरण निम्नलिखित प्रमेय पर निर्भर करता है धुरी को मजबूत डी-सीढ़ी प्रमेय कहा जाता है।

माना एक डी-धुरी हो n इसके फलकों की संख्या है और l इसकी लंबाई है तो धुरी के साथ और स्वरूप की लंबाई नीचे से घिरी हुई है विशेष रूप से अगर , तब डी-सीढ़ी अनुमान का उल्लंघन करता है

वितरण लंबाई 6 के साथ एक 5-आयामी धुरी का निर्माण करने के लिए आगे बढ़ता है जिससे यह सिद्ध होता है कि एक और धुरी एकत्र है जो हिर्श अनुमान के प्रतिरूप के रूप में कार्य करती है इन दो धुरी में पहले 48 स्वरूप और 322 कोने हैं जबकि अनुमान को रद्द करने वाले तर्क में 86 स्वरूप हैं और 43-कोने हैं यह उदाहरण बहुपद हिर्श अनुमान का निराकरण नहीं करता है जो एक खुली समस्या बनी हुई है।[14]


टिप्पणियाँ

  1. 1.0 1.1 Ziegler (1994), p. 84.
  2. Dantzig (1963), pp. 160 and 168.
  3. E.g. see Naddef (1989) for 0-1 polytopes.
  4. Kalai & Kleitman (1992).
  5. Santos (2011).
  6. Kalai (2010).
  7. "Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch", Gaussianos, May 24, 2010
  8. Santos (2011)
  9. Klee & Walkup (1967).
  10. Ziegler (1994)
  11. Ziegler (1994)
  12. Ziegler (1994)
  13. Santos (2011)
  14. Santos (2011)


संदर्भ