हिर्श अनुमान

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

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

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

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

अनुमान का कथन

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

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

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

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

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

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

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

1. $\delta (P)\leq n-d$ सभी डी-आयामी बहुशीर्षों के लिए एन स्वरूपों के साथ P
2. $\delta (P)\leq d$ सभी डी-आयामी बहुशीर्षों के लिए 2d स्वरूपों के साथ P

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

प्रति उदाहरण

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

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

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

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

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

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

संदर्भ

• 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.