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.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.329-334, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184443
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:59:09
Dernière modification le : jeudi 11 mai 2017 - 01:02:52
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:13:04

Fichier

dmAE0164.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184443, version 1

Collections

Citation

Martin Marciniszyn, Dieter Mitsche, Miloš Stojaković. Balanced Avoidance Games on Random Graphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.329-334, 2005, DMTCS Proceedings. 〈hal-01184443〉

Partager

Métriques

Consultations de la notice

442

Téléchargements de fichiers

79