LissafiKafin bugawaNazariyyaKaratun minti 4

HANYOYIN SADARWA NA KA-CI-KA-TASHI SUKAN DAINA KARƁAR LAUNI A WANI ƘAYYADADDEN CUNKOSO

Ɗauki graph — ɗigo da mahaɗai suka haɗa — da akwatin launuka. Tsarin launi da ya dace (proper colouring) da launuka q yana ba kowane ɗigo ɗaya daga cikin launuka q ta yadda ɗigo biyu da ke haɗe ba za su taɓa raba launi ɗaya ba. Idan mahaɗai kaɗan ne, hakan mai sauƙi ne. Idan suna da yawa, yakan zama ba zai yiwu ba.

Yanzu gina graph ɗin ta hanyar ka-ci-ka-tashi: ɗigo n, kowane ma’auratan ɗigo ana haɗa su da kansu (independently) da wata ƙaramar yiwuwa (probability), ta yadda ɗigo ɗaya yana da maƙwabta d a matsakaici. Yayin da d ke ƙaruwa, graph ta ka-ci-ka-tashi tana wucewa daga “kusan tabbas za a iya yi mata launi da launuka q” (almost surely) zuwa “kusan tabbas ba za a iya ba”. A ina ne daidai sauyin yake faruwa? Wannan tambaya, ga kowane ƙayyadadden adadin launuka q daga uku zuwa sama, ita ce batun wata sabuwar takarda ta Gaia Carenini, a Jami’ar Cambridge (University of Cambridge).

Sauyin da zai iya girgiza

A cikin wata takarda ta 1999 da aka jera a cikin jerin manazarta, Achlioptas da Friedgut sun tabbatar da cewa sauyin yana da kaifi (sharp): ga kowane girma n, akwai wani matsakaicin mataki na iyaka (critical average degree) d_q(n) wanda ɗan ƙasa da shi, kusan tabbas za a iya yi wa graph ɗin launi, kuma ɗan sama da shi, kusan tabbas ba za a iya ba. Tagar da sauyin ke faruwa a cikinta tana ƙanƙancewa har ta ɓace.

Amma hakan ya bar wata ƙofa a buɗe. Babu abin da ya hana ƙimar iyakar kanta ta yi kai-komo (oscillating) yayin da graph ke girma — tana zaune a wuri ɗaya ga graph na wani girma, ɗan wani wuri dabam ga waɗanda suka fi girma, ba tare da ta taɓa tsayawa ba. Hasashen haɗuwa na Achlioptas–Friedgut (convergence conjecture) ya ce hakan ba ya faruwa: ga kowane q, akwai wata tsayayyar ƙima guda ɗaya d_q, wadda ƙasa da ita ana iya yi wa graph na ka-ci-ka-tashi launi, sama da ita kuma ba za a iya ba.

Abin da masana physics suka yi hasashe

Physics na ƙididdiga (statistical physics) yana da hoton abin da ke faruwa. Yayin da ake ƙara mahaɗai, ingantattun tsarin launi suna haɗuwa zuwa gungu (clusters): tsarin launi da ke cikin gungu ɗaya suna kama da juna, yayin da gungu biyu suke bambanta a kan ɗigo da yawa. Sannan, a wani mataki da ake kira condensation (dunƙulewa), ’yan manyan gungu kaɗan suna riƙe da kaso mai yawa na dukkan tsarin launi — kuma sai daga baya ne tarin tsarin launi ya zama fanko. Wannan tsari yana bayyana dalilin da ya sa hujjojin ƙirge ke shan wahala kusa da iyakar.

Ga launuka masu yawa, ayyukan da suka gabata sun riga sun taƙaita iyakar zuwa wani ƙunƙuntaccen zango: tana tsakanin kusan 2q log q − log q − 2 log 2 da 2q log q − log q − 1, giɓi mai faɗin 2 log 2 − 1 yayin da q ke ƙaruwa. Amma “ƙunƙuntacce” ba “ƙayyadadde” ba ne, kuma ga ƙananan adadin launuka kamar uku, tambayar ta kasance a buɗe.

Matsala tagwaye, wadda aka fara warwarewa

Yin launi yana da tagwaye: satisfiability (yiwuwar gamsarwa), matsalar zaɓar ƙimar gaskiya ko ƙarya ga masu sauyawa (variables) ta yadda dukkan jerin sharuɗɗan hankali (logical constraints) na ka-ci-ka-tashi za su cika. A can ma, an san cewa akwai iyaka mai kaifi, ba tare da hujjar cewa tana tsayawa ba. Wani rahoto na Carenini daga 2026, wanda takardar ta ambata, ya sanar da hujjar cewa tana tsayawa, ga kowane tsawon sharaɗi (constraint length) daga uku zuwa sama, ta hanyar nuna cewa tagar sauyin ƙunƙuntacciya ce sosai. Sabuwar takardar tana daidaita wannan hujja ga yin launi.

Ma’auratan da suka daskare tare

Hujjar tana tafiya ta jerin rage-rage (reductions). Yayin da ake ƙara mahaɗai na ka-ci-ka-tashi ɗaya bayan ɗaya, bari H ya zama lokacin da graph ɗin ta daina yiwuwar yi mata launi. Idan H ya ɗan bambanta kaɗan ne daga wata graph ta ka-ci-ka-tashi zuwa wata — cikin tagar kusan mahaɗai n/(log n)² — to dole ne iyakar ta tsaya. Wani sanannen rashin daidaito (inequality) na gargajiya yana mayar da hakan tambaya game da graph ta ƙarshe da za a iya yi wa launi: a matsakaici, sababbin mahaɗai na ka-ci-ka-tashi nawa za ta iya jurewa?

Nan ne babban ra’ayin ya shigo: ma’aurata masu daskarewa (frozen pairs). Ɗigo biyu suna zama ma’aurata masu daskarewa idan kowane ingantaccen tsarin launi yana ba su launi ɗaya. Sabon mahaɗi yana da kisa daidai lokacin da ya haɗa irin waɗannan ma’aurata. Ɗigo guda ɗaya ba zai iya daskarewa a kan wani launi na musamman ba, domin musanya launukan koyaushe yana ba da wani ingantaccen tsarin launi; abin da ake tilastawa shi ne dangantaka tsakanin ɗigo biyu. A cikin aikin Carenini, ana bin diddigin yadda waɗannan rukunoni masu daskarewa ke girma yayin da ake ƙara mahaɗai, ta hanyar share mahaɗi ɗaya ko ɗigo gaba ɗaya da kuma duba zaɓuɓɓukan da suka sake bayyana. Ƙiyasin sun nuna cewa graph ta ƙarshe da za a iya yi wa launi ba za ta iya daɗewa ba, wanda ke ƙunƙuntar da tagar isasshe don tabbatar da hasashen.

Abin da har yanzu ba a sani ba

Ka’idar (theorem) ta ce iyakar d_q tana wanzuwa ga kowane q ≥ 3. Ba ta faɗi a ina take ba: takardar ba ta ba da wata ƙima gare ta ba, ko da ga launuka uku. Takardar daftari ne (preprint) mai marubuci guda ɗaya, kuma ba a yi mata bitar takwarorinsu (peer review) ba. Tana ƙarewa da wata gajeriyar sanarwa cewa babu ɗaya daga cikin hujjojinta na lissafi da babban samfurin harshe (large language model) ya samar.