Problémy čisté matematiky ****************************************************************************************** * Problémy čisté matematiky ****************************************************************************************** Představte si, že vlastníte několik dolů a několik skladů. Vytěžený materiál mezi nimi pře kolejích. Protože potřebujete mít propojené všechny doly se všemi sklady, musejí se koleje těchto místech ale nejčastěji dochází k nehodám, a proto je nutné spojení navrhnout tak, a křížily co nejméně a docházelo k co možná nejmenším ztrátám. Podobnými, avšak mnohem kompl problémy se zabývá matematická disciplína zvaná kombinatorika. Právě za vyřešení několika kombinatorických domněnek získal Martin Balko z Matematicko-fyzikální fakulty UK ocenění N 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 do nikdo nevyvrátil ani nepotvrdil. Je úkolem ostatních matematiků pokusit se ji ověřit a dok 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 najít jisté podstruktury ve velkých zobecněných bodových množinách. Počítače nám nedávno p při dosažení pokroku u Hararyho–Hillovy domněnky o průsečíkových číslech úplných grafů, kt 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 s matematiků Conlona, Foxe, Leea a Sudakova ohledně takzvaných Ramseyových čísel. S kolegy z Štýrského Hradce jsme za použití důkazů asistovaných počítačem také potvrdili platnost zná 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á do vrcholy konvexního pětiúhelníku, přičemž uvnitř něj není žádný jiný bod. Je známo, že tato vždy existuje, pokud máme k dispozici alespoň deset bodů. Nás zajímalo, kolik takových mno když počet bodů v rovině poroste do nekonečna, a jak rychle bude jejich počet narůstat. A 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ře základ, ze kterého se rozvíjí. Potřebovali jsme projít všechny množiny nanejvýš s jedenáct v nich vhodné podstruktury. S tím nám pomohl právě počítač. Další výpočty jsme ale dělali 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ád Snad to nebude působit příliš pochybovačně, ale zdá se mi, že použít v roce 2019 při práci 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, by výpočetně náročné a bez počítače bychom je řešili opravdu hodně dlouho. Práci nám usnadnil (SAT je zkratkou anglického výrazu pro splnitelnost – safisfability, pozn. red.), které po a poskytují zajímavé výsledky. Počítačový důkaz také často dá pouze dílčí výsledek, od něh 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 formule. Podstatnou částí celého problému je zjištění, jakou formuli vůbec chceme řešit a jsou k tomu nejvhodnější. Původně jsme se chtěli pokusit vyvrátit Erdősovu–Szerekesovu domněnku, starou přes osmdesá nám sice nepodařilo, ale díky tomuto úsilí jsme vyvrátili její pozdější zesílení – a to je dnešních úspěchů. Je běžné, že matematik vysloví domněnku, a ještě za osmdesát let není nikdo schopen ji vyv potvrdit? Autorem této domněnky je Paul Erdős, naprostá legenda mezi kombinatoriky. V době, kdy ji v devatenáct let. Je to skutečně fascinující osobnost a příběh, protože v době, kdy s George domněnku formuloval, neměli pro její platnost příliš silné důkazy. Zjednodušeně řečeno si příkladů, měli dojem, že by to mohlo platit, a tak domněnku formulovali. A dodnes ji nikdo 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 An začínám věřit. Snahou o její vyvrácení ale můžeme najít nové, zajímavé konstrukce množin a které ještě neznáme. Na tento problém existuje hodně různorodých extremálních příkladů, co znamená, že je opravdu složitý. Jeho řešení bude zřejmě spočívat v nějaké hlubší strukturá 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 do zrovna moc, ale když se v matematice na něco vypíše finanční odměna, je to opravdu důležit 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 rozlousk 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ž 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ů. J oblast, na kterou se už upřely i zraky předních světových matematiků. Do doby, než jsme ji systematicky studovat, se jí ovšem nikdo moc nevěnoval. Myslím, že se nám ve studiu Ramsey 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 abso