Hirsch conjecture
गणितीय प्रोग्रामिंग और पॉलीहेड्रल संयोजन विज्ञान में, हिर्श अनुमान यह कथन है कि डी-आयामी यूक्लिडियन स्थान में एक एन-फेस पॉलीटोप के किनारे-वर्टेक्स ग्राफ का व्यास एन-डी से अधिक नहीं है। अर्थात, पॉलीटोप के किसी भी दो शीर्षों को अधिकतम एन-डी पर लंबाई के पथ से एक दूसरे से जोड़ा जाना चाहिए। अनुमान पहली बार 1957 में जॉर्ज बी. डैंटजिग द्वारा एक पत्र में सामने रखा गया था और रैखिक प्रोग्रामिंग में सिम्प्लेक्स विधि के विश्लेषण से प्रेरित था, क्योंकि एक पॉलीटोप का व्यास सिम्प्लेक्स विधि द्वारा आवश्यक चरणों की संख्या पर एक निचली सीमा प्रदान करता है। यह अनुमान अब सामान्य रूप से गलत माना जाता है। हिर्श अनुमान डी <4 और विभिन्न विशेष मामलों के लिए सिद्ध किया गया था, जबकि व्यास पर सबसे अच्छी ज्ञात ऊपरी सीमाएं केवल एन और डी में उप-घातीय हैं। पचास से अधिक वर्षों के बाद, मई 2010 में कैंटाब्रिया विश्वविद्यालय के फ्रांसिस्को सैंटोस लील द्वारा एक प्रति-उदाहरण की घोषणा की गई थी। परिणाम सिएटल में 100 इयर्स सम्मेलन में प्रस्तुत किया गया थाः क्ली और ग्रनबॉम का गणित और एनल्स ऑफ मैथमेटिक्स में दिखाई दिया। विशेष रूप से, पेपर ने 43 से अधिक व्यास के साथ 86 पहलुओं का 43-आयामी पॉलीटोप प्रस्तुत किया। सिम्प्लेक्स विधि के विश्लेषण के लिए प्रति-उदाहरण का कोई प्रत्यक्ष परिणाम नहीं है, क्योंकि यह बड़ी लेकिन अभी भी रैखिक या बहुपद संख्या में चरणों की संभावना से इंकार नहीं करता है। समस्या के विभिन्न समतुल्य सूत्रीकरण दिए गए थे, जैसे कि डी-चरण अनुमान, जिसमें कहा गया है कि डी-आयामी यूक्लिडियन स्थान में किसी भी 2डी-पक्षीय पॉलीटोप का व्यास डी से अधिक नहीं है; सैंटोस लील का प्रति-उदाहरण भी इस अनुमान को गलत साबित करता है। अनुमान का कथन एक उत्तल पॉलीटोप का ग्राफ कोई भी ग्राफ है जिसके शीर्ष शीर्ष के साथ द्विभाजन में इस तरह से होते हैं कि ग्राफ के किसी भी दो शीर्ष एक किनारे से जुड़ जाते हैं यदि और केवल तभी जब दो संबंधित शीर्ष पॉलीटोप के एक किनारे से जुड़े होते हैं। का व्यास, दर्शाया गया है, इसके किसी भी ग्राफ का व्यास है। ये परिभाषाएँ अच्छी तरह से परिभाषित हैं क्योंकि एक ही पॉलीटोप के किसी भी दो ग्राफ को ग्राफ के रूप में समरूप होना चाहिए। फिर हम हिर्श अनुमान को निम्नानुसार बता सकते हैंः अनुमान मान लीजिए कि यह n पहलुओं के साथ एक डी-आयामी उत्तल पॉलीटोप है। फिर. उदाहरण के लिए, तीन आयामों में एक घन के छह पहलू होते हैं। हिर्श अनुमान तब इंगित करता है कि इस घन का व्यास तीन से अधिक नहीं हो सकता है। अनुमान को स्वीकार करने का मतलब यह होगा कि घन के किसी भी दो शीर्षों को अधिकतम तीन चरणों का उपयोग करके शीर्ष से शीर्ष तक एक पथ द्वारा जोड़ा जा सकता है। कम से कम 8 आयाम के सभी पॉलीटोप के लिए, यह सीमा वास्तव में इष्टतम है; आयाम के किसी भी पॉलीटोप का व्यास n-d से कम नहीं होता है, जिसमें n पहले की तरह इसके पहलुओं की संख्या होती है। दूसरे शब्दों में, लगभग सभी मामलों के लिए, अनुमान एक पॉलीटोप के किसी भी दो शीर्षों को उसके किनारों के साथ एक पथ से जोड़ने के लिए आवश्यक चरणों की न्यूनतम संख्या प्रदान करता है। चूँकि सिम्प्लेक्स विधि अनिवार्य रूप से व्यवहार्य क्षेत्र के कुछ शीर्ष से एक इष्टतम बिंदु तक एक मार्ग का निर्माण करके संचालित होती है, हिर्श अनुमान सबसे खराब स्थिति में सिम्प्लेक्स विधि को समाप्त करने के लिए आवश्यक एक निचली सीमा प्रदान करेगा। हिर्श अनुमान बहुपद हिर्श अनुमान का एक विशेष मामला है, जो दावा करता है कि कुछ सकारात्मक पूर्णांक k मौजूद है, जैसे कि सभी बहुपदों के लिए, जहां n पी के पहलुओं की संख्या है। प्रगति और मध्यवर्ती परिणाम हिर्श अनुमान कई मामलों के लिए सही साबित हुआ है। उदाहरण के लिए, आयाम 3 या उससे कम का कोई भी पॉलीटोप अनुमान को संतुष्ट करता है। एन पहलुओं के साथ कोई भी डी-आयामी पॉलीटोप जो अनुमान को भी संतुष्ट करता है। अनुमान को हल करने के अन्य प्रयास एक अलग समस्या तैयार करने की इच्छा से प्रकट हुए, जिसका समाधान हिर्श अनुमान का संकेत देगा। विशेष महत्व का एक उदाहरण डी-स्टेप अनुमान है, जो हिर्श अनुमान का एक विश्राम है जिसे वास्तव में इसके बराबर दिखाया गया है। प्रमेय निम्नलिखित कथन समतुल्य हैंः n पहलुओं वाले सभी डी-आयामी पॉलीटोप के लिए। 2 डी पहलुओं वाले सभी डी-आयामी पॉलीटोप के लिए। दूसरे शब्दों में, हिर्श अनुमान को साबित या गलत साबित करने के लिए, केवल पॉलीटोप पर विचार करने की आवश्यकता है जो इसके आयाम से ठीक दोगुने पहलुओं वाले हैं। एक अन्य महत्वपूर्ण छूट यह है कि हिर्श अनुमान सभी पॉलीटोप के लिए तभी लागू होता है जब यह सभी सरल पॉलीटोप के लिए लागू होता है। दुर्भाग्य से, हिर्श अनुमान सभी मामलों में सच नहीं है, जैसा कि 2011 में फ्रांसिस्को सैंटोस द्वारा दिखाया गया था। सैंटोस का एक प्रति-उदाहरण का स्पष्ट निर्माण इस तथ्य से आता है कि अनुमान को केवल सरल पॉलीटोप पर विचार करने के लिए शिथिल किया जा सकता है, और हिर्श और डी-चरण अनुमानों के बीच समानता से। विशेष रूप से, सैंटोस स्पिंडल नामक पॉलीटोप के एक विशेष वर्ग की जांच करके अपना प्रति-उदाहरण प्रस्तुत करता है। परिभाषा ए डी-स्पिंडल एक डी-आयामी पॉलीटोप है जिसके लिए अलग-अलग शीर्षों की एक जोड़ी मौजूद है जैसे कि प्रत्येक पहलू में इन दो शीर्षों में से एक होता है। इन दो शीर्षों के बीच सबसे छोटे मार्ग की लंबाई को धुरी की लंबाई कहा जाता है। हिर्श अनुमान का खंडन निम्नलिखित प्रमेय पर निर्भर करता है, जिसे स्पिंडल के लिए मजबूत डी-चरण प्रमेय के रूप में संदर्भित किया जाता है। प्रमेय (सैंटोस) को एक डी-स्पिंडल माना जाता है। माना n इसके पहलुओं की संख्या है, और माना l इसकी लंबाई है। फिर एक-स्पिंडल मौजूद होता है, जिसमें पहलू और नीचे से बंधी लंबाई होती है। विशेष रूप से, यदि, तो डी-चरण अनुमान का उल्लंघन करता है। सैंटोस तब 6 लंबाई के साथ एक 5-आयामी स्पिंडल का निर्माण करने के लिए आगे बढ़ता है, इसलिए यह साबित करता है कि एक और स्पिंडल मौजूद है जो हिर्श अनुमान के विपरीत उदाहरण के रूप में कार्य करता है। इन दो स्पिंडल में से पहले में 48 पहलू और 322 शीर्ष हैं, जबकि वास्तव में अनुमान को गलत साबित करने वाले स्पिंडल में 86 पहलू हैं और यह 43-आयामी है। यह प्रति-उदाहरण बहुपद हिर्श अनुमान को गलत साबित नहीं करता है, जो एक खुली समस्या बनी हुई है। टिप्पणियाँ संदर्भ। गणित में प्रिंसटन लैंडमार्क्स, प्रिंसटन यूनिवर्सिटी प्रेस, 1998 श्रृंखला में पुनः मुद्रित। .. .. .. .. पॉलीहेड्रल कॉम्बिनेटोरिक्स अनुमान अप्रमाणित अनुमान रैखिक प्रोग्रामिंग