Naredni sastanak Seminara biće održan u petak, 25. oktobra 2024. godine u sali 301f Matematičkog instituta SANU sa početkom u 12 časova.
Predavač: Aleksa Džuklevski, Prirodno-matematički fakultet, Novi Sad
Naslov predavanja: ERDOS-SEKEREŠ MAKER-BREAKER IGRE
Apstrakt:
Erdos-Sekereš Maker-Breaker igra je igra u kojoj dva igrača naizmenično postavljaju tačke u ravni tako da nikoje tri nisu kolinearne. Prvi igrač (Maker) počinje igru postavljanjem tačke i ima za cilj da se u ravni u nekom trenutku pojavi konveksan k-tougao (za dato, fiksno, k) u čijoj unutrašnjosti se ne nalaze druge tačke (u daljem k-rupa) dok drugi igrač ima za cilj da se to nikada ne desi. Das i Valla su pokazali da za svako k <= 8 Maker ima pobedničku strategiju. Unapređujući ovaj rezultat, pokazujemo da Maker ima pobedničku strategiju za svaki prirodan broj k.
Takođe razmatramo nebalansiranu igru, u kojoj Breaker može da stavi s tačaka u svakom potezu i pokazujemo da Maker i dalje ima pobedničku strategiju za sve prirodne k i realne s. Jedna varijacija ove igre koja je razmatrana u literaturi je bihromatska verzija, u kojoj igrači igraju tačke koje su različitih boja i u kojoj je sada Maker-ov cilj da konstruiše k-rupu čija su temena tačke njegove boje. U bihromatskoj verziji pokazujemo da Maker i dalje ima pobedničku strategiju dokle god je prednost Breakera manja od 2 tačke po potezu i pokazujemo da za svako k >= 8 i prednost od bar 12 tačaka po potezu, Breaker ima pobedničku strategiju. Takođe pokazujemo da u dvopoteznoj igri (prvo Maker postavi neki skup tačaka pa onda Breaker i igra se završava) Breaker ima pobedničku strategiju ako ima prednost od bar 2 tačke za svaku Makerovu, dok koristeći gustinsku Hejls-Džuet teoremu pokazujemo da Maker pobeđuje ako ima prednost koja je veća od jedne tačke po potezu.
Na predavanju će biti predstavljeni dokazi prve i poslednje teoreme, dok će većina glavnih ideja (ako ne i oni sami) ostalih dokaza takođe biti predstavljena.
Ovo je zajednički rad sa: Alexey Pokrovskiy, Csaba D. Toth, Tomaš Valla i Lander Verlinde.
Napomena: Predavanja se mogu pratiti na daljinu preko linka:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj
Registraciona forma je dostupna na:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73
