یک هوش مصنوعی حدسی دربارهٔ رنگ‌آمیزی از دههٔ 1990 را غرق می‌کند

شبکه‌ای از نقطه‌ها را در نظر بگیرید که با خط‌ها به هم وصل شده‌اند — یک گراف. یک رنگ‌آمیزی کلی (total colouring) به هر نقطه و هر خط رنگی می‌دهد و از سه قاعده پیروی می‌کند: دو نقطهٔ همسایه متفاوت‌اند، دو خطی که در یک نقطه به هم می‌رسند متفاوت‌اند، و هر خط با دو نقطهٔ انتهایی‌اش متفاوت است. کمترین تعداد رنگی که جواب می‌دهد عدد رنگی کلی (total chromatic number) نام دارد و با χ″(G) نوشته می‌شود.

حالا کار را سخت‌تر کنید. به هر نقطه و هر خط فهرست خودش از رنگ‌های مجاز را بدهید، همهٔ فهرست‌ها به یک اندازهٔ k، و رنگ‌آمیزی معتبری بخواهید که از فهرست‌ها برگزیده شود. کوچک‌ترین k که با هر فهرستی جواب بدهد، عدد رنگی کلیِ فهرستی است، χ″ℓ(G). هرگز نمی‌تواند از χ″(G) کوچک‌تر باشد: اگر همهٔ فهرست‌ها یکسان باشند، به مسئلهٔ معمولی بازمی‌گردید.

حدسی از اواخر دههٔ 1990

سه گروه — بورودین، کوستوچکا و وودال؛ یوان، موهار و شکرکوفسکی؛ هیلتون و جانسون — در اواخر دههٔ 1990 به‌طور مستقل پیشنهاد کردند که فهرست‌های شخصی هرگز هزینه‌ای ندارند:

χ″ℓ(G) = χ″(G) برای هر گراف (حتی با چند خط میان دو نقطه).

این حدس رنگ‌آمیزی کلیِ فهرستی (List Total Colouring Conjecture) است. شواهد از آن پشتیبانی می‌کرد: برای گراف‌هایی که هیچ نقطه‌شان بیش از دو خط ندارد برقرار است، و معلوم بود که هر گراف با دقیقاً سه خط در هر نقطه (گراف مکعبی) حداکثر به 5 رنگ از فهرست‌ها نیاز دارد.

مثال نقض

جاناتان نوئل (Jonathan Noel) از دانشگاه ویکتوریا در کانادا اکنون گرافی مکعبی با 20 نقطه نشان می‌دهد که χ″ = 4 اما χ″ℓ = 5 دارد. حدس نادرست است.

ساختار فشرده است. چهار نسخه از گرافی کوچک به نام K₂,₃ بردارید: دو نقطهٔ «خصوصی» که هر کدام به همان سه نقطهٔ «پایانه» وصل‌اند. سپس هر جفت از نسخه‌ها را با دقیقاً یک خطِ «متقاطع» میان پایانه‌ها به هم وصل کنید. در پایان هر نقطه سه خط دارد.

گراف G با یک رنگ‌آمیزی کلی تنها با چهار رنگ، که با شکل‌ها و سبک خط‌ها نشان داده شده است. — شکل 1، Noel (2026)، arXiv:2609.38417.

در بازی معمولی چهار رنگ کافی است: رنگ 4 به همهٔ نقطه‌های خصوصی و همهٔ خط‌های متقاطع می‌رسد که هرگز با هم تماس ندارند، و یک جدول کوچک و یک قاعدهٔ چرخه‌ای بقیه را سامان می‌دهند.

فهرست‌هایی که برآورده نمی‌شوند

دام از رنگ‌های 1 تا 5 استفاده می‌کند. هر نقطه و خطِ بلوک i فهرست «همهٔ رنگ‌ها جز i» را می‌گیرد؛ خط‌های متقاطع فهرست‌هایی با دقت برگزیده می‌گیرند که 5 یا i + 2 را ندارند. برهان سپس مانند یک داستان کارآگاهی کوتاه پیش می‌رود:

• لم: در هر رنگ‌آمیزی 4 رنگی از K₂,₃، دو نقطهٔ خصوصی باید هم‌رنگ باشند.
• پس هر بلوک 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؟