AI YAZAMISHA DHANIO LA UPAKAJI RANGI LA MIAKA YA 1990

Chukua mtandao wa vituo vilivyounganishwa kwa mistari — grafu. Upakaji rangi kamili (total colouring) humpa rangi kila kituo na kila mstari, kwa kufuata kanuni tatu: vituo viwili jirani vinatofautiana, mistari miwili inayokutana kwenye kituo inatofautiana, na mstari unatofautiana na vituo vyake viwili vya ncha. Idadi ndogo kabisa ya rangi inayofanya kazi inaitwa namba ya rangi kamili (total chromatic number), inayoandikwa χ″(G).

Sasa lifanye liwe gumu zaidi. Mpe kila kituo na kila mstari orodha yake binafsi ya rangi zinazoruhusiwa, orodha zote zikiwa na ukubwa sawa k, na dai upakaji rangi halali uliochaguliwa kutoka kwenye orodha. k ndogo kabisa inayofanya kazi orodha ziwe vyovyote vile ni namba ya rangi kamili ya orodha, χ″ℓ(G). Haiwezi kamwe kuwa ndogo kuliko χ″(G): ikiwa orodha zote zinafanana, unarudi kwenye tatizo la kawaida.

Dhanio la mwishoni mwa miaka ya 1990

Makundi matatu — Borodin, Kostochka na Woodall; Juvan, Mohar na Škrekovski; Hilton na Johnson — yalipendekeza kwa kujitegemea, mwishoni mwa miaka ya 1990, kwamba orodha binafsi hazigharimu chochote kamwe:

χ″ℓ(G) = χ″(G) kwa kila grafu (hata ikiwa na mistari mingi kati ya vituo viwili).

Hili ndilo Dhanio la Upakaji Rangi Kamili wa Orodha (List Total Colouring Conjecture). Ushahidi uliliunga mkono: ni kweli kwa grafu ambazo hakuna kituo chenye mistari zaidi ya miwili, na kila grafu yenye mistari mitatu hasa kwa kila kituo (grafu ya kicubiki, cubic graph) ilijulikana kuhitaji upeo wa rangi 5 kutoka kwenye orodha.

Mfano kinzani

Jonathan Noel, wa Chuo Kikuu cha Victoria nchini Kanada, sasa anaonyesha grafu ya kicubiki yenye vituo 20 iliyo na χ″ = 4 lakini χ″ℓ = 5. Dhanio si kweli.

Ujenzi wake ni mfupi. Chukua nakala nne za grafu ndogo inayoitwa K₂,₃: vituo viwili “binafsi”, kila kimoja kikiunganishwa na vituo vilevile vitatu vya “ncha”. Kisha unganisha kila jozi ya nakala kwa mstari mmoja hasa wa “kuvuka” kati ya vituo vya ncha. Mwishowe kila kituo kinakuwa na mistari mitatu.

Grafu ya vituo 20 iliyochorwa kama vitalu vinne vilivyounganishwa kwa mistari ya kuvuka, ikiwa imepakwa rangi nne.

Grafu G yenye upakaji rangi kamili kwa rangi nne tu, unaoonyeshwa kwa maumbo na mitindo ya mistari. — Kielelezo 1, Noel (2026), arXiv:2609.38417.

Rangi nne zinatosha katika mchezo wa kawaida: rangi 4 inaenda kwa vituo vyote binafsi na mistari yote ya kuvuka, ambavyo kamwe havigusani, na jedwali dogo na kanuni ya mzunguko hushughulikia vilivyobaki.

Orodha zisizoweza kutoshelezwa

Mtego unatumia rangi kuanzia 1 hadi 5. Kila kituo na mstari wa kitalu i unapata orodha “rangi zote isipokuwa i”; mistari ya kuvuka inapata orodha zilizochaguliwa kwa uangalifu zisizo na 5 au i + 2. Uthibitisho kisha unaenda kama hadithi fupi ya upelelezi:

Lema: katika upakaji wowote wa rangi 4 wa K₂,₃, vituo viwili binafsi lazima viwe na rangi moja.
Kwa hiyo kila kitalu i kina jozi ya rangi {i, sᵢ}, na kila mstari wa kuvuka kati ya vitalu viwili lazima utumie rangi iliyo katika jozi zote mbili.
Kuhesabu kidogo kunaonyesha kwamba rangi moja t lazima iwe katika jozi zote nne.
Kwa kila t inayowezekana, mstari mmoja mahususi wa kuvuka unakuta rangi hiyo haipo kwenye orodha yake. Mkinzano.

Grafu ileile, kila kituo na mstari ukiwekwa alama ya rangi isiyokuwemo kwenye orodha yake.

Ugawaji wa orodha: kila kituo na mstari unaweza kutumia kila rangi kuanzia 1 hadi 5 isipokuwa ile iliyoonyeshwa. Hakuna upakaji rangi kamili unaoweza kuheshimu orodha hizi. — Kielelezo 2, Noel (2026), arXiv:2609.38417.

Umepatikana na mashine, umekaguliwa na mwanahisabati

Makala ni wazi isivyo kawaida kuhusu chimbuko lake. Tarehe 24 Septemba 2026, Noel aliiagiza ChatGPT 6 Astra Ultra ilikanushe dhanio hilo, nayo ikatoa mfano kinzani, “kwa mchango mdogo kutoka kwa mwandishi”. Aliikagua hoja na kuandika upya maandishi kutoka kwa rasimu zilizozalishwa na modeli; modeli pia ilisaidia kusahihisha, ilipendekeza marejeo na kuchora vielelezo. “Mwandishi anabeba jukumu kamili kwa usahihi,” tamko linamalizia. Makala ni chapisho la awali (preprint), lakini uthibitisho ni mfupi kiasi kwamba msomaji yeyote mwenye subira anaweza kuuhakiki.

Pengo la moja, au zaidi?

Orodha binafsi zinaweza kugharimu rangi moja ya ziada. Je, zinaweza kugharimu zaidi? Pengo la tatu lingeangusha pia dhanio jamaa lililochunguzwa sana, Dhanio la Upakaji Rangi Kingo wa Orodha (List Edge Colouring Conjecture), kwa sababu χ″ℓ ≤ χ′ℓ + 2 na χ″ ≥ χ′. Noel anamalizia kwa swali lililo wazi ambalo mfano kinzani wa AI unaliacha likiwa bado limesimama: je, χ″ℓ(G) ≤ χ″(G) + 1 kwa kila grafu?