हिर्श अनुमान: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (23 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
[[File:Icosidodecahedral graph.png|thumb|एक [[इकोसिडोडेकाहेड्रॉन]] का ग्राफ, एक उदाहरण जिसके लिए अनुमान सत्य है।]][[गणितीय प्रोग्रामिंग|गणितीय निर्माण]] और [[पॉलीहेड्रल कॉम्बिनेटरिक्स|बहुफलकीय साहचर्य]] में हिर्श अनुमान यह कथन है कि आयामी | [[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> जो संकेतन विधि के विश्लेषण के लिए सीधा परिणाम नहीं है क्योंकि यह रैखिक या बहुपद चरणों की संभावना से पीछे नहीं हटता। | ||
समस्या के समान सूत्र दिए गए थे जैसे कि डी-सीढ़ी जिसमें कहा गया है कि डी-आयामी यूक्लिड के नियमों के अनुरूप अंतरिक्ष में किसी भी | इसमें समस्या के समान सूत्र दिए गए थे जैसे कि डी-सीढ़ी जिसमें कहा गया है कि डी-आयामी यूक्लिड के नियमों के अनुरूप अंतरिक्ष में किसी भी 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>\delta(P)\leq n-d</math> | ||
उदाहरण के लिए तीन आयामों में एक घन के छह | उदाहरण के लिए तीन आयामों में एक घन के छह स्वरूप होते हैं हिर्श अनुमान तब संकेत करता है कि इस घन का व्यास तीन से अधिक नहीं हो सकता तथा अनुमान को स्वीकार करने का अर्थ यह होगा कि घन के किन्हीं दो सिरों को अधिकतम तीन चरणों का उपयोग करके पथ द्वारा जोड़ा जा सकता है वास्तव में 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 के स्वरूपों की संख्या है। | ||
== प्रगति और मध्यवर्ती परिणाम == | == प्रगति और मध्यवर्ती परिणाम == | ||
कई | कई घटनाओं में हिर्श अनुमान सही सिद्ध हुआ है जैसे कि आयाम 3 या उससे कम के बहुशीर्ष अनुमान को संतुष्ट करता है एन स्वरूपों के साथ कोई भी डी-आयामी बहुशीर्ष जैसे कि <math> n-d\leq 6 </math> अनुमान को भी संतुष्ट करता है<ref>{{harvtxt|Ziegler|1994}}</ref>अनुमान को हल करने के दूसरे प्रयास को हिर्श अनुमान लागू करेगा इसका एक महत्वपूर्ण उदाहरण डी-सीढ़ी अनुमान है तथा हिर्श अनुमान का एक अवशेष जो वास्तविक रूप से इसके समरूप दिखाया गया है | ||
अनुमान को हल करने के | |||
प्रमेय निम्नलिखित कथन समतुल्य हैं | |||
# <math>\delta(P)\leq n-d </math> सभी डी- | # <math>\delta(P)\leq n-d </math> सभी डी-आयामी बहुशीर्षों के लिए एन स्वरूपों के साथ P है। | ||
# <math>\delta(P)\leq d </math> सभी डी- | # <math>\delta(P)\leq d </math> सभी डी-आयामी बहुशीर्षों के लिए 2d स्वरूपों के साथ P है। | ||
दूसरे शब्दों में | दूसरे शब्दों में हिर्श अनुमान को सिद्ध करने या अस्वीकार करने के लिए बहुशीर्षों पर विचार करने की जरूरत है जो कि इसके आयाम के रूप में कई स्वरूप सिद्ध हैं तथा इसमें एक महत्वपूर्ण तथ्य यह है कि हिर्श अनुमान सभी बहुशीर्षों के लिए मान्य है और यह सभी सरल बहुशीर्षों के लिए है।<ref>{{harvtxt|Ziegler|1994}}</ref> | ||
== प्रति उदाहरण == | == प्रति उदाहरण == | ||
[[File:Octahedron.jpg|thumb|[[अष्टफलक]] धुरी के सबसे प्रसिद्ध उदाहरणों में से एक है।]] | [[File:Octahedron.jpg|thumb|[[अष्टफलक]] धुरी के सबसे प्रसिद्ध उदाहरणों में से एक है।]]हिर्श अनुमान सभी घटनाओं में सही नहीं है जैसा कि 2011 में फ्रांसिस्को वितरण द्वारा दिखाया गया था कि वितरण का विरोध करना इसका मुख्य उदाहरण है तथा हिर्श अनुमान को केवल सरल बहुशीर्ष पर विचार करने के लिए आराम दिया जा सकता है अब हिर्श अनुमान के बीच समानता और डी-सीढ़ी <ref>{{harvtxt|Santos|2011}}</ref> विशेष रूप से वितरण धुरी नामक बहुशीर्षों के एक विशेष वर्ग की जांच करके अपना प्रति उदाहरण प्रस्तुत करता है। | ||
परिभाषा में एक डी-धुरी और एक डी-आकार बहुशीर्ष हैं जिसमें <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> डी-सीढ़ी अनुमान का उल्लंघन करता है | |||
वितरण लंबाई 6 के साथ एक 5-आयामी धुरी का निर्माण करने के लिए आगे बढ़ता है जिससे यह सिद्ध होता है कि एक और धुरी एकत्र है जो हिर्श अनुमान के प्रतिरूप के रूप में कार्य करती है इन दो धुरी में पहले 48 स्वरूप और 322 कोने हैं जबकि अनुमान को रद्द करने वाले तर्क में 86 स्वरूप हैं और 43-कोने हैं यह उदाहरण बहुपद हिर्श अनुमान का निराकरण नहीं करता है जो एक खुली समस्या बनी हुई है।<ref>{{harvtxt|Santos|2011}}</ref> | |||
| Line 59: | Line 58: | ||
{{Disproved conjectures}} | {{Disproved conjectures}} | ||
[[Category:Collapse templates]] | |||
[[Category: | |||
[[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]अनुमान को हल करने के दूसरे प्रयास को हिर्श अनुमान लागू करेगा इसका एक महत्वपूर्ण उदाहरण डी-सीढ़ी अनुमान है तथा हिर्श अनुमान का एक अवशेष जो वास्तविक रूप से इसके समरूप दिखाया गया है
प्रमेय निम्नलिखित कथन समतुल्य हैं
- सभी डी-आयामी बहुशीर्षों के लिए एन स्वरूपों के साथ P है।