हिर्श अनुमान

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

गणितीय प्रोग्रामिंग और पॉलीहेड्रल कॉम्बिनेटरिक्स में हिर्श अनुमान यह कथन है कि एज (ज्यामिति) - वर्टेक्स (ज्यामिति) ग्राफ (असतत गणित) एक एन-पहलू (गणित) polytope डी'-डायमेंशनल में यूक्लिडियन अंतरिक्ष का व्यास (ग्राफ़ सिद्धांत) n − d से अधिक नहीं है। यानी पॉलीटॉप के किसी भी दो शीर्ष (ज्यामिति) को ग्राफ थ्योरी की शब्दावली के पथ द्वारा एक दूसरे से जोड़ा जाना चाहिए Walks at most n − dअनुमान सबसे पहले एक पत्र द्वारा प्रस्तुत किया गया था Warren M. Hirsch 1957 में जॉर्ज बी. डेंटजिग को और रैखिक प्रोग्रामिंग में सिम्प्लेक्स विधि के विश्लेषण से प्रेरित था क्योंकि पॉलीटॉप का व्यास सिम्प्लेक्स विधि द्वारा आवश्यक चरणों की संख्या पर कम सीमा प्रदान करता है अनुमान अब सामान्य रूप से झूठा माना जाता है।

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

समस्या के विभिन्न समतुल्य सूत्र दिए गए थे जैसे कि डी-स्टेप अनुमान जिसमें कहा गया है कि डी-डायमेंशनल यूक्लिडियन स्पेस में किसी भी 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$ सभी डी-डायमेंशनल पॉलीटोप्स के लिए $P$ 2d पहलुओं के साथ।

दूसरे शब्दों में, हिर्श अनुमान को साबित करने या अस्वीकार करने के लिए, किसी को केवल पॉलीटोप्स पर विचार करने की जरूरत है, जो इसके आयाम के रूप में दो बार कई पहलुओं के साथ है। एक और महत्वपूर्ण छूट यह है कि हिर्श अनुमान सभी पॉलीटॉप्स के लिए है अगर और केवल अगर यह सभी सरल पॉलीटॉप्स के लिए है।

प्रति उदाहरण

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

दुर्भाग्य से, हिर्श अनुमान सभी मामलों में सही नहीं है, जैसा कि 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.