Order dimension
ریاضی میں، جزوی طور پر ترتیب شدہ سیٹ (پوسیٹ) کا طول و عرض کل آرڈرز کی سب سے چھوٹی تعداد ہے جس کا چوراہا جزوی آرڈر کو جنم دیتا ہے۔ اس تصور کو بعض اوقات آرڈر طول و عرض یا جزوی ترتیب کا دشنک-ملر طول و عرض بھی کہا جاتا ہے۔ پہلے مطالعہ شدہ ترتیب طول و عرض ؛ یہاں فراہم کردہ اس موضوع کے مزید تفصیلی علاج کے لیے، دیکھیں۔ رسمی تعریف ایک محدود پوزیٹ P کا طول و عرض سب سے کم عدد t ہے جس کے لیے P کی لکیری توسیعات کا ایک خاندان موجود ہے تاکہ، P میں ہر x اور y کے لیے، x P میں y سے پہلے ہو اگر اور صرف اس صورت میں جب یہ تمام لکیری توسیعات میں y سے پہلے ہو۔ یعنی آرڈر طول و عرض کی ایک متبادل تعریف کل آرڈرز کی کم سے کم تعداد ہے جیسے کہ P ان کے پروڈکٹ میں اجزاء کے لحاظ سے ترتیب کے ساتھ سرایت کرتا ہے یعنی۔ اگر اور صرف اگر سب کے لیے i (،)۔ ریالائزرز X پر لکیری آرڈرز کے ایک خاندان کو پوزیٹ P = (X، <P) کا ریالائزر کہا جاتا ہے، اگر، جس کا مطلب یہ ہے کہ X میں کسی بھی x اور y کے لیے، x <Py قطعی طور پر جب x <1y، x <2y، اور x <ty۔ اس طرح، پوزیٹ P کی طول و عرض کی مساوی تعریف "P کے حقیقت ساز کی سب سے کم بنیادی حیثیت" ہے۔ یہ دکھایا جا سکتا ہے کہ لکیری ایکسٹینشنز کا کوئی بھی غیر خالی خاندان R ایک محدود جزوی طور پر ترتیب شدہ سیٹ P کا حقیقت ساز ہے اگر اور صرف اس صورت میں جب، P کے ہر اہم جوڑے (x, y) کے لیے، R میں کسی ترتیب کے لیے y <ix۔ مثال کے طور پر n کو مثبت عدد مان لیں، اور P کو عناصر ai اور b پر جزوی ترتیب مان لیں (1 ≤ i ≤ n کے لیے) جس میں جب بھی i ≤ bj ہوتا ہے، لیکن کوئی دوسرے جوڑے موازنہ نہیں ہوتے ہیں۔ خاص طور پر، اے آئی اور بی پی میں بے مثال ہیں ؛ پی کو تاج گراف کی مبنی شکل کے طور پر دیکھا جا سکتا ہے۔ مثال میں n = 4 کے لیے اس قسم کی ترتیب دکھائی گئی ہے۔ پھر، ہر ایک i کے لیے، کسی بھی حقیقت ساز کو ایک لکیری ترتیب پر مشتمل ہونا چاہیے جو تمام aj کے ساتھ شروع ہوتا ہے سوائے ai (کسی ترتیب میں) کے، پھر bi، پھر ai شامل ہوتا ہے، اور باقی تمام bj کے ساتھ ختم ہوتا ہے۔ اس کی وجہ یہ ہے کہ اگر کوئی ریئلائزر ہوتا جس میں اس طرح کا آرڈر شامل نہ ہوتا، تو اس ریئلائزر کے آرڈرز کے انٹرسیکشن میں آئی پریسیڈنگ بی ہوتا، جو پی میں آئی اور بی کی عدم موازنہیت سے متصادم ہوتا۔ اور اس کے برعکس، لکیری آرڈرز کا کوئی بھی خاندان جس میں ہر ایک کے لیے اس قسم کا ایک آرڈر شامل ہوتا ہے، اس کے انٹرسیکشن کے طور پر پی ہوتا ہے۔ اس طرح، P کا طول و عرض بالکل n ہے۔ درحقیقت، P کو طول و عرض n کی پوزیشن کی معیاری مثال کے طور پر جانا جاتا ہے، اور اسے عام طور پر Sn سے ظاہر کیا جاتا ہے۔ آرڈر طول و عرض دو کے ساتھ جزوی آرڈرز کو جزوی آرڈرز کے طور پر نمایاں کیا جا سکتا ہے جن کا تقابلی گراف مختلف جزوی آرڈر کے تقابلی گراف کی تکمیل ہے۔ یعنی، P آرڈر طول و عرض دو کے ساتھ ایک جزوی ترتیب ہے اگر اور صرف اس صورت میں جب عناصر کے ایک ہی سیٹ پر جزوی ترتیب Q موجود ہو، جیسے کہ مختلف عناصر کا ہر جوڑا x، y ان دو جزوی ترتیبات میں سے بالکل ایک میں موازنہ ہو۔ اگر P کو دو لکیری ایکسٹینشنز کے ذریعے حاصل کیا جاتا ہے، تو P کی تکمیل کرنے والی جزوی ترتیب Q کو دو لکیری ایکسٹینشنز میں سے کسی ایک کو الٹ کر حاصل کیا جا سکتا ہے۔ لہذا، طول و عرض دو کے جزوی ترتیبات کے تقابلی گراف بالکل تعدد گراف ہیں، وہ گراف جو خود تقابلی گراف ہیں اور تقابلی گراف کی تکمیل کرتے ہیں۔ آرڈر طول و عرض دو کے جزوی آرڈرز میں سیریز متوازی جزوی آرڈرز شامل ہیں۔ وہ بالکل جزوی ترتیبات ہیں جن کے ہس خاکے میں غلبہ کے خاکے ہوتے ہیں، جو کارٹیسیئن نقاط کے طور پر ایک حقیقت پسند کے دو تغیرات میں پوزیشنوں کو استعمال کرکے حاصل کیے جا سکتے ہیں۔ کمپیوٹیشنل پیچیدگی کثیر الجہتی وقت میں اس بات کا تعین کرنا ممکن ہے کہ آیا دیئے گئے محدود جزوی طور پر ترتیب شدہ سیٹ میں زیادہ سے زیادہ دو ترتیب طول و عرض ہیں، مثال کے طور پر، یہ جانچ کر کے کہ آیا جزوی ترتیب کا تقابلی گراف ایک ترتیب گراف ہے۔ تاہم، کسی بھی k ≤ 3 کے لیے، یہ جانچنا NP مکمل ہے کہ آیا آرڈر کا طول و عرض زیادہ سے زیادہ k ہے۔ گرافوں کے واقع پازیٹ کسی بھی غیر ہدایت شدہ گراف G کے واقع پازیٹ میں G کے عمودی اور کنارے اس کے عناصر کے طور پر ہوتے ہیں۔ اس پوزیشن میں، x ≤ y اگر x = y یا x میں سے کوئی ایک عمودی ہے، تو y ایک کنارے ہے، اور x y کا اختتامی نقطہ ہے۔ بعض قسم کے گرافوں کو ان کے انسیڈینس پوزیٹ کے آرڈر طول و عرض سے منسوب کیا جا سکتا ہے: ایک گراف ایک پاتھ گراف ہے اگر اور صرف اس صورت میں جب اس کے انسیڈینس پوزیٹ کا آرڈر طول و عرض زیادہ سے زیادہ دو ہو، اور شنائڈر کے نظریہ کے مطابق یہ ایک پلینر گراف ہے اگر اور صرف اس صورت میں جب اس کے انسیڈینس پوزیٹ کا آرڈر طول و عرض زیادہ سے زیادہ تین ہو۔ n عمودی پر ایک مکمل گراف کے لیے، انسیڈنس پوزیٹ کا آرڈر طول و عرض ہے۔ اس کے بعد یہ ہوتا ہے کہ تمام سادہ این-ورٹیکس گرافوں میں آرڈر طول و عرض کے ساتھ انسیڈنس پوزیٹ ہوتے ہیں۔ طول و عرض کی عمومی کاری k-طول و عرض (تحریری) کا تصور ہے جو زیادہ سے زیادہ k پر لمبائی کی زنجیروں کی کم سے کم تعداد ہے جس کی پیداوار میں جزوی ترتیب کو سرایت کیا جا سکتا ہے۔ خاص طور پر، کسی آرڈر کے 2-طول و عرض کو سب سے چھوٹے سیٹ کے سائز کے طور پر دیکھا جا سکتا ہے تاکہ آرڈر اس سیٹ پر شمولیت کے آرڈر میں سرایت کرے۔ وقفہ جہتی حوالہ جات بھی دیکھیں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ آرڈر تھیوری طول و عرض کا نظریہ