একটি এআই ডুবিয়ে দিল ১৯৯০-এর দশকের এক রঙকরণ অনুমান

রেখা দিয়ে যুক্ত বিন্দুর একটি জাল নিন — একটি গ্রাফ। সম্পূর্ণ রঙকরণ (টোটাল কালারিং) প্রতিটি বিন্দু ও প্রতিটি রেখাকে একটি রঙ দেয়, তিনটি নিয়ম মেনে: পাশাপাশি দুটি বিন্দুর রঙ আলাদা, একটি বিন্দুতে মেলা দুটি রেখার রঙ আলাদা, আর একটি রেখার রঙ তার দুই প্রান্তবিন্দু থেকে আলাদা। যত কম রঙে এটি সম্ভব, সেই সংখ্যাকে বলে সম্পূর্ণ বর্ণসংখ্যা (টোটাল ক্রোমাটিক নাম্বার), লেখা হয় χ″(G)।

এবার কঠিন করা যাক। প্রতিটি বিন্দু ও প্রতিটি রেখাকে অনুমোদিত রঙের নিজস্ব তালিকা দিন, সব তালিকা একই মাপের k, এবং তালিকা থেকে বেছে নেওয়া একটি বৈধ রঙকরণ দাবি করুন। তালিকা যা-ই হোক না কেন যে ক্ষুদ্রতম k কাজ করে, সেটি তালিকা সম্পূর্ণ বর্ণসংখ্যা, χ″ℓ(G)। এটি কখনো χ″(G)-এর চেয়ে ছোট হতে পারে না: সব তালিকা অভিন্ন হলে আপনি সাধারণ সমস্যাতেই ফিরে যান।

১৯৯০-এর দশকের শেষের একটি অনুমান

তিনটি দল — বোরোদিন, কস্তোচকা ও উডল; ইউভান, মোহার ও শ্‌ক্রেকোভস্কি; হিলটন ও জনসন — ১৯৯০-এর দশকের শেষ দিকে স্বাধীনভাবে প্রস্তাব করেন যে ব্যক্তিগত তালিকার জন্য কখনো কোনো মূল্য দিতে হয় না:

প্রতিটি গ্রাফের জন্য χ″ℓ(G) = χ″(G) (দুটি বিন্দুর মধ্যে একাধিক রেখা থাকলেও)।

এটিই তালিকা সম্পূর্ণ রঙকরণ অনুমান (List Total Colouring Conjecture)। প্রমাণাদি এর পক্ষে ছিল: যে গ্রাফে কোনো বিন্দুতে দুটির বেশি রেখা নেই, সেখানে এটি সত্য, আর জানা ছিল যে প্রতিটি বিন্দুতে ঠিক তিনটি রেখাওয়ালা প্রতিটি গ্রাফের (ঘনক বা কিউবিক গ্রাফ) তালিকা থেকে সর্বোচ্চ ৫টি রঙ লাগে।

প্রতি-উদাহরণ

কানাডার ইউনিভার্সিটি অব ভিক্টোরিয়ার জোনাথন নোয়েল এখন ২০ বিন্দুর একটি ঘনক গ্রাফ দেখিয়েছেন, যার χ″ = ৪ কিন্তু χ″ℓ = ৫। অনুমানটি ভুল।

গঠনটি সংক্ষিপ্ত। K₂,₃ নামের একটি ছোট গ্রাফের চারটি প্রতিলিপি নিন: দুটি “ব্যক্তিগত” বিন্দু, প্রতিটি একই তিনটি “প্রান্তীয়” (টার্মিনাল) বিন্দুর সঙ্গে যুক্ত। তারপর প্রতিলিপিগুলোর প্রতিটি জোড়াকে টার্মিনালগুলোর মধ্যে ঠিক একটি “আড়াআড়ি” রেখা দিয়ে যুক্ত করুন। শেষে প্রতিটি বিন্দুতে তিনটি করে রেখা হয়।

মাত্র চারটি রঙে সম্পূর্ণ রঙকরণসহ গ্রাফ G, রঙগুলো আকৃতি ও রেখার ধরন দিয়ে দেখানো। — চিত্র ১, নোয়েল (২০২৬), arXiv:2609.38417।

সাধারণ খেলায় চারটি রঙই যথেষ্ট: রঙ ৪ যায় সব ব্যক্তিগত বিন্দু আর সব আড়াআড়ি রেখায়, যারা কখনো পরস্পরকে ছোঁয় না, আর একটি ছোট সারণি ও একটি চক্রীয় নিয়ম বাকিটা সামলায়।

যে তালিকা পূরণ করা যায় না

ফাঁদটিতে ১ থেকে ৫ পর্যন্ত রঙ ব্যবহৃত হয়। খণ্ড i-এর প্রতিটি বিন্দু ও রেখা পায় “i ছাড়া সব রঙ” তালিকা; আড়াআড়ি রেখাগুলো পায় সযত্নে বাছাই করা তালিকা, যাতে ৫ বা i + 2 নেই। তারপর প্রমাণটি এগোয় একটি ছোট গোয়েন্দা গল্পের মতো:

• লেমা: K₂,₃-এর যেকোনো ৪-রঙকরণে দুটি ব্যক্তিগত বিন্দুর রঙ একই হতে হবে।
• তাই প্রতিটি খণ্ড i-এর একজোড়া রঙ থাকে {i, sᵢ}, এবং দুটি খণ্ডের মধ্যকার প্রতিটি আড়াআড়ি রেখাকে এমন রঙ ব্যবহার করতে হবে যা দুটি জোড়াতেই আছে।
• সামান্য গোনাগুনতি দেখায়, কোনো একটি রঙ t চারটি জোড়াতেই থাকতে হবে।
• t-এর প্রতিটি সম্ভাব্য মানের জন্য, একটি নির্দিষ্ট আড়াআড়ি রেখা দেখে যে সেই রঙটি তার তালিকায় নেই। স্ববিরোধ।

তালিকা বণ্টন: প্রতিটি বিন্দু ও রেখা ১ থেকে ৫ পর্যন্ত নির্দেশিত রঙটি বাদে যেকোনো রঙ ব্যবহার করতে পারে। কোনো সম্পূর্ণ রঙকরণই এই তালিকাগুলো মানতে পারে না। — চিত্র ২, নোয়েল (২০২৬), arXiv:2609.38417।

যন্ত্র খুঁজে পেয়েছে, গণিতবিদ যাচাই করেছেন

গবেষণাপত্রটি তার উৎস সম্পর্কে অস্বাভাবিক রকম খোলামেলা। ২০২৬ সালের ২৪ সেপ্টেম্বর নোয়েল ChatGPT 6 Astra Ultra-কে অনুমানটি খণ্ডন করার নির্দেশ দেন, এবং সেটি “লেখকের সামান্য সহায়তায়” প্রতি-উদাহরণটি তৈরি করে। তিনি যুক্তিগুলো যাচাই করেন এবং মডেলের তৈরি খসড়া থেকে লেখাটি নতুন করে লেখেন; মডেলটি প্রুফ দেখতেও সাহায্য করেছে, তথ্যসূত্র প্রস্তাব করেছে এবং চিত্রগুলো এঁকেছে। ঘোষণাটি শেষ হয় এই বাক্যে: “নির্ভুলতার পূর্ণ দায়িত্ব লেখকের।” গবেষণাপত্রটি একটি প্রিপ্রিন্ট, কিন্তু প্রমাণটি এতই ছোট যে ধৈর্যশীল যেকোনো পাঠক তা যাচাই করতে পারেন।

এক রঙের ব্যবধান, নাকি আরও বেশি?

ব্যক্তিগত তালিকা একটি বাড়তি রঙ দাবি করতে পারে। আরও বেশি কি পারে? তিনের ব্যবধান হলে বহুল-অধ্যয়িত এক আত্মীয়, তালিকা প্রান্ত রঙকরণ অনুমানও (List Edge Colouring Conjecture) ভেঙে পড়বে, কারণ χ″ℓ ≤ χ′ℓ + 2 এবং χ″ ≥ χ′। নোয়েল শেষ করেছেন একটি উন্মুক্ত প্রশ্ন দিয়ে, যা এআই-এর প্রতি-উদাহরণ অমীমাংসিত রেখে গেছে: প্রতিটি গ্রাফের জন্য কি χ″ℓ(G) ≤ χ″(G) + 1?