ریاضیپری پرنٹنظریہ5 منٹ کا مطالعہ

بے ترتیب نیٹ ورک ایک مقررہ کثافت پر رنگے جانے کے قابل نہیں رہتے

ایک گراف لیجیے — یعنی روابط سے جڑے ہوئے نقطے — اور رنگوں کا ایک ڈبہ۔ q رنگوں کے ساتھ ایک جائز رنگ آمیزی (proper colouring) ہر نقطے کو q میں سے ایک رنگ اس طرح دیتی ہے کہ دو جڑے ہوئے نقطوں کا رنگ کبھی ایک نہ ہو۔ روابط کم ہوں تو یہ آسان ہے۔ زیادہ ہوں تو ناممکن ہو جاتا ہے۔

اب گراف کو بے ترتیبی سے بنائیے: n نقطے، جن کا ہر جوڑا ایک چھوٹے سے احتمال کے ساتھ آزادانہ طور پر جوڑا جاتا ہے، اس طرح کہ ایک نقطے کے اوسطاً d پڑوسی ہوں۔ جوں جوں d بڑھتا ہے، بے ترتیب گراف “q رنگوں سے تقریباً یقینی طور پر (almost surely) قابلِ رنگ” کی حالت سے “تقریباً یقینی طور پر ناقابلِ رنگ” کی حالت میں چلا جاتا ہے۔ یہ تبدیلی ٹھیک کہاں ہوتی ہے؟ تین اور اس سے زیادہ رنگوں کی کسی بھی مقررہ تعداد q کے لیے یہی سوال University of Cambridge سے وابستہ Gaia Carenini کے ایک نئے مقالے کا موضوع ہے۔

ایک تبدیلی جو ڈگمگا سکتی تھی

1999 کے ایک مقالے میں، جو کتابیات میں درج ہے، Achlioptas اور Friedgut نے ثابت کیا کہ یہ عبور دو ٹوک (sharp) ہے: ہر جسامت n کے لیے ایک فیصلہ کن اوسط درجہ (average degree) d_q(n) موجود ہے، جس سے ذرا نیچے گراف تقریباً یقینی طور پر قابلِ رنگ ہوتا ہے اور ذرا اوپر تقریباً یقینی طور پر نہیں۔ جس وقفے میں یہ تبدیلی ہوتی ہے وہ سکڑ کر کچھ بھی نہیں رہ جاتا۔

لیکن اس سے ایک رخنہ باقی رہ گیا۔ کوئی چیز اس بات میں مانع نہیں تھی کہ گراف بڑے ہونے کے ساتھ خود فیصلہ کن قدر ڈولتی رہے — ایک جسامت کے گرافوں کے لیے ایک جگہ پر، بڑے گرافوں کے لیے ذرا کہیں اور، اور کبھی نہ ٹھہرے۔ Achlioptas–Friedgut کا تقاربی قیاس (convergence conjecture) کہتا ہے کہ ایسا نہیں ہوتا: ہر q کے لیے ایک واحد مستقل d_q موجود ہے، جس سے نیچے بے ترتیب گراف قابلِ رنگ ہوتے ہیں اور جس سے اوپر نہیں۔

ماہرینِ طبیعیات کی پیش گوئی

شماریاتی طبیعیات کے پاس اس عمل کی ایک تصویر موجود تھی۔ جیسے جیسے روابط شامل ہوتے ہیں، درست رنگ آمیزیاں جھرمٹوں (clusters) میں بٹ جاتی ہیں: ایک جھرمٹ کے اندر کی رنگ آمیزیاں ایک دوسرے سے ملتی جلتی ہیں، جبکہ دو جھرمٹ بہت سے نقطوں پر ایک دوسرے سے مختلف ہوتے ہیں۔ پھر، ایک مرحلے پر جسے تکثیف (condensation) کہتے ہیں، چند بڑے جھرمٹ تمام رنگ آمیزیوں کا ایک خاطر خواہ حصہ اپنے اندر سمیٹ لیتے ہیں — اور اس کے بعد ہی جا کر رنگ آمیزیوں کا مجموعہ خالی ہوتا ہے۔ یہی تنظیم واضح کرتی ہے کہ دہلیز کے قریب گنتی پر مبنی دلائل کیوں مشکل میں پڑ جاتے ہیں۔

زیادہ رنگوں کے لیے، پچھلی تحقیق دہلیز کو پہلے ہی ایک تنگ دائرے میں محدود کر چکی تھی: یہ تقریباً 2q log q − log q − 2 log 2 اور 2q log q − log q − 1 کے درمیان واقع ہے، یعنی q بڑھنے کے ساتھ 2 log 2 − 1 چوڑائی کا ایک فرق۔ لیکن “تنگ” کا مطلب “مقررہ” نہیں، اور تین جیسی کم تعداد کے رنگوں کے لیے سوال کھلا رہا۔

ایک جڑواں مسئلہ، جسے پہلے حل کیا گیا

رنگ آمیزی کا ایک جڑواں بھی ہے: تسکین پذیری (satisfiability)، یعنی متغیرات کے لیے سچ یا جھوٹ کی قدریں اس طرح چننے کا مسئلہ کہ بے ترتیب منطقی شرائط کی ایک فہرست کی سب شرطیں پوری ہوں۔ وہاں بھی ایک دو ٹوک دہلیز کا وجود معلوم تھا، مگر اس بات کا کوئی ثبوت نہیں تھا کہ وہ ٹھہر جاتی ہے۔ مقالے میں حوالہ دی گئی 2026 کی ایک رپورٹ میں، Carenini نے اس بات کے ثبوت کا اعلان کیا کہ وہ ٹھہر جاتی ہے، تین اور اس سے زیادہ کی ہر شرطی لمبائی (constraint length) کے لیے، یہ دکھا کر کہ عبور کا وقفہ بہت تنگ ہے۔ نیا مقالہ اسی دلیل کو رنگ آمیزی پر ڈھالتا ہے۔

نقطوں کے جوڑے جو ایک ساتھ منجمد ہیں

ثبوت تخفیفات (reductions) کے ایک سلسلے کے ذریعے آگے بڑھتا ہے۔ ایک ایک کر کے بے ترتیب روابط شامل کرتے ہوئے، فرض کیجیے H وہ لمحہ ہے جب گراف قابلِ رنگ نہیں رہتا۔ اگر H ایک بے ترتیب گراف سے دوسرے تک بہت کم بدلتا ہے — تقریباً n/(log n)² روابط کے ایک وقفے کے اندر — تو دہلیز کو لازماً ٹھہرنا ہوگا۔ ایک کلاسیکی عدم مساوات اسے آخری قابلِ رنگ گراف کے بارے میں ایک سوال میں بدل دیتی ہے: اوسطاً، وہ کتنے نئے بے ترتیب روابط جھیل پاتا ہے؟

یہاں کلیدی تصور سامنے آتا ہے: منجمد جوڑے (frozen pairs)۔ دو نقطے ایک منجمد جوڑا بناتے ہیں جب ہر درست رنگ آمیزی انہیں ایک ہی رنگ دیتی ہے۔ ایک نیا ربط ٹھیک اسی وقت مہلک ہوتا ہے جب وہ ایسے کسی جوڑے کو جوڑتا ہے۔ اکیلے نقطے کسی ایک خاص رنگ پر منجمد نہیں ہو سکتے، کیونکہ رنگوں کو آپس میں ادل بدل کرنے سے ہمیشہ ایک اور درست رنگ آمیزی مل جاتی ہے؛ جو چیز لازم ہو جاتی ہے وہ دو نقطوں کے درمیان ایک رشتہ ہے۔ Carenini کا طریقہ یہ ہے کہ روابط شامل ہونے کے ساتھ ان منجمد گروہوں کی نشوونما پر نظر رکھی جائے، ایک ربط یا پورا نقطہ حذف کر کے اور ان انتخابات کو دیکھ کر جو دوبارہ ظاہر ہوتے ہیں۔ تخمینے دکھاتے ہیں کہ آخری قابلِ رنگ گراف زیادہ دیر نہیں ٹک سکتا، جو وقفے کو اتنا تنگ کر دیتا ہے کہ قیاس ثابت ہو جائے۔

جو ابھی نامعلوم ہے

یہ قضیہ (theorem) کہتا ہے کہ ہر q ≥ 3 کے لیے دہلیز d_q موجود ہے۔ یہ نہیں بتاتا کہ وہ کہاں ہے: مقالہ اس کی کوئی قدر نہیں دیتا، تین رنگوں کے لیے بھی نہیں۔ مقالہ ایک پری پرنٹ ہے جسے ایک ہی شخص نے لکھا ہے، اور اس کا ہم مرتبہ جائزہ نہیں ہوا۔ یہ ایک مختصر بیان پر ختم ہوتا ہے کہ اس کی ریاضیاتی دلائل میں سے کوئی بھی کسی بڑے لسانی ماڈل (large language model) نے تیار نہیں کی۔