Sparse Graphs Coalition

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.

13-17 September 2021

• Mirjana Mikalački (organiser)
• Miloš Stojaković (organiser)

Registration details: tbc

Submission details: tbc

Submission deadline: tbc

A couple of introductory talks, an open problem session, work in groups (duration depending on enthusiasm).

1. Monday, 13 September
  9h45 - Introduction
2. Tuesday, 14 September
3. Wednesday, 15 September
4. Thursday, 16 September
5. Friday, 17 September

(All the times should be read Central European Summer Time, i.e. UTC+2).