HAƊA KOWANE ƊIGO DA KOWANE ƊAYA: MAFI ƘARANCIN ƘETAREWA, AN TABBATAR

Sa ɗigo biyar a kan takarda kuma ka haɗa kowane biyu da layi mai lanƙwasa: layuka goma gaba ɗaya. Suna iya lanƙwasa yadda ka ga dama, amma babu ɗayansu da zai ratsa ta ɗigo na uku. Ka yi ƙoƙarin guje wa kowace ƙetarewa, za ka kasa. Da ɗigo biyar, aƙalla ƙetarewa 1 ba za a iya kauce mata ba; da shida, aƙalla 3; da goma, aƙalla 60.

Masana lissafi suna kiran irin wannan hoto zanen cikakken jadawali (complete graph) Kₙ — maki n, an haɗa kowane biyu — kuma mafi ƙarancin ƙetarewa da kowane zane zai iya kaiwa lambar ƙetarewarsa (crossing number). Martin Balko, na Charles University a Jamhuriyar Czech, ya kira tambayar “ɗaya daga cikin shahararrun matsaloli a ka’idar jadawalai ta topology (topological graph theory)”.

Ƙirgen wani mai zane

A ƙarshen shekarun 1950, mai zane ɗan Birtaniya Anthony Hill ya gina zanen Kₙ waɗanda adadin ƙetarewarsu daidai yake da

Z(n) = ¼ ⌊n/2⌋ ⌊(n − 1)/2⌋ ⌊(n − 2)/2⌋ ⌊(n − 3)/2⌋

inda ⌊ ⌋ ke nufin zagaye lamba zuwa ƙasa. Hasashen cewa babu zane da zai iya yin abin da ya fi haka Guy ne ya fara wallafa shi, daga baya Harary da Hill suka tattauna shi, kuma Erdős da Guy suka yaɗa shi. Ana kiransa hasashen Harary–Hill (Harary–Hill conjecture), ko hasashen Guy.

Dabarar tana hawa da sauri:

• ɗigo 4 ko ƙasa da haka: ƙetarewa 0
• ɗigo 5: 1
• ɗigo 7: 9
• ɗigo 10: 60
• ɗigo 14: 315

Shekaru sittin na amsoshi rabi-rabi

Zanen da ke da ƙetarewa daidai Z(n) sun wanzu ga kowane adadin ɗigo; abu mai wuya shi ne nuna cewa babu zane da ya fi haka.

Fiye da shekaru sittin, an tabbatar da hakan ne kawai ga wasu nau’o’in zane na musamman — misali da dukan ɗigogin a kan layi ɗaya kuma kowane layi mai lanƙwasa yana tsayawa a gefe ɗaya na wannan layin, ko da ɗigogin a kan ƙwallo (sphere) kuma kowane layi yana bin hanya mafi gajarta. Balko da kansa, tare da Fulek da Kynčl, sun warware ɗaya daga cikin irin waɗannan rukunoni. Zuwa 2021, kwamfutoci sun tabbatar da dabarar har zuwa ɗigo 14. Ga adadin ɗigo masu yawan gaske, mafi kyawun sakamako na gaba ɗaya sun tabbatar da aƙalla 98.5%, sannan 98.99%, na Z(n).

Hujja, sannan wadda ta fi haske

A 2026, OpenAI ta sanar da hujja ga kowane adadin ɗigo, wadda takardar Balko ta lissafa a matsayin “OpenAI Math Release preprint” kuma ta danganta ka’idar (theorem) gare ta. Takardar ba ta faɗi yadda aka samo wannan hujja ba. A kalmomin Balko, ta asali “gajeruwa ce in an kwatanta”, amma “tana da wuyar bi sosai”. Takardarsa ta farko (preprint) ta gabatar da wata siga mai sauƙi wadda, kamar yadda ya rubuta, “ke buƙatar ilimin farko kawai na linear algebra da ka’idar jadawalai”. Wani masanin lissafi, Gelasio Salazar, yana shirya wani bayani dabam, dalla-dalla.

Ƙirga coefficients maimakon ƙetarewa

Tunda zanen da aka sani sun riga sun kai Z(n), iyakar ƙasa (lower bound) kawai ke buƙatar hujja. Tana ɗaukar matakai huɗu.

1. Lambobi mara (odd) sun isa. Ana iya sake zana mafi kyawun zane ta yadda layukan da ke raba ɗigo ba za su taɓa ƙetare juna ba; sai kowace ƙetarewa ta shafi ɗigo 4 daban-daban. Cire kowanne cikin ɗigo 6 ɗaya bayan ɗaya: kowane hoton ɗigo 5 da ya rage yana da aƙalla ƙetarewa 1, kuma kowace ƙetarewa tana tsira daga daidai 2 cikin cirewa 6 (tana ɓacewa duk lokacin da aka cire ɗaya daga cikin ɗigonta 4, kuma tana tsira daga sauran 2). Don haka ninki biyu na ƙetarewar aƙalla 6 ne: aƙalla 3, wato Z(6). Ƙirgen iri ɗaya yana aiki ga kowace lamba cika (even).
2. Iyalin polynomials. A ba kowane ɗigo lambarsa ta kansa. Ƙetarewa tana shafar layuka biyu, saboda haka ɗigo huɗu, saboda haka lambobi huɗu. Balko yana amfani da polynomials masu masu-canji (variables) huɗu, waɗanda aka zaɓa ta yadda iyalin ke da daidai Z(n) coefficients masu zaman kansu idan n lamba mara ce — ga ɗigo 7, 3 × 3 = 9.
3. Ƙetarewa kaɗan na barin wuri. Neman polynomial ya zama sifili a wata ƙetarewa daidaito (equation) ɗaya ne. Idan daidaitattun sun yi ƙasa da coefficients masu ’yanci, linear algebra koyaushe tana barin mafita wadda ba sifili ba. Don haka zane mai ƙetarewa ƙasa da Z(n) zai zo da polynomial wanda ba sifili ba da ke zama sifili a dukan ƙetarewarsa; a ɗauki wanda darajarsa (degree) ta fi ƙanƙanta.
4. Fili (plane) yana mayar da martani. Ilimin siffofi (geometry) yana shigowa ta hanyar wata hujja ta gargajiya guda ɗaya: rufaffen zagaye (closed loop) a cikin fili yana ƙetare wani daga dama zuwa hagu daidai adadin lokutan da yake ƙetarewa daga hagu zuwa dama. Da nauyi (weights) da aka zaɓa da kyau, wannan yana ba da jimlar murabba’an ƙimomin polynomial ɗin, wasu an ƙirga su a matsayin tabbatattu (positive), wasu korau (negative), wadda jimlarta sifili ce. Dukan abubuwan tabbatattu suna a wuraren ƙetarewa, inda polynomial ɗin sifili ne, don haka dole korau ɗin su zama sifili su ma. Amfani na biyu da hujjar zagayen ya sa polynomial ɗin ya zama mai rabuwa da wani tsayayyen factor; rabawa yana ba da polynomial wanda ba sifili ba mai ƙaramin daraja da halaye iri ɗaya, wanda ba zai yiwu ba, tunda mun ɗauki mafi ƙanƙanta.

Wannan hujjar alamomi (sign argument) ita ce babban sauyin Balko: ta maye gurbin hujjar asali “da ta ƙunshi nondegenerate bilinear form da orthogonal complements”. Ya kuma tabbatar da hujjar zagayen ta wata hanya dabam kuma ya keɓe kowane ɗigo kai tsaye fiye da da.

Wasu hanyoyin haɗi da aka warware lokaci guda

Amsar tana zama Z(n) idan, maimakon ƙetarewa, an ƙirga nau’i-nau’i na layukan da ke ƙetare juna ko kaɗan, ko waɗanda ke ƙetare juna sau mara (odd) — muddin layukan da ke raba ɗigo ba su taɓa haɗuwa a wani wuri ba. Haɗe da ragewa (reductions) da aka yi a baya, ka’idar tana kuma ba da ainihin lambobin ƙetarewa ga cikakkun jadawalai da aka cire wasu haɗi daga cikinsu, ga kwafin cikakken jadawali da aka jera kamar sarƙa bisa hanya ko kewaye da zagaye mai lamba cika (even cycle), da kuma ga wani iyali na hanyoyin haɗi masu kama da fractal da ake kira extended Sierpiński graphs.

Ka cire layi guda ɗaya daga cikakken jadawalin ɗigo 6, kuma mafi ƙarancinsa yana sauka daga ƙetarewa 3 zuwa 2; a ɗigo 8, daga 18 zuwa 15.