हिर्श अनुमान

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

गणितीय प्रोग्रामिंग और पॉलीहेड्रल कॉम्बिनेटरिक्स में हिर्श अनुमान यह कथन है कि डी-डायमेंशनल यूक्लिडियन स्पेस में एन-पहलू पॉलीटॉप के एज-वर्टेक्स ग्राफ का व्यास n - d से अधिक नहीं हैअर्थात् पॉलीटॉप के किन्हीं भी दो शीर्षों को अधिकतम n-d लंबाई के पथ द्वारा एक-दूसरे से जोड़ा जाना चाहिए अनुमान पहली बार 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.