Polyhedral combinatorics
پولی ہیڈرل کمبینٹوریکس ریاضی کی ایک شاخ ہے، جو کمبینٹوریکس اور مجرد جیومیٹری کے اندر ہے، جو کنویکس پولی ہیڈرا اور اعلی جہتی کنویکس پولی ٹاپس کے چہروں کی گنتی اور وضاحت کے مسائل کا مطالعہ کرتی ہے۔ پولی ہیڈرل کمبینٹوریکس میں تحقیق دو الگ الگ شعبوں میں ہوتی ہے۔ اس شعبے میں ریاضی دان پولی ٹاپس کے امتزاج کا مطالعہ کرتے ہیں۔ مثال کے طور پر، وہ ایسی عدم مساوات کی تلاش کرتے ہیں جو صوابدیدی پولی ٹاپس میں یا پولی ٹاپس کے کچھ اہم ذیلی طبقات میں عمودی، کناروں اور اعلی جہتوں کے چہروں کی تعداد کے درمیان تعلقات کو بیان کرتی ہیں، اور پولی ٹاپس کی دیگر مشترکہ خصوصیات کا مطالعہ کرتے ہیں جیسے کہ ان کا رابطہ اور قطر (کسی دوسرے سرے سے کسی بھی سرے تک پہنچنے کے لیے درکار مراحل کی تعداد)۔ مزید برآں، بہت سے کمپیوٹر سائنس دان انٹیجر پروگرامنگ کے مسائل سے پیدا ہونے والے بعض مخصوص پولی ٹاپس (خاص طور پر 0-1 پولی ٹاپس، جن کے عمودی حصے ہائپر کیوب کے ذیلی سیٹ ہیں) کے چہروں کی درست وضاحت میں تحقیق کو بیان کرنے کے لیے "پولی ہیڈرل کمبینٹوریکس" کا جملہ استعمال کرتے ہیں۔ چہرے اور چہرے کی گنتی کرنے والے ویکٹر ایک کنویکس پولیٹوپ P کے چہرے کو P اور ایک بند نصف جگہ H کے چوراہے کے طور پر اس طرح بیان کیا جا سکتا ہے کہ H کی حد میں P کا کوئی اندرونی نقطہ نہ ہو۔ چہرے کا طول و عرض اس ہل کا طول و عرض ہے۔ 0 جہتی چہرے خود عمودی ہوتے ہیں، اور 1 جہتی چہرے (جنہیں کناروں کے نام سے جانا جاتا ہے) عمودی حصوں کے جوڑوں کو جوڑنے والے لکیر کے حصے ہوتے ہیں۔ نوٹ کریں کہ اس تعریف میں خالی سیٹ اور پورے پولیٹوپ P کے چہرے بھی شامل ہیں۔ اگر P کا خود طول و عرض d ہے، تو طول و عرض d−1 والے P کے چہروں کو P کے پہلو کہا جاتا ہے اور طول و عرض d−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) = βxd−i−1 کے گتانک کے طور پر کرتے ہیں (مثال کے طور پر، آکٹا ہیڈرون کے لیے یہ کثیر الجہتی f (x) = x3 + 6x2 + 12x + 8 دیتا ہے)، تو h-ویکٹر کثیر الجہتی h (x) = f (x−1) کے گتانک کی فہرست دیتا ہے (پھر، آکٹا ہیڈرون کے لیے، h (x) = x3 + 3x2 + 3x + 1)۔ جیسا کہ زیگلر لکھتے ہیں، "سادہ پولی ٹاپس کے بارے میں مختلف مسائل کے لیے، ایچ-ویکٹر f-ویکٹرز کے مقابلے چہرے کے نمبروں کے بارے میں معلومات کو انکوڈ کرنے کا ایک بہت زیادہ آسان اور جامع طریقہ ہے۔" مساوات اور عدم مساوات پولیٹوپ کے f-ویکٹر کے کوفیشنٹس کے درمیان سب سے اہم تعلق یولر کا فارمولا β (−1) آئی ایف آئی = 0 ہے، جہاں توسیعی f-ویکٹر کے کوفیشنٹس پر رقم کی شرائط کی حد ہوتی ہے۔ تین جہتوں میں، توسیع شدہ 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۔ اسٹینٹز تھیوریم کے مطابق ان مساوات اور عدم مساوات کو پورا کرنے والا کوئی بھی 3 جہتی انٹیجر ویکٹر کنویکس پولی ہیڈرون کا f-ویکٹر ہوتا ہے۔ اعلی جہتوں میں، پولیٹوپ کے چہروں کی تعداد کے درمیان دیگر تعلقات بھی اہم ہو جاتے ہیں، بشمول ڈیہن-سمرویل مساوات جو سادہ پولیٹوپس کے ایچ-ویکٹر کے لحاظ سے ظاہر ہوتی ہیں، تمام k کے لیے سادہ شکل hk = hd−k لیتی ہیں۔ k = 0 کے ساتھ ان مساوات کی مثال یولر کے فارمولے کے مساوی ہے لیکن d> 3 کے لیے ان مساوات کی دیگر مثالیں ایک دوسرے سے لکیری طور پر آزاد ہیں اور اضافی طریقوں سے ایچ-ویکٹرز (اور اس لیے f-ویکٹرز) کو بھی محدود کرتی ہیں۔ پولیٹوپ چہرے کی گنتی پر ایک اور اہم عدم مساوات اوپری باؤنڈ تھیوریم کے ذریعہ دی گئی ہے، جو سب سے پہلے اس کے ذریعہ ثابت ہوئی ہے، جس میں کہا گیا ہے کہ n عمودی کے ساتھ ایک D-جہتی پولیٹوپ میں کسی دوسرے طول و عرض کے زیادہ سے زیادہ اتنے ہی چہرے ہو سکتے ہیں جتنے پڑوسی پولیٹوپ کے برابر ہوتے ہیں۔ عمودی: جہاں ستارے کا مطلب ہے کہ جب d یکساں ہو تو رقم کی آخری اصطلاح کو آدھا کر دیا جانا چاہیے۔ غیر علامتی طور پر، اس کا مطلب یہ ہے کہ تمام جہتوں کے زیادہ تر چہرے موجود ہیں۔ یہاں تک کہ چار جہتوں میں بھی، کنویکس پولی ٹاپس کے ممکنہ f-ویکٹروں کا مجموعہ چار جہتی انٹیجر لیٹس کا کنویکس سب سیٹ نہیں بناتا، اور ان ویکٹروں کی ممکنہ اقدار کے بارے میں بہت کچھ نامعلوم رہتا ہے۔ گراف تھیوریٹک خصوصیات پولی ٹاپس کے چہروں کی تعداد کی تحقیقات کے ساتھ ساتھ، محققین نے ان کی دیگر مشترکہ خصوصیات کا مطالعہ کیا ہے، جیسے کہ پولی ٹاپس کے عمودی اور کناروں سے حاصل کردہ گراف کی وضاحت (ان کا 1-سکلیٹا)۔ بالنسکی کا نظریہ بیان کرتا ہے کہ کسی بھی ڈی-جہتی کنویکس پولیٹوپ سے اس طرح حاصل کردہ گراف ڈی-ورٹیکس سے جڑا ہوا ہے۔ تین جہتی پولی ہیڈرا کے معاملے میں، اس خاصیت اور پلانریٹی کو پولی ہیڈرا کے گراف کی قطعی خصوصیت کے لیے استعمال کیا جا سکتا ہے: اسٹینٹز تھیوریم میں کہا گیا ہے کہ G تین جہتی پولی ہیڈرون کا کنکال ہے اگر اور صرف اس صورت میں جب G 3-ورٹیکس سے منسلک پلانر گراف ہو۔ ایک تھیوریم (جس کا پہلے مائیکا پیرلز نے قیاس کیا تھا) میں کہا گیا ہے کہ کوئی بھی اس کے گراف سے ایک سادہ پولیٹوپ کے چہرے کی ساخت کو دوبارہ تشکیل دے سکتا ہے۔ یعنی، اگر کوئی غیر ہدایت شدہ گراف ایک سادہ پولیٹوپ کا کنکال ہے، تو صرف ایک پولیٹوپ (مشترکہ مساوات تک) ہے جس کے لیے یہ درست ہے۔ یہ (غیر سادہ) پڑوسی پولی ٹاپس کے بالکل برعکس ہے جس کا گراف ایک مکمل گراف ہے ؛ ایک ہی گراف کے لیے بہت سے مختلف پڑوسی پولی ٹاپس ہو سکتے ہیں۔ منفرد سنک سمتوں پر مبنی اس تھیوریم کا ایک اور ثبوت ان کے ذریعے دیا گیا تھا، اور دکھایا گیا تھا کہ اس تھیوریم کو ان کے گراف سے سادہ پولی ٹاپس کے چہرے کی جالی کی تعمیر نو کے لیے کثیر الجہتی ٹائم الگورتھم حاصل کرنے کے لیے کیسے استعمال کیا جائے۔ تاہم، یہ جانچنا کہ آیا کسی دیئے گئے گراف یا جالی کو ایک سادہ پولیٹوپ کے چہرے کی جالی کے طور پر محسوس کیا جاسکتا ہے، سادہ پولیٹوپس کے ادراک کے مساوی (قطعیت کے لحاظ سے) ہے، جسے حقیقی کے وجودی نظریہ کے لیے مکمل دکھایا گیا تھا۔ لکیری پروگرامنگ کے لیے سمپلیکس طریقہ کار کے تناظر میں، پولیٹوپ کے قطر کو سمجھنا ضروری ہے، جو کسی دوسرے سرے سے راستے کے ذریعے کسی بھی سرے تک پہنچنے کے لیے درکار کم از کم کناروں کی تعداد ہے۔ لکیری پروگرام کی لکیری عدم مساوات کا نظام پولیٹوپ کے پہلوؤں کی وضاحت کرتا ہے جو پروگرام کے تمام قابل عمل حل کی نمائندگی کرتا ہے، اور سمپلیکس طریقہ اس پولیٹوپ میں کسی راستے پر چل کر بہترین حل تلاش کرتا ہے۔ اس طرح، قطر اس طریقہ کار کے لیے درکار مراحل کی تعداد پر ایک کم حد فراہم کرتا ہے۔ ہرش قیاس، جسے اب غلط قرار دیا گیا ہے، نے ایک مضبوط (لکیری) پابند تجویز کیا کہ مقررہ طول و عرض اور پہلوؤں کی تعداد کے ساتھ پولیٹوپ کا قطر کتنا بڑا ہو سکتا ہے۔ ان کے قطر پر کمزور (نیم کثیر الجہتی اور) اوپری حدود کے ساتھ ساتھ پولی ٹاپس کی خصوصی کلاسوں کے لیے ہرش قیاس کے ثبوت بھی معلوم ہیں۔ کمپیوٹیشنل خصوصیات یہ فیصلہ کرنا کہ آیا کسی دی گئی پولیٹوپ کے عمودی حصوں کی تعداد کسی قدرتی نمبر k سے منسلک ہے، کمپیوٹیشنل طور پر ایک مشکل مسئلہ ہے اور پیچیدگی کلاس پی پی کے لیے مکمل ہے۔ 0-1 پولی ٹاپس کے پہلو انٹیجر پروگرامنگ کے لیے کٹنگ پلین طریقوں کے تناظر میں اہم ہے کہ وہ پولی ٹاپس کے پہلوؤں کو درست طریقے سے بیان کرنے کے قابل ہو جن کے عمودی حصے مشترکہ اصلاح کے مسائل کے حل سے مطابقت رکھتے ہیں۔ اکثر، ان مسائل کے حل ہوتے ہیں جنہیں بائنری ویکٹر کے ذریعے بیان کیا جا سکتا ہے، اور متعلقہ پولی ٹاپس میں ورٹیکس کوآرڈینیٹ ہوتے ہیں جو تمام صفر یا ایک ہوتے ہیں۔ مثال کے طور پر، برخوف پولیٹوپ پر غور کریں، جو کہ n × n میٹرکس کا مجموعہ ہے جو پرموٹیشن میٹرکس کے کنویکس امتزاج سے تشکیل پایا جا سکتا ہے۔ مساوی طور پر، اس کے عمودی حصوں کو ایک مکمل دو طرفہ گراف میں تمام کامل ملاپ کو بیان کرنے کے طور پر سوچا جا سکتا ہے، اور اس پولیٹوپ پر لکیری اصلاح کے مسئلے کو دو طرفہ کم از کم وزن کامل ملاپ کے مسئلے کے طور پر سمجھا جا سکتا ہے۔ برخوف-وان نیومن تھیوریم میں کہا گیا ہے کہ اس پولیٹوپ کو دو قسم کی لکیری عدم مساوات یا مساوات سے بیان کیا جا سکتا ہے۔ سب سے پہلے، ہر میٹرکس سیل کے لیے، ایک رکاوٹ ہے کہ اس سیل کی غیر منفی قدر ہے۔ اور دوسرا، میٹرکس کی ہر صف یا کالم کے لیے، ایک رکاوٹ ہے کہ اس صف یا کالم میں موجود خلیوں کا مجموعہ ایک کے برابر ہے۔ صف اور کالم کی رکاوٹیں طول و عرض n2 − 2n + 1 کی ایک لکیری ذیلی جگہ کی وضاحت کرتی ہیں جس میں برخوف پولیٹوپ واقع ہے، اور غیر منفی رکاوٹیں اس ذیلی جگہ کے اندر برخوف پولیٹوپ کے پہلوؤں کی وضاحت کرتی ہیں۔ تاہم، برخوف پولیٹوپ اس لحاظ سے غیر معمولی ہے کہ اس کے پہلوؤں کی مکمل تفصیل دستیاب ہے۔ بہت سے دوسرے 0-1 پولی ٹاپس کے لیے، تیزی سے بہت سے یا سپر ایکسپونینشیل طور پر بہت سے پہلو ہیں، اور ان کے پہلوؤں کی صرف جزوی وضاحت دستیاب ہے۔ خلاصہ پولیٹوپ کمبنیٹوریئل کمیونیٹیٹو الجبرا میٹرائڈ پولیٹوپ آرڈر پولیٹوپ آسان دائرہ مستحکم مماثل پولیٹوپ نوٹ حوالہ جات بھی دیکھیں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ بیرونی روابط۔