Martin Marciniszyn ; Dieter Mitsche ; Miloš Stojaković
-
Balanced Avoidance Games on Random Graphs
dmtcs:3454 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3454
Balanced Avoidance Games on Random Graphs
Authors: Martin Marciniszyn 1; Dieter Mitsche 1; Miloš Stojaković 1
NULL##NULL##NULL
Martin Marciniszyn;Dieter Mitsche;Miloš Stojaković
1 Institute of Theoretical Computer Science [Zurich]
We introduce and study balanced online graph avoidance games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with $n$ vertices are revealed two at a time in a random order. In each move, Painter immediately and irrevocably decides on a balanced coloring of the new edge pair: either the first edge is colored red and the second one blue or vice versa. His goal is to avoid a monochromatic copy of a given fixed graph $H$ in both colors for as long as possible. The game ends as soon as the first monochromatic copy of $H$ has appeared. We show that the duration of the game is determined by a threshold function $m_H = m_H(n)$. More precisely, Painter will asymptotically almost surely (a.a.s.) lose the game after $m = \omega (m_H)$ edge pairs in the process. On the other hand, there is an essentially optimal strategy, that is, if the game lasts for $m = o(m_H)$ moves, then Painter will a.a.s. successfully avoid monochromatic copies of H using this strategy. Our attempt is to determine the threshold function for certain graph-theoretic structures, e.g., cycles.