Stránka přeložená strojově pro lepší dosažitelnost obsahu tazateli užívajícími češtinu.
Jaro 2022 - přehled harmonogramu
Diana Piguet (Akademie věd ČR): Dokonalé balení degenerovaných grafů
Pondělí 21. února, 14:00, místnost C417
Rodina grafů se zabalí do hostitelského grafu, pokud v hostitelském grafu existují hranově nesouvislé kopie každého prvku rodiny. Budu hovořit o dokonalém zabalení degenerovaných grafů sublineárního maximálního stupně do úplného grafu. Tato práce byla motivována dvěma krásnými stromovými balícími domněnkami - jednou Ringelovou z roku 1963 a druhou Gyárfásovou z roku 1976. Jedná se o společnou práci s Peterem Allenem, Julií Böttcherovou, Dennisem Clemensem, Janem Hladkým a Anuschem Tarazem.
Mykhaylo Tyomkyn (Univerzita Karlova): Slabé nasycení v grafech a hypergrafech
Pondělí 28. února, 14:00, místnost C417
Pro dva r-uniformní hypergrafy G a H říkáme, že G je slabě nasycený H, pokud lze chybějící hrany v G postupně doplňovat a v každém kroku vytvořit novou kopii H. Veličina wsat(n,H) měří nejmenší velikost slabě H nasyceného r-grafu řádu n. Pro r=2 krátký argument Alona (1985) ukazuje, že pro libovolný graf H má wsat(n,H)/n s rostoucím n tendenci k limitě. Tuza v roce 1992 vyslovil domněnku, že pro libovolné r má veličina wsat(n,H)/n^{r-1} podobně limitu c(H). Představím nedávný důkaz Tuzovy domněnky. Společná práce s Asafem Shapirou.
Samuel Mohr (Masarykova univerzita): Inducibilita cyklů
Pondělí 21. března, 14:00, místnost C417
Při daných kladných celých číslech k a n se můžeme ptát na maximální počet indukovaných cyklů délky k v n-vrcholovém grafu. Tento typ otázek o indukovatelnosti cyklů včetně stability vznikl již před několika desetiletími a byl podnícen i Erdősovými domněnkami. V roce 1975 Pippenger a Golumbic vyslovili domněnku, o níž se všeobecně věřilo, že obecná odpověď je k!/(k^k-k). V poslední době bylo dosaženo některých konkrétních exaktních výsledků pomocí metod vlajkové algebry. V této přednášce podám přehled o známých výsledcích a aproximacích. Bude také představen způsob, jakým byly zapojeny nerovnosti vlajkové algebry k získání exaktních výsledků. Můj výzkum byl podpořen DAAD.
Filip Pokrývka (Masarykova univerzita): Modelová kontrola prvního řádu intervalových grafů
Pondělí 28. března, 14:00, místnost C417
Třída intervalových grafů je geometrická třída grafů, kde relace hran je relací průniku intervalů na reálné ose. Pro daný intervalový graf lze efektivně vypočítat geometrickou reprezentaci, takže geomterické vlastnosti lze využít k řešení obtížných problémů. Tato přednáška se zaměřuje na problém kontroly modelu prvního řádu (FO MC), protože tento metaproblém zachycuje všechny problémy vyjádřitelné v logice prvního řádu (např. k-CLIQUE, k-DOMINATING SET). První výsledky prezentované na ICALP'13 ukázaly tvrdost FO MC na intervalových grafech obecně a ukázaly přirozenou podtřídu intervalových grafů, ve které je tento problém efektivně řešitelný. Tyto výsledky byly vylepšeny v příspěvku na FOCS'15, kde byl uveden další příklad efektivně řešitelné podtřídy. Naše výsledky dávají úplnou odpověď na otázku, kdy mají dědičné podtřídy intervalových grafů efektivní FO MC.
Jedná se o společnou práci s Petrem Hliněným.
Nathanael Arkor (Masarykova univerzita): Co je to důkaz?
Pondělí 4. dubna, 14:00, místnost C417
Všichni důvěrně známe pojem důkaz, který je v matematice nezbytný. Nejspíše jsme se však jen zřídkakdy zamysleli nad tím, co přesně tvoří důkaz. Pro každodenní matematiku se tato otázka může zdát nedůležitá, protože účelem důkazu je jednoduše předat porozumění ostatním matematikům. V posledních letech je však stále jasnější, že existuje významná potřeba počítačové verifikace matematiky: to vyžaduje obecný, formální pojem důkazu.
Na základě myšlenek z teorie typů představím obecný pojem dedukčního systému, který zachycuje různé formální systémy důkazů, a budu diskutovat o tom, jak takový pojem zapadá do rostoucí vize budoucnosti matematiky. Pro motivaci těchto myšlenek uvedu příklady z algebry, logiky a teorie typů.
Při přednášce se neočekává znalost teorie typů.
Walner Mendonça (IST Rakousko): Tiling hranově barevných grafů s několika monochromatickými grafy omezeného stupně (Tiling edge-coloured graphs with few monochromatic bounded-degree graphs)
Pondělí 11. dubna, 14:00, místnost C417
Gerencsér a Gyárfás v roce 1967 dokázali, že pro libovolné dvoubarevné hrany K_n je možné rozdělit V(K_n) na dvě monokromatické cesty. Tento výsledek, který má přímočarý důkaz, motivoval mnoho dalších náročných problémů, které byly v posledních letech intenzivně studovány. Například otevřená domněnka Erdőse, Gyárfáse a Pybera z roku 1991 říká, že pro libovolné r-ové zbarvení hran K_n existuje r monochromatických cest rozdělujících V(K_n). V literatuře můžeme najít i další verze problému, kde nás místo rozdělení na cesty zajímá rozdělení na stromy, cykly, nebo dokonce mocniny cyklů.
Grinshpun a Sárkőzy studovali obecnější verzi problému, kde je zajímalo rozdělení V(K_n) na několik monochromatických podgrafů, které jsou kopiemi dané rodiny grafů omezeného stupně. Dokázali, že pro libovolnou rodinu grafů ℱ = {F_i : i ∈ N} takovou, že |F_i| = i a Δ(F_i) ≤ D, platí: pro libovolné dvoubarevné hrany K_n existuje rozdělení V(K_n) na nejvýše 2^{O(D log D)} monochromatických podgrafů, které jsou kopiemi grafů z ℱ.
Předpokládali, že pro libovolné r-ové zbarvení hran K_n je možné rozdělit V(K_n) na 2^{D^C} monochromatických podgrafů, které jsou kopiemi grafů z ℱ, kde C=C(r) je konstanta, která závisí pouze na r. V této přednášce představíme první pokrok směrem ke Grinshpun-Sárkőzyho domněnce stanovením superexponenciální hranice.
Tomas Juškevičius (Akademie věd ČR): Vědecký pracovník (J. B.): Antikoncentrace součtů náhodných vektorů: k domněnkám Leader-Radcliffa a Lee Jonese
Pondělí 25. dubna, 14:00, místnost C417
V této přednášce se budeme zabývat antikoncentračními nerovnostmi pro součty náhodných vektorů. Konkrétně asymptoticky stanovíme dvě domněnky: jednu podle Lee Jonese (1978) a druhou podle Leader-Radcliffa (1994). Možná překvapivě je hlavní složkou pro stanovení druhého výsledku věta o silném dokonalém grafu podle Chudnovského, Robertsona, Seymoura a Thomase (2002).
Přednáška vychází z nedávné společné práce s V. Kurauskasem (Vilniuská univerzita).
Zuzana Patáková (Univerzita Karlova): O Radonově a frakční Hellyho větě
Pondělí 2. května, 14:00, místnost C417
Radonova věta hraje základní roli v mnoha výsledcích kombinatorické konvexity. Říká, že libovolnou množinu d+2 bodů v R^d lze rozdělit na dvě části tak, aby se jejich konvexní trupy protínaly. Vyplývá z ní Hellyho věta a jak bylo nedávno ukázáno, také její robustnější verze, tzv. frakční Hellyho věta. Standardními technikami z toho následně plyne existence slabých epsilonových sítí a (p,q)-věta.
Ukážeme, že tyto výsledky můžeme získat i bez předpokladu konvexity, když ji nahradíme velmi slabými topologickými podmínkami. Přesněji řečeno, vzhledem k průsečíkově uzavřené rodině F podmnožin R^d budeme složitost F měřit supremem prvních d/2 Bettiho čísel nad všemi prvky F. Ukážeme, že omezená složitost F zaručuje verze všech výše uvedených výsledků. Částečně založeno na společné práci s Xavierem Goaocem a Andreasem Holmsenem.
Přednáška vychází z nedávné společné práce s V. Kurauskasem (Vilniuská univerzita).
Alexandre Duret-Lutz (EPITA): Duturec (Duturec): Praktické aplikace rozkladu střídavého cyklu
Pondělí 23. května, 14:00, místnost C417
Společná práce s Antoniem Casaresem, Klárou J. Meyerovou, Florianem Renkinem a Salomonem Sickertem.
V roce 2021 zavedli Casares, Colcombet a Fijalkow rozklad střídavých cyklů (ACD) ke studiu vlastností a transformací Müllerových automatů. Představujeme první praktickou implementaci ACD ve dvou různých nástrojích, Owl a Spot, a adaptujeme ji na rámec Emerson-Leiových automatů, tj. ω-automatů, jejichž podmínky přijetí jsou definovány booleovskými formulemi.
ACD poskytuje transformaci Emerson-Leiových automatů na paritní automaty se silnou zárukou optimality: výsledný paritní automat je minimální mezi těmi automaty, které lze získat duplikací stavů. Naše empirické výsledky ukazují, že tato transformace je v praxi použitelná. Dále ukazujeme, jak lze pomocí ACD zobecnit mnoho dalších specializovaných konstrukcí, jako je rozhodování o typičnosti automatů a degeneralizace zobecněných Büchiho automatů, a poskytujeme tak rámec praktických algoritmů pro ω-automaty.
David Munhá Correia (ETH Zürich): Erdösova domněnka o pancykličnosti hamiltonovských grafů
Pondělí 13. června, 14:00, místnost C417
Graf s n vrcholy je hamiltonovský, pokud obsahuje cyklus pokrývající všechny jeho vrcholy, a je pancyklický, pokud obsahuje cykly všech délek od 3 do n. Metaproblémem, který se studuje již nejméně padesát let, je pochopit, jak blízko jsou si tyto dva pojmy. Znamená každá netriviální podmínka implikující hamiltonovost také pancykličnost? A jaké podmínky je třeba přidat, aby bylo zajištěno, že hamiltonovský graf je také pancyklický?
V roce 1972 Erdös vyslovil domněnku, že existuje absolutní konstanta C taková, že každý hamiltonovský graf G na alespoň n = C α(G
)2 vrcholech je pancyklický, kde α(G) označuje velikost největší nezávislé množiny v G. Tuto domněnku dokážeme v silné formě tím, že ukážeme, že stačí (2+o(1))α(G
)2 vrcholů, a to je těsné až na člen o(1).
Jedná se o společnou práci s Nemanjou Draganićem a Bennym Sudakovem.
Fan Wei (Princeton University): Lokální max-cut ve vyhlazeném polynomiálním čase
Pondělí 29. srpna, 14:00, místnost C417
V této přednášce ukážeme, že v prostředí vyhlazené analýzy (kde každý parametr je perturbován nezávislou malou chybou) je složitost algoritmu lokálního hledání pro max-cut v grafu, který je také ekvivalentní asynchronní Hopfieldově síti, nebo přirozeného algoritmu pro nalezení Nashovy rovnováhy ve hře o stranickou příslušnost (příklad potenciální hry), polynomiální. Jedná se o první dokázanou vyhlazenou polynomiální hranici pro tyto modely; dříve nejlepší známá hranice je n^{O(log(n))}.
Jedná se o společnou práci s Omerem Angelem, Sebastienem Bubeckem a Yuvalem Peresem.