In a strong game played on the edge set of a graph $G$ there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of $G$ (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique $K_k$, a perfect matching, a Hamilton cycle, etc.). In this paper we consider strong games played on the edge set of a random graph $G\sim G(n,p)$ on $n$ vertices. We prove that $G\sim G(n,p)$ is typically such that Red can win the perfect matching game played on $E(G)$, provided that $p\in(0,1)$ is a fixed constant.
@article{10_37236_5414,
author = {Asaf Ferber and Pascal Pfister},
title = {Strong games played on random graphs},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {1},
doi = {10.37236/5414},
zbl = {1355.05169},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5414/}
}
TY - JOUR
AU - Asaf Ferber
AU - Pascal Pfister
TI - Strong games played on random graphs
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/5414/
DO - 10.37236/5414
ID - 10_37236_5414
ER -
%0 Journal Article
%A Asaf Ferber
%A Pascal Pfister
%T Strong games played on random graphs
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/5414/
%R 10.37236/5414
%F 10_37236_5414
Asaf Ferber; Pascal Pfister. Strong games played on random graphs. The electronic journal of combinatorics, Tome 24 (2017) no. 1. doi: 10.37236/5414
