Polyhedral combinatorics
পলিহেড্রাল কম্বিনেটরিকস হল গণিতের একটি শাখা, যা কম্বিনেটরিকস এবং বিচ্ছিন্ন জ্যামিতির মধ্যে থাকে, যা উত্তল পলিহেড্রা এবং উচ্চ-মাত্রিক উত্তল পলিটোপগুলির মুখগুলি গণনা এবং বর্ণনা করার সমস্যাগুলি অধ্যয়ন করে। পলিহেড্রাল কম্বিনেটরিক্সের গবেষণা দুটি স্বতন্ত্র ক্ষেত্রে পড়ে। এই ক্ষেত্রে গণিতবিদরা পলিটোপগুলির সংমিশ্রণ অধ্যয়ন করেন; উদাহরণস্বরূপ, তারা এমন অসমতা খোঁজেন যা নির্বিচারে পলিটোপগুলিতে বা পলিটোপগুলির কিছু গুরুত্বপূর্ণ উপশ্রেণীতে উচ্চতর মাত্রার শীর্ষ, প্রান্ত এবং মুখের সংখ্যার মধ্যে সম্পর্ক বর্ণনা করে এবং পলিটোপগুলির অন্যান্য সংমিশ্রণ বৈশিষ্ট্য যেমন তাদের সংযোগ এবং ব্যাস (অন্য কোনও শীর্ষ থেকে যে কোনও শীর্ষে পৌঁছানোর জন্য প্রয়োজনীয় পদক্ষেপের সংখ্যা) অধ্যয়ন করে। উপরন্তু, অনেক কম্পিউটার বিজ্ঞানী পূর্ণসংখ্যা প্রোগ্রামিং সমস্যা থেকে উদ্ভূত নির্দিষ্ট পলিটোপগুলির (বিশেষত 0-1 পলিটোপ, যার শীর্ষগুলি হাইপারকিউবের উপসেট) মুখগুলির সুনির্দিষ্ট বিবরণ নিয়ে গবেষণা বর্ণনা করতে "পলিহেড্রাল কম্বিনেটরিক্স" বাক্যাংশটি ব্যবহার করেন। মুখ এবং মুখ-গণনাকারী ভেক্টর একটি উত্তল পলিটোপ পি-এর একটি মুখকে পি এবং একটি বদ্ধ অর্ধস্থান এইচ-এর ছেদ হিসাবে সংজ্ঞায়িত করা যেতে পারে যাতে এইচ-এর সীমানায় পি-এর কোনও অভ্যন্তরীণ বিন্দু না থাকে। একটি মুখের মাত্রা হল এই কাঠামোর মাত্রা। 0-মাত্রিক মুখগুলি শীর্ষগুলি এবং 1-মাত্রিক মুখগুলি (প্রান্ত বলা হয়) শীর্ষগুলির জোড়াগুলিকে সংযুক্তকারী রেখা বিভাগ। লক্ষ্য করুন যে এই সংজ্ঞাটিতে খালি সেট এবং পুরো পলিটোপ পি অন্তর্ভুক্ত রয়েছে। যদি পি-এর নিজেই মাত্রা ডি থাকে, তবে ডি-1 মাত্রা সহ পি-এর মুখগুলিকে পি-এর দিক বলা হয় এবং ডি-2 মাত্রা সহ মুখগুলিকে শৈলশিরা বলা হয়। পি-এর মুখগুলি আংশিকভাবে অন্তর্ভুক্তির দ্বারা ক্রমবদ্ধ করা যেতে পারে, একটি মুখ জাল তৈরি করে যার উপরের উপাদান পি নিজেই এবং এর নীচের উপাদান হিসাবে খালি সেট রয়েছে। পলিহেড্রাল কম্বিনেটরিক্সের একটি মূল সরঞ্জাম হল একটি পলিটোপের f-ভেক্টর, ভেক্টর (f0, f1,., fd−1) যেখানে fi হল পলিটোপের i-মাত্রিক বৈশিষ্ট্যের সংখ্যা। উদাহরণস্বরূপ, একটি ঘনক্ষেত্রের আটটি শীর্ষ, বারোটি প্রান্ত এবং ছয়টি দিক রয়েছে, তাই এর f-ভেক্টর হল (8,12,6)। দ্বৈত পলিটোপে বিপরীত ক্রমে একই সংখ্যা সহ একটি f-ভেক্টর থাকে; সুতরাং, উদাহরণস্বরূপ, নিয়মিত অক্টা-হেড্রন, যা একটি ঘনক্ষেত্রের দ্বৈত, তার f-ভেক্টর (6,12,8) থাকে। কনফিগারেশন ম্যাট্রিক্সগুলিতে নিয়মিত পলিটোপগুলির এফ-ভেক্টরগুলি তির্যক উপাদান হিসাবে অন্তর্ভুক্ত থাকে। বর্ধিত f-ভেক্টরটি f-ভেক্টরের প্রতিটি প্রান্তে এক নম্বরকে একত্রিত করে, মুখের জালের সমস্ত স্তরে বস্তুর সংখ্যা গণনা করে গঠিত হয়; ভেক্টরের বাম দিকে, f−1 = 1 খালি সেটটিকে একটি মুখ হিসাবে গণনা করে, যখন ডান দিকে, fd = 1 নিজেই P গণনা করে। ঘনক্ষেত্রের জন্য বর্ধিত f-ভেক্টর হল (1,8,12,6,1) এবং অক্টা-হেড্রনের জন্য এটি (1,6,12,8,1)। যদিও এই উদাহরণের পলিহেড্রার ভেক্টরগুলি একমুখী (সহগগুলি, বাম থেকে ডান ক্রমে নেওয়া হয়, সর্বাধিক বৃদ্ধি পায় এবং তারপর হ্রাস পায়), এমন উচ্চ-মাত্রিক পলিটোপ রয়েছে যার জন্য এটি সত্য নয়। সরল পলিটোপগুলির জন্য (পলিটোপ যেখানে প্রতিটি দিক একটি সিম্প্লেক্স), এই ভেক্টরগুলিকে রূপান্তর করা প্রায়শই সুবিধাজনক, যা এইচ-ভেক্টর নামে একটি ভিন্ন ভেক্টর তৈরি করে। যদি আমরা f-ভেক্টরের পদগুলিকে (চূড়ান্ত 1 বাদ দিয়ে) একটি বহুপদীর সহগ হিসাবে ব্যাখ্যা করি (উদাহরণস্বরূপ, অষ্টতলয়টির জন্য এটি বহুপদী f (x) = x3 + 6x2 + 12x + 8 দেয়), তাহলে h-ভেক্টর বহুপদী h (x) = f (x−1) (আবার, অষ্টতলয়টির জন্য, h (x) = x3 + 3x2 + 3x + 1) এর সহগ তালিকাভুক্ত করে। জিগলার লিখেছেন, "সরল পলিটোপ সম্পর্কে বিভিন্ন সমস্যার জন্য, এইচ-ভেক্টরগুলি এফ-ভেক্টরের তুলনায় মুখের সংখ্যা সম্পর্কে তথ্য এনকোড করার জন্য অনেক বেশি সুবিধাজনক এবং সংক্ষিপ্ত উপায়।" সমতা এবং অসমতা একটি পলিটোপের এফ-ভেক্টরের সহগগুলির মধ্যে সবচেয়ে গুরুত্বপূর্ণ সম্পর্ক হল অয়লারের সূত্র এস (−1) আই. এফ. আই = 0, যেখানে বর্ধিত এফ-ভেক্টরের সহগগুলির উপর যোগফলের শর্তাবলী। তিনটি মাত্রায়, বর্ধিত f-ভেক্টরের (1, v, e, f, 1) বাম এবং ডান প্রান্তে দুটি 1 কে সমীকরণের ডান দিকে সরানো এই পরিচয়কে আরও পরিচিত আকারে রূপান্তরিত করে v − e + f = 2। এই বিষয়টি থেকে যে একটি ত্রিমাত্রিক পলিহেড্রনের প্রতিটি দিকের কমপক্ষে তিনটি প্রান্ত থাকে, এটি 2e ≤ 3f দ্বিগুণ গণনা করে অনুসরণ করে এবং অয়লারের সূত্র থেকে e এবং f দূর করার জন্য এই অসমতা ব্যবহার করে আরও অসমতা e ≤ 3v−6 এবং f ≤ 2v−4-এর দিকে পরিচালিত করে। দ্বৈততা দ্বারা, e ≤ 3f−6 এবং v ≤ 2f−4। এটি স্টেনিৎজের উপপাদ্য থেকে অনুসরণ করা হয় যে এই সমতা এবং অসমতা পূরণকারী যে কোনও ত্রিমাত্রিক পূর্ণসংখ্যা ভেক্টর একটি উত্তল পলিহেড্রনের f-ভেক্টর। উচ্চতর মাত্রায়, একটি পলিটোপের মুখের সংখ্যার মধ্যে অন্যান্য সম্পর্কগুলিও গুরুত্বপূর্ণ হয়ে ওঠে, যার মধ্যে রয়েছে ডেহন-সমারভিল সমীকরণগুলি, যা সরল পলিটোপগুলির এইচ-ভেক্টরের পরিপ্রেক্ষিতে প্রকাশ করা হয়, সমস্ত কে-এর জন্য সহজ রূপ এইচকে = এইচডি-কে গ্রহণ করে। কে = 0 সহ এই সমীকরণগুলির উদাহরণ অয়লারের সূত্রের সমতুল্য তবে ডি> 3-এর জন্য এই সমীকরণগুলির অন্যান্য দৃষ্টান্তগুলি একে অপরের থেকে রৈখিকভাবে স্বাধীন এবং এইচ-ভেক্টরগুলিকে (এবং তাই অতিরিক্ত উপায়ে এফ-ভেক্টরগুলিকেও) সীমাবদ্ধ করে। পলিটোপ মুখ গণনার ক্ষেত্রে আরেকটি গুরুত্বপূর্ণ অসমতা দেওয়া হয়েছে আপার বাউন্ড উপপাদ্য দ্বারা, যা প্রথমে দ্বারা প্রমাণিত হয়, যা বলে যে n শীর্ষযুক্ত একটি d-মাত্রিক পলিটোপে একই সংখ্যক শীর্ষযুক্ত পার্শ্ববর্তী পলিটোপের মতো অন্য যে কোনও মাত্রার সর্বাধিক সংখ্যক মুখ থাকতে পারেঃ যেখানে তারকাচিহ্নটির অর্থ হল যে যোগফলের চূড়ান্ত পদটি অর্ধেক করা উচিত যখন d জোড় হয়। উপসর্গহীনভাবে, এটি বোঝায় যে সমস্ত মাত্রার বেশিরভাগ মুখ রয়েছে। এমনকি চারটি মাত্রায়, উত্তল পলিটোপগুলির সম্ভাব্য f-ভেক্টরের সেটটি চার-মাত্রিক পূর্ণসংখ্যা জালকের একটি উত্তল উপসেট গঠন করে না এবং এই ভেক্টরগুলির সম্ভাব্য মান সম্পর্কে অনেক কিছু অজানা থেকে যায়। গ্রাফ-তাত্ত্বিক বৈশিষ্ট্য পলিটোপগুলির মুখের সংখ্যা অনুসন্ধানের পাশাপাশি গবেষকরা তাদের অন্যান্য সমন্বিত বৈশিষ্ট্যগুলি অধ্যয়ন করেছেন, যেমন পলিটোপগুলির শীর্ষ এবং প্রান্ত থেকে প্রাপ্ত গ্রাফের বিবরণ (তাদের 1-কঙ্কাল)। বালিনস্কির উপপাদ্য বলে যে কোনও ডি-মাত্রিক উত্তল পলিটোপ থেকে এইভাবে প্রাপ্ত গ্রাফটি ডি-ভার্টেক্স-সংযুক্ত। ত্রিমাত্রিক পলিহেড্রার ক্ষেত্রে, এই বৈশিষ্ট্য এবং প্ল্যানারিটি পলিহেড্রার গ্রাফগুলিকে সঠিকভাবে চিহ্নিত করতে ব্যবহার করা যেতে পারেঃ স্টেনিৎজের উপপাদ্য বলে যে জি একটি ত্রিমাত্রিক পলিহেড্রনের কঙ্কাল যদি এবং শুধুমাত্র যদি জি একটি 3-ভার্টেক্স-সংযুক্ত প্ল্যানার গ্রাফ হয়। এর একটি উপপাদ্য (পূর্বে মিশা পার্লস দ্বারা অনুমান করা হয়েছিল) বলে যে কেউ তার গ্রাফ থেকে একটি সাধারণ পলিটোপের মুখের কাঠামো পুনর্গঠন করতে পারে। অর্থাৎ, যদি একটি প্রদত্ত অনির্দিষ্ট গ্রাফ একটি সাধারণ পলিটোপের কঙ্কাল হয়, তবে শুধুমাত্র একটি পলিটোপ (সমন্বিত সমতুল্য পর্যন্ত) থাকে যার জন্য এটি সত্য। এটি (অ-সহজ) পার্শ্ববর্তী পলিটোপগুলির সাথে তীব্র বৈপরীত্য যার গ্রাফ একটি সম্পূর্ণ গ্রাফ; একই গ্রাফের জন্য বিভিন্ন পার্শ্ববর্তী পলিটোপ থাকতে পারে। অনন্য সিঙ্ক ওরিয়েন্টেশনের উপর ভিত্তি করে এই উপপাদ্যটির আরেকটি প্রমাণ দ্বারা দেওয়া হয়েছিল এবং দেখানো হয়েছিল যে কীভাবে এই উপপাদ্যটি ব্যবহার করে তাদের গ্রাফ থেকে সাধারণ পলিটোপগুলির ফেস ল্যাটিসগুলি পুনর্গঠনের জন্য একটি পলিনোমিয়াল টাইম অ্যালগরিদম বের করা যায়। যাইহোক, একটি প্রদত্ত গ্রাফ বা জালকে একটি সাধারণ পলিটোপের মুখের জাল হিসাবে উপলব্ধি করা যায় কিনা তা পরীক্ষা করা সরল পলিটোপগুলির উপলব্ধির সমতুল্য (মেরুকরণ দ্বারা), যা দ্বারা বাস্তব অস্তিত্ব তত্ত্বের জন্য সম্পূর্ণ হিসাবে দেখানো হয়েছিল। লিনিয়ার প্রোগ্রামিংয়ের জন্য সিম্প্লেক্স পদ্ধতির প্রসঙ্গে, একটি পলিটোপের ব্যাস বোঝা গুরুত্বপূর্ণ, অন্য কোনও শীর্ষ থেকে কোনও পথ দিয়ে যে কোনও শীর্ষে পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম প্রান্তের সংখ্যা। একটি রৈখিক প্রোগ্রামের রৈখিক বৈষম্যের ব্যবস্থা একটি পলিটোপের দিকগুলিকে সংজ্ঞায়িত করে যা প্রোগ্রামের সমস্ত সম্ভাব্য সমাধানের প্রতিনিধিত্ব করে এবং সিম্প্লেক্স পদ্ধতিটি এই পলিটোপে একটি পথ অনুসরণ করে সর্বোত্তম সমাধান খুঁজে পায়। সুতরাং, ব্যাস এই পদ্ধতির জন্য প্রয়োজনীয় পদক্ষেপের সংখ্যার উপর একটি নিম্ন সীমা প্রদান করে। হির্শের অনুমান, যা এখন অপ্রমাণিত, নির্দিষ্ট মাত্রা এবং দিকগুলির সংখ্যা সহ একটি পলিটোপের ব্যাস কতটা বড় হতে পারে তার উপর একটি শক্তিশালী (রৈখিক) বন্ধনের পরামর্শ দেয়। তাদের ব্যাসের উপরের সীমানাগুলি দুর্বল (আধা-বহুপদী এবং) জানা যায়, পাশাপাশি পলিটোপগুলির বিশেষ শ্রেণীর জন্য হির্শ অনুমানের প্রমাণও পাওয়া যায়। গণনামূলক বৈশিষ্ট্য একটি প্রদত্ত পলিটোপের শীর্ষগুলির সংখ্যা কিছু প্রাকৃতিক সংখ্যা k দ্বারা আবদ্ধ কিনা তা নির্ধারণ করা একটি গণনামূলকভাবে কঠিন সমস্যা এবং জটিলতা শ্রেণীর পিপি-র জন্য সম্পূর্ণ। 0-1 পলিটোপগুলির দিকগুলি পূর্ণসংখ্যা প্রোগ্রামিংয়ের জন্য কাটিং-প্লেন পদ্ধতির প্রসঙ্গে এটি গুরুত্বপূর্ণ যে পলিটোপগুলির দিকগুলি সঠিকভাবে বর্ণনা করতে সক্ষম হতে হবে যার সংমিশ্রণগত অপ্টিমাইজেশান সমস্যার সমাধানের সাথে সামঞ্জস্যপূর্ণ শীর্ষ রয়েছে। প্রায়শই, এই সমস্যাগুলির সমাধান থাকে যা বাইনারি ভেক্টর দ্বারা বর্ণনা করা যেতে পারে এবং সংশ্লিষ্ট পলিটোপগুলির শীর্ষ স্থানাঙ্ক থাকে যা সমস্ত শূন্য বা এক। উদাহরণস্বরূপ, বারখফ পলিটোপ বিবেচনা করুন, n × n ম্যাট্রিক্সের সেট যা ক্রমাঙ্কন ম্যাট্রিক্সের উত্তল সংমিশ্রণ থেকে গঠিত হতে পারে। সমতুল্যভাবে, এর শীর্ষগুলি একটি সম্পূর্ণ দ্বিদলীয় গ্রাফের সমস্ত নিখুঁত মিলগুলি বর্ণনা করে বলে মনে করা যেতে পারে এবং এই পলিটোপে একটি রৈখিক অপ্টিমাইজেশান সমস্যাকে দ্বিদলীয় ন্যূনতম ওজন নিখুঁত মিল সমস্যা হিসাবে ব্যাখ্যা করা যেতে পারে। বারখফ-ভন নিউম্যান উপপাদ্য বলে যে এই পলিটোপকে দুই ধরনের রৈখিক বৈষম্য বা সমতা দ্বারা বর্ণনা করা যেতে পারে। প্রথমত, প্রতিটি ম্যাট্রিক্স কোষের জন্য একটি সীমাবদ্ধতা রয়েছে যে এই কোষের একটি অ-ঋণাত্মক মান রয়েছে। এবং দ্বিতীয়ত, ম্যাট্রিক্সের প্রতিটি সারি বা কলামের জন্য, একটি সীমাবদ্ধতা রয়েছে যে সেই সারি বা কলামের কোষগুলির যোগফল একটির সমান। সারি এবং কলামের সীমাবদ্ধতাগুলি n2 − 2n + 1 মাত্রার একটি রৈখিক সাবস্পেসকে সংজ্ঞায়িত করে যেখানে বারখফ পলিটোপ অবস্থিত এবং অ-নেতিবাচকতা সীমাবদ্ধতাগুলি সেই সাবস্পেসের মধ্যে বারখফ পলিটোপের দিকগুলি সংজ্ঞায়িত করে। যাইহোক, বারখফ পলিটোপটি অস্বাভাবিক কারণ এর দিকগুলির একটি সম্পূর্ণ বিবরণ পাওয়া যায়। অন্যান্য অনেক 0-1 পলিটোপগুলির জন্য, সূচকীয়ভাবে অনেকগুলি বা সুপারএক্সপোনেন্সিয়ালভাবে অনেকগুলি দিক রয়েছে এবং তাদের দিকগুলির কেবল আংশিক বিবরণ পাওয়া যায়। আরও দেখুন বিমূর্ত পলিটোপ কম্বিনেটরিয়াল কমিউটেটিভ বীজগণিত ম্যাট্রয়েড পলিটোপ অর্ডার পলিটোপ সরল গোলক স্থিতিশীল ম্যাচিং পলিটোপ নোটস রেফারেন্স। । । । । । । । । । । । । । । বাইরের লিঙ্ক।