This is an old revision of the document!
Table of Contents
2021 Session 6 : Positional games on sparse/random graphs
We play positional games on edge sets of graphs, two players alternately claim unclaimed edges of a given graph until all the edges are claimed. There are several variants of positional games:
- In a Maker-Breaker game Maker wants to achieve a graph property (fixed in advance, say “having a triangle”) on the graph she claimed. Breaker wants to prevent her from doing that.
- In an Avoider-Enforcer game, Enforcer wins if Avoider has the property on her graph, and Avoider wins otherwise.
- Etc.
Generally, given a game (i.e. given a base graph, a target graph property, and a variant of positional game) we want to figure out which player has a winning strategy. (It is known that one player must have a winning strategy.)
- If the game is played on a random graph, we study the probability for a player to win.
- Given a graph property, we may ask what's the smallest graph density on which a player can win.
- Etc.
We can choose a more focused topic, depending on the interest. In any case, there is a number of open problems to work on.
Workshop dates
13-17 September 2021
Confirmed participants
- Mirjana Mikalački (organiser)
- Miloš Stojaković (organiser)
Registration details: closed August 29th.
Open problems
Submission details: Send them by email to the organizers.
Submission deadline: Friday September 10th, 2021 (AoE)
Schedule
1. Monday * 10:00 (CET) Tutorial on Positional Games (The tutorial is meant for those who would like to brush up their knowledge on positional games.) * 14:00 (CET) Open Problem Session 2. Tuesday - Friday * Work in groups.