Blow-up lemma
بلو اپ لیما، جسے 1997 میں جانوس کوملوس، گابر این سارکزی، اور اینڈری زیمیرڈی نے ثابت کیا، انتہائی گراف تھیوری کا ایک اہم نتیجہ ہے، خاص طور پر باقاعدگی کے طریقہ کار کے تناظر میں۔ اس میں کہا گیا ہے کہ زیمیرڈی کی باقاعدگی لیما کے بیان میں باقاعدہ جوڑے باؤنڈ ڈگری کے پھیلے ہوئے گرافوں کو سرایت کرنے کے تناظر میں مکمل دو طرفہ گرافوں کی طرح برتاؤ کرتے ہیں۔ تعریفیں اور بیان بلو اپ لیما کو باضابطہ طور پر بیان کرنے کے لیے، ہمیں پہلے ایک سپر ریگولر جوڑے کے تصور کی وضاحت کرنے کی ضرورت ہے۔ سپر ریگولر جوڑے ورٹیکس سیٹ کے ذیلی سیٹوں کی ایک جوڑی کو-سپر ریگولر کہا جاتا ہے اگر ہر اور اطمینان بخش کے لیے اور ہمارے پاس ہے اور اس کے علاوہ، سب کے لیے اور سب کے لیے۔ یہاں کے ساتھ اور اس طرح کے جوڑوں کی تعداد کو ظاہر کرتا ہے جو کہ ایک کنارے ہے۔ بلو اپ لیما کا بیان ترتیب اور مثبت پیرامیٹرز کے گراف کو دیکھتے ہوئے، ایک مثبت موجود ہے جو مندرجہ ذیل ہے۔ آئیے صوابدیدی مثبت عدد ہوں اور آئیے ہم کے عمودی حصوں کو سائز کے جوڑی کے لحاظ سے جداگانہ سیٹوں سے تبدیل کرتے ہیں (اڑتے ہوئے)۔ ہم ایک ہی ورٹیکس سیٹ پر دو گراف بناتے ہیں۔ پہلا گراف متعلقہ ورٹیکس سیٹوں اور کے درمیان مکمل دو طرفہ گراف کے ساتھ ہر کنارے کو تبدیل کرکے حاصل کیا جاتا ہے۔ ایک سپارسر گراف G ہر کنارے کو اور کے درمیان ایک-سپر-ریگولر جوڑی سے تبدیل کر کے بنایا جاتا ہے۔ اگر اس کے ساتھ ایک گراف سرایت کے قابل ہے تو یہ پہلے سے ہی جی پروف اسکیچ میں سرایت کے قابل ہے۔ بلو اپ لیما کا ثبوت ایک بے ترتیب لالچی الگورتھم (آر جی اے) کے استعمال پر مبنی ہے تاکہ اس کے عمودی حصوں کو ترتیب سے سرایت کیا جا سکے۔ اس کے بعد دلیل الگورتھم کی ناکامی کی شرح کو اس طرح پابند کرکے آگے بڑھتی ہے کہ یہ پیرامیٹرز کے مناسب انتخاب کے لیے 1 (اور حقیقت میں) سے کم ہو۔ اس کا مطلب یہ ہے کہ الگورتھم کے کامیاب ہونے کا غیر صفر امکان ہے، اس لیے ایک سرایت موجود ہونی چاہیے۔ اس طریقے سے تمام عمودی حصوں کو براہ راست سرایت کرنے کی کوشش کام نہیں کرتی کیونکہ الگورتھم اس وقت پھنس سکتا ہے جب عمودی حصوں کی صرف ایک چھوٹی سی تعداد باقی رہ جائے۔ اس کے بجائے، ہم عمودی سیٹ کا ایک چھوٹا سا حصہ الگ کرتے ہیں، جسے بفر عمودی کہتے ہیں، اور باقی عمودی حصوں کو سرایت کرنے کی کوشش کرتے ہیں۔ بفر عمودی حصوں کو بعد میں ہال کے شادی کے نظریہ کا استعمال کرتے ہوئے سرایت کیا جاتا ہے تاکہ بفر عمودی حصوں اور بفر عمودی حصوں کے بقیہ عمودی حصوں کے درمیان ایک کامل ملاپ تلاش کیا جا سکے۔ نوٹیشن ہم پچھلے حصوں میں متعارف کرائے گئے تمام نوٹیشن کو ادھار لیتے ہیں۔ جانے دیں۔ چونکہ اس میں سرایت کی جا سکتی ہے، ہم سب کے ساتھ لکھ سکتے ہیں۔ ایک ورٹیکس کے لیے، آئیے اشارہ کریں۔ کے لیے، کے متعلقہ ورٹیکس سیٹوں کے درمیان کناروں کی کثافت کو ظاہر کرتا ہے۔ یہ وہ سرایت ہے جسے ہم بنانا چاہتے ہیں۔ یہ آخری وقت ہے جس کے بعد الگورتھم ختم ہوتا ہے۔ الگورتھم فیز 0 کا خاکہ: ابتدائی طور پر لالچ سے عمودی حصوں کے زیادہ سے زیادہ سیٹ کے طور پر بفر عمودی حصوں کے سیٹ کا انتخاب کریں کم از کم ایک دوسرے سے فاصلہ رکھیں فہرست میں باقی عمودی حصوں (ان میں) کو ترتیب دیں، پہلے کے پڑوسیوں کو رکھیں۔ موجودہ ترجیحی عمودی قطار کا اعلان کریں، جو ابتدائی طور پر خالی ہے۔ تمام "آزاد مقامات" کے سیٹ کی نمائندگی کرنے والے عمودی حصوں کی طرف سے انڈیکس کردہ سیٹوں کی ایک صف کا اعلان کریں، یعنی عمودی حصے میں غیر استعمال شدہ عمودی حصوں کے سیٹ کو پہلے سے سرایت شدہ پڑوسیوں سے کسی بھی ملحقہ شرائط کی خلاف ورزی کیے بغیر نقشہ بنایا جا سکتا ہے۔ شروع کیا جاتا ہے۔ مرحلہ 1: بے ترتیب لالچی ایمبیڈنگ بقیہ عمودی حصوں کے سیٹ میں سے ایک ورٹیکس کا انتخاب مندرجہ ذیل طریقے سے کریں: اگر ترجیحی عمودی حصوں کی قطار خالی نہیں ہے، تو اس میں سے ورٹیکس کا انتخاب کریں بصورت دیگر، بقیہ عمودی حصوں کی فہرست میں سے ایک ورٹیکس کا انتخاب کریں "اچھے" انتخاب کے سیٹ میں سے بے ترتیب طور پر ورٹیکس کے لیے تصویر کا انتخاب کریں، جہاں انتخاب اچھا ہے اگر کوئی بھی نیا فری سیٹ متوقع قیمت سے سائز میں زیادہ مختلف نہ ہو۔ مفت سیٹوں کو اپ ڈیٹ کریں، اور ایسے عمودی حصے رکھیں جن کے مفت سیٹ ترجیحی عمودی سیٹوں کے سیٹ میں آخری اپ ڈیٹ میں ان کے سائز کے لحاظ سے بہت چھوٹے ہو گئے ہیں اگر قطار میں کسی بھی سیٹ کا کافی بڑا حصہ موجود ہو۔ اگر کسی میں بھی غیر بفر عمودی حصے سرایت کرنے کے لیے باقی ہیں یا، وقت کو اپ ڈیٹ کریں اور مرحلہ 1 پر واپس جائیں ؛ بصورت دیگر مرحلہ 2 کی طرف بڑھیں۔ مرحلہ 2: بقیہ عمودی حصوں کے لیے کونگ-ہال کا ملاپ سرایت کرنے کے لیے چھوڑے گئے عمودی حصوں کے سیٹ پر غور کریں، جو قطعی طور پر ہے، اور آزاد مقامات کے سیٹ پر غور کریں۔ ان دونوں سیٹوں کے درمیان ایک دو طرفہ گراف بنائیں، ہر ایک میں شامل ہوں، اور اس دو طرفہ گراف میں ایک بہترین مماثلت تلاش کریں۔ اس مماثلت کے مطابق سرایت کریں۔ درستگی کا ثبوت درستگی کا ثبوت تکنیکی اور کافی ملوث ہے، اس لیے ہم تفصیلات کو چھوڑ دیتے ہیں۔ بنیادی دلیل اس طرح آگے بڑھتی ہے: مرحلہ 1: زیادہ تر عمودی حصے اچھے ہیں، اور کافی عمودی حصے آزاد ہیں، بیک وقت اس پر انڈکشن کے ذریعے ثابت کریں کہ اگر وقت پر سرایت شدہ سرے ہیں، تو انتخاب کا صرف ایک چھوٹا سا حصہ خراب ہے۔ تمام آزاد سیٹ غیر سرایت شدہ عمودی حصوں کے لیے کافی بڑے ہیں۔ مرحلہ 2: "مین لیما" پر غور کریں، اور ایسا جو بہت چھوٹا نہیں ہے۔ اس واقعہ پر غور کریں جہاں پہلے مرحلے کے دوران کوئی عمودی سرایت نہیں ہوتی ہے کیونکہ ہر ایک وقت ایسا ہوتا ہے کہ اس وقت کے آزاد عمودی کا حصہ چھوٹا ہوتا ہے۔ پھر، ہم ثابت کرتے ہیں کہ ہونے کا امکان کم ہے۔ مرحلہ 3: مرحلہ 1 اعلی امکان کے ساتھ کامیاب ہوتا ہے پہلا مرحلہ ناکام ہونے کا واحد طریقہ یہ ہے کہ اگر یہ رک جائے، کیونکہ پہلے مرحلے سے ہم جانتے ہیں کہ ہمیشہ اچھے عمودی کا کافی انتخاب ہوتا ہے۔ پروگرام صرف اس وقت رکتا ہے جب قطار بہت لمبی ہو۔ اس کے بعد دلیل ناکامی کے تمام طریقوں پر یونین باؤنڈنگ کے ذریعے آگے بڑھتی ہے، یہ نوٹ کرتے ہوئے کہ کسی خاص انتخاب کے لیے، اور قطار کے ایک ذیلی سیٹ کی نمائندگی کرنے کے ساتھ جو ناکام ہوا، ٹرپل "مین لیما" کی شرائط کو پورا کرتا ہے، اور اس طرح اس کے ہونے کا امکان کم ہوتا ہے۔ مرحلہ 4: ابتدائی مرحلے میں کوئی قطار نہیں یاد رکھیں کہ فہرست ترتیب دی گئی تھی تاکہ بفر میں عمودی کے پڑوسیوں کو پہلے سرایت مل جائے۔ ان تمام عمودی حصوں کے سرایت ہونے تک کے وقت کو ابتدائی مرحلہ کہا جاتا ہے۔ انڈکشن کے ذریعے ثابت کریں کہ ابتدائی مرحلے کے دوران قطار میں کوئی عمودی حصہ شامل نہیں ہوتا ہے۔ اس کے بعد بفر عمودی کے تمام پڑوسی باقی عمودی سے پہلے شامل ہو جاتے ہیں۔ مرحلہ 5: بفر عمودی حصوں میں کافی آزاد دھبے ہوتے ہیں کسی بھی اور کے لیے، ہم اس امکان پر کافی بڑی نچلی حد تلاش کر سکتے ہیں کہ، اس مفروضے پر مشروط ہے جو کسی بھی عمودی حصے کے سرایت ہونے سے پہلے آزاد تھا۔ مرحلہ 6: مرحلہ 2 اعلی امکان کے ساتھ کامیاب ہوتا ہے۔ ہال کے شادی کے نظریہ کے مطابق، مرحلہ 2 صرف اس صورت میں ناکام ہوتا ہے جب ہال کی حالت کی خلاف ورزی ہو۔ ایسا ہونے کے لیے، کچھ اور اس طرح کا ہونا ضروری ہے۔ مفت سیٹوں کی وسعت سے بہت چھوٹا نہیں ہو سکتا (مرحلہ 1)۔ اگر بہت زیادہ ہے، تو زیادہ امکان کے ساتھ، اس طرح کی صورت میں ناکامی کا امکان کم ہوگا۔ اگر نہ تو بہت چھوٹا ہے اور نہ ہی بہت بڑا، تو یہ نوٹ کرتے ہوئے کہ یہ غیر استعمال شدہ عمودی کا ایک بڑا مجموعہ ہے، ہم مرکزی لیما اور یونین باؤنڈ ناکامی کے امکان کا استعمال کر سکتے ہیں۔ ایپلی کیشنز بلو اپ لیما میں گھنے گراف کو سرایت کرنے میں متعدد ایپلی کیشنز ہیں۔ 1962 میں، لاجوس پوسا نے قیاس کیا کہ کم از کم ڈگری والے ہر ورٹیکس گراف میں کم از کم ہیملٹنین سائیکل کا مربع ہوتا ہے، جو ڈیراک کے نظریہ کو عام کرتا ہے۔ پال سیمور نے 1974 میں اس قیاس کو مزید آگے بڑھا کر مندرجہ ذیل تک بڑھایا: کم از کم ڈگری والے عمودی حصوں پر موجود ہر گراف میں کم از کم ہیملٹنین سائیکل کی-th طاقت ہوتی ہے۔ بلو اپ لیما کو کوملوس، سارکزی، اور زیمیرڈی نے 1998 میں (فکسڈ کے لیے) کی تمام کافی بڑی اقدار کے قیاس کو ثابت کرنے کے لیے استعمال کیا تھا۔ ایلون-یوسٹر قیاس 1995 میں، نوگا ایلون اور رافیل یوسٹر نے معروف ہجنل-زیمیرڈی تھیوریم کی عمومی شکل کو صوابدیدی عوامل (صرف مکمل گراف کے بجائے) پر غور کیا، اور مندرجہ ذیل بیان کو ثابت کیا: عمودی کے ساتھ ہر فکسڈ گراف کے لیے، n عمودی کے ساتھ اور کم سے کم ڈگری کے ساتھ کسی بھی گراف G میں H کی عمودی جداگانہ کاپیاں ہوتی ہیں۔ انہوں نے یہ بھی قیاس کیا کہ نتیجہ صرف ایک مستقل (لکیری کے بجائے) غلطی کے ساتھ ہوتا ہے: ہر انٹیجر کے لیے ایک مستقل موجود ہوتا ہے کہ عمودی کے ساتھ ہر گراف کے لیے، عمودی اور کم سے کم ڈگری کے ساتھ کوئی بھی گراف کم از کم عمودی جداگانہ کاپیاں رکھتا ہے۔ یہ قیاس کوملوس، سارکوزی اور زیمیرڈی نے 2001 میں بلو اپ لیما کا استعمال کرتے ہوئے ثابت کیا تھا۔ تاریخ اور تغیرات بلو اپ لیما، جو سب سے پہلے 1997 میں کوملوس، سارکزی اور زیمیرڈی نے شائع کیا تھا، موجودہ ثبوت کی تکنیکوں کی اصلاح کے طور پر ابھرا جس میں پھیلاؤ گراف کو سرایت کرنے کے لیے باقاعدگی کے طریقہ کار کا استعمال کیا گیا تھا، جیسا کہ پھیلے ہوئے درختوں پر بولوباس قیاس کے ثبوت میں، ہیملٹنین سائیکل کی کے-تھ گراف پاور پر قابو پانے کے لیے ضروری کم از کم ڈگری کے بارے میں پوسا-سیمور قیاس آرائی پر کام کریں، اور گراف کے لیے درکار کم از کم ڈگری پر ایلون-یوسٹر قیاس آرائی کا ثبوت ایک کامل ایچ-فیکٹر ہو۔ ان تمام نظریات کے ثبوت زیادہ تر عمودی حصوں کو سرایت کرنے کے لیے بے ترتیب لالچی الگورتھم کے استعمال پر انحصار کرتے ہیں، اور پھر بقیہ عمودی حصوں کے لیے سرایت تلاش کرنے کے لیے کینیگ ہال جیسی دلیل کا استعمال کرتے ہیں۔ بلو اپ لیما کے پہلے ثبوت میں بھی اسی طرح کی دلیل کا استعمال کیا گیا۔ تاہم، بعد میں 1997 میں، انہی مصنفین نے ایک اور مقالہ شائع کیا جس میں بے ترتیب الگورتھم کو تعیناتی بنانے کے لیے بہتری پائی گئی۔ پیٹر کیواش نے 2010 میں بلو اپ لیما کو ہائپر گراف میں عام کیا۔ اسٹیفن گلوک اور فیلکس جووس نے 2018 میں اندردخش گراف کے لیے بلو اپ لیما کی ایک قسم دریافت کی۔ 2019 میں، پیٹر ایلن، جولیا بوچر، ہیپ ہان، یوشیہارو کوہائکاوا، اور یوری پرسن نے گراف تھیوری میں باؤنڈ ڈگری گرافز کو بے ترتیب اور سڈورینڈم گرافز میں سرایت کرنے کے لیے بلو اپ لیما کے غیر معمولی تشبیہات پائے۔