ذكاء اصطناعي يُسقط حدسية تلوين من تسعينيات القرن الماضي

لنأخذ شبكة من نقاط تربطها خطوط، أي بيانًا (graph). التلوين الكلي يعطي لونًا لكل نقطة ولكل خط، وفق ثلاث قواعد: نقطتان متجاورتان تختلفان في اللون، وخطّان يلتقيان عند نقطة يختلفان، والخط يختلف عن نقطتي طرفيه. وأصغر عدد من الألوان يحقق ذلك يُسمّى العدد اللوني الكلي، ويُكتب χ″(G).

لنجعل الأمر أصعب الآن. لنعطِ كل نقطة وكل خط قائمته الخاصة من الألوان المسموح بها، وكل القوائم بالحجم نفسه k، ولنطلب تلوينًا صالحًا مختارًا من القوائم. وأصغر k ينجح أيًّا كانت القوائم هو العدد اللوني الكلي بالقوائم، χ″ℓ(G). ولا يمكن أبدًا أن يكون أصغر من χ″(G): فإذا كانت كل القوائم متطابقة، نعود إلى المسألة العادية.

حدسية من أواخر التسعينيات

اقترحت ثلاث مجموعات، هي بورودين وكوستوتشكا ووودال؛ ويوفان وموهار وشكريكوفسكي؛ وهيلتون وجونسون، كلٌّ على حدة في أواخر التسعينيات، أن القوائم الخاصة لا تكلّف شيئًا أبدًا:

χ″ℓ(G) = χ″(G) لكل بيان (حتى مع وجود عدة خطوط بين نقطتين).

هذه هي حدسية التلوين الكلي بالقوائم (List Total Colouring Conjecture). وكانت الأدلة تدعمها: فهي صحيحة للبيانات التي لا يخرج فيها من أي نقطة أكثر من خطين، وكان معروفًا أن كل بيان يخرج من كل نقطة فيه ثلاثة خطوط بالضبط (أي بيان تكعيبي) يحتاج إلى 5 ألوان على الأكثر من القوائم.

المثال المضاد

يقدّم جوناثان نويل، من جامعة فيكتوريا في كندا، الآن بيانًا تكعيبيًا من 20 نقطة فيه χ″ = 4 لكن χ″ℓ = 5. فالحدسية خاطئة.

والبناء موجز. خذ أربع نسخ من بيان صغير يُسمّى K₂,₃: نقطتان “خاصّتان”، كلٌّ منهما موصولة بالنقاط “الطرفية” الثلاث نفسها. ثم اربط كل زوج من النسخ بخط “عابر” واحد بالضبط بين نقاط طرفية. فينتهي الأمر بأن يخرج من كل نقطة ثلاثة خطوط.

البيان G مع تلوين كلي بأربعة ألوان فقط، مبيَّنة بالأشكال وأنماط الخطوط. — الشكل 1، نويل (2026)، arXiv:2609.38417.

وفي اللعبة العادية تكفي أربعة ألوان: يُعطى اللون 4 لكل النقاط الخاصة ولكل الخطوط العابرة، التي لا يلامس بعضها بعضًا أبدًا، ويتكفّل جدول صغير وقاعدة دورية بالباقي.

قوائم يستحيل إرضاؤها

يستخدم الفخ الألوان من 1 إلى 5. فتحصل كل نقطة وكل خط في الكتلة i على القائمة “كل الألوان ما عدا i”؛ وتحصل الخطوط العابرة على قوائم منتقاة بعناية ينقصها 5 أو i + 2. ثم يسير البرهان كقصة بوليسية قصيرة:

• مأخوذة: في أي تلوين لـ K₂,₃ بأربعة ألوان، يجب أن يكون للنقطتين الخاصتين اللون نفسه.
• إذن لكل كتلة i زوج من الألوان {i, sᵢ}، ويجب أن يستخدم كل خط عابر بين كتلتين لونًا مشتركًا بين الزوجين.
• ويُظهر عدّ بسيط أن لونًا ما t يجب أن ينتمي إلى الأزواج الأربعة جميعًا.
• ولكل قيمة ممكنة لـ t، يجد خط عابر محدد أن ذلك اللون غائب عن قائمته. تناقض.

توزيع القوائم: يمكن لكل نقطة وكل خط استخدام كل الألوان من 1 إلى 5 ما عدا اللون المشار إليه. ولا يمكن لأي تلوين كلي أن يحترم هذه القوائم. — الشكل 2، نويل (2026)، arXiv:2609.38417.

اكتشفته آلة وتحقق منه رياضي

الورقة صريحة على نحو غير مألوف بشأن أصلها. ففي 24 سبتمبر 2026، وجّه نويل ChatGPT 6 Astra Ultra إلى دحض الحدسية، فـقدّم المثال المضاد “بمساهمة ضئيلة من المؤلف”. وتحقق هو من الحجج وأعاد كتابة النص انطلاقًا من مسودات ولّدها النموذج؛ كما ساعد النموذج في التدقيق، واقترح مراجع، ورسم الأشكال. ويختتم الإقرار بعبارة: “يتحمّل المؤلف المسؤولية الكاملة عن الصحة”. والورقة مسودة أولية، لكن البرهان قصير بما يكفي ليتحقق منه أي قارئ يتحلّى بالصبر.

فارق لون واحد، أم أكثر؟

يمكن للقوائم الخاصة أن تكلّف لونًا إضافيًا. فهل يمكن أن تكلّف أكثر؟ إن فارقًا من ثلاثة ألوان سيُسقط أيضًا قريبةً مدروسة جيدًا، هي حدسية تلوين الأضلاع بالقوائم (List Edge Colouring Conjecture)، لأن χ″ℓ ≤ χ′ℓ + 2 وχ″ ≥ χ′. ويختم نويل بسؤال مفتوح يتركه المثال المضاد الذي وجده الذكاء الاصطناعي قائمًا: هل χ″ℓ(G) ≤ χ″(G) + 1 لكل بيان؟