Студентски семинар, 25. октобар 2024.
- 23. Октобар, 2024
- Коментари (0)
Наредни састанак Семинара биће одржан у петак, 25. октобра 2024. године у сали 301ф Математичког института САНУ са почетком у 12 часова.
Предавач: Алекса Џуклевски, Природно-математички факултет, Нови Сад
Наслов предавања: ЕРДОС-СЕКЕРЕШ MAKER-BREAKER ИГРЕ
Апстракт:
Ердос-Секереш Макер-Breaker игра је игра у којој два играча наизменично постављају тачке у равни тако да никоје три нису колинеарне. Први играч (Maker) почиње игру постављањем тачке и има за циљ да се у равни у неком тренутку појави конвексан k-тоугао (за дато, фиксно, k) у чијој унутрашњости се не налазе друге тачке (у даљем k-рупа) док други играч има за циљ да се то никада не деси. Das и Valla су показали да за свако к <= 8 Макер има победничку стратегију. Унапређујући овај резултат, показујемо да Maker има победничку стратегију за сваки природан број k.
Такође разматрамо небалансирану игру, у којој Breaker може да стави s тачака у сваком потезу и показујемо да Maker и даље има победничку стратегију за све природне k и реалне s. Једна варијација ове игре која је разматрана у литератури је бихроматска верзија, у којој играчи играју тачке које су различитих боја и у којој је сада Maker-ов циљ да конструише k-рупу чија су темена тачке његове боје. У бихроматској верзији показујемо да Maker и даље има победничку стратегију докле год је предност Breakera мања од 2 тачке по потезу и показујемо да за свако k >= 8 и предност од бар 12 тачака по потезу, Breaker има победничку стратегију. Такође показујемо да у двопотезној игри (прво Maker постави неки скуп тачака па онда Breaker и игра се завршава) Breaker има победничку стратегију ако има предност од бар 2 тачке за сваку Makerovu, док користећи густинску Хејлс-Џует теорему показујемо да Maker побеђује ако има предност која је већа од једне тачке по потезу.
На предавању ће бити представљени докази прве и последње теореме, док ће већина главних идеја (ако не и они сами) осталих доказа такође бити представљена.
Ово је заједнички рад са: Alexey Pokrovskiy, Csaba D. Toth, Tomaš Valla i Lander Verlinde.
Напомена: Предавања се могу пратити на даљину преко линка:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj
Регистрациона форма је доступна на:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73
Коментари(0)