Problémy čisté matematiky

Představte si, že vlastníte několik dolů a několik skladů. Vytěžený materiál mezi nimi přepravujete po kolejích. Protože potřebujete mít propojené všechny doly se všemi sklady, musejí se koleje křížit. Na těchto místech ale nejčastěji dochází k nehodám, a proto je nutné spojení navrhnout tak, aby se koleje křížily co nejméně a docházelo k co možná nejmenším ztrátám. Podobnými, avšak mnohem komplikovanějšími problémy se zabývá matematická disciplína zvaná kombinatorika. Právě za vyřešení několika starých kombinatorických domněnek získal Martin Balko z Matematicko-fyzikální fakulty UK ocenění Neuron v oboru computer science.

Začněme jednoduše – co je v matematice domněnka?

Jde zpravidla o jasně formulovanou hypotézu, kterou vyslovil nějaký matematik. Platnost domněnky zatím nikdo nevyvrátil ani nepotvrdil. Je úkolem ostatních matematiků pokusit se ji ověřit a dokázat její platnost, nebo ji naopak pomocí protipříkladů vyvrátit.

Jakou domněnku se vám podařilo vyvrátit?

Za pomoci počítače jsme vyvrátili Petersovu–Szekeresovu domněnku z roku 2006, kdy jsme se snažili najít jisté podstruktury ve velkých zobecněných bodových množinách. Počítače nám nedávno pomohly také při dosažení pokroku u Hararyho–Hillovy domněnky o průsečíkových číslech úplných grafů, která zůstává nevyřešena již od padesátých let. Navíc se nám podařilo vyřešit dva otevřené problémy od slavných matematiků Conlona, Foxe, Leea a Sudakova ohledně takzvaných Ramseyových čísel. S kolegy z Prahy a Štýrského Hradce jsme za použití důkazů asistovaných počítačem také potvrdili platnost známé domněnky o pěti dírách v bodových množinách, která byla otevřena od osmdesátých let.

V čem teorie pěti děr spočívá?

Přestavte si, že máte hodně bodů v rovině. Mezi nimi hledáte takovou pětici bodů, která dohromady dává vrcholy konvexního pětiúhelníku, přičemž uvnitř něj není žádný jiný bod. Je známo, že tato bodová množina vždy existuje, pokud máme k dispozici alespoň deset bodů. Nás zajímalo, kolik takových množin budeme mít, když počet bodů v rovině poroste do nekonečna, a jak rychle bude jejich počet narůstat. A podařilo se nám dokázat, že jejich počet roste rychleji než lineárně v celkovém počtu bodů.

Jak je možné, že tento problém během několika desetiletí nevyřešil nikdo před vámi?

Měli jsme štěstí. Základ našeho důkazu spočívá v matematické indukci. Pro tu je vždy potřeba získat nějaký základ, ze kterého se rozvíjí. Potřebovali jsme projít všechny množiny nanejvýš s jedenácti body a vyhledat v nich vhodné podstruktury. S tím nám pomohl právě počítač. Další výpočty jsme ale dělali už jen s tužkou a papírem.

Váš úspěch tedy stojí na tom, že jste použili počítač?

Ano, množin s jedenácti body je totiž tak mnoho, že bez použití počítače bychom to nezvládli.

Snad to nebude působit příliš pochybovačně, ale zdá se mi, že použít v roce 2019 při práci počítač není zase tak převratné. Vy jste za to dostal ocenění…

Zní to primitivně, ale vůbec to není jednoduché. Úlohy, které jsme potřebovali vyřešit, byly mimořádně výpočetně náročné a bez počítače bychom je řešili opravdu hodně dlouho. Práci nám usnadnily SAT řešiče (SAT je zkratkou anglického výrazu pro splnitelnost – safisfability, pozn. red.), které počítají rychle a poskytují zajímavé výsledky. Počítačový důkaz také často dá pouze dílčí výsledek, od něhož se můžeme odrazit, ale zbytek důkazu se většinou ještě musí dodělat.

Mohl by každý, kdo použije SAT řešič, dojít ke stejnému výsledku a domněnku vyřešit?

Nejspíš by byl schopen vyřešit danou formuli. Řešení matematického problému ovšem nespočívá jen ve vyřešení formule. Podstatnou částí celého problému je zjištění, jakou formuli vůbec chceme řešit a které prostředky jsou k tomu nejvhodnější.

Původně jsme se chtěli pokusit vyvrátit Erdősovu–Szerekesovu domněnku, starou přes osmdesát let. To se nám sice nepodařilo, ale díky tomuto úsilí jsme vyvrátili její pozdější zesílení – a to je jeden z našich dnešních úspěchů.

Je běžné, že matematik vysloví domněnku, a ještě za osmdesát let není nikdo schopen ji vyvrátit, nebo potvrdit?

Autorem této domněnky je Paul Erdős, naprostá legenda mezi kombinatoriky. V době, kdy ji vyslovil, mu bylo devatenáct let. Je to skutečně fascinující osobnost a příběh, protože v době, kdy s Georgem Szekeresem domněnku formuloval, neměli pro její platnost příliš silné důkazy. Zjednodušeně řečeno si prošli pár příkladů, měli dojem, že by to mohlo platit, a tak domněnku formulovali. A dodnes ji nikdo nevyvrátil.

Budete na jejím vyvrácení dále pracovat?

Vzhledem k tomu, že se nám ji pořád nepodařilo vyvrátit, a vzhledem k nedávnému průlomu Andrewa Suka, v ni začínám věřit. Snahou o její vyvrácení ale můžeme najít nové, zajímavé konstrukce množin a možná i nějaké, které ještě neznáme. Na tento problém existuje hodně různorodých extremálních příkladů, což většinou znamená, že je opravdu složitý. Jeho řešení bude zřejmě spočívat v nějaké hlubší strukturální vlastnosti, která nám zatím uniká.

Vyřešení problému by tedy pro kombinatoriku bylo velkým průlomem.

Jednoznačně. Na tento problém dokonce Paul Erdős vypsal finanční odměnu ve výši pět set dolarů. To není zrovna moc, ale když se v matematice na něco vypíše finanční odměna, je to opravdu důležitý problém. Na některé úlohy to bývá třeba jen deset dolarů.

Funguje to v matematice tak, že se vracíte ke starším problémům, které se snažíte rozlousknout, nebo se můžeme těšit na vaši vlastní Balkovu domněnku, na jejíž vyřešení bude také vypsána odměna?

Doufám, že můžeme, byla by to pocta. Atraktivita domněnky se měří tím, kolik lidí ji považuje za zajímavou a kolik z nich se jí bude věnovat.

Začal jsem se například zabývat studiem takzvaných Ramseyových čísel uspořádaných grafů. Jde o novou oblast, na kterou se už upřely i zraky předních světových matematiků. Do doby, než jsme ji začali s kolegy systematicky studovat, se jí ovšem nikdo moc nevěnoval. Myslím, že se nám ve studiu Ramseyových čísel podařilo nastolit nový trend. Momentálně pracuji na rozšíření této teorie na hypergrafy.

RNDr. Martin Balko, Ph.D

Působí na katedře aplikované matematiky Matematicko-fyzikální fakulty UK. V minulosti absolvoval stáže na Ben Gurionově univerzitě v Beer Ševě a na Institutu Alfréda Rényiho v Budapešti.