ایک مصنوعی ذہانت نے 1990 کی دہائی کا رنگ آمیزی کا قیاس غلط ثابت کر دیا

لکیروں سے جڑے نقطوں کا ایک جال لیجیے — یعنی ایک گراف۔ کلی رنگ آمیزی (total colouring) ہر نقطے اور ہر لکیر کو تین اصولوں کے مطابق ایک رنگ دیتی ہے: دو پڑوسی نقطے مختلف ہوں، ایک نقطے پر ملنے والی دو لکیریں مختلف ہوں، اور ہر لکیر اپنے دونوں سرے کے نقطوں سے مختلف ہو۔ کام کرنے والے رنگوں کی کم سے کم تعداد کو کلی رنگی عدد (total chromatic number) کہتے ہیں، جسے χ″(G) لکھا جاتا ہے۔

اب اسے مشکل بنائیے۔ ہر نقطے اور ہر لکیر کو اجازت یافتہ رنگوں کی اپنی فہرست دیجیے، سب فہرستیں ایک ہی سائز k کی، اور تقاضا کیجیے کہ فہرستوں میں سے چن کر ایک درست رنگ آمیزی کی جائے۔ وہ سب سے چھوٹا k جو فہرستیں جیسی بھی ہوں کام کرے، فہرستی کلی رنگی عدد χ″ℓ(G) کہلاتا ہے۔ یہ کبھی χ″(G) سے چھوٹا نہیں ہو سکتا: اگر تمام فہرستیں یکساں ہوں تو آپ عام مسئلے پر واپس آ جاتے ہیں۔

1990 کی دہائی کے آخر کا ایک قیاس

تین گروہوں — بوروڈن، کوستوچکا اور ووڈال؛ یووان، موہار اور شکریکووسکی؛ ہلٹن اور جانسن — نے 1990 کی دہائی کے آخر میں ایک دوسرے سے آزادانہ طور پر یہ تجویز کیا کہ ذاتی فہرستوں کی کبھی کوئی قیمت نہیں ہوتی:

ہر گراف کے لیے χ″ℓ(G) = χ″(G) (چاہے دو نقطوں کے درمیان کئی لکیریں ہوں)۔

یہ فہرستی کلی رنگ آمیزی کا قیاس (List Total Colouring Conjecture) ہے۔ شواہد اس کے حق میں تھے: یہ ان گرافوں کے لیے درست ہے جن میں کسی نقطے پر دو سے زیادہ لکیریں نہیں، اور یہ معلوم تھا کہ ہر نقطے پر ٹھیک تین لکیروں والے ہر گراف (یعنی مکعبی گراف) کو فہرستوں سے زیادہ سے زیادہ 5 رنگ درکار ہوتے ہیں۔

جوابی مثال

کینیڈا کی یونیورسٹی آف وکٹوریا کے جوناتھن نوئل اب 20 نقطوں والا ایک مکعبی گراف پیش کرتے ہیں جس کا χ″ = 4 ہے مگر χ″ℓ = 5۔ قیاس غلط ہے۔

یہ ساخت مختصر ہے۔ K₂,₃ نامی ایک چھوٹے گراف کی چار نقول لیجیے: دو “نجی” نقطے، جن میں سے ہر ایک انہی تین “ٹرمینل” نقطوں سے جڑا ہے۔ پھر نقول کے ہر جوڑے کو ٹرمینلز کے درمیان ٹھیک ایک “آر پار” لکیر سے جوڑ دیجیے۔ آخر میں ہر نقطے پر تین لکیریں ہوتی ہیں۔

گراف G صرف چار رنگوں کی کلی رنگ آمیزی کے ساتھ، جنہیں شکلوں اور لکیروں کے انداز سے دکھایا گیا ہے۔ — شکل 1، Noel (2026)، arXiv:2609.38417۔

عام کھیل میں چار رنگ کافی ہیں: رنگ 4 تمام نجی نقطوں اور تمام آر پار لکیروں کو ملتا ہے، جو کبھی ایک دوسرے کو نہیں چھوتیں، اور باقی کام ایک چھوٹی سی جدول اور ایک چکری اصول سنبھال لیتے ہیں۔

فہرستیں جو پوری نہیں کی جا سکتیں

پھندا 1 سے 5 تک کے رنگ استعمال کرتا ہے۔ بلاک i کے ہر نقطے اور لکیر کو “i کے سوا تمام رنگ” والی فہرست ملتی ہے؛ آر پار لکیروں کو احتیاط سے چنی گئی فہرستیں ملتی ہیں جن میں 5 یا i + 2 غائب ہوتا ہے۔ پھر ثبوت ایک مختصر جاسوسی کہانی کی طرح آگے بڑھتا ہے:

• لیما: K₂,₃ کی کسی بھی 4-رنگ آمیزی میں دونوں نجی نقطوں کا رنگ ایک ہی ہونا چاہیے۔
• لہٰذا ہر بلاک i کے پاس رنگوں کا ایک جوڑا {i، sᵢ} ہوتا ہے، اور دو بلاکس کے درمیان ہر آر پار لکیر کو ایسا رنگ استعمال کرنا ہوگا جو دونوں جوڑوں میں مشترک ہو۔
• تھوڑی سی گنتی سے پتا چلتا ہے کہ کوئی ایک رنگ t چاروں جوڑوں میں شامل ہونا چاہیے۔
• ہر ممکنہ t کے لیے ایک مخصوص آر پار لکیر دیکھتی ہے کہ یہ رنگ اس کی فہرست میں موجود ہی نہیں۔ تضاد۔

فہرستوں کی تقسیم: ہر نقطہ اور لکیر 1 سے 5 تک کے تمام رنگ استعمال کر سکتی ہے، سوائے اس کے جو دکھایا گیا ہے۔ کوئی بھی کلی رنگ آمیزی ان فہرستوں کی پابندی نہیں کر سکتی۔ — شکل 2، Noel (2026)، arXiv:2609.38417۔

مشین نے ڈھونڈا، ریاضی دان نے جانچا

مقالہ اپنی ابتدا کے بارے میں غیر معمولی طور پر صاف گو ہے۔ 24 ستمبر 2026 کو نوئل نے ChatGPT 6 Astra Ultra سے قیاس کو غلط ثابت کرنے کو کہا، اور اس نے جوابی مثال پیش کر دی، “مصنف کی بہت کم شرکت کے ساتھ”۔ انہوں نے دلائل جانچے اور ماڈل کے تیار کردہ مسودوں سے متن دوبارہ لکھا؛ ماڈل نے پروف ریڈنگ میں بھی مدد کی، حوالہ جات تجویز کیے اور اشکال بنائیں۔ اعلان ان الفاظ پر ختم ہوتا ہے: “درستگی کی پوری ذمہ داری مصنف پر ہے”۔ مقالہ ایک پری پرنٹ ہے، لیکن ثبوت اتنا مختصر ہے کہ کوئی بھی صابر قاری اسے جانچ سکتا ہے۔

ایک کا فرق، یا زیادہ؟

ذاتی فہرستیں ایک اضافی رنگ کا تقاضا کر سکتی ہیں۔ کیا یہ اس سے زیادہ کا تقاضا کر سکتی ہیں؟ تین کا فرق ایک خوب مطالعہ شدہ رشتے دار قیاس، یعنی فہرستی کنارہ رنگ آمیزی کے قیاس (List Edge Colouring Conjecture)، کو بھی گرا دے گا، کیونکہ χ″ℓ ≤ χ′ℓ + 2 اور χ″ ≥ χ′۔ نوئل ایک کھلے سوال پر بات ختم کرتے ہیں جو مصنوعی ذہانت کی جوابی مثال کے بعد بھی قائم ہے: کیا ہر گراف کے لیے χ″ℓ(G) ≤ χ″(G) + 1 ہے؟