हिर्श अनुमान: Difference between revisions
No edit summary |
No edit summary |
||
| 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डी-स्वरूप | समस्या के समान सूत्र दिए गए थे जैसे कि डी-सीढ़ी जिसमें कहा गया है कि डी-आयामी यूक्लिड के नियमों के अनुरूप अंतरिक्ष में किसी भी 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 आयाम वाले सभी | उदाहरण के लिए तीन आयामों में एक घन के छह स्वरूप होते हैं हिर्श अनुमान तब संकेत करता है कि इस घन का व्यास तीन से अधिक नहीं हो सकता अनुमान को स्वीकार करने का अर्थ यह होगा कि घन के किन्हीं भी दो सिरों को अधिकतम तीन चरणों का उपयोग करके पथ द्वारा जोड़ा जा सकता है वास्तव में 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 के स्वरूपों की संख्या है। | ||
| Line 18: | Line 18: | ||
== प्रगति और मध्यवर्ती परिणाम == | == प्रगति और मध्यवर्ती परिणाम == | ||
कई घटनाओं में हिर्श अनुमान सही सिद्ध हुआ है जैसे कि आयाम 3 या उससे कम के | कई घटनाओं में हिर्श अनुमान सही सिद्ध हुआ है जैसे कि आयाम 3 या उससे कम के बहुशीर्ष अनुमान को संतुष्ट करता है एन स्वरूपों के साथ कोई भी डी-आयामी बहुशीर्ष जैसे कि <math> n-d\leq 6 </math> अनुमान को भी संतुष्ट करता है<ref>{{harvtxt|Ziegler|1994}}</ref>अनुमान को हल करने के दूसरे प्रयास को हिर्श अनुमान लागू करेगा इसका एक महत्वपूर्ण उदाहरण डी-सीढ़ी अनुमान है हिर्श अनुमान का एक अवशेष जो वास्तविक रूप से इसके समरूप दिखाया गया है | ||
'प्रमेय' निम्नलिखित कथन समतुल्य हैं | 'प्रमेय' निम्नलिखित कथन समतुल्य हैं | ||
| Line 24: | Line 24: | ||
# <math>\delta(P)\leq d </math> सभी डी-आयामी बहुशीर्षों के लिए 2d स्वरूपों के साथ P | # <math>\delta(P)\leq d </math> सभी डी-आयामी बहुशीर्षों के लिए 2d स्वरूपों के साथ P | ||
दूसरे शब्दों में हिर्श अनुमान को सिद्ध करने या अस्वीकार करने के लिए केवल बहुशीर्षों पर विचार करने की जरूरत है जो कि इसके आयाम के रूप में कई स्वरूपों साथ है और एक महत्वपूर्ण तथ्य यह है कि हिर्श अनुमान सभी बहुशीर्षों के लिए मान्य है और यह केवल सभी सरल बहुशीर्षों के लिए | दूसरे शब्दों में हिर्श अनुमान को सिद्ध करने या अस्वीकार करने के लिए केवल बहुशीर्षों पर विचार करने की जरूरत है जो कि इसके आयाम के रूप में कई स्वरूपों साथ है और एक महत्वपूर्ण तथ्य यह है कि हिर्श अनुमान सभी बहुशीर्षों के लिए मान्य है और यह केवल सभी सरल बहुशीर्षों के लिए है<ref>{{harvtxt|Ziegler|1994}}</ref> | ||
Revision as of 10:22, 10 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
- सभी डी-आयामी बहुशीर्षों के लिए 2d स्वरूपों के साथ P
दूसरे शब्दों में हिर्श अनुमान को सिद्ध करने या अस्वीकार करने के लिए केवल बहुशीर्षों पर विचार करने की जरूरत है जो कि इसके आयाम के रूप में कई स्वरूपों साथ है और एक महत्वपूर्ण तथ्य यह है कि हिर्श अनुमान सभी बहुशीर्षों के लिए मान्य है और यह केवल सभी सरल बहुशीर्षों के लिए है[12]
प्रति उदाहरण
दुर्भाग्य से, हिर्श अनुमान सभी मामलों में सही नहीं है, जैसा कि 2011 में फ्रांसिस्को सैंटोस द्वारा दिखाया गया था। सैंटोस का काउंटर उदाहरण का स्पष्ट निर्माण इस तथ्य से दोनों आता है कि अनुमान को केवल सरल पॉलीटोप्स पर विचार करने के लिए आराम दिया जा सकता है, और हिर्श के बीच समानता से और डी-स्टेप अनुमान।[13] विशेष रूप से सैंटोस स्पिंडल नामक पॉलीटोप्स के एक विशेष वर्ग की जांच करके अपना प्रति उदाहरण प्रस्तुत करता है।
'परिभाषा' एक डी-स्पिंडल एक डी-आयामी पॉलीटोप है जिसके लिए अलग-अलग शीर्षों की एक जोड़ी मौजूद है जैसे कि हर पहलू इन दो शीर्षों में से ठीक एक शामिल है।
इन दो शीर्षों के बीच के सबसे छोटे पथ की लंबाई को धुरी की लंबाई कहा जाता है। हिर्श अनुमान का खंडन निम्नलिखित प्रमेय पर निर्भर करता है, जिसे स्पिंडल के लिए मजबूत डी-स्टेप प्रमेय कहा जाता है।
'प्रमेय (सैंटोस)' चलो एक डी-धुरी हो। मान लीजिए n इसके फलकों की संख्या है, और l इसकी लंबाई है। फिर एक मौजूद है -धुरी, , साथ पहलू और लंबाई नीचे से घिरी हुई है . विशेष रूप से, अगर , तब डी-स्टेप अनुमान का उल्लंघन करता है।
सैंटोस फिर लंबाई 6 के साथ एक 5-आयामी धुरी का निर्माण करने के लिए आगे बढ़ता है, जिससे यह साबित होता है कि एक और धुरी मौजूद है जो हिर्श अनुमान के प्रतिरूप के रूप में कार्य करता है। इन दो तकुओं में से पहले में 48 पहलू और 322 कोने हैं, जबकि अनुमान को वास्तव में खारिज करने वाले तर्कु में 86 पहलू हैं और यह 43-आयामी है। यह प्रति उदाहरण बहुपद हिर्श अनुमान का खंडन नहीं करता है, जो एक खुली समस्या बनी हुई है।[14]
टिप्पणियाँ
- ↑ 1.0 1.1 Ziegler (1994), p. 84.
- ↑ Dantzig (1963), pp. 160 and 168.
- ↑ E.g. see Naddef (1989) for 0-1 polytopes.
- ↑ Kalai & Kleitman (1992).
- ↑ Santos (2011).
- ↑ Kalai (2010).
- ↑ "Francisco Santos encuentra un contraejemplo que refuta la conjetura de Hirsch", Gaussianos, May 24, 2010
- ↑ Santos (2011)
- ↑ Klee & Walkup (1967).
- ↑ Ziegler (1994)
- ↑ Ziegler (1994)
- ↑ Ziegler (1994)
- ↑ Santos (2011)
- ↑ Santos (2011)
संदर्भ
- Dantzig, George B. (1963), Linear Programming and Extensions, Princeton Univ. Press. Reprinted in the series Princeton Landmarks in Mathematics, Princeton University Press, 1998.
- Kalai, Gil (10 May 2010). "Francisco Santos Disproves the Hirsch Conjecture". Retrieved 11 May 2010.
- 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, S2CID 37821778.
- Klee, Victor; Walkup, David W. (1967), "The d-step conjecture for polyhedra of dimension d < 6", Acta Mathematica, 133: 53–78, doi:10.1007/BF02395040, MR 0206823.
- Miranda, Eva (2012), "The Hirsch conjecture has been disproved: An interview with Francisco Santos" (PDF), Newsletter of the European Mathematical Society (86): 31–36.
- Naddef, Denis (1989), "The Hirsch conjecture is true for (0,1)-polytopes", Mathematical Programming, 45 (1): 109–110, doi:10.1007/BF01589099, MR 1017214, S2CID 24632864.
- Santos, Francisco (2011), "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, S2CID 15325169
- Ziegler, Günter M. (1994), "The Hirsch Conjecture", Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, pp. 83–93.
