Společný seminář DIMEA a FORMELA

Alexander Rabinovich (Univerzita v Tel Avivu): O míře nejednoznačnosti automatů konečného stavu

Pondělí 10. února, 14:00, místnost C417

Automat je jednoznačný, pokud má pro každý vstup maximálně jeden přijímající výpočet. Automat je k-nejednoznačný, pokud má pro každý vstup nanejvýš k přijímající výpočty. Automat je omezeně nejednoznačný, pokud je pro některé k nejednoznačný. Automat je konečně (respektive spočetně) nejednoznačný, pokud má pro každý vstup nanejvýš konečně (respektive spočetně) mnoho přijímajících výpočtů.
U automatů přes konečná slova (a přes konečné stromy) je na každém vstupu nanejvýš konečně mnoho přijímajících výpočtů. Proto je každý automat na konečných slovech a na konečných stromech konečně nejednoznačný. Avšak nad nekonečnými slovy a nad nekonečnými stromy existují nedeterministické automaty s nespočetně mnoha přijímajícími výpočty.
V této přednášce zkoumám nedávné výsledky o stupni nejednoznačnosti automatů a běžných jazyků.

Théo Pierron (Masarykova univerzita): Několik Brooksových výsledků pro mocniny grafů

Pondělí 24. února, 14:00, místnost C417

Vzhledem k celému číslu k znamená vybarvení k-té síly grafu přiřazení barev jeho vrcholům takovým způsobem, že vrcholy ve vzdálenosti maximálně k dostávají různé barvy. Když k je 1, dostaneme standardní představu o zbarvení a Brooksova věta uvádí, že každý připojený graf maximálního stupně D> 2 kromě kliky na vrcholech D + 1 lze obarvit pomocí barev D (tj. O jednu barvu méně než naivní) horní hranice). Pro k> 1 platí podobný výsledek: s výjimkou Mooreových grafů lze naivní horní hranici snížit o 2. V této přednášce si ukážeme, jak tyto výsledky rozšířit, aby se při zvýšení k ušetřilo více barev.

Matjaž Krnc (University of Primorska): Na cestách, kterým se lze v grafech vyhnout

Pondělí 2. března, 14:00, místnost C417

Vrcholu v v grafu G se lze vyhnout, pokud je každá indukovaná cesta na třech vrcholech se středním vrcholem v obsažena v indukovaném cyklu. G. Dirac (1961) ukázal, že každý akordový graf má takový vrchol, a Ohtsuki et al. (1976) ukázal existenci odvratitelného vrcholu pro každý graf. Beisegel a kol. (2019) zobecnili tento pojem na cesty, kterým se lze vyhnout, a Bonamy et al. (2019+) ukázal, že pro každé kladné celé číslo k obsahuje každý graf obsahující indukovanou P _k také vyloučitelnou P _k . Tím se zevšeobecňují zmíněné výsledky týkající se odvrátitelných vrcholů, stejně jako výsledky Chvátala a kol. (2002) o existenci jednoduchých cest. V této přednášce ukážeme, že pro každé kladné celé číslo k a každý graf G lze každou indukovanou P _k z G posunout na vyloučitelnou P _k . Společná práce s V. Gurvichem, M. Milaničem a M. Vyalyim.

Jan Volec (České vysoké učení technické): Prahová hodnota pro stupeň K4-

Pondělí 9. března, 14:00, místnost C417

Prahová hodnota stupně ex ₂ (n, F) 3 uniformního hypergrafu F je minimální d taková, že každý 3 uniformní hypergraf na n vrcholech, ve kterém je každá dvojice vrcholů obsažena alespoň v hranách d + 1, obsahuje kopie F jako podgraf. V této přednášce se zaměříme na prahový stupeň K4-, jedinečný 3 uniformní hypergraf se 4 vrcholy a 3 hranami. Pomocí vlajkových algeber ukážeme, že ex ₂ (n, K4-) = n / 4 + O (1), což potvrzuje domněnku Nagle z roku 1999. Navíc ukazujeme, že pro každý téměř extrémní 3 uniformní hypergraf H existuje existuje kvazi náhodný turnaj T na stejné sadě vrcholů tak, že H je blízko v editační vzdálenosti k hypergrafu cyklicky orientovaných trojúhelníků T. Tím se získá velmi blízký vztah mezi prahovou hodnotou K4- stupně a existencí zkosit Hadamardovy matice, což nám umožňuje určit přesnou hodnotu ex ₂ (n, K4-) pro nekonečně mnoho hodnot n. Ve skutečnosti ukážeme, že stanovení přesné hodnoty ex ₂ (n, K4-) pro n = 4k + 3 je ekvivalentní Seberryho domněnce, že pro každé n = 4k existuje šikmá Hadamardova matice. Toto je společné dílo s Victorem Falgasem-Ravrym, Olegem Pighurkem a Emilem Vaughanem.