Strong games played on random graphs (Q510354)

Summary: 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~ 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.