Skip to Main content Skip to Navigation
New interface
Conference papers

Balanced Avoidance Games on Random Graphs

Abstract : 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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184443
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:59:09 PM
Last modification on : Thursday, May 27, 2021 - 1:54:05 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:13:04 AM

File

dmAE0164.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Martin Marciniszyn, Dieter Mitsche, Miloš Stojaković. Balanced Avoidance Games on Random Graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.329-334, ⟨10.46298/dmtcs.3454⟩. ⟨hal-01184443⟩

Share

Metrics

Record views

108

Files downloads

360