Hirsch conjecture
ریاضیاتی پروگرامنگ اور پولی ہیڈرل کمبینٹوریکس میں، ہرش قیاس یہ بیان ہے کہ ڈی-جہتی یوکلڈین اسپیس میں این-فیسیٹ پولیٹوپ کے ایج-ورٹیکس گراف کا قطر این-ڈی سے زیادہ نہیں ہے۔ یعنی، پولیٹوپ کے کسی بھی دو عمودی حصوں کو زیادہ سے زیادہ این-ڈی لمبائی کے راستے سے ایک دوسرے سے جوڑا جانا چاہیے۔ یہ قیاس سب سے پہلے 1957 میں جارج بی ڈینٹزگ کے خط میں پیش کیا گیا تھا اور لکیری پروگرامنگ میں سمپلیکس طریقہ کے تجزیے سے متاثر ہوا تھا، کیونکہ پولیٹوپ کا قطر سمپلیکس طریقہ کار کے لیے درکار مراحل کی تعداد پر کم حد فراہم کرتا ہے۔ یہ قیاس اب عام طور پر غلط معلوم ہوتا ہے۔ ہرش قیاس ڈی <4 اور مختلف خصوصی معاملات کے لیے ثابت کیا گیا تھا، جبکہ قطر پر سب سے مشہور اوپری حدود صرف این اور ڈی میں ذیلی تعریفی ہیں۔ پچاس سال سے زیادہ عرصے کے بعد، مئی 2010 میں کینٹابریا یونیورسٹی کے فرانسسکو سینٹوس لیال نے ایک جوابی مثال کا اعلان کیا۔ نتیجہ سیئٹل میں 100 سال کی کانفرنس میں پیش کیا گیا: کلی اور گرون بوم کی ریاضی اور اینلز آف میتھمیٹکس میں شائع ہوا۔ خاص طور پر، کاغذ نے 43 سے زیادہ قطر کے ساتھ 86 پہلوؤں کا 43 جہتی پولیٹوپ پیش کیا۔ جوابی مثال کے سمپلیکس طریقہ کار کے تجزیے کے لیے کوئی براہ راست نتائج نہیں ہیں، کیونکہ یہ اقدامات کی ایک بڑی لیکن اب بھی لکیری یا کثیر تعداد کے امکان کو مسترد نہیں کرتا ہے۔ اس مسئلے کی مختلف مساوی فارمولیشنز دی گئی تھیں، جیسے کہ ڈی-اسٹیپ قیاس، جس میں کہا گیا ہے کہ ڈی-جہتی یوکلڈین اسپیس میں کسی بھی 2 ڈی-فیسیٹ پولیٹوپ کا قطر ڈی سے زیادہ نہیں ہے۔ سینٹوس لیال کی جوابی مثال بھی اس قیاس کو غلط ثابت کرتی ہے۔ قیاس کا بیان کنویکس پولیٹوپ کا گراف کوئی بھی گراف ہوتا ہے جس کے عمودی حصے کنویکس کے عمودی حصوں کے ساتھ اس طرح سے جڑے ہوتے ہیں کہ گراف کے کوئی بھی دو عمودی حصے ایک کنارے سے جڑے ہوں اگر اور صرف اس صورت میں جب ان کے دو متعلقہ عمودی حصے پولیٹوپ کے کنارے سے جڑے ہوں۔ کا قطر، جس کی نشاندہی کی گئی ہے، اس کے کسی بھی گراف کا قطر ہے۔ یہ تعریفیں اچھی طرح سے متعین ہیں کیونکہ ایک ہی پولیٹوپ کے کسی بھی دو گراف کو گراف کی طرح آئسومورفک ہونا چاہیے۔ اس کے بعد ہم ہرش قیاس کو اس طرح بیان کر سکتے ہیں: قیاس آئیے کہ یہ n پہلوؤں کے ساتھ ایک d-جہتی کنویکس پولیٹوپ ہے۔ پھر۔ مثال کے طور پر، تین جہتوں میں ایک مکعب کے چھ پہلو ہوتے ہیں۔ اس کے بعد ہرش قیاس اس بات کی نشاندہی کرتا ہے کہ اس مکعب کا قطر تین سے زیادہ نہیں ہو سکتا۔ قیاس کو قبول کرنے کا مطلب یہ ہوگا کہ مکعب کے کسی بھی دو عمودی حصوں کو زیادہ سے زیادہ تین مراحل کا استعمال کرتے ہوئے عمودی سے عمودی راستے سے جوڑا جا سکتا ہے۔ طول و عرض کے تمام پولی ٹاپس کے لیے کم از کم 8، یہ باؤنڈ دراصل زیادہ سے زیادہ ہے۔ طول و عرض کے کسی بھی پولی ٹاپ کا قطر n-d سے کم نہیں ہوتا ہے، جس میں n اس کے پہلوؤں کی تعداد ہوتی ہے، جیسا کہ پہلے تھا۔ دوسرے لفظوں میں، تقریبا تمام معاملات کے لیے، قیاس اس کے کناروں کے ساتھ کسی راستے سے پولیٹوپ کے کسی بھی دو عمودی حصوں میں شامل ہونے کے لیے درکار کم از کم مراحل فراہم کرتا ہے۔ چونکہ سمپلیکس طریقہ بنیادی طور پر قابل عمل خطے کے کچھ سرے سے ایک بہترین نقطہ تک راستہ بنا کر کام کرتا ہے، اس لیے ہرش قیاس سب سے خراب صورت حال میں سمپلیکس طریقہ کو ختم کرنے کے لیے درکار نچلی حد فراہم کرے گا۔ ہرش قیاس کثیر الجہتی ہرش قیاس کا ایک خاص معاملہ ہے، جس میں دعوی کیا گیا ہے کہ کچھ مثبت عدد k موجود ہے، جیسے کہ تمام پولی ٹاپس کے لیے، جہاں n پی کے پہلوؤں کی تعداد ہے۔ پیش رفت اور درمیانی نتائج ہرش قیاس متعدد معاملات کے لیے درست ثابت ہوا ہے۔ مثال کے طور پر، طول و عرض 3 یا اس سے کم والا کوئی بھی پولیٹوپ قیاس کو مطمئن کرتا ہے۔ کوئی بھی ڈی جہتی پولیٹوپ جس کے n پہلو ہوتے ہیں جو قیاس کو بھی مطمئن کرتے ہیں۔ قیاس کو حل کرنے کی دیگر کوششیں ایک مختلف مسئلہ وضع کرنے کی خواہش سے ظاہر ہوئیں جس کا حل ہرش قیاس کو ظاہر کرے گا۔ خاص اہمیت کی ایک مثال ڈی-اسٹیپ قیاس ہے، جو کہ ہرش قیاس کی ایک نرمی ہے جو حقیقت میں اس کے مساوی دکھائی گئی ہے۔ نظریہ مندرجہ ذیل بیانات مساوی ہیں: n پہلوؤں والے تمام d-جہتی پولی ٹاپس کے لیے۔ 2 ڈی پہلوؤں والے تمام ڈی جہتی پولی ٹاپس کے لیے۔ دوسرے لفظوں میں، ہرش قیاس آرائی کو ثابت یا غلط ثابت کرنے کے لیے، کسی کو صرف پولی ٹاپس پر غور کرنے کی ضرورت ہے جس کے طول و عرض سے بالکل دوگنا پہلو ہیں۔ ایک اور اہم نرمی یہ ہے کہ ہرش قیاس تمام پولی ٹاپس کے لیے تب ہی ہوتا ہے جب یہ تمام سادہ پولی ٹاپس کے لیے ہو۔ جوابی مثال بدقسمتی سے، ہرش کا قیاس تمام معاملات میں درست نہیں ہے، جیسا کہ 2011 میں فرانسسکو سینٹوس نے دکھایا تھا۔ سینٹوس کی جوابی مثال کی واضح تعمیر اس حقیقت سے آتی ہے کہ قیاس آرائی کو صرف سادہ پولی ٹاپس پر غور کرنے کے لیے نرم کیا جا سکتا ہے، اور ہرش اور ڈی-اسٹیپ قیاس آرائیوں کے درمیان مساوات سے۔ خاص طور پر، سینٹوس پولٹوپس کے ایک خاص طبقے کی جانچ کر کے اپنی جوابی مثال پیش کرتا ہے جسے اسپنڈلز کہا جاتا ہے۔ تعریف اے ڈی-اسپنڈل ایک ڈی جہتی پولیٹوپ ہے جس کے لیے الگ الگ عمودی کا ایک جوڑا موجود ہے جس کے ہر پہلو میں ان دو عمودی میں سے بالکل ایک ہوتا ہے۔ ان دونوں چوٹیوں کے درمیان مختصر ترین راستے کی لمبائی کو تکلے کی لمبائی کہا جاتا ہے۔ ہرش قیاس کی تردید مندرجہ ذیل تھیوریم پر منحصر ہے، جسے اسپنڈلز کے لیے مضبوط ڈی-مرحلہ تھیوریم کہا جاتا ہے۔ نظریہ (سینٹوس) کو ایک ڈی-اسپنڈل ہونے دیں۔ فرض کریں کہ n اس کے پہلوؤں کی تعداد ہے، اور l اس کی لمبائی ہے۔ اس کے بعد ایک-تکلا موجود ہوتا ہے، جس کے پہلو اور لمبائی نیچے سے منسلک ہوتی ہے۔ خاص طور پر، اگر، تو ڈی-مرحلہ قیاس کی خلاف ورزی کرتا ہے۔ سینٹوس پھر لمبائی 6 کے ساتھ ایک 5 جہتی تکلا بنانے کے لیے آگے بڑھتا ہے، اس لیے یہ ثابت کرتا ہے کہ ایک اور تکلا موجود ہے جو ہرش قیاس کی جوابی مثال کے طور پر کام کرتا ہے۔ ان دو تکلوں میں سے پہلے میں 48 پہلو اور 322 عمودی ہیں، جبکہ وہ تکلا جو حقیقت میں قیاس کو غلط ثابت کرتا ہے اس کے 86 پہلو ہیں اور یہ 43 جہتی ہے۔ یہ جوابی مثال کثیر الجہتی ہرش قیاس کو غلط ثابت نہیں کرتی، جو کہ ایک کھلا مسئلہ بنی ہوئی ہے۔ حوالہ جات نوٹ کریں۔ ریاضی میں پرنسٹن لینڈمارکس، پرنسٹن یونیورسٹی پریس، 1998 کی سیریز میں دوبارہ شائع ہوا۔ ۔ ۔ ۔ ۔ پولی ہیڈرل کمبینٹوریکس قیاس آرائیاں غیر مصدقہ قیاس آرائیاں لکیری پروگرامنگ