Pričakovali bi, da so zahtevni matematični problemi, ki so na rešitev čakali desetletja ali stoletja, abstraktni, za laika nerazumljivi in v običajnem svetu neuporabni. Vsi niso takšni, a redki so tako razumljivi, ilustrativni in kratki kot nekateri izreki iz teorije grafov.

Južnoafriški matematik Francis Guthrie je leta 1852 barval zemljevid angleških grofij. Ugotovil je, da zadostujejo že štiri barve, pa nobeni sosednji grofiji ne bosta iste barve. Opažanje je pokazal svojemu bratu Fredericku, ki je tedaj še študiral matematiko pri slavnem Augustusu De Morganu na Univerzitetnem kolidžu v Londonu. De Morgan je z zanimivim problemom seznanil matematične kroge.



Izkazalo se je, da lahko vse zemljevide resnično pobarvamo s štirimi barvami.* Toda trditev še vedno zveni neintuitivno, saj si v domišljiji vendarle lahko zamislimo poljubno zapletene zemljevide. Poklicni in ljubiteljski matematiki so to počeli, vendar nikomur ni uspelo narisati zemljevida, ki bi zahteval več kot štiri barve. Trditve se je prijelo ime izrek štirih barv.
 

Težave z dokazovanjem

Sledilo je več poskusov dokazov, med njimi so nekateri za pravilne veljali več desetletij. Alfred Kempe je leta 1879 zapisal dokaz, katerega nepravilnost so odkrili šele leta 1890. Podobno je kot dokaz 11 let veljalo delo Petra Guthrieja Taita. Nekateri delni dokazi so obstajali in nerešeno je ostalo le vprašanje, ali je pravilni odgovor štiri ali pet. Trivialno je pokazati, da tri barve ne morejo biti dovolj. Enostaven je tudi dokaz, da pet barv vedno zadostuje. Zadostujejo štiri?

Vsi primeri kažejo tako, vendar trdnega dokaza ni bilo. Da bi izrek ovrgli, bi bil dovolj že en sam protiprimer, a za potrditev ne moremo preveriti vseh neskončno mnogo primerov. Potrebujemo dokaz. Kljub neuspešnosti so številni poskusi prinesli opazen napredek in novo razumevanje v veji matematike, ki se imenuje teorija grafov.



Na veljaven dokaz izreka je bilo treba počakati do leta 1976, ko sta ga objavila Kenneth Appel in Wolfgang Haken. Dokaz ni dvignil veliko prahu le zato, ker je rešil 125 let star problem, temveč predvsem zaradi svoje nekonvencionalnosti. Bil je prvi pomemben izrek, ki so ga dokazali z računalnikom.
 

Eleganca ali surova moč

Matematiki so vedno veljali za velike estete. Logično ni prav nobene razlike med elegantnim dokazom, ki je vsem razumljiv in v nekaj vrsticah koncizno dokaže izrek, ter špagetastim dokazom, v katerem preverimo vse možne primere. Ima pa v svetu matematikov večjo vrednost prvi. Razlog ni zgolj nečimrnost; krajše dokaze je načeloma lažje preveriti, pogosto pa vsebujejo tudi kakšen dodaten uvid v problem in odkrijejo kakšno dodatno povezavo.

Appel in Haken sta pokazala, da obstaja samo 1936 različnih konfiguracij, na katere je mogoče poenostaviti vsak zemljevid. Računalnik je potem preveril vse konfiguracije in ugotovil, da jih je možno pobarvati s štirimi barvami. Nekateri matematiki so bili najprej močno skeptični do takšnega dokaza, ker se ga ne da preveriti ročno. To pa pomeni, da je treba zaupati (ali preveriti), da je računalniška koda pravilna, da prevajalnik nima hroščev in da računalnik strojno kodo izvaja brez napak.



Po začetni skepsi matematična skupnost danes ta dokaz priznava. Število različnih konfiguracij so še zmanjšali, na 633, preverili pa so jih z drugimi algoritmi na drugih računalnikih. Izrek je bil dokazan na več načinov, tudi z računalniškim programom za dokazovanje izrekov Coq. Računalniški dokazi so danes v matematiki normalno sprejeti. Med znanimi primeri so še igra štiri v vrsto, optimalna rešitev Rubikove kocke, najgostejše zlaganje krogel (Keplerjev problem) in še nekaj drugih.

Izrek štirih barv ostaja lep primer, da imajo v matematiki včasih elegantna in preprosta vprašanja zapletene in nič kaj elegantne dokaze.
 

Teorija grafov

Barvanje zemljevidov je zanimiv, razumljiv, poučen in uporaben problem, a na prvi pogled deluje izoliran od preostalega sveta. V resnici pa sodi na področje teorije grafov. Grafi so množice objektov (vozlišč), ki imajo medsebojne povezave. Zemljevid lahko poenostavimo v omrežje vozlišč, kjer vsako vozlišče predstavlja državo, povezana pa so tista, katerih države mejijo druga na drugo. Taka predstavitev je uporabna, ker se s tem izgubijo nebistvene značilnosti, kot so dolžina mej, oblika držav in podobno, ostanejo pa le informacije o medsebojni povezanosti. Dobili smo graf.

Izrek štirih barv torej v matematičnem jeziku pravi, da lahko vsak ravninski graf pobarvamo s štirimi barvami na način, da nobeni vozlišči z medsebojno povezavo nista enake barve. Seveda pa so lahko grafi neprimerno bolj zapleteni od zemljevidov in tedaj niso več ravninski. Graf je ravninski, če ga lahko narišemo tako, da se povezave med seboj ne sekajo (razen v skupnih vozliščih). Za grafe, ki niso ravninski, ne zadostujejo štiri barve.

Teorija barvanja grafov se uporablja za reševanje številnih problemov, denimo pri sestavljanju urnikov, sedežnih redov, optimizacijskih problemih in celo reševanju sudokuja.
 

Ruski matematik Jaroslav Šitov je dokazal, da Hedetniemijeva domneva ne drži. Foto Inštitut Maxa Plancka

Nekatere domneve ne držijo

Povsem drugačna pa je zgodba, ki jo je spisal 30-letni ruski matematik Jaroslav Šitov. Doktoriral je šele pred štirimi leti, v svojem življenjepisu pa ima med raziskovalnimi interesi na prvem mestu zapisano: zabavati se. Trenutno je izredni profesor na katedri za aplikativno matematiko inštituta za elektroniko in matematiko na moskovski ekonomski fakulteti.

Pred dvema mesecema je objavil kratek, eleganten, tristranski dokaz, ki je ovrgel 53 let staro domnevo o barvanju grafov, ki jo je v svoji doktorski disertaciji postavil matematik Stephen Hedetniemi. Ukvarja se s tenzorskim produktom dveh grafov, ki predstavlja nov, večji graf. V njem so vozlišča pari vozlišč iz prvotnih grafov, povezana pa so le, če sta povezana tudi oba para vozlišč v prvotnih grafih. Hedetniemi je trdil, da za barvanje novega grafa potrebujemo toliko barv, kolikor jih potrebujemo za barvanje manj zahtevnega izmed prvotnih grafov.

Od leta 1966 do letošnjega maja matematikom ni uspelo najti protiprimera, torej tenzorskega produkta dveh grafov, ki bi za barvanje zahteval manj barv kot katerikoli od prvotnih grafov. Če zelo dolgo časa veliko pametnim ljudem ne uspe najti protiprimera, matematiki običajno s stisnjenimi zobmi hipotezo sprejmejo kot verjetno resnično.

To ni tako nezaslišan primer, kot bi si v rigoroznem svetu matematike predstavljali; Riemannova hipoteza je nedokazana že 160 let, odkar si jo je Bernhard Riemann zamislil, pa to ne povzroča preveč težav. Še več, na tej hipotezi, ki sicer sodi na povsem drugo področje matematike, temelji cel kup drugih dokazov in izrekov, povezanih s praštevili in drugimi tematikami iz teorije števil. A za Riemannovo hipotezo velja podobno, kot je prej za Hedetniemijevo – zelo veliko zelo pametnih ljudi že zelo dolgo išče protiprimer, pa ga ne najdejo, dokaza zanjo pa tudi ne.

Hedetniemijevo domnevo so v nekaterih posebnih primerih dokazali, recimo za grafe s kromatičnim številom največ štiri ali necelim kromatičnim številom in za ciklične grafe. Po drugi strani so dokazali, da za usmerjene grafe ali grafe z neskončnim številom barv ne drži. Nihče pa ni vedel, kaj je res v osnovnem primeru: na končnih, neusmerjenih grafih s celoštevilčnim kromatičnim številom. Toda splošno prepričanje je bilo, da drži, je pojasnil Noga Alon s Princetona.


 

Kaj je razumel Šitov

Članek, ki ga je maja objavil Šitov, na treh straneh elegantno in jedrnato pokaže, da Hedetniemijeva domneva ne drži. Obstajajo namreč primeri grafov, pri katerih je možno tenzorski produkt pobarvati z manj barvami kakor kateregakoli izmed prvotnih grafov. S tem dokazom, ki ga je matematična skupnost sprejela, se je Šitov zapisal v zgodovino.

Kot je pojasnil Anthony Bonato z Ryersonove univerze v Torontu, so številni verjeli v Hedetniemijevo hipotezo, ker nihče ni našel protiprimera. Zdaj pa je Šitov pokazal metodo, ki tvori protiprimere. Njegov dokaz je Pavol Hell z univerze Simona Fraserja v Burnabyju v Kanadi označil za elementaren, a genialen. Pravzaprav je neverjetno, da se ga v vseh teh letih ni domislil nihče drug. Očitno je Šitov problem razumel bolje in globlje kot kdorkoli drug.

Šitov uporablja graf in njegov eksponentni graf. V dokazu nastopata graf z najmanj 4¹⁰⁰ vozlišči in njegov eksponentni graf z vsaj 4^10.000 vozlišči, kar je bistveno več od števila vseh atomov v vesolju. To še zdaleč niso največja števila, ki so se kdaj pojavila v kakšnem matematičnem dokazu. Nasprotno, v primerjavi z nekaterimi sta resnično majceni, je komentiral Šitov.

Na odkritje se je že odzval Hedetniemi. Kot je dejal, je navdušen, da je problem po toliko letih rešen. Dokaz Šitova je eleganten, preprost in kakovosten, je še dodal. V matematiki je bilo že precej domnev ali izrekov, ki so veljali dolga leta, pa so se na koncu izkazali za nepravilne. Na drugi strani so domneve, ki so jim vsi verjeli, a so bile dokazane šele po mnogo letih. Pierre de Fermat je že v 17. stoletju postavil oboje: Fermatov zadnji izrek iz leta 1637 je šele leta 1994 dokazal Andrew Wiles, njegov izrek o praštevilih pa je že v 18. stoletju ovrgel Leonhard Euler.

V matematiki je še vedno cela vrsta nedokazanih domnev in za nekatere so razpisane celo milijonske nagrade. Nekatere imajo praktično izjemno vrednost, druge so zgolj estetski dragulji. Vse so nerešene zato, ker so zelo težke ali pa neresnične. Marsikatera je verjetno oboje.

* To velja za zemljevide, kjer države nimajo eksklav. Peto barvo potrebujemo, če želimo drugače in skladno pobarvati morja in jezera.

–––
Matej Huš je znanstveni sodelavec na Kemijskem inštitutu, kjer raziskuje kemijske procese na ravni kvantne mehanike.