بے ترتیب جال اک مِتھی ہوئی گھنتا اُتے رنگے جان جوگے نہیں رہندے
اک گراف (graph) لوو — کڑیاں نال جُڑے بندو — تے رنگاں دی اک ڈبی۔ q رنگاں نال اک ٹھیک رنگائی (proper colouring) ہر بندو نوں q رنگاں وچوں اک رنگ دیندی اے، ایس طرح کہ دو جُڑے ہوئے بندو کدی اکو رنگ سانجھا نہ کرن۔ تھوڑیاں کڑیاں نال، ایہہ سوکھا اے۔ بہتیاں نال، ایہہ ناممکن ہو جاندا اے۔
ہن گراف بے ترتیبی نال بناؤ: n بندو، ہر جوڑا اک نِکی جہی احتمال (probability) نال، دوجیاں توں آزاد، جُڑیا ہویا، ایس طرح کہ اک بندو دے اوسطاً d گوانڈھی ہون۔ جیویں جیویں d ودھدا اے، بے ترتیب گراف «لگ بھگ یقینی طور تے (almost surely) q رنگاں نال رنگیا جا سکدا اے» توں «لگ بھگ یقینی طور تے نہیں» ول لنگھ جاندا اے۔ ایہہ تبدیلی ٹھیک ٹھیک کتھے ہوندی اے؟ تن توں اُتے رنگاں دی کسے وی مِتھی ہوئی گنتی q لئی، ایہو سوال University of Cambridge وچ Gaia Carenini دے اک نویں مقالے دا موضوع اے۔
اک تبدیلی جیہڑی شاید ڈگمگاندی ہووے
1999 دے اک مقالے وچ، جیہڑا حوالیاں دی فہرست وچ درج اے، Achlioptas تے Friedgut نے ثابت کیتا کہ ایہہ تبدیلی تِکھی (sharp) اے: ہر سائز n لئی، اک نازک اوسط درجہ (critical average degree) d_q(n) ہوندا اے، ایس طرح کہ ایہدے توں تھوڑا تھلے گراف لگ بھگ یقینی طور تے رنگیا جا سکدا اے، تے ایہدے توں تھوڑا اُتے لگ بھگ یقینی طور تے نہیں۔ اوہ کھڑکی جیہدے وچ تبدیلی ہوندی اے، سُنگڑ کے کجھ وی نہیں رہندی۔
پر ایہدے نال اک موری کھلی رہ گئی۔ کوئی شے نازک قیمت نوں آپ، گراف وڈے ہون نال، جھولن (oscillating) توں نہیں روکدی سی — اک سائز دے گرافاں لئی اک تھاں، وڈیاں لئی تھوڑا ہور کتے، تے کدی نہ ٹِکے۔ Achlioptas–Friedgut دا مِلاپ قیاس (convergence conjecture) آکھدا اے کہ ایہہ نہیں ہوندا: ہر q لئی، اک اکلا مستقل d_q ہوندا اے، جیہدے تھلے بے ترتیب گراف رنگے جا سکدے نیں تے جیہدے اُتے نہیں۔
طبیعیات داناں دی پیش گوئی
شماریاتی طبیعیات (statistical physics) کول ایس گل دی اک تصویر سی کہ کیہ ہوندا اے۔ جیویں جیویں کڑیاں پائیاں جاندیاں نیں، جائز رنگائیاں ٹولیاں (clusters) وچ کٹھیاں ہو جاندیاں نیں: اک ٹولی دے اندر رنگائیاں اک دوجے نال ملدیاں جلدیاں نیں، جدکہ دو ٹولیاں بہت سارے بندواں اُتے وکھریاں ہوندیاں نیں۔ فیر، اک مرحلے اُتے جنہوں تکثیف (condensation) آکھدے نیں، گنتی دیاں کجھ وڈیاں ٹولیاں ساریاں رنگائیاں دا اک چوکھا حصہ سانبھ لیندیاں نیں — تے رنگائیاں دا مجموعہ صرف بعد وچ خالی ہوندا اے۔ ایہہ ترتیب دسدی اے کہ حد دے نیڑے گنتی والیاں دلیلاں (counting arguments) کیوں اوکھیاں ہو جاندیاں نیں۔
بہتے رنگاں لئی، پہلاں دے کم نے حد نوں پہلاں ای اک تنگ رینج وچ بنھ دتا سی: ایہہ لگ بھگ 2q log q − log q − 2 log 2 تے 2q log q − log q − 1 دے وچکار اے، یعنی جیویں جیویں q ودھدا اے، 2 log 2 − 1 چوڑائی دا اک پاڑ۔ پر «تنگ» دا مطلب «مِتھا ہویا» نہیں، تے تن ورگیاں رنگاں دیاں نِکیاں گنتیاں لئی سوال کھلا رہیا۔
اک جڑواں مسئلہ، جیہڑا پہلاں ہتھ وچ لیا گیا
رنگائی دا اک جڑواں اے: پورا ہون جوگتا (satisfiability)، یعنی متغیراں (variables) لئی سچ یا جھوٹ دیاں قیمتاں ایس طرح چُنن دا مسئلہ کہ بے ترتیب منطقی شرطاں دی اک فہرست ساری دی ساری پوری ہووے۔ اوتھے وی اک تِکھی حد دا ہونا جانیا جاندا سی، بغیر ایس ثبوت دے کہ اوہ ٹِک جاندی اے۔ مقالے وچ حوالہ دتی گئی 2026 دی اک رپورٹ وچ، Carenini نے ایس گل دے ثبوت دا اعلان کیتا سی کہ اوہ ٹِکدی اے، تن توں اُتے شرطاں دی ہر لمبائی (constraint length) لئی، ایہہ وکھا کے کہ تبدیلی دی کھڑکی بہت تنگ اے۔ نواں مقالہ اوس دلیل نوں رنگائی اُتے ڈھالدا اے۔
اوہ جوڑے جیہڑے اکٹھے جمے ہوئے نیں
ثبوت گھٹاؤاں (reductions) دی اک لڑی راہیں اگے ودھدا اے۔ بے ترتیب کڑیاں اک اک کر کے پاندیاں، H نوں اوہ لمحہ مِتھو جدوں گراف رنگے جان جوگا نہیں رہندا۔ جے H اک بے ترتیب گراف توں دوجے تیکر تھوڑا ای بدلدا اے — لگ بھگ n/(log n)² کڑیاں دی کھڑکی دے اندر — تے حد نوں ٹِکنا ای پیندا اے۔ اک کلاسیکی نابرابری (inequality) ایہنوں آخری رنگے جان جوگے گراف بارے اک سوال وچ بدل دیندی اے: اوسطاً، اوہ کنیاں نویاں بے ترتیب کڑیاں جھل جاندا اے؟
ایتھے مُکھ تصور آندا اے: جمے ہوئے جوڑے (frozen pairs)۔ دو بندو اک جمیا ہویا جوڑا بناندے نیں جدوں ہر جائز رنگائی اوہناں نوں اکو رنگ دیندی اے۔ اک نویں کڑی ٹھیک اوس ویلے مارو ہوندی اے جدوں اوہ اجیہے جوڑے نوں جوڑدی اے۔ اکلے بندو کسے اک خاص رنگ اُتے جم نہیں سکدے، کیونجے رنگاں دی ادلا بدلی ہمیشہ اک ہور جائز رنگائی دیندی اے؛ جیہڑی شے لازمی بن جاندی اے اوہ دو بندواں وچکار اک رشتہ اے۔ Carenini نے ایہناں جمیاں ہویاں جماعتاں (frozen classes) دے ودھن دا، کڑیاں پان دے نال نال، پِچھا کیتا اے: اک کڑی یا پورا بندو مٹا کے تے اوہ چوناں ویکھ کے جیہڑیاں مڑ ظاہر ہوندیاں نیں۔ اندازے وکھاندے نیں کہ آخری رنگے جان جوگا گراف بہتا چِر نہیں ٹِک سکدا، جیہڑا کھڑکی نوں اینا تنگ کر دیندا اے کہ قیاس ثابت ہو جاوے۔
جو اجے اَن جانیا اے
تھیورم آکھدا اے کہ حد d_q ہر q ≥ 3 لئی موجود اے۔ ایہہ نہیں دسدا کہ ایہہ کتھے اے: مقالہ ایہدی کوئی قیمت نہیں دیندا، تن رنگاں لئی وی نہیں۔ مقالہ اک ای لکھاری دا پری پرنٹ اے تے ایہدی اجے ہم مرتبہ جانچ نہیں ہوئی۔ ایہہ اک نِکے جہے بیان نال مُکدا اے کہ ایہدی کوئی وی ریاضیاتی دلیل کسے وڈے زبانی ماڈل (large language model) نے نہیں بنائی۔
