HisabatiChapisho la awaliNadhariaDakika 3 za kusoma

MITANDAO YA NASIBU HUKOMA KUWEZA KUPAKWA RANGI KATIKA MSONGAMANO THABITI

Chukua grafu — nukta zilizounganishwa kwa viungo — na sanduku la rangi. Upakaji rangi halali (proper colouring) wenye rangi q humpa kila nukta moja ya rangi q kwa namna ambayo nukta mbili zilizounganishwa hazishiriki rangi moja kamwe. Viungo vikiwa vichache, hilo ni rahisi. Vikiwa vingi, linakuwa haliwezekani.

Sasa jenga grafu kwa nasibu: nukta n, kila jozi ikiunganishwa kwa kujitegemea kwa uwezekano mdogo, kiasi kwamba kila nukta ina majirani d kwa wastani. Kadiri d inavyoongezeka, grafu ya nasibu hupita kutoka “karibu kwa hakika (almost surely) inaweza kupakwa rangi q” hadi “karibu kwa hakika haiwezi”. Mabadiliko hutokea wapi hasa? Swali hilo, kwa idadi yoyote isiyobadilika ya rangi q kuanzia tatu kwenda juu, ndilo mada ya makala mpya ya Gaia Carenini, wa Chuo Kikuu cha Cambridge.

Mabadiliko ambayo huenda yakayumba

Katika makala ya mwaka 1999 iliyoorodheshwa katika bibliografia, Achlioptas na Friedgut walithibitisha kwamba mpito huo ni wa ghafla (sharp): kwa kila ukubwa n, kuna digrii ya wastani muhimu d_q(n) ambayo, chini yake kidogo, grafu karibu kwa hakika inaweza kupakwa rangi, na juu yake kidogo, karibu kwa hakika haiwezi. Dirisha ambamo mabadiliko hutokea hupungua hadi kutoweka.

Lakini hilo liliacha mwanya. Hakuna kilichozuia thamani muhimu yenyewe kuyumbayumba (oscillating) kadiri grafu zinavyokuwa kubwa zaidi — ikikaa mahali pamoja kwa grafu za ukubwa mmoja, kwingine kidogo kwa kubwa zaidi, bila kutulia kamwe. Dhana ya muunganiko ya Achlioptas–Friedgut (convergence conjecture) inasema kwamba hilo halitokei: kwa kila q, kuna thamani moja isiyobadilika d_q, ambayo chini yake grafu za nasibu zinaweza kupakwa rangi na juu yake haziwezi.

Kile wanafizikia walichotabiri

Fizikia ya kitakwimu ilikuwa na picha ya kinachoendelea. Viungo vinapoongezwa, upakaji rangi halali hujipanga katika makundi (clusters): upakaji rangi ndani ya kundi moja hufanana, ilhali makundi mawili hutofautiana kwenye nukta nyingi. Kisha, katika hatua inayoitwa mgandamano (condensation), makundi machache makubwa hushikilia sehemu kubwa ya upakaji rangi wote — na baadaye tu ndipo seti ya upakaji rangi inakuwa tupu. Mpangilio huo unaeleza kwa nini hoja za kuhesabu hutatizika karibu na kizingiti.

Kwa rangi nyingi, kazi za awali zilikuwa tayari zimekibana kizingiti katika masafa membamba: kiko kati ya takriban 2q log q − log q − 2 log 2 na 2q log q − log q − 1, pengo lenye upana wa 2 log 2 − 1 kadiri q inavyoongezeka. Lakini “membamba” si “thabiti”, na kwa idadi ndogo za rangi kama tatu, swali lilibaki wazi.

Tatizo pacha, lililoshughulikiwa kwanza

Upakaji rangi una pacha: utoshelevu (satisfiability), tatizo la kuchagua thamani za kweli au uongo kwa vigeu ili orodha ya vikwazo vya kimantiki vya nasibu vyote viwe kweli. Huko pia, kizingiti cha ghafla kilijulikana kuwepo bila uthibitisho kwamba kinatulia. Katika ripoti ya mwaka 2026 iliyotajwa katika makala, Carenini alitangaza uthibitisho kwamba kinatulia, kwa kila urefu wa vikwazo (constraint length) kuanzia tatu kwenda juu, kwa kuonyesha kwamba dirisha la mpito ni jembamba sana. Makala mpya inarekebisha hoja hiyo kwa ajili ya upakaji rangi.

Jozi zilizoganda pamoja

Uthibitisho unaendelea kupitia mnyororo wa upunguzaji (reductions). Ukiongeza viungo vya nasibu kimoja kimoja, acha H iwe wakati ambapo grafu inakoma kuweza kupakwa rangi. Ikiwa H inatofautiana kidogo tu kutoka grafu moja ya nasibu hadi nyingine — ndani ya dirisha la takriban viungo n/(log n)² — basi kizingiti lazima kitulie. Kanuni ya kawaida ya kutolingana (inequality) hugeuza hilo kuwa swali kuhusu grafu ya mwisho inayoweza kupakwa rangi: kwa wastani, inastahimili viungo vipya vingapi vya nasibu?

Hapa ndipo linakuja wazo kuu: jozi zilizoganda (frozen pairs). Nukta mbili huunda jozi iliyoganda pale kila upakaji rangi halali unapozipa rangi moja. Kiungo kipya huleta mwisho hasa pale kinapounganisha jozi kama hiyo. Nukta moja moja haziwezi kugandishwa kwenye rangi moja mahususi, kwa sababu kubadilishana rangi hutoa daima upakaji rangi mwingine halali; kinacholazimishwa ni uhusiano kati ya nukta mbili. Carenini anafuatilia jinsi madaraja haya yaliyoganda yanavyokua viungo vinapoongezwa, kwa kufuta kiungo au nukta nzima na kuangalia machaguo yanayojitokeza tena. Makadirio yanaonyesha kwamba grafu ya mwisho inayoweza kupakwa rangi haiwezi kudumu muda mrefu, jambo linalobana dirisha vya kutosha kuthibitisha dhana hiyo.

Kisichojulikana bado

Theoremu inasema kwamba kizingiti d_q kipo kwa kila q ≥ 3. Haisemi kiko wapi: makala haitoi thamani yake, hata kwa rangi tatu. Makala ni chapisho la awali lenye mwandishi mmoja na halijapitiwa na wataalamu wenzao. Inamalizika kwa kauli fupi kwamba hakuna hoja yake yoyote ya kihisabati iliyozalishwa na modeli kubwa ya lugha.