Společný seminář DIMEA a FORMELA

Guillermo Alberto Perez (University of Antwerp): Netrpělivý může použít omezený optimismus k minimalizaci lítosti

Čtvrtek 3. října, 14:00, místnost C417

Hry se slevou poskytují formální model pro studium posilovacího učení, kde je agent lákán k získání odměn brzy, protože pozdější odměny jsou diskontovány. Když agent interaguje s prostředím, může si uvědomit, že při zpětném pohledu by mohla zvýšit svou odměnu odlišným hraním: tento rozdíl ve výsledcích představuje její lítost. Agent se tak může rozhodnout dodržovat strategii minimálního lítosti. V tomto článku je ukázáno, že (1) vždy existují strategie s politováním minimální, které jsou přípustné - strategie je nepřípustná, pokud existuje jiná strategie, která vždy vede lépe; (2) výpočet minimální možné lítosti nebo ověření, že strategie je politováníhodná - minimální, lze provést v coNP a NP, bez ohledu na výpočetní náklady na numerickou analýzu (v opačném případě se tato hranice stává PSPACE).

Tomáš Kaiser (UWB Plzeň): Malé triangulace projekčních prostor

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

Trojúhelník reálného projektivního prostoru RP ^d dimenze d lze získat barycentrickým dělením hranice (d + 1) -dimenzionálního simplexu a identifikováním antipodálních bodů. Tato triangulace má exponenciálně mnoho vrcholů v d. Na druhou stranu, Arnoux a Marin v roce 1991 prokázali, že počet vrcholů triangulace RP ^d musí být větší než d + 2 zvolit 2. Od té doby je otevřeným problémem, zda existují takovéto triangulace s polynomiálně mnoha vrcholy v d. Budeme diskutovat o naší nedávné práci související s touto otázkou (společně s Matejem Stehlíkem).

Tom Kelly (University of Birmingham): O hustotě kritických grafů bez velkých klik

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

Graf je kritický k, pokud má chromatické číslo k a každý správný podgraf je (k - 1) - barevný. Hustota kritických grafů byla rozsáhle studována. Uvádíme zlepšení nejznámější dolní meze hustoty kritických grafů bez velkých klik. Diskutujeme také o souvislosti s možnou generalizací Reedovy domněnky. Společná práce s Luke Postle.

Péter Pál Pach (Vysoká škola technická a ekonomická v Budapešti): Polynomiální Schurova věta

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

Uvažujeme Ramseyho problém pro rovnici x + y = p (z), kde p je polynom s celočíselnými koeficienty. Za předpokladu, že p (1) p (2) je dokonce, ukážeme, že pro jakékoli 2-zbarvení kladných celých čísel má rovnice x + y = p (z) nekonečně mnoho monochromatických řešení. Ve skutečnosti ukazujeme, že počet monochromatických roztoků s x, y, z v {1,2, ..., n} je alespoň n ^ {2 / d ^ 3-o (1)}, kde d = deg (p).

Na druhé straně, když p (1) p (2) je liché, to znamená, že když p dosáhne pouze lichých hodnot, pak by nemělo existovat žádné monochromatické řešení, např. Je tomu tak, když obarvíme celá čísla podle jejich parita. My dáme charakterizaci všech 2-barev s vyloučením monochromatických roztoků na x + y = p (z).

Jedná se o společnou práci s Hong Liu a Csaba Sándor.

Michał Dębski (Masarykova univerzita): Centrovaná zbarvení omezených stupňových grafů

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

Barvení vrcholu vrcholu grafu G je p-centrováno, pokud pro každý připojený podgraf H z G existuje barva, která se objevuje přesně jednou na H, nebo c používá více než p barev na H. To souvisí s jinými pojmy sparity grafu, tj. třída grafů omezila expanzi pouze tehdy, existuje-li funkce f taková, že každý graf z této třídy připouští p-středové zbarvení s použitím maximálně f (p) barev.

Ukážu, že grafy s omezeným maximálním stupněm připouštějí p-centrované zbarvení pomocí O (p) barev - což vyvrací dohadu Pilipczuk a Siebertz. Důkaz používá metodu komprese entropie.

Přednáška bude založena na společném příspěvku se Stefanem Felsnerem, Piotrem Mickem a Felixem Schröderem: https://arxiv.org/abs/1907.04586

Robert Hancock (Masarykova univerzita): Meze posloupností latinských čtverců

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

Představujeme teorii limitů latinských čtverců, paralelizující nedávné teorie limitů hustých grafů a permutací. Prostor limitních objektů - tzv. Latinonů - jsou dvě distribuční funkce s hodnotou distribuce. Levá konvergence k nim je definována pomocí hustot k k k podvzorců. Hlavním výsledkem je věta o kompaktnosti, která uvádí, že každá posloupnost latinských čtverců rostoucích řádů má jako akumulační bod latinu. Dále ukazujeme (prostřednictvím posledních výsledků Keevashových na kombinačních návrzích), že prostor latinů je minimální, že každý latinský jazyk lze aproximovat latinskými čtverci. Představujeme také vhodnou verzi řezu na vzdálenost a dokážeme protějšky počítání lemmatu, vzorkování lemmatu a inverzní počítání lemmatu. Jedná se o společnou práci s Frederikem Garbem, Janem Hladkým a Maryamem Sharifzadehem.

Martin Koutecký (Univerzita Karlova v Praze): Presburger se setká s Cambridge Analytica

Pondělí 2. prosince, 14:00, místnost C417

Cambridge Analytica je neslavná a nyní bankrotující (ale určitě přežít) společnost, která pomohla zmanipulovat volby po celém světě (včetně kampaní Brexit a Trump) prostřednictvím cílené reklamy na sociálních sítích. Chceme analyzovat takové úkoly a události z pohledu výpočetní složitosti a kladou otázky jako: co je nejlevnější úplatkářství, díky kterému můj kandidát vyhraje? Co když v základní sociální síti dochází k šíření názorů? Co když k manipulaci dochází současně více agenty? Odpověď na tyto otázky je užitečná nejen pro potenciálního úplatku, ale také pro pozorovatele, kteří chtějí odhalit úplatky nebo mít smysluplná opatření (překvapivě nepolapitelný) pojem vítězství.

Presburgerova aritmetika (PrA) je teorie prvního řádu přirozených čísel s přídavkem, pojmenovaná na počest Mojžíze Presburgera, který ji představil v roce 1929 a prokázal její rozhodnutelnost. Zatímco otázky položené výše jsou obecně těžké, ukazujeme, že když je počet typů voličů malý (obvykle, když je počet kandidátů malý), problémy mohou být formulovány jako modelová kontrola krátkých vět PrA a již Presburgerův důkaz dává algoritmus s nastavitelným sledovatelným parametrem. V této přednášce představím Cooperův algoritmus ze 70. let, který je rychlejší než Presburgerův původní postup. Stále zůstává mnoho zajímavých otázek.

Yanitsa Pehova (University of Warwick): Těsné balení Hamitonových cyklů v bipartitních digrafech

Pondělí 16. prosince, 14:00, místnost C417

V roce 1981 Jackson ukázal, že přímý bipartitní turnaj (kompletní bipartitní graf, jehož okraje jsou orientovány tak, že každý vrchol má stejný in- a outdegree), obsahuje Hamiltonův cyklus a předpokládá se, že ve skutečnosti může být okrajová sada rozdělena do Hamiltonu cykly. Prokazujeme přibližnou verzi této domněnky: Pro každý c> 1/2 a ε> 0 existuje n ₀ tak, že každý cn-pravidelný bipartitní digraf na 2n ≥ n ₀ vrcholech obsahuje (1-ε) cn edge-disjoint Hamiltonovy cykly . Toto je společná práce s Anitou Liebenau (UNSW).