Společný seminář DIMEA a FORMELA

Podzim 2021 – přehled rozvrhu

Tomáš Kaiser (Západočeská univerzita): Samostatné transverzály v grafech

Pondělí 20. září, 14:00, místnost C417

Nechť G je graf s oddílem P jeho vrcholové množiny. Nezávislá transverzála v G (vzhledem k P) je nezávislá množina G protínající každou třídu P. Nezávislé transverzály mají přirozené souvislosti s řadou problémů a od 70. let 20. století jsou podmínky jejich existence široce studovány. Budeme diskutovat topologické a pravděpodobnostní argumenty používané ke stanovení takových podmínek, stejně jako nedávný vývoj související s metodou komprese entropie. Zahrnuje společnou práci s Carlou Groenlandovou, Mattem Walesem a Oscarem Treffersem.

Filip Pokrývka (Masarykova univerzita): Twin-width of circle grafs

Pondělí, 4. října, 14:00, místnost C417

V roce 2020 Bonet a spol. zaveden parametr grafů nazvaný twin-width. Následovala řada výsledků, které ukázaly, že třídy grafů s omezenou šířkou dvojčete mají ovladatelnou kontrolu modelu prvního řádu a poté následovaly příklady tříd s omezenou šířkou dvojčete. Jedním z nejzajímavějších výsledků třídy grafů je, že jakákoli dědičná vlastní podtřída permutačních grafů má ohraničenou šířku dvojčat, zatímco třída všech permutačních grafů nikoli. Studovali jsme nadtřídu permutačních grafů nazývanou kruhové grafy (průsečíkový graf tětiv kruhu) a došli jsme k závěru, že dědičná podtřída kruhových grafů má ohraničenou šířkou dvojčat právě tehdy, když zakazuje některý graf permutace jako indukovaný podgraf. Jde o společnou práci s Petrem Hliněným.

Thekla Hamm (TU Vídeň): Jednotný rámec pro charakterizaci a výpočet šířkových opatření

Pondělí 11. října, 14:00, místnost C417

Algoritmy pro výpočet nebo aproximaci optimálních rozkladů pro dekompoziční parametry, jako je treewidth nebo clique-width, byly dosud tradičně přizpůsobeny konkrétním šířkovým parametrům. Navíc pro mim-width nebyly známy žádné účinné algoritmy pro výpočet dobrých rozkladů, a to ani při vysoce restriktivních parametrizacích. V této práci identifikujeme 𝓕-branchwidth jako třídu generických dekompozičních parametrů, které mohou zachytit mim-width, treewidth, clique-width a také další míry. Ukazujeme, že zatímco existuje nekonečný počet parametrů 𝓕-větvení, jen hrstka z nich je asymptoticky odlišná. Poté vyvíjíme algoritmy s pevnými parametry a kernelizační algoritmy (v rámci několika strukturálních parametrizací), které dokážou vypočítat každou možnou 𝓕-větev, poskytující sjednocující rámec, který dokáže efektivně získat téměř optimální stromové rozklady, k-výrazy a také optimální mim-šířku rozklady. Na základě společné práce s Eduardem Eibenem, Robertem Ganianem, Larsem Jaffkem a O-joungem Kwonem.

Pedro Campos Araújo (Česká akademie věd): Hamiltonovy cykly v rovnoměrně hustých hypergrafech

Pondělí 18. října, 14:00, místnost C417

Studujeme dostatečné podmínky pro existenci Hamiltonových cyklů v rovnoměrně hustých 3-uniformních hypergrafech. Ukázali jsme, že pokud má n-vrcholový 3-jednotný hypergraf H=(V,E) vlastnost, že pro libovolnou množinu vrcholů X a pro libovolnou sbírku dvojic vrcholů P je počet hyperhran složených dvojicí patřící do P a jeden vrchol z X je alespoň (1/4+o(1))|X||P| - o(|V|³) a H má minimální vrcholový stupeň alespoň Ω(|V|²), pak H obsahuje těsný Hamiltonův cyklus. Pravděpodobnostní konstrukce ukazuje, že konstanta 1/4 je v tomto kontextu optimální. Diskutujeme také možná rozšíření na vyšší uniformity.

Jan Hladký (Akademie věd ČR): Normy grafů a lemma regularity

Pondělí, 1. listopadu, 14:00, místnost C417

Normy grafů jsou poměrně nedávným konceptem, který se objevil s teorií grafonů. Tento koncept byl zvláště užitečný pro pokrok související s notoricky známým dohadem Sidorenka. Vysvětlím toto spojení a také vysvětlím, jak to souvisí s operací čerpání indexu, která je jádrem důkazů různých lemmat pravidelnosti. Diskuse je založena na arXiv:1809.03797.

Ander Lamaison (Masarykova univerzita): Hypergrafy s minimální pozitivní jednotnou turánskou hustotou

Pondělí, 8. listopadu, 15:00

Změna: Tato přednáška bude online a bude sloučena s  Webinář EPC

Reiher, Rödl a Schacht ukázali, že jednotná Turánova hustota každého 3-uniformního hypergrafu je buď 0 nebo alespoň 1/27, a zeptali se, zda existují 3-uniformní hypergrafy s jednotnou Turanovou hustotou rovnou nebo libovolně blízkou 1/27. Sestrojíme 3-uniformní hypergrafy s jednotnou Turánovou hustotou rovnou 1/27. To je založeno na společné práci s Frederikem Garbem a Danielem Králem.

Cornelius Brand (TU Vienna): Algebraické metody v algoritmech parametrizovaných grafů

Pondělí 15. listopadu, 14:00, místnost C417

V tomto příspěvku předložím přehled nedávných pokroků v algoritmech parametrizovaných grafů využívajících algebraické metody. Konkrétněji uvažujeme (speciální případy) problému isomorfismu podgrafu a ptáme se, zda se daný graf vzoru objeví jako podgraf v daném hostitelském grafu, kde parametrizujeme podle velikosti grafu vzoru. Svou pozornost omezíme hlavně na důležitý speciální případ, kdy je vzorem cesta. Jak se ukazuje, tento problém umožňuje elegantní formulaci z hlediska mnohorozměrných polynomů. Tato formulace může být následně vyřešena použitím řady algebraických objektů, jako jsou vnější algebry (B., Dell, Husfeldt, STOC'18 a B., ESA'19) nebo algebry diferenciálních operátorů (Pratt, FOCS'19 , B. a Pratt, ICALP'21). Lehce uvedeme nezbytné matematické pojmy posledně uvedeného přístupu, poukážeme na jeho aplikace na jiné problémy a načrtneme, jak se propojuje s jinými technikami v této oblasti, zejména s reprezentativními rodinami (viz např. Fomin et al., JACM, 2016 ).

Jan Volec (ČVUT Praha): Barevná verze Mantelovy věty

Pondělí 22. listopadu, 14:00, místnost C417

Klasický výsledek Mantel říká, že každý graf hustoty větší než 1/2 musí obsahovat trojúhelník a konstanta 1/2 je nejlepší možná. Nedávno DeVos, McDonald a Montejano dokázali následující tvrzení inspirované Mantelem: každý 2hranný n-vertexový graf s oběma barevnými třídami, které mají velikost větší než n²/6, obsahuje nemonchromatický trojúhelník a opět je nejlepší hranice. možný. Při daném počtu barev k≥2 se domnívali, že přirozené zobecnění jejich 2barevného extremálního grafu poskytne extremální grafy i pro obecné nastavení. Konkrétně domněnka říká, že pokud G je graf obarvený k-hranami, přičemž každá z barevných tříd má velikost větší než n²/(4k-2), pak G obsahuje nemonochromatický trojúhelník. V této přednášce představujeme vlajkový algebraický přístup pro obecnou otázku DeVose, McDonalda a Montejana v barvě k, která nám zřejmě umožňuje potvrdit jejich domněnku pro jakoukoli pevnou hodnotu k, kterou jsme uvažovali (zejména jsme ověřili domněnka pro všechny 10^6 > k). Přesněji, dáno celým číslem k, popisujeme lineární relaxaci původního extremálního problému pro k barev, jejichž rozměr na k vůbec nezávisí. Toto je společná práce se Sergejem Norinem.

Vít Musil (Masarykova univerzita): Kombinatorická expresivita neuronových sítí

Pondělí 29. listopadu, 14:00, místnost C417

Sada nástrojů populárních metod v informatice se dělí na dvě hlavní složky. Na jedné straně existují klasické algoritmické techniky z diskrétní optimalizace – grafové algoritmy, SAT-solvery, celočíselné programovací řešiče – často se silně optimalizovanými implementacemi a teoretickými zárukami na běh a výkon. Na druhé straně existuje oblast hlubokého učení, která umožňuje extrakci funkcí na základě dat a také flexibilní návrh end-to-end architektur. Dosažení fúze hlubokého učení s kombinatorickými algoritmy slibuje transformační změny umělé inteligence. Představujeme univerzální, snadno implementovatelnou, rychlou a teoreticky fundovanou metodu umožňující začlenění řešičů do neuronových sítí. Ukazujeme, že naše metoda dosahuje nejmodernějšího výkonu na různých benchmarcích počítačového vidění.

Anselm Paulus (MPI Tübingen): Kombinatorická expresivita neuronových sítí

Čtvrtek 16. prosince, 14:00, místnost C417

Během posledních let dosáhlo hluboké učení úžasných úspěchů v mnoha oblastech, jako je počítačové vidění a zpracování přirozeného jazyka. Ale zatímco neuronové sítě vynikají v získávání informací z nezpracovaných dat, notoricky se potýkají s úkoly zahrnujícími algoritmické uvažování. Takové úlohy mohou být často efektivně řešeny kombinatorickými řešiteli, kteří mohou stavět na dlouhé historii vývoje. Tyto řešitele však obvykle vyžadují čistou abstraktní formulaci problému namísto hrubých dat. Jak můžeme překlenout propast mezi těmito dvěma světy? Tato přednáška pojednává o dvou nedávno vyvinutých metodách, Blackbox Backpropagation a CombOptNet, které umožňují bezproblémovou integraci kombinatorických řešičů do end-to-end trénovatelných architektur hlubokého učení.