Forcing graph
گراف تھیوری میں، فورسنگ گراف وہ ہوتا ہے جس کی کثافت اس بات کا تعین کرتی ہے کہ آیا گراف کی ترتیب نیم بے ترتیب ہے۔ یہ اصطلاح سب سے پہلے 1989 میں چنگ، گراہم اور ولسن نے وضع کی تھی، اور گراف کے ترتیبات میں چھیدورانڈومنیس کے مطالعہ میں گراف کو مجبور کرنا ایک اہم کردار ادا کرتا ہے۔ تعریفیں لیٹ، جسے ذیلی گراف کثافت کہا جاتا ہے (خاص طور پر، کی کنارے کی کثافت ہے)۔ گرافوں کی ترتیب کو نیم بے ترتیب کہا جاتا ہے اگر، تمام گرافوں کے لیے، کنارے کی کثافت کچھ کے قریب پہنچتی ہے اور بڑھتے ہوئے قریب پہنچتی ہے، جہاں کناروں کی تعداد ہے۔ بدیہی طور پر، اس کا مطلب یہ ہے کہ دیئے گئے کنارے کی کثافت کے ساتھ گراف کی ترتیب میں گراف ہومومورفزم کی تعداد ہوتی ہے جس کی بے ترتیب گراف کی ترتیب میں توقع کی جائے گی۔ گراف کو فورسنگ کہا جاتا ہے اگر تمام گراف کے ترتیبات کے لیے جہاں لامحدود تک پہنچتا ہے، اگر قریب آتا ہے تو نیم بے ترتیب ہوتا ہے۔ دوسرے لفظوں میں، صرف ایک ہی گراف کی ہومومورفزم کثافت کی جانچ کر کے اس بات کی تصدیق کی جا سکتی ہے کہ گراف کی ترتیب نیم بے ترتیب ہے۔ گرافون کی زبان کا استعمال کرتے ہوئے گراف کو مجبور کرنے کی دوسری تعریف ہے۔ رسمی طور پر، گراف کو فورسنگ کہا جاتا ہے اگر ہر گرافون ایسا ہو جو مستقل ہو۔ بدیہی طور پر، یہ سمجھ میں آتا ہے کہ یہ تعریفیں متعلق ہیں۔ مستقل گرافون ایرڈس-رینی بے ترتیب گراف کی نمائندگی کرتا ہے، لہذا کوئی توقع کر سکتا ہے کہ اس کا نیم بے ترتیب گراف کے ساتھ قریبی تعلق ہوگا۔ درحقیقت یہ تعریفیں مساوی ہیں۔ مثالوں پر غور کرنے والا پہلا مجبور کرنے والا گراف 4-سائیکل ہے، کیونکہ یہ نیم بے ترتیب کے دیگر حالات کے ساتھ قریبی تعلق رکھتا ہے۔ چنگ، گراہم اور ولسن نے اسی مقالے میں دکھایا تھا کہ فارم کے ہر یکساں سائیکل اور مکمل دو طرفہ گراف مجبور کر رہے ہیں۔ کونلون، فاکس، اور سوڈاکوف نے اس آخری نتیجہ کو ایک حصے میں دو عمودی کے ساتھ تمام دو طرفہ گرافوں کو شامل کرنے کے لیے بڑھایا جو دوسرے حصے میں مکمل ہیں۔ گراف کا ایک خاندان جب بھی سب کے قریب آتا ہے تو مجبور کرنا نیم بے ترتیب ہوتا ہے۔ مجبور کرنے والے خاندانوں کی خصوصیت کرنا مجبور کرنے والے گراف کی خصوصیت سے کہیں زیادہ مشکل ہے، لہذا بہت کم ایسے ہیں جو معلوم ہیں۔ معروف مجبور کرنے والے خاندانوں میں شامل ہیں:، جہاں ایک مثبت عدد ہے ؛، جہاں اور ساتھ مثبت عدد ہیں ؛، جہاں ؛ اور، جہاں اور۔ مجبور کرنے والا قیاس 2004 میں سکوکن اور تھوما نے پیش کیا تھا اور 2010 میں کونلون، فاکس اور سوڈاکوف نے اسے باقاعدہ بنایا تھا۔ یہ گراف کو مجبور کرنے کے لیے ایک خصوصیت فراہم کرتا ہے، جسے مندرجہ ذیل طور پر باقاعدہ بنایا گیا ہے: اس دعوے کی ایک سمت معروف ہے۔ چنگ، گراہم اور ولسن نے دکھایا کہ اگر کسی گراف کا ایک عجیب چکر ہے، تو یہ مجبور نہیں کیا جا سکتا، لہذا اگر کوئی گراف مجبور کر رہا ہے، تو اسے دو طرفہ ہونا چاہیے۔ نیز، کونلون، فاکس، اور سوڈاکوف نے استدلال کیا کہ جب تقریبا باقاعدہ (اور ضروری نہیں کہ نیم بے ترتیب) گراف ترتیب ہو تو ہر جنگل تک پہنچتا ہے۔ اس طرح، مجبور کرنے والا گراف دو طرفہ ہونا چاہیے اور اس کا کم از کم ایک چکر ہونا چاہیے۔ دوسری سمت ابھی ثابت ہونا باقی ہے، لیکن کوئی مجبور کرنے والا گراف نہیں ملا ہے جس میں یہ دونوں خصوصیات نہ ہوں۔ مجبور کرنے والے قیاس سے سڈورنکو کا قیاس بھی ظاہر ہوتا ہے، جو میدان میں ایک دیرینہ قیاس ہے۔ یہ معلوم ہے کہ تمام مجبور کرنے والے گراف سڈورنکو ہیں، لہذا اگر مجبور کرنے والا قیاس درست ہے، تو کم از کم ایک سائیکل والے تمام دو طرفہ گراف سڈورنکو ہوں گے۔ چونکہ درخت سڈورنکو ہیں، اس لیے تمام دو طرفہ گراف سڈورنکو ہوں گے۔ حوالہ جات گراف خاندان