Hirsch conjecture
গাণিতিক প্রোগ্রামিং এবং পলিহেড্রাল কম্বিনেটরিকসে, হির্শ অনুমানটি হল বিবৃতি যে ডি-ডাইমেনশনাল ইউক্লিডিয়ান স্পেসে একটি এন-ফেস পলিটোপের প্রান্ত-ভার্টেক্স গ্রাফের ব্যাস এন-ডি এর বেশি নয়। অর্থাৎ, পলিটোপের যে কোনও দুটি শীর্ষকে সর্বাধিক এন-ডি দৈর্ঘ্যের পথ দ্বারা একে অপরের সাথে সংযুক্ত করতে হবে। অনুমানটি প্রথম 1957 সালে জর্জ বি ড্যান্টজিগ দ্বারা একটি চিঠিতে দেওয়া হয়েছিল এবং রৈখিক প্রোগ্রামিংয়ে সিম্প্লেক্স পদ্ধতির বিশ্লেষণ দ্বারা অনুপ্রাণিত হয়েছিল, কারণ একটি পলিটোপের ব্যাস সিম্প্লেক্স পদ্ধতির দ্বারা প্রয়োজনীয় পদক্ষেপের সংখ্যার উপর একটি নিম্ন সীমা সরবরাহ করে। অনুমানটি এখন সাধারণভাবে মিথ্যা বলে জানা যায়। হির্শ অনুমানটি ডি <4 এবং বিভিন্ন বিশেষ ক্ষেত্রে প্রমাণিত হয়েছিল, যেখানে ব্যাসের উপরের সর্বাধিক পরিচিত সীমানা কেবল এন এবং ডি-তে উপ-সূচক। পঞ্চাশ বছরেরও বেশি সময় পরে, 2010 সালের মে মাসে ক্যান্টাব্রিয়া বিশ্ববিদ্যালয়ের ফ্রান্সিসকো সান্তোস লিল দ্বারা একটি পাল্টা উদাহরণ ঘোষণা করা হয়েছিল। ফলাফলটি সিয়াটলে 100 ইয়ারসঃ দ্য ম্যাথমেটিক্স অফ ক্লি অ্যান্ড গ্রুনবাম সম্মেলনে উপস্থাপন করা হয়েছিল এবং অ্যানালস অফ ম্যাথমেটিক্সে প্রকাশিত হয়েছিল। বিশেষত, গবেষণাপত্রে 43 টিরও বেশি ব্যাস সহ 86 টি দিকের একটি 43-মাত্রিক পলিটোপ উপস্থাপন করা হয়েছিল। সিম্প্লেক্স পদ্ধতির বিশ্লেষণের জন্য পাল্টা উদাহরণের কোনও সরাসরি পরিণতি নেই, কারণ এটি একটি বৃহত্তর কিন্তু এখনও রৈখিক বা বহুপদী সংখ্যক ধাপের সম্ভাবনাকে বাতিল করে না। সমস্যার বিভিন্ন সমতুল্য সূত্র দেওয়া হয়েছিল, যেমন ডি-ধাপের অনুমান, যা বলে যে ডি-মাত্রিক ইউক্লিডীয় স্থানে যে কোনও 2ডি-দিকের পলিটোপের ব্যাস ডি-এর বেশি নয়; সান্তোস লীলের পাল্টা উদাহরণও এই অনুমানকে অস্বীকার করে। অনুমানের বিবৃতি একটি উত্তল পলিটোপের গ্রাফ হল এমন কোনও গ্রাফ যার শীর্ষগুলি এর শীর্ষগুলির সাথে এমনভাবে দ্বিখণ্ডিত হয় যে গ্রাফের যে কোনও দুটি শীর্ষ একটি প্রান্ত দ্বারা যুক্ত হয় যদি এবং কেবলমাত্র যদি এর দুটি সংশ্লিষ্ট শীর্ষগুলি পলিটোপের একটি প্রান্ত দ্বারা যুক্ত হয়। এর ব্যাস, চিহ্নিত, এর যে কোনও একটি গ্রাফের ব্যাস। এই সংজ্ঞাগুলি সু-সংজ্ঞায়িত কারণ একই পলিটোপের যে কোনও দুটি গ্রাফ অবশ্যই গ্রাফের মতো সমরূপ হতে হবে। তারপরে আমরা হির্শ অনুমানটি নিম্নরূপ বর্ণনা করতে পারিঃ অনুমান ধরা যাক n দিক সহ একটি ডি-মাত্রিক উত্তল পলিটোপ। তারপর। উদাহরণস্বরূপ, তিন মাত্রার একটি ঘনক্ষেত্রের ছয়টি দিক রয়েছে। হির্শ অনুমান তখন নির্দেশ করে যে এই ঘনক্ষেত্রের ব্যাস তিনটির বেশি হতে পারে না। অনুমানটি গ্রহণ করা বোঝায় যে ঘনক্ষেত্রের যে কোনও দুটি শীর্ষ সর্বাধিক তিনটি ধাপ ব্যবহার করে শীর্ষ থেকে শীর্ষে যাওয়ার পথ দ্বারা সংযুক্ত হতে পারে। কমপক্ষে 8 মাত্রার সমস্ত পলিটোপগুলির জন্য, এই বন্ধনটি আসলে সর্বোত্তম; মাত্রার কোনও পলিটোপের ব্যাস n-d এর চেয়ে কম হয় না, যার মধ্যে n হল আগের মতো তার দিকগুলির সংখ্যা। অন্য কথায়, প্রায় সব ক্ষেত্রেই, অনুমানটি একটি পলিটোপের যে কোনও দুটি শীর্ষকে তার প্রান্ত বরাবর একটি পথ দিয়ে যুক্ত করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ সরবরাহ করে। যেহেতু সিম্প্লেক্স পদ্ধতিটি মূলত সম্ভাব্য অঞ্চলের কিছু শীর্ষ থেকে একটি সর্বোত্তম বিন্দু পর্যন্ত একটি পথ তৈরি করে কাজ করে, তাই হির্শ অনুমানটি সবচেয়ে খারাপ পরিস্থিতিতে সিম্প্লেক্স পদ্ধতিটি শেষ করার জন্য প্রয়োজনীয় একটি নিম্ন সীমা সরবরাহ করবে। হির্শ অনুমানটি বহুপদী হির্শ অনুমানের একটি বিশেষ উদাহরণ, যা দাবি করে যে কিছু ধনাত্মক পূর্ণসংখ্যা k রয়েছে যাতে, সমস্ত পলিটোপগুলির জন্য, যেখানে n হল পি-এর দিকগুলির সংখ্যা। অগ্রগতি এবং মধ্যবর্তী ফলাফল হির্শ অনুমানটি বেশ কয়েকটি ক্ষেত্রে সত্য প্রমাণিত হয়েছে। উদাহরণস্বরূপ, 3 বা তার কম মাত্রার যে কোনও পলিটোপ অনুমানকে সন্তুষ্ট করে। n দিক সহ যে কোনও ডি-ডাইমেনশনাল পলিটোপ যা অনুমানকেও সন্তুষ্ট করে। অনুমানটি সমাধানের অন্যান্য প্রচেষ্টা একটি ভিন্ন সমস্যা গঠনের আকাঙ্ক্ষা থেকে প্রকাশিত হয়েছিল যার সমাধান হির্শ অনুমানকে বোঝাবে। বিশেষ গুরুত্বের একটি উদাহরণ হল ডি-স্টেপ অনুমান, হির্শ অনুমানের একটি শিথিলতা যা আসলে এর সমতুল্য হিসাবে দেখানো হয়েছে। উপপাদ্য নিম্নলিখিত বিবৃতিগুলি সমতুল্যঃ n দিক সহ সমস্ত ডি-মাত্রিক পলিটোপগুলির জন্য। 2ডি দিক সহ সমস্ত ডি-ডাইমেনশনাল পলিটোপগুলির জন্য। অন্য কথায়, হির্শ অনুমানকে প্রমাণ বা খণ্ডন করার জন্য, একজনকে কেবল তার মাত্রার ঠিক দ্বিগুণ দিক সহ পলিটোপগুলি বিবেচনা করতে হবে। আরেকটি উল্লেখযোগ্য শিথিলতা হল যে হির্শ অনুমান সমস্ত পলিটোপগুলির জন্য প্রযোজ্য যদি এবং শুধুমাত্র যদি এটি সমস্ত সাধারণ পলিটোপগুলির জন্য প্রযোজ্য হয়। বিপরীত উদাহরণ দুর্ভাগ্যবশত, হির্শ অনুমান সব ক্ষেত্রেই সত্য নয়, যেমনটি 2011 সালে ফ্রান্সিসকো সান্তোস দেখিয়েছেন। সান্টোসের একটি পাল্টা উদাহরণের স্পষ্ট নির্মাণ এই সত্য থেকে আসে যে অনুমানটি কেবল সাধারণ পলিটোপগুলি বিবেচনা করার জন্য শিথিল করা যেতে পারে এবং হির্শ এবং ডি-পদক্ষেপের অনুমানগুলির মধ্যে সমতা থেকে। বিশেষ করে, স্যান্টোস স্পিন্ডল নামক একটি নির্দিষ্ট শ্রেণীর পলিটোপ পরীক্ষা করে তার পাল্টা উদাহরণ তৈরি করে। সংজ্ঞা এ ডি-স্পিন্ডল হল একটি ডি-মাত্রিক পলিটোপ যার জন্য এক জোড়া স্বতন্ত্র শীর্ষ রয়েছে যাতে এর প্রতিটি দিক এই দুটি শীর্ষের মধ্যে ঠিক একটি থাকে। এই দুটি শীর্ষের মধ্যে সংক্ষিপ্ততম পথের দৈর্ঘ্যকে স্পিন্ডলের দৈর্ঘ্য বলা হয়। হির্শ অনুমানের অসঙ্গতি নিম্নলিখিত উপপাদ্যের উপর নির্ভর করে, যা স্পিন্ডলের জন্য শক্তিশালী ডি-ধাপ উপপাদ্য হিসাবে উল্লেখ করা হয়। উপপাদ্য (সান্টোস) একটি ডি-স্পিন্ডল ধরা যাক। ধরা যাক n হল এর দিকগুলির সংখ্যা, এবং l হল এর দৈর্ঘ্য। তারপরে একটি-স্পিন্ডল রয়েছে, যার দিকগুলি এবং নীচের দিকে একটি দৈর্ঘ্য দ্বারা আবদ্ধ। বিশেষ করে, যদি, তাহলে ডি-ধাপের অনুমান লঙ্ঘন করে। সান্টোস তারপর 6 দৈর্ঘ্যের একটি 5-মাত্রিক স্পিন্ডল তৈরি করতে এগিয়ে যায়, তাই প্রমাণ করে যে আরেকটি স্পিন্ডল রয়েছে যা হির্শ অনুমানের পাল্টা উদাহরণ হিসাবে কাজ করে। এই দুটি স্পিন্ডলের মধ্যে প্রথমটির 48টি দিক এবং 322টি শীর্ষ রয়েছে, যেখানে যে স্পিন্ডলটি প্রকৃতপক্ষে অনুমানকে অস্বীকার করে তার 86টি দিক রয়েছে এবং এটি 43-মাত্রিক। এই পাল্টা উদাহরণটি বহুপদী হির্শ অনুমানকে খণ্ডন করে না, যা একটি উন্মুক্ত সমস্যা হিসাবে রয়ে গেছে। উল্লেখগুলি উল্লেখ করুন। প্রিন্সটন ল্যান্ডমার্কস ইন ম্যাথমেটিক্স, প্রিন্সটন ইউনিভার্সিটি প্রেস, 1998 সিরিজে পুনরায় মুদ্রিত। । । । । পলিহেড্রাল কম্বিনেটরিক্স অনুমান অপ্রমাণিত অনুমান রৈখিক প্রোগ্রামিং