User Tools

Site Tools


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), University of Novi Sad
  • Miloš Stojaković (organiser), University of Novi Sad
  • Grzegorz Adamski, Adam Mickiewicz University Poznan
  • Małgorzata Bednarska-Bzdęga, Adam Mickiewicz University Poznan
  • Dennis Clemens, TU Hamburg
  • Vojtech Dvorak, University of Cambridge, UK
  • Asaf Ferber, University of California Irvine
  • Jovana Forcan, University of Novi Sad
  • Pranshu Gupta, TU Hamburg
  • Fabian Hamann, TU Hamburg
  • Michael Krivelevich, Tel Aviv University
  • Ander Lamaison, Masaryk University in Brno
  • Thomas Lesgourges, UNSW Sydney
  • Anita Liebenau, UNSW Sydney
  • Allan Lo, University of Birmingham, UK
  • Tomasz Łuczak, Adam Mickiewicz University Poznan
  • Yannick Mogge, TU Hamburg
  • Tobias Müller, Groningen University
  • Nacim Oijid, LIRIS, Université Lyon 1
  • Amedeo Sgueglia, London School of Economics
  • Jelena Stratijev, University of Novi Sad
  • Tuan Tran, IBS Daejeon Korea
  • Marcin Witkowski, Adam Mickiewicz University Poznan

Registration details: closed August 29th.

Open problems

Submission details: Send them by email to the organizers.

Submission deadline: Friday September 10th, 2021 (AoE)


1. Monday
  * 10:00 (CET) Miloš Stojaković: 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.

Zoom link to tutorial:

Research results

sessions/2021sessions/2021session6.txt · Last modified: 2022/02/10 12:45 by ross.kang