% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{}{}{} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need \usepackage{enumitem} \setlist{itemsep=5pt,parsep=0pt,topsep=4pt,partopsep=0pt,leftmargin=30pt} % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Strong games played on random graphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Asaf Ferber\\ \small Department of Mathematics\\[-0.8ex] \small Massachusetts Institute of Technology\\[-0.8ex] \small Cambridge, U.S.A.\\ \small\tt ferbera@mit.edu\\ \and Pascal Pfister\\ \small Institute of Theoretical Computer Science\\[-0.8ex] \small ETH Z\"urich\\[-0.8ex] \small Z\"urich, Switzerland\\ \small\tt ppfister@inf.ethz.ch } \date{\dateline{Jul 16, 2015}{Jan 17, 2017}{}\\ \small Mathematics Subject Classifications: 05C57} \begin{document} \maketitle \begin{abstract} 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. % keywords are optional \bigskip\noindent \textbf{Keywords:} positional games, perfect matching, random graphs \end{abstract} \section{Introduction} \emph{Strong games}, as a specific type of \emph{Positional games}, involve two players alternately claiming unoccupied elements of a set $X$, which is referred to as the \emph{board} of the game. The two players are called \emph{Red} (the first player) and \emph {Blue} (the second player). The focus of Red's and Blue's attention is a given family $\mathcal{H} \subseteq 2^X$ of subsets of $X$, called the \emph{hypergraph of the game}, or sometimes referred to as the \emph{winning sets of the game}. The course of the game is that Red and Blue take turns in claiming previously unclaimed elements of $X$, \emph{exactly one} element each time, with Red starting the game. The winner of such a strong game $(X, \mathcal{H})$ is the first player to claim all elements of some winning set $F \in \mathcal{H}$. If this has not happened until the end of the game, i.e. until all elements of $X$ have been claimed by either Red or Blue, the game is declared a \emph{draw}. One classical example of a strong game is the child game Tic-Tac-Toe and its close relative $n$-in-a-row, where the target sets are horizontal, vertical and diagonal lines of a square grid. The player completing a whole line first wins. If at the end of the game no line has been completely claimed by either of the players, then the game is declared a draw. Another interesting example is the following generalization of Tic-Tac-Toe -- the $[n]^d$ game. Here, the board is the $d$-dimensional discrete cube $X=[n]^d$, and the winning sets are all the \emph{combinatorial lines} in $X$. Note that, in this notation, the $[3]^2$ game is the familiar Tic-Tac-Toe. It is also natural to play Positional games on the edge set of a graph $G=(V,E)$. In this case, $X=E$ and the target sets are all the edge sets of subgraphs of $G$ which possess some given graph property $\mathcal P$, such as `being connected', `containing a perfect matching', `admitting a Hamilton cycle', `being not $k$-colorable', `containing an isomorphic copy of a given graph $H$' etc. Since a strong game is a finite, perfect information game (as all of the Positional games), a well known fact from Game Theory asserts that, assuming the two players play according to their optimal strategies, the game outcome is determined and it can be in principle: win of Red, win of Blue, or a draw. In reality however, there are only two possible outcomes for this kind of games (assuming optimal strategies). Applying the so-called \emph{strategy stealing principle}, which was observed by John Nash in 1949, it follows that the first player (Red) cannot lose the game, if she plays according to her optimal strategy. Hence any strong game, if Red and Blue play according to their optimal strategies, is either \emph{Red's win} or ends in a draw. On one hand, this argument sounds (and indeed is) very general and powerful, but on the other hand, the strategy stealing argument is very inexplicit and gives no clue for how such an optimal strategy for Red looks like. Another general tool in the theory of strong games are Ramsey-type arguments. They assert that if a hypergraph $\mathcal{H} \subseteq 2^X$ is non-2-colorable (that is, in every colouring of the elements of the board $X$ with two colors, there must exist a monochromatic $F\in \mathcal{H}$), then Red has a winning strategy in the strong game $(X, \mathcal{H})$. The most striking example of an application of this method is probably for the above mentioned $[n]^d$ game. Hales and Jewett, in one of the cornerstone papers of modern Ramsey theory \cite{HJ}, proved that for a given $n$ and a large enough $d\ge d_0(n)$, every 2-colouring of $[n]^d$ contains a monochromatic combinatorial line. Thus, the strong game played on such a board cannot end in a draw and is hence Red's win (but again, no clue how a winning strategy looks like!). Regretfully, the above two main tools (strategy stealing, Ramsey-type arguments) exhaust our set of general tools available to handle strong games. In addition, both tools are inexplicit, and Ramsey-type statements frequently provide astronomic bounds. The inherent difficulty in analysing strong games can be explained partially by the fact that they are not hypergraph monotone. By this we mean the existence of examples, e.g. provided by J\'ozsef Beck, (Ch. 9.4 of \cite{jozsef2009inevitable}), of game hypergraphs $\mathcal{H}$ which are Red's win, yet one can add an extra set $A$ to $\mathcal{H}$ to obtain a new hypergraph $\mathcal{H}'$ which is a draw. This is what Beck calls the \emph{extra set paradox}, and it is indeed quite disturbing. Partly due to the great difficulty of studying strong games, \emph{weak games}, also known as \emph{Maker-Breaker games,} were introduced. In the \emph{Maker-Breaker game} $(X,\mathcal{H})$, two players, called Maker and Breaker, take turns in claiming previously unclaimed elements of $X$, with Breaker going first. Each player claims exactly one element of $X$ per turn. Again, the set $X$ is called the \emph{board} of the game and the members of $\mathcal{H}$ are referred to as the \emph{winning sets}. Maker wins the game as soon as she occupies all elements of some winning set $F\in \mathcal{H}$. If Maker does not fully occupy any winning set by the time every board element is claimed by some player, then Breaker wins the game. Note that being the first player is never a disadvantage in a Maker-Breaker game (see e.g. \cite{beck2008combinatorial}). Hence, in order to prove that Maker can win some Maker-Breaker game as the first or second player, it suffices to prove that she can win this game as the second player. Using fast strategies for Maker-Breaker games (see \cite{hefetz2009fast}), some (perhaps surprising) results about particular strong games played on the edge set of a complete graph $K_n$ have been obtained recently. The few examples of such strong games for which an explicit winning strategy, based on a fast Maker-Breaker strategy, is known, include the \emph{perfect matching} game, the \emph{Hamilton cycle} game and the \emph{k-vertex-connectivity} game (see \cite{ferber2011winning}, \cite{ferber2014weak}), where Red's aim is to build a perfect matching, a Hamilton cycle, and a $k$-vertex-connected spanning subgraph of a complete graph $K_n$, respectively. Since the problem of finding explicit winning strategies for Red is quite hard, and since there are no general tools for it, it is just natural to continue exploring such strategies on different type of boards. Hopefully, at some point in the near future a general tool will appear. A very natural candidate to begin with is the well known binomial random graph $G\sim G(n,p)$, where each edge of the complete graph $K_n$ is being kept with probability $p$, independently at random (for a very good survey on random graphs the reader is referred to the excellent book \cite{bollobas2001random}). In this paper we initiate the study of strong games played on the edge set of a typical $G\sim G(n,p)$. In particular, we analyse the \emph{perfect matching} game played on $G$ and provide Red with an explicit winning strategy (though a bit complicated). Here is our main result: \begin{theorem} \label{thm:perfect_matching} Let $p\in (0,1)$ be a fixed constant. Then, a graph $G \sim G(n,p)$ is w.h.p.\ (with high probability, meaning with probability going to $1$ as $n$ tends to infinity) such that Red has a winning strategy for the perfect matching game played on $E(G)$. \end{theorem} \subsection{Notation and terminology} Our graph-theoretic notation is standard and follows that of \cite{west2001introduction}. In particular, we use the following. For a graph $G$, let $V(G)$ and $E(G)$ denote its sets of vertices and edges respectively. Moreover, let $e(G) := |E(G)|$ be the number of edges of $G$ and, for any two disjoint subset $S,T \subset V(G)$ let $e(S,T)$ be the number of edges with one endpoint in $S$ and the other in $T$ (this set is denoted by $E(S,T)$). For a set $S\subseteq V(G)$, let $G[S]$ denote the subgraph of $G$, induced on the vertices of S. Assume that some strong game, played on the edge set of some graph $G$, is in progress. At any given moment during this game, we denote the graph spanned by Red's edges by $R$, and the graph spanned by Blue's edges by $B$. We furthermore denote by $d_{R}(v)$ and $d_{B}(v)$ the degree of a given vertex $v\in V(G)$ in $R$ and in $B$ respectively. For a set $S\subseteq V(G)$, let $R[S]$ and $B[S]$ denote the subgraph of $R$ and of $B$ induced by the vertices of $S$. Moreover, we denote by $d_{R[S]}(v)$ and $d_{B[S]}(v)$ the degree of a given vertex $v \in S$ in the induced subgraph $R[S]$ and in $B[S]$ respectively. At any point during the game, the vertices of $G\setminus(R\cup B)$ are called \emph{free vertices} and any edge not yet claimed is called a \emph{free edge}. Moreover, any vertex $v \in V$ with $d_R(v)=0$ and $d_B(v) >0$ is called \emph{distinct}. \subsection{Proof outline} The main idea of our proof is to show the following two things: on the one hand, Red can build a perfect matching `fast', i.e. by claiming not much more edges than needed for a perfect matching. On the other hand, we need to make sure that Blue cannot build a perfect matching faster than Red. These two things than assure that the strong perfect matching game on $G \sim G(n,p)$ is Red's win. For the first goal, the basic tool of our proof is to partition the graph $G \sim G(n,p)$ into small, disjoint cliques of even size, and then play on each of these `subboards' separately. Since the strong perfect matching game is a fast win for Red on a clique (see \cite{ferber2011winning}), Red will eventually build a perfect matching on all subboards and therewith also on the entire graph $G$. In general, Red tries to build a perfect matching in each subboard consecutively. If, theoretically, Blue would play along and always play in the same subboard as Red, the strategy to win the strong perfect matching game on $K_n$ from \cite{ferber2011winning} would suffice to ensure Red's win. Unfortunately, Blue can claim whatever edges she likes, i.e. Blue can decide to not play in the same subboard as Red. Thus a main part of our proof is to slightly alter the strategy from \cite{ferber2011winning} and adapt it to our needs, hence producing different strategies Red can use on different subboards. For each subboard Red will choose her strategy separately, her choice depending only on the blue edges present in the subboard right before Red starts claiming edges in it. Red skips her `subboard by subboard approach only if Blue tries to isolate a vertex or claims to many edges in a subboard Red did not yet play on. In this case Red immediately reacts on Blue's last move and answers in the subboard Blue is `attacking'. The main idea to achieve the second goal is that Red needs to control the number of `wasted moves' which, roughly speaking, is the number of edges claimed by a player which do not bring her closer to a perfect matching. For example, if at some point Blue claims an edge touching an already touched vertex, then clearly she cannot finish her matching in $n/2$ moves, where $n$ is the number of vertices of the graph $G$. Thus, if Red can make sure at any point during the game that she did not `waste more moves' than Blue, she for sure wins the game, as every perfect matching is of the same size and since she started the game. Hence, the difficulty of Red's strategy will be to maintain this `advantage' on the number of `wasted moves'. To this end, note that Blue can essentially force Red to `waste' a move only once on each subboard, namely by blocking the last edge (say $uv$) Red needs to build a perfect matching. To circumvent such attacks, Red will create a `trap' for Blue on every subboard. For every subboard it holds that, if Blue touches at some point a vertex $v$ which is isolated in Red's graph, then Red can keep this vertex $v$ isolated until she needs to claim only one edge $uv$ to build a perfect matching (on this subboard). Then, as every time that Blue claims an edge touching this vertex $v$ again, Blue postpones her win by another step. This is true especially whenever Blue blocks Red's last edge $uv$, and thus in this case Red gets some spare moves to continue and eventually build her perfect matching on this subboard. If however Blue did not create such a `trap vertex' and nevertheless blocks the last edge $uv$ of Red's perfect matching on a certain subboard, Red applies the following trick: she `imports' two vertices $x$ and $y$ from the next subboard, hence giving her the opportunity to claim another free and independent edge in this subboard, e.g. $ux$, and in the same time ensuring that Blue created a `trap vertex', namely $v$. So that Red is always able to do this `importing', we need to refine our partitioning of the vertex set and make sure that such two vertices $x$ and $y$ always exist. This is achieved by showing that we can partition the vertex set not only into disjoint cliques of small, even size, but also arrange them in a ordering such that all edges between any two consecutive cliques are present as well. \medskip The rest of the paper is structured as follows: the partitioning of the graph $G \sim G(n,p)$ into small, disjoint subboards of even size is derived in Theorem \ref{thm:auxiliary} and Lemma \ref{partitioning_lemma} in section \ref{sec:partition}. In section \ref{sec: PM game on Kn} we describe a slightly altered strategy to play the strong perfect matching game on a subclique of a graph (see Lemma \ref{lemma:strategy_strong}). This strategy is then the key ingredient used to describe the different substrategies Red will choose from to play on each subboard of the partitioned graph. These substrategies are described in detail in section \ref{sec:substrategies}. The proof of Theorem \ref{thm:perfect_matching} can be found in section \ref{sec: proof}, where we describe Red's winning strategy (using the aforementioned substrategies) and prove that Red can indeed follow it. \section{Preliminaries and tools} In this section we introduce some tools used in the proof of Theorem \ref{thm:perfect_matching}. \subsection{Partitioning of $G \sim G(n,p)$}\label{sec:partition} We first show the following auxiliary theorem and a partitioning lemma for a graph $G \sim G(n,p)$ which will allow Red to partition the board $E(G)$ into suitable subboards. \begin{theorem} \label{thm:auxiliary} Let $n$ be a sufficiently large integer and let $0 1$ holds immediately after Blue's $(n/4+2)$nd move, then Red skips to Stage M. Otherwise, for every $n/4 + 3 \leq j \leq n/2-1$, in her $j$th move Red claims an edge $e_j \in E(G[U])$ which is independent of her previously claimed edges while making sure that $D_j \leq 1$. Red then proceeds to Stage III. \medskip \textbf{Stage III:} Red completes her perfect matching in $E(H)$ by claiming at most 3 additional edges as follows: Let $u,v \in V(H)$ be the two last vertices Red needs to connect to build a perfect matching on $E(H)$ and w.l.o.g. let $u$ be the designated trap vertex, resp. the $V(H)$-distinct vertex. In her $(n/2)$nd move, Red claims $uv$ and finishes her perfect matching in $E(H)$. If this is not possible, let $xy$ and $wz$ be two red edges such that $B[\lbrace u, v, w, z, x, y \rbrace]$ consists solely of the edge $uv$. In her $(n/2)$nd move Red claims the edge $vy$. In her $(n/2+1)$st move, Red claims the edge $ux$ and thus finishes her perfect matching in $E(H)$. If this is not possible, Red claims the edge $uz$. Since Blue cannot claim both $xw$ and $vw$ in her next move, Red claims one of them in her $(n/2+2)$nd move and thus finishes her perfect matching in $E(H)$. \medskip \textbf{Stage M:} Let $I_H := \lbrace v \in V(H) \ : d_{R[V(H)]}(v)=0 \rbrace$ be the set of isolated vertices of Red in $V(H)$. Note that $|I_H|=n/2-4$ is even. Playing on $E(G[I_H])$, Red follows the strategy $\mathcal{S}^{weak}_{n/2 -4}$. \medskip It remains to prove that Red can indeed follow all parts of the strategy. We will now prove inductively that Red can follow Stage II of her strategy (either for $n/4 +2$ or $n/2-1$ moves). Observe that for both cases in Stage I we have that $D_1 \leq 1$, and thus the induction basis is fulfilled. Additionally, note that, since Blue can create at most two $V(H)$-distinct vertices in one round, we have that $D'_{j+1} - D_j \leq 2$. We distinguish now two cases: \begin{description} \item[Case 1:] $D_j = 1$.\\ If $D'_{j+1} = 1$, let $u \in V(H)$ be the $V(H)$-distinct vertex with $d_{B[V(H)]}(u) \geq 1$ and $d_{R[V(H)]}(u)=0$. Then Red claims any free edge $xy \in E(G[V(H) \setminus \lbrace u \rbrace])$ which is independent of all her previously claimed edges in $E(H)$ and hence $D_j=D_{j+1}=1$.\\ Else, if $D'_{j+1} = 2$, let $u \neq w \in V(H)$ be the two $V(H)$-distinct vertices. Then Red claims an arbitrary free edge $wx$ with $x \neq u$ in $E(H)$ which is independent of all her previously claimed edges and hence $D_j=D_{j+1}=1$.\\ Else, if $D'_{j+1} = 3$, let $u \neq w \neq z \in V(H)$ be the three $V(H)$-distinct vertices. Then w.l.o.g. let $wz$ be the edge Blue claimed in her last move. This means that $uw$ and $uz$ are still free, since there was only one $V(H)$-distinct vertex before Blue's move. Hence Red claims one of them, thus ensuring that $D_j=D_{j+1}=1$. \item[Case 2:] $D_j = 0$.\\ If $D'_{j+1} = 0$, then Red claims any free edge $uv \in E(G[U])$ (note that this is the only case where the auxiliary vertex-set $U$ is not equal to $V(H)$), which is independent of all her previously claimed edges in $E(H)$ and hence $D_j=D_{j+1}=0$.\\ Else, if $D'_{j+1} = 1$, let $u \in V(H)$ be the $V(H)$-distinct vertex. Then Red claims an arbitrary free edge $xy \in E(G[V(H) \setminus \lbrace u \rbrace])$ which is independent of all her previously claimed edges in $E(H)$ and hence $D_{j+1}=1$.\\ Else, if $D'_{j+1} = 2$, let $u \neq w \in V(H)$ be the two $V(H)$-distinct vertices. Then Red claims an arbitrary free edge $wx$ with $x \neq u$ in $E(H)$ which is independent of all her previously claimed edges and hence $D_{j+1}=1$. \end{description} Note that with keeping $D_j \leq 1$, Red ensures that there are always enough vertices $v \in V(H)$ with $d_{B[V(H)]}(v)=d_{R[V(H)]}(v)=0$. Therefore those independent edges which Red claims always exist. Thus, Red can follow Stage II of her strategy. Whenever Red reaches Stage III, the above induction ensures that Red's graph consists of a matching with $n/2 - 1$ edges and additionally $D_{n/2-1} \leq 1$. Thus, if $uv$ is the last edge Red needs to finish her perfect matching on $E(H)$, we can w.l.o.g. assume that $d_{B[H]}(v) =0$. Hence, since $\Delta(B[V(H)]) \leq n/4-3$, and therefore Blue cannot have connected $u$ to more than $n/4-3$ edges of Red's matching, such two red edges $xy$ and $wz$ will always exist. Therewith, when Stage III is completed, Red built a perfect matching in $E(H)$ in at most $n/2+2$ moves. Additionally, it holds that $0 = w_{R[V(H)]} \leq w_{B[V(H)]}$ for the first $n/2 - 1$ moves, thus it remains to argue what happens to the number of wasted moves when Red needs $n/2 +1$ or $n/2 +2$ moves to build her perfect matching. We distinguish two cases: first, consider the case when $D_{n/2-1} = 1$. Then $d_{B[V(H)]}(u) \geq 1$ before Red's $(n/2)$th move. Thus, if Blue claims $uv$ (resp. $ux$) we have that $w_{B[V(H)]} \geq 1 = w_{R[V(H)]} $ (resp. $w_{B[V(H)]} \geq 2 = w_{R[V(H)]}$). Else, $D_{n/2-1} = 0$, which means that there never existed a $V(H)$-distinct vertex during the game. Thus, $u$ is the designated trap vertex from Stage I. Then, if Blue claims $uv$ (resp. $ux$) we have that $d_{B[V(H)]}(u) = 1 = w_{R[V(H)]}$ (resp. $d_{B[V(H)]}(u) = 2 = w_{R[V(H)]}$). Thus, after Stage III we have that Red built a perfect matching in at most $n /2 +2$ moves and the statements from Lemma \ref{lemma:strategy_strong} are true. Whenever Red reaches Stage M, it holds that $\Delta (B[V(H)]) > 1$ and hence $w_{B[V(H)]} \geq 1$. Thus, Red can play according to Maker's strategy on $E(G[I_H])$, therewith increasing $w_{R[V(H)]}$ to 1, and complete her perfect matching in another $n/4 -1$ moves. Additionally, since $w_{R[V(H)]} = 0$ for the first $n/4+2$ moves, it holds that $w_{R[V(H)]}=1 \leq w_{B[V(H)]}$ at any point during the game. Thus, after Stage M we have that Red built a perfect matching in $n/2 +1$ moves, and the statements from Lemma \ref{lemma:strategy_strong} are true. \end{proof} Henceforth, the strategy described in the proof above will be denoted by $\mathcal{S}^{a.strong}_{n}$. It will be the key ingredient of the proof of Theorem \ref{thm:perfect_matching}. Before we start the proof of Theorem \ref{thm:perfect_matching}, let us make a last remark, which follows directly from the second last paragraph of the proof. \begin{remark}\label{remark: $D_j$ = 1} Whenever Red follows the strategy $\mathcal{S}^{a.strong}_{n}$, if there exists a $V(H)$-distinct vertex $u \in V(H)$ (that is, a vertex $u$ for which $d_{B[V(H)]}(u) \geq 1$ and $d_{R[V(H)]}(u)=0$) after Red's $(n/2 -1)$st move, then we know that $w_{R[V(H)]} \leq w_{B[V(H)]}$ is true at any time. %Or in other words, if there exists a $H$-distinct vertex $u \in V(H)$ at some point, then Red does not `waste more moves' than Blue while playing according to $\mathcal{S}^{a.strong}_n$. \end{remark} \section{Proof of Theorem \ref{thm:perfect_matching}} \label{sec: proof} %The main idea of Red's strategy is to build a perfect matching on $G \sim G(n,p)$ `quickly' while ensuring that $w_{R} \leq w_{B}$ stays true. To this end, Red partitions $V(G)$ into suitable, cyclically ordered subgraphs as obtained by applying Lemma \ref{partitioning_lemma} to $G$. In her strategy, Red then mostly neglects all the edges in between those `subboards' and plays on each subboard separately, trying to complete a perfect matching on each board in a cyclic order. The crucial observation here is that whenever Blue blocks the last edge Red needs for a perfect matching on a subboard, using the fact that the union of two consecutive subboards is a clique as well, Red can `import' two vertices from the next subboard to circumvent Blue's attack. Red is only being interrupted in this `subboard by subboard' approach if Blue tries to block a vertex or claims too many edges on a subboard which Red has not yet been playing on. Whenever a certain amount of edges in a specific subboard or edges incident with the same vertex is reached in Blue's graph, Red marks the relevant subboard as `dangerous' and gives this board a special attention. %\medskip For the description of Red's strategy to win the strong perfect matching game on a graph $G \sim G(n,p)$, we will use the following notation and definitions: Assume that the graph $G \sim G(n,p)$ is partitioned according to Lemma \ref{partitioning_lemma}. Hence we have a partition $V(G)=V_{1}\cup\ldots\cup V_{t}$ into $t$ disjoint subsets. For all $1 \leq i \leq t$, let $E_i := E(G[V_i])$ be the subboards Red will play on and define $m_i := |V_i|$. At any point during the game, let $R_i \subset R$ be the subgraph of Red's graph induced on $V_i$ and let $B_i \subset B$ be the subgraph of Blue's graph induced on $V_i$. For any vertex $v \in V_i$, we denote by $d_{B_i}(v)$ the degree of $v$ in this induced subgraph $B_i$. Moreover, we denote by $w_{B_i} := w_{B[V_i]}$, respectively $w_{R_i} := w_{R[V_i]}$, the number of wasted moves of Blue, respectively Red, on the subboard $E_i$. A subboard $E_i$ is called \emph{inactive} if $e(R_i) = 0$, it is called \emph{active} if $e(R_i) \geq 1$, but $R_i$ does not contain a perfect matching, and it is called \emph{safe} if $R_i$ contains a perfect matching. Additionally, if a subboard $E_i$ is inactive and $w_{B_i}$ turns 1, we call the subboard $E_i$ \emph{dangerous}. Every dangerous subboard stays dangerous until Red completed her perfect matching on it (at which point it becomes safe). \medskip The strategy which we describe below enables Red to build a perfect matching on $G \sim G(n,p)$ `quickly' while ensuring that $w_{R} \leq w_{B}$ stays true at all times. The main idea is that Red (mostly) neglects all the edges in between the subboards and plays on each subboard separately, with the aim to complete a perfect matching on each board while ensuring that $w_{R_i} \leq w_{B_i}$. Note that this condition can be interpreted and is sometimes referred to a as `Red does not waste more moves than Blue' on the subboard $E_i$. Whenever possible, Red will consider the subboards in cyclic order, meaning that she tries to complete her perfect matching on $E_i$ before claiming an edge on $E_{i+1}$. Observe, crucially, that Red ignores most of the blue edges in between the subboards (until the very end of the strategy) and counts the number of wasted moves of Blue `locally', that is, on every subboard separately. Otherwise, since we will use the degree of some specified vertices to give a lower bound on the number of wasted moves of Blue, it could happen that an edge $u_i u_j$ with $u_i \in V_i$ and $u_j \in V_j$ adds a `plus 1' to the number of wasted moves in two subboards. Another important observation is that the partition of $V(G)$ allows us to nullify the `natural' attack point of Blue, which is blocking the last edge Red needs for a perfect matching on a subboard $E_i$. Whenever Blue blocks such an edge, using the fact that the union of two consecutive subboards is a clique as well, Red `imports' two suitable vertices from $V_{i+1}$ to circumvent Blue's attack. %If this is not possible, Blue will have claimed most edges of $E(V_i, V:{i+1})$, therewith `wasting' lots of moves (recall that all edges between $V_i$ and $V_{i+1}$ are present). Red only interrupts this `subboard by subboard' approach if Blue tries to block a vertex or claims too many edges on an inactive subboard. Thus, when a subboard $E_i$ becomes dangerous, Red gives this board a special attention and, whenever Blue claims an edge in $E_i$, Red skips her `subboard by subboard' approach and answers on $E_i$ instead. The description of Red's strategy comes in two parts. First, we introduce the three substrategies called $\mathcal{S}_{dangerous}$, $\mathcal{S}_{trap}$ and $\mathcal{S}_{empty}$. These substrategies give Red three alternatives of how to play on the subboards $E_i$. For each subboard $E_i$ Red will decide to follow one of these three substrategies, depending on how Blue's graph $B_i$ looks like right before Red claims her first edge on $E_i$. % Roughly speaking, the aim of Red is to claim a perfect matching on $E_i$ in at most $n/2 + 4$ moves while ensuring that $w_{R_i} \leq w_{B_i}$. After introducing these substrategies, we describe the so called \emph{overall strategy}, and prove that Red can indeed follow this overall strategy. This strategy shows how Red actually plays the game on the edge set of the graph $G$, i.e. how Red chooses the substrategies for the subboards $E_i$. \medskip In the following, we introduce the three substrategies $\mathcal{S}_{trap}$, $\mathcal{S}_{dangerous}$ and $\mathcal{S}_{empty}$. Here we only describe under which conditions Red chooses a substrategy and what she can achieve by following it. The detailed description of each substrategy and the proofs that Red can indeed play according to these substrategies are postponed to Section \ref{sec:substrategies}. \medskip \noindent \textbf{\boldmath $\mathcal{S}_{trap}$:} The strategy $\mathcal{S}_{trap}$ is used on subboards $E_i$ where, right before Red claims her first edge on $E_i$, it holds that $e(B_i) \geq 1$ and $w_{B_i} = 0$. By following the strategy $\mathcal{S}_{trap}$, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves ensuring that $w_{R_i} \leq w_{B_i}$ at any time. \medskip \noindent \textbf{\boldmath $\mathcal{S}_{dangerous}$:} The strategy $\mathcal{S}_{dangerous}$ is used to play on subboards $E_i$ where, right before Red claims her first edge on $E_i$, it holds that $w_{B_i} = 1$. By following the strategy $\mathcal{S}_{dangerous}$, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves ensuring that $w_{R_i} < w_{B_i}$ at any time. \medskip \noindent \textbf{ \boldmath $\mathcal{S}_{empty}$:} The strategy $\mathcal{S}_{empty}$ is used to play on subboards $E_i$ where, right before Red claims her first edge on $E_i$, it holds that $e(B_i) = 0$. By following the strategy $\mathcal{S}_{empty}$, Red achieves the following: \begin{enumerate} \item[$P1$:] If there exists a $V_i$-distinct vertex $u \in V_i$ after Red's $(m_i /2 -1)$st move on $E_i$ or if $\Delta(B_i) >1$ before Red's $(m_i /4 + 3)$rd move on $E_i$, then $w_{R_i} \leq w_{B_i}$ at any time. \item[$P2$:] Else, if $E_{i+1}$ is (resp. was) dangerous, then $w_{R_i} + w_{R_{i+1}} \leq w_{B_i} + w_{B_{i+1}}$ at any time. \item[$P3$:] Else, $w_{R_i} + 2 < w_{B[V_i, V_{i+1}]} $ at any time, where we denote by $B[V_i, V_{i+1}]$ the bipartite graph consisting of all the blue edges between $V_i$ and $V_{i+1}$. \end{enumerate} Note that we need these three technical conditions $P1$, $P2$ and $P3$ since $w_{R_i} \leq w_{B_i}$ cannot be achieved on an `empty' subboard (Blue can decide only to play on $E_i$ to block the very last edge Red needs for a perfect matching, thus blocking Red without `wasting' a move). Thus, conditions $P2$ and $P3$ follow directly from Red's attempt to circumvent such an attack by `importing' two vertices from $V_{i+1}$ (details in Section \ref{subsec:empty}). \medskip Thus, assuming that these three substrategies exist, we can now describe the Overall Strategy and therewith prove Theorem \ref{thm:perfect_matching}. \begin{proof}[Proof of Theorem \ref{thm:perfect_matching}] First we propose a strategy for Red and then prove that the proposed strategy is indeed a winning strategy for the perfect matching game played on a typical $G\sim G(n,p)$. From now on, we condition on $G$ satisfying all the properties mentioned in the statements in Section \ref{sec:partition}. Hence let $V(G)=V_{1}\cup\ldots\cup V_{t}$ be the partition of $G\sim G(n,p)$ into $t$ disjoint subsets as described in Lemma \ref{partitioning_lemma}. \bigskip \noindent \textbf{Overall Strategy:} During the game, except for the first move, Red always reacts to Blue's last move. Hence, we consider one \emph{round} as one move of Blue and a countermove of Red (except for round 0, which only consists of the first move of Red). At any point during the game, if Red is unable to follow the proposed strategy or if Red claims more than $n/2 + 4t$ edges (where $t$ is the number of subboards obtained by partitioning $V(G)$), then she forfeits the game. As long as Red's graph does not contain a perfect matching, Red does the following: In her first move of the game Red claims an edge $ab \in E_1$ obtained by following $\mathcal{S}_{empty}$ on $E_1$. In any other move, let $e_j$ be the edge which has just been claimed by Blue in her $j$th move. First, Red checks whether for some $i\leq t$ we have $e_j \in E_i$ and $E_i$ is dangerous. If this is the case, Red answers according to the strategy $\mathcal{S}_{dangerous}$ on $E_i$. Otherwise, if there exists some active subboard, then Red chooses the smallest integer $i \leq t$ for which $E_i$ is active and plays on $E_i$ according to her chosen strategy $\mathcal{S}_i$ (it is described below how Red chooses the strategy $\mathcal{S}_i$ on each subboard $E_i$). Otherwise, there are no active subboards and Red's graph contains a perfect matching on the subboards $E_1,\dots,E_{k-1}$ for some $k \in [t]$. In this case Red wants to play on $E_k$ (which is not dangerous) according to the strategy $\mathcal{S}_k$, which she chooses in the following way: \begin{description} \item[Case 1:] $2 \leq k \leq t-1$.\\ If $e(B_k) \geq 1$, then Red defines $\mathcal{S}_k = \mathcal{S}_{trap}$. Else, $e(B_k) = 0$ and then Red defines $\mathcal{S}_k = \mathcal{S}_{empty}$. \item[Case 2:] $k=t$.\\ If $e(B_t) \geq 1$, then Red defines $\mathcal{S}_k = \mathcal{S}_{trap}$. Else, if $e(B_t) = 0$ and there exists a vertex $u \in V_t$ with $d_B(u) \geq 1$, then Red defines $\mathcal{S}_t = \mathcal{S}^{a.strong}_{m_t}$. However, if $e(B_t) = 0$ and $d_B(v) =0$ for all $v \in V_k$, we need to distinguish between the following two subcases: \begin{description} \item[Case 2.1:] Blue's graph does not contain a perfect matching of $G[V \setminus V_t]$. \\ Then Red plays according to the Maker-Breaker strategy $\mathcal{S}^{weak}_{m_t}$ on $E_t$. \item[Case 2.2:] Blue's graph contains a perfect matching of $G[V \setminus V_t]$. \\ Then Red claims an arbitrary edge $ab \in E_t$ in her first move on $E_t$. If Blue claims an edge $xy \in E_t$ in her first move on $E_t$, Red skips to Stage II of $\mathcal{S}^{a.strong}_{m_t}$ and finishes her perfect matching accordingly. Else, Red plays according to $\mathcal{S}^{weak}_{m_t-2}$ on $E(G[V_t \setminus\lbrace a,b \rbrace])$. \end{description} \end{description} It remains to prove that Red can indeed follow this Overall Strategy and that, by following it, Red can build a perfect matching on $E(G)$ in at most $n / 2 + 4t$ moves ensuring that $w_{R} \leq w_{B}$ at any time during the game. The Overall Strategy considers all possible cases since either Blue has already claimed an edge in $E_i$ or not when Red needs to choose how to play on $E_i$. Note that if $w_{B_i}$ turns 1, Red immediately sets $\mathcal{S}_i = \mathcal{S}_{dangerous}$ and answers on $E_i$. Thus, whenever Red can choose the strategy to play on $E_i$, it holds that $w_{B_i} = 0$. Therefore, whenever Red decides to play according to one of the three substrategies, the respective assumptions on the subboards are fulfilled. Therewith, observe that for all $1 \leq i \leq t$ Red can follow the overall strategy and play accordingly on every subboard. Moreover, Red needs to claim at most $m_i /2 +4$ edges to finish her perfect matching on every $E_i$. Hence, since $m_i$ is even for all $1 \leq i \leq t-1$ by Lemma \ref{partitioning_lemma}, she finishes her perfect matching on $E(G)$ in at most $n/2 + 4t$ moves. Thus it remains to show that Blue cannot claim a perfect matching on $E(G)$ before Red finishes her perfect matching. Whenever Red plays according to Case 2.1 on $E_t$, Red finishes the game in exactly $m_t / 2 +1$ moves (as Red's graph contains a perfect matching of $G[V \setminus V_t]$). But since Blue's graph does not contain a perfect matching of $G[V \setminus V_t]$ (and $e(B_t) = 0$), it follows that Blue cannot finish a perfect matching of $G$ in less than $m_t / 2 +1$ moves. Thus Red finishes her perfect matching before Blue does and hence wins the game. Whenever Red plays according to Case 2.2 on $E_t$, note that if Blue claims an edge $xy \in E_t$ after Red claimed $ab \in E_t$, then by symmetry we may assume that $d_{B_t}(x) = 1$ and $d_{R_t}(x) = 0$. Thus, when Red plays according to $\mathcal{S}^{a.strong}_{m_t}$, we have that there exists a $V_t$-distinct vertex, and therefore Remark \ref{remark: $D_j$ = 1} ensures that $w_{R_t} \leq w_{B_t}$ at any time. But this implies that Blue cannot build a perfect matching on $E_t$ faster than Red, thus Red wins the game. Else, if Blue does not claim an edge in $E_t$ after Red claimed $ab \in E_t$, We know that Blue's graph does not contain a perfect matching of $G[V \setminus (V_t \setminus \{a,b\})]$ (as $d_B(a) = d_B(b) = 0$ right before Red claimed $ab$). Thus the same argument as for Case 2.1 shows that Red wins the game. For all other scenarios, we will show that $w_R \leq w_B$ at any point during the game, and thus Blue cannot claim a perfect matching before Red does. To this end, first consider the case when Red plays according to $\mathcal{S}_{dangerous}$ or $\mathcal{S}_{trap}$ on $E_t$. Then, since Red plays according to one of the three substrategies on every subboard $E_i$, we have that $$w_R = \sum_{i=1}^{t} w_{R_i} \leq \sum_{i=1}^{t} w_{B_i} + \sum_{i=1}^{t-1} w_{B[V_i, V_{i+1}]} \leq w_B,$$ where the last inequality follows since $E_i$ and $E_{j}$, $E_i$ and $E(V_j, V_{j+1})$, as well as $E(V_i, V_{i+1})$ and $E(V_{j}, V_{j+1})$ are pairwise distinct for all $i,j \in [t]$. Therewith, the only remaining case is when $e(B_t) = 0$ but there exists a trap vertex $u \in V_t$ with $d_B(u) \geq 1$, right before Red claims her first edge on $E_t$. Note that $e(B_t) = 0$ means that $E_t$ is not dangerous. Hence, the case $P2$ from the strategy $\mathcal{S}_{empty}$ cannot occur on $E_{t-1}$ and therewith $w_{R_{t-1}} \leq w_{B_{t-1}}$ or $w_{R_{t-1}} +2 < w_{B[V_{t-1}, V_t]}$. Let us consider these two cases separately: if $w_{R_{t-1}} +2 < w_{B[V_{t-1}, V_t]}$, since $w_{R_t} \leq 2$ (Red plays according to $\mathcal{S}^{a.strong}_{m_t}$ on $E_t$), it holds that $w_{R_{t-1}} + w_{R_t} < w_{B[V_{t-1}, V_t]}$ (note that this is the only case where we need this `strange looking' additional +2 in the property $P3$). Thus $$w_R = \sum_{i=1}^{t} w_{R_i} \leq \sum_{i=1}^{t} w_{B_i} + \sum_{i=1}^{t-1} w_{B[V_i, V_{i+1}]} \leq w_B$$ at any time during the game. Else, if $w_{R_{t-1}} \leq w_{B_{t-1}}$, we have for the first $t-1$ subboards at any time that \begin{equation}\label{eq:wasted moves} \sum_{i=1}^{t-1} w_{R_i} \leq \sum_{i=1}^{t-1} w_{B_i} + \sum_{i=1}^{t-2} w_{B[V_i, V_{i+1}]}. \end{equation} Note that we did not consider blue edges incident to any vertex $v \in V_t$ to derive inequality (\ref{eq:wasted moves}) (as the second sum on the right side of the above inequality only sums up to $t-2$). Furthermore, as Red decides to play according to $\mathcal{S}^{a.strong}_{m_t}$ on $E_t$, Lemma \ref{lemma:strategy_strong} asserts us that either $w_{R_t} \leq w_{B_t}$ (in which case, together with inequality (\ref{eq:wasted moves}), we are done), or that $w_{R_t} = d_{B_t}(u)$. In the latter case, let $uv$ be an edge incident to $u$ in Blue's graph right before Red claimed her first edge on $E_t$. Hence, we have that $w_{R_t} \leq d_{B[V_t \cup \{v\}]}(u) -1 \leq w_{B[V_t \cup \{v\}]}$. Thus, since we did not consider blue edges in $E(v,V_t)$ to derive inequality (\ref{eq:wasted moves}), it follows that $w_R \leq w_B$, concluding the proof. \end{proof} \section{Substrategies}\label{sec:substrategies} In this section, we describe the three substrategies $\mathcal{S}_{trap}$, $\mathcal{S}_{dangerous}$ and $\mathcal{S}_{empty}$ in detail and prove that Red can indeed follow them. Note that these substrategies rely on $\mathcal{S}^{weak}_n$, which ensures that Maker can win the weak perfect matching game on $K_n$ in at most $n/2+1$ moves, and the strategy $\mathcal{S}^{a.strong}_n$, as described in the proof of Lemma \ref{lemma:strategy_strong}. \subsection{Substrategy $\mathcal{S}_{trap}$} \noindent \textbf{\boldmath $\mathcal{S}_{trap}$:} The strategy $\mathcal{S}_{trap}$ is used on subboards $E_i$ where, right before Red claims her first edge on $E_i$, it holds that $e(B_i) \geq 1$ and $w_{B_i} = 0$. Thus Blue's graph consists of 1 up to $m_i / 2$ independent edges. The main idea of Red is to `dissect' all but at most one of Blue's edges and thus split the board $E_i$ into two `halves', since then Red can use the strategy $\mathcal{S}^{a.strong}_n$ on both `halves'. In what follows we propose a strategy and then prove that, by following it, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves ensuring that $w_{R_i} \leq w_{B_i}$ at any time. The strategy $\mathcal{S}_{trap}$ can be divided into the following two cases: \begin{description} \item[Case 1:] $e(B_i) = 1$.\\ Then Red plays according to $\mathcal{S}^{a.strong}_{m_i}$ on $E_i$. \item[Case 2:] $e(B_i) > 1$.\\ Then, Red partitions the vertex set $V_i=U_{i,1} \cup U_{i,2}$ into two subsets, such that \begin{enumerate} \item[$(i)$] $|U_{i,1}|$ and $|U_{i,2}|$ are even if $|V_i|$ is even, \item[$(ii)$] $||U_{i,1}| - |U_{i,2}|| \leq 2$, and \item[$(iii)$] Blue's graph contains at most one edge in $E(G[U_{i,1}]) \cup E(G[U_{i,2}])$. \end{enumerate} If Blue's graph contains an edge $xy$ in $E(G[U_{i,1}]) \cup E(G[U_{i,2}])$, assume w.l.o.g. that $xy \in E(G[U_{i,1}])$. Let $u_1u_2 \in E(B_i)$ be an edge such that $u_1 \in U_{i,1}$ and $u_2 \in U_{i,2}$. Before her first move, Red chooses $u_2$ to be the designated trap vertex when playing according to the strategy $\mathcal{S}^{a.strong}_{|U_{i,2}|}$ on $E(G[U_{i,2}])$. In her first move, Red then plays according to the strategy $\mathcal{S}^{a.strong}_{|U_{i,1}|}$ on $E(G[U_{i,1}])$. Else, if Blue's graph contains no edge in $E(G[U_{i,1}]) \cup E(G[U_{i,2}])$, let $u_1u_2, v_1v_2 \in E(B_i)$ be two edges such that $u_1, v_1 \in U_{i,1}$ and $u_2, v_2 \in U_{i,2}$. Before her first move, Red chooses $v_1$, resp. $u_2$, to be the designated trap vertices when playing according to the strategy $\mathcal{S}^{a.strong}_{|U_{i,1}|}$ on $E(G[U_{i,1}])$, resp. $\mathcal{S}^{a.strong}_{|U_{i,2}|}$ on $E(G[U_{i,2}])$. In her first move, Red then plays according to the strategy $\mathcal{S}^{a.strong}_{|U_{i,1}|}$ on $E(G[U_{i,1}])$. Then, as long as Red's graph does not contain a perfect matching on $E_i$, Red plays as follows:\\ If the last edge Blue claimed was in $E(G[U_{i,j}])$ for a $j \in \{1,2\}$, and Red's graph does not contain a perfect matching on $E(G[U_{i,j}])$, Red plays according to $\mathcal{S}^{a.strong}_{|U_{i,j}|}$ on $E(G[U_{i,j}])$.\\ Else, if Red's graph does not contain a perfect matching on $E(G[U_{i,1}])$, Red plays according to $\mathcal{S}^{a.strong}_{|U_{i,1}|}$ on $E(G[U_{i,1}])$.\\ Else, Red plays according to $\mathcal{S}^{a.strong}_{|U_{i,2}|}$ on $E(G[U_{i,2}])$. \end{description} It remains to prove that Red can indeed follow this strategy and, by following it, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves ensuring that $w_{R_i} \leq w_{B_i}$. First, for the partitioning of $V_i$ into $U_{i,1}$ and $U_{i,2}$, recall that $B_i$ consists of independent edges only. Therefore, if $m_i$ is divisible by 4, Red can `dissect' all edges of Blue and, by distributing free vertices equally, obtain a partition of $V_i$ into two equitable halves $U_{i,1}$ and $U_{i,2}$ of even size. If $m_i$ is however not divisible by 4 and there are no free vertices to distribute (i.e. if $B_i$ consists of $m_i /2$ independent edges), Red might not be able to dissect all edges in order to keep $|U_{i,1}|$ and $|U_{i,2}|$ even. But then, by dissecting all but one of Blue's edges, the described partitioning of $V_i$ is possible. For Case 1, note that the assumptions of Lemma \ref{lemma:strategy_strong}, $(i)$, are fulfilled, and thus Red can play according to $\mathcal{S}^{a.strong}_{m_i}$ on $E_i$. Hence Red builds a perfect matching in at most $m_i / 2 + 2$ moves while ensuring that $w_{R_i} \leq w_{B_i}$. For Case 2, let us first argue that assumptions of Lemma \ref{lemma:strategy_strong} are fulfilled for both $U_{i,1}$ and $U_{i,2}$. Note that, since $e(B_i) \geq 2$ right before the partitioning of $V_i$, we either have one blue edge in $E(B[U_{i,1}])$ and at least one blue edge between $U_{i,1}$ and $U_{i,2}$ or at least two blue edges between $U_{i,1}$ and $U_{i,2}$. Thus all the above used edges exist. Furthermore, since $E(B[U_{i,2}])$ is empty right after the partitioning, it contains at most one edge right before Red claims her first edge on $E(U_{i,2})$. Thus, for both $E(B[U_{i,1}])$ and $E(B[U_{i,2}])$, right before Red claims her first edge on them, the assumptions of Lemma \ref{lemma:strategy_strong} are fulfilled. Therefore, by applying the strategy $\mathcal{S}^{a.strong}_{|U_{i,j}|}$ on $E( U_{i,j})$ for both $j \in \{1,2\}$, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves. It hence remains to argue that $w_{R_i} \leq w_{B_i}$ is true at any time. First, let us consider the case when there exists one edge $xy$ in $E(B[U_{i,1}])$ right after the partitioning. Then Lemma \ref{lemma:strategy_strong}, $(i)$, asserts that $w_{R[U_{i,1}]} \leq w_{B[U_{i,1}]}$ at any time. Additionally, by Lemma \ref{lemma:strategy_strong}, we either have that $w_{R[U_{i,2}]} \leq w_{B[U_{i,2}]}$ (in which case $w_{R_i} \leq w_{B_i}$ follows directly) or that $d_{B[U_{i,2}]}(u_2) = w_{R[U_{i,2}]}$, where $u_2$ is the designated trap vertex chosen right after the partitioning. Since there exists at least one edge $u_1u_2$ with $u_1 \in U_{i,1}$, we have that $w_{R[U_{i,2}]} \leq d_{B_i}(u_2) -1$. Thus, since we did not consider edges of $E(B[U_{i,1}, U_{i,2}])$ to derive $w_{R[U_{i,1}]} \leq w_{B[U_{i,1}]}$, it holds that $w_{R_i} = w_{R[U_{i,1}]} + w_{R[U_{i,2}]} \leq w_{B[U_{i,1}]} + (d_{B_i}(u_2) -1) \leq w_{B_i}$ is true at any time. On the other hand, if $E(B[U_{i,1}]) \cup E(B[U_{i,2}])$ is empty right after the partitioning, first note that if Blue produces a $U_{i,j}$-distinct vertex before Red's $(|U_{i,j}| /2 - 1)$st move on $E(U_{i,j})$ either for both or just one $j \in \{1,2\}$, then $w_{R_i} \leq w_{B_i}$ is true at any time. This holds in the first case because $w_{R[U_{i,j}]} \leq w_{B[U_{i,j}]}$ for both $j \in \{1,2\}$ (by Remark \ref{remark: $D_j$ = 1}) is true at any time or in the latter case by the argument above. It thus remains to argue what happens if Blue neither creates a $U_{i,1}$-distinct nor a $U_{i,2}$-distinct vertex. In this case, note that Red chooses the designated trap vertices $v_1$ and $u_2$ such that they are not incident to each other in Blue's graph (right after the partitioning). Therefore, by Lemma \ref{lemma:strategy_strong}, we have that $d_{B[U_{i,1}]}(v_1) = w_{R[U_{i,1}]}$ and $d_{B[U_{i,2}]}(u_2) = w_{R[U_{i,2}]}$ after Red finished her perfect matching on $E_i$. These two equalities, together with the two different blue edges $u_1u_2, v_1v_2 \in E(U_{i,1}, U_{i,2})$ then give us that $w_{R_i} \leq w_{B_i}$ is true at any time. \subsection{Substrategy $\mathcal{S}_{dangerous}$} \noindent \textbf{\boldmath $\mathcal{S}_{dangerous}$:} The strategy $\mathcal{S}_{dangerous}$ is used to play on subboards $E_i$ where, right before Red claims her first edge on $E_i$, it holds that $w_{B_i} = 1$. Note that in this case $e(B_i) > 2$ and $B_i$ consists of either one path of length 2 or one path of length 3 together with some independent edges. The main idea of Red is again to `dissect' all but at most one of Blue's edges and thus split the board $E_i$ into two `halves', since then Red can use the strategy $\mathcal{S}^{a.strong}_n$. In what follows we propose a strategy and then prove that, by following it, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves ensuring that $w_{R_i} < w_{B_i}$ at any time. The strategy $\mathcal{S}_{dangerous}$ can be divided into the following cases: \begin{description} \item[Case 1:] $e(B_i) = 2$.\\ Let $xy$ and $yz$ in $E(B_i)$ be the two edges Blue already claimed. Then Red claims $xz$, and plays on $V \setminus \{x,z\}$ according to $\mathcal{S}^{a.strong}_{m_i -2}$. \item[Case 2:] $e(B_i) > 2$ and Blue's graph contains a path of length 2.\\ Let $xyz$ be the path of length 2 in Blue's graph. Red partitions the vertex set $V_i=U_{i,1} \cup U_{i,2}$ into two subsets, as described in the strategy $\mathcal{S}_{trap}$, additionally making sure that $x$ and $z$ belong to $U_{i,1}$ and $y$ belongs to $U_{i,2}$. Then Red ignores that the edge $xy$ is coloured blue and plays as described in Case 2 of the strategy $\mathcal{S}_{trap}$. \item[Case 3:] $e(B_i) > 2$ and Blue's graph contains a path of length 3.\\ Let $wxyz$ be the path of length 3 in Blue's graph. Red partitions the vertex set $V_i=U_{i,1} \cup U_{i,2}$ into two subsets, as described in the strategy $\mathcal{S}_{trap}$, additionally making sure that $x$ and $z$ belong to $U_{i,1}$ and $w$ and $y$ belong to $U_{i,2}$. Then Red ignores that the edge $xy$ is coloured blue and plays as described in Case 2 of the strategy $\mathcal{S}_{trap}$. \end{description} It remains to prove that Red can indeed follow this strategy and, by following it, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves ensuring that $w_{R_i} < w_{B_i}$. To this end, first observe that when $B_i$ consists only of the path $xyz$ of length 2, Red can claim $xz$, hence ensuring that there exists exactly one $V_i$-distinct vertex. Thus Red can play according to the strategy $\mathcal{S}^{a.strong}_{m_i -2}$ on $V \setminus \{x,z\}$ and build a perfect matching in at most $m_i/2 + 2$ moves. Additionally, since $0=w_{R_i} < w_{B_i}=1$ and $y$ is already $V_i$-distinct in the beginning, it follows from Remark \ref{remark: $D_j$ = 1} that $w_{R_i} < w_{B_i}$ is true at any time. For the partition of $V_i$ note that `dissecting' the edges immediately gives us the additional conditions on $x,y,z$ and $w$, thus this partition can be obtained. For Cases 2 and 3 note that by `ignoring' the colouring of the edge $xy$ (which lies in between $U_{i,1}$ and $U_{i,2}$), since $e(B_i) > 2$, we have the exact same conditions as in Case 2 of the strategy $\mathcal{S}_{trap}$ (at least two independent edges in Blue's graph). Thus Red can play as described in Case 2 of the strategy $\mathcal{S}_{trap}$ and build a perfect matching in at most $m_i / 2 +4$ moves. Additionally, since Red does not `waste more moves' than Blue when playing according to $\mathcal{S}_{trap}$, and again since $w_{R_i} < w_{B_i}$ in the beginning, we have that $w_{R_i} < w_{B_i}$ is true at any time. \subsection{Substrategy $\mathcal{S}_{empty}$}\label{subsec:empty} \noindent \textbf{ \boldmath $\mathcal{S}_{empty}$:} The strategy $\mathcal{S}_{empty}$ is used to play on subboards $E_i$ where, right before Red claims her first edge on $E_i$, it holds that $e(B_i) = 0$. It achieves the following: \begin{enumerate} \item[$P1$:] If there exists a $V_i$-distinct vertex $u \in V_i$ after Red's $(m_i /2 -1)$st move on $E_i$ or if $\Delta(B_i) >1$ before Red's $(m_i /4 + 3)$rd move on $E_i$, then $w_{R_i} \leq w_{B_i}$ at any time. \item[$P2$:] Else, if $E_{i+1}$ is (resp. was) dangerous, then $w_{R_i} + w_{R_{i+1}} \leq w_{B_i} + w_{B_{i+1}}$ at any time. \item[$P3$:] Else, $w_{R_i} + 2 < w_{B[V_i, V_{i+1}]} $ at any time, where we denote by $B[V_i, V_{i+1}]$ the bipartite graph consisting of all the blue edges between $V_i$ and $V_{i+1}$. \end{enumerate} The strategy $\mathcal{S}_{empty}$ consists of the following stages: \medskip \textbf{Stage I:} Red claims an arbitrary edge $ab \in E_i$ and skips to Stage II. \medskip \textbf{Stage II:} Red follows Stage II (and Stage M, if needed) of the strategy $\mathcal{S}^{a.strong}_{m_i}$. Then Red skips to Stage III below. \medskip \textbf{Stage III:} Red completes her perfect matching on $E_i$ as follows: Let $u,v \in V_i$ be the last two vertices Red needs to connect to finish her perfect matching on $V_i$. Assume w.l.o.g. that $d_{B_i}(v) = 0$. If $d_{B_i}(u) \geq 1$ right after Red's $(m_i /2 -1)$st move, then Red finishes her perfect matching according to Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$. Otherwise, we distinguish between the following two cases: \begin{description} \item[Case 1:] $e(R_{i+1}) \geq 1$.\\ Then Red claims $uv$. If this is not possible, Red plays as described in Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$ and finishes her perfect matching in at most three moves. \item[Case 2:] $e(R_{i+1}) = 0$.\\ Then Red claims $uv$. If this is not possible, Red chooses two vertices $x,y \in V_{i+1}$ such that \begin{enumerate} \item[$(i)$] the edges $ux$ and $vy$ are still free, and \item[$(ii)$] the number of Blue edges $yz$ with $z \in V_i$ is smaller than $ m_i / 4 +1$. \end{enumerate} If this is not possible, Red uses Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$ to finish her perfect matching on the subboard $E_i$ in at most three moves. Otherwise, Red claims the edge $ux$. Before her next move, Red updates $V_i := V_i \cup \lbrace x,y \rbrace$ and $V_{i+1} := V_{i+1} \setminus \lbrace x,y \rbrace$. Then Red claims $vy$. If this is not possible, Red uses Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$ to finish her perfect matching on the updated subboard $E_i$ in at most three moves. \end{description} It remains to prove that Red can indeed follow this strategy and, by following it, Red builds a perfect matching on $E_i$ in at most $m_i / 2 + 4$ moves ensuring that the properties $P1$, $P2$ and $P3$ are achieved. Note that after Stage I there exists no $V_i$-distinct vertex, hence Red can skip to Stage II of the strategy $\mathcal{S}^{a.strong}_{m_i}$. Thus, whenever Red skips to Stage M of the strategy $\mathcal{S}^{a.strong}_{m_i}$, meaning that $\Delta(B_i) > 1$ before Red's $(m_i /4 + 3)$rd move on $E_i$, it follows that $w_{R_i} \leq w_{B_i}$ at any time (which gives us a first case of $P1$). Moreover, Red then builds a perfect matching on $E_i$ in $m_i / 2 + 1$ moves. Note that, while following Stages I and II of the strategy $\mathcal{S}^{a.strong}_{m_i}$, Red made sure there is at most one $V_i$-distinct vertex after each of her moves, thus we can assume w.l.o.g. that that $d_{B_i}(v) = 0$ whenever Red reaches Stage III. Thus, If $d_{B_i}(u) \geq 1$, i.e. there exists a $V_i$-distinct vertex after Red's $(m_i /2 -1)$st move, Red essentially plays according to $\mathcal{S}^{a.strong}_{m_i}$ on $E_i$. Therefore, we have that Red finishes her perfect matching in at most three moves, and Remark \ref{remark: $D_j$ = 1} ensures that $w_{R_i} \leq w_{B_i}$ (which gives us another case of $P1$). %For Stage III, note that whenever Red uses Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$ to finish her perfect matching on the (updated) subboard $E_i$ in at most three moves, we are in the following situation: Blue claimed the last edge, say $uv$, which Red needs to finish her perfect matching on $E_i$. Since in these cases we cannot be sure that $d_{B_i}(u) \geq 1$ right before Blue claims $uv$, we only can be sure that $d_{B_i}(u) \geq w_{R_i}$ after Red used Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$ (by Lemma \ref{lemma:strategy_strong}, $(ii)$). Since $d_{B_i}(u) \geq w_{R_i}$ is equivalent to $w_{B_i} -1 \geq w_{B_i} $, we need to make sure that there exists a `spare wasted move' of Blue. Whenever Red plays according to Stage III, Case 1, note that $e(R_{i+1}) \geq 1$ means that $E_{i+1}$ is, respectively was, a dangerous subboard. Therewith, $w_{R_{i+1}} < w_{B_{i+1}}$. Since there exists no $V_i$-distinct vertex after Red's $(m_i /2 -1)$st move, no red edge is connected in Blue's graph to $u$ or $v$. Thus, if Red cannot claim $uv$, she can indeed follow Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$. In this case, Lemma \ref{lemma:strategy_strong} ensures only that $d_{B_i}(u) = w_{R_i}$, which is the same as saying $w_{R_{i}} - 1 \leq w_{B_{i}}$. But then, as $w_{R_{i+1}} < w_{B_{i+1}}$, we have that $w_{R_i} + w_{R_{i+1}} \leq w_{B_{i}} + w_{B_{i+1}}$ (which gives us $P2$). Moreover, Red builds a perfect matching on $E_i$ in at most $m_i /2 +2$ moves. Whenever Red plays according to Stage III, Case 2, first note the following: if such two vertices $x$ and $y$ do not exist, then Blue claimed lots of edges between $V_i$ and $V_{i+1}$ (remember that all edges between $V_i$ and $V_{i+1}$ are present). Especially it means that $d_{B[V_i, V_{i+1}]}(u) \geq m_i /4 +1$ or $d_{B[V_i, V_{i+1}]}(y) \geq m_i /4 +1$. Thus we have that $w_{B[V_i, V_{i+1}]} > m_i / 4$. Since $w_{R_i} \leq 2$ when Red finishes her perfect matching according to Stage III of $\mathcal{S}^{a.strong}_{m_i}$ (which she can do by the same argument as above), we have that $w_{R_i} + 2 \leq 4 < w_{B[V_i, V_{i+1}]}$ (which gives us $P3$). Moreover, Red builds a perfect matching on $E_i$ in $m_i /2 +2$ moves. Otherwise, after Red claimed $ux$ and updated $V_i$, we have that $d_{B_i}(v) = 1$ and $d_{R_i}(u) = 0$, i.e. there exists a $V_i$-distinct vertex after Red's $(m_i / 2 -1)$st move. Thus, if Red cannot claim $yv$ in her $(m_i /2)$nd move, as $y$ is connected to at most $m_i/4 +1$ vertices in $V_i$ and $d_{B_i}(v)$ =1, Red can play according to Stage III of the strategy $\mathcal{S}^{a.strong}_{m_i}$ and therewith Remark \ref{remark: $D_j$ = 1} ensures that $w_{R_i} \leq w_{B_i}$ (again a case of $P1$). Moreover, Red builds a perfect matching on $E_i$ in $m_i /2 +2$ moves. \section{Concluding remarks} In this paper we considered the perfect matching game played on the edge set of a typical $G\sim G(n,p)$, for any fixed constant $p$. Since a perfect matching appears in a typical $G\sim G(n,p)$ when $p\geq\frac{\ln n+\omega(1)}{n}$ (see e.g., \cite{bollobas2001random}), it will be interesting to extend our result for every $p$ in this regime. Clearly, our proof technique, which is based on the existence of large cliques, can not work for small $p$'s. It might be very interesting to analyse other games as well. For example, a natural game to analyse is the Hamiltonicity game. Using similar arguments we indeed managed to provide Red with a winning strategy for the Hamiltonicity game played on the edge set of a typical $G\sim G(n,p)$ where $p$ is constant. However, the proof is quite long and technical so we will only upload it to arXiv as a draft for the curious reader. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} Most of this work has been taken in ETH, Z\"urich as part of a master thesis of the second author, while the first author was a postdoc there. We would like to thank ETH, Z\"urich for providing us with a perfect environment for doing research. Finally, we would like to thank the anonymous referees for reading our manuscript and providing many helpful comments. \begin{thebibliography}{10} \bibitem{beck2008combinatorial} J{\'o}zsef Beck, \newblock {\em Combinatorial games: tic-tac-toe theory}, Encyc. Math. Appl. {\bf114}, \newblock Cambridge University Press, 2008. \bibitem{jozsef2009inevitable} J{\'o}zsef Beck, \newblock {\em Inevitable randomness in discrete mathematics}, University Lecture Series {\bf49}, \newblock American Mathematical Soc., 2009. \bibitem{bollobas2001random} B{\'e}la Bollob{\'a}s, \newblock {\em Random graphs} (2nd ed.) \newblock Cambridge University Press, 2001. \bibitem{ferber2011winning} Asaf Ferber and Dan Hefetz, \newblock Winning strong games through fast strategies for weak games. \newblock {\em Electron. J. Combin.}, 18(1):P144, 2011. \bibitem{ferber2014weak} Asaf Ferber and Dan Hefetz, \newblock Weak and strong k-connectivity games, \newblock {\em European J. Combin.}, 35:169--183, 2014. \bibitem{frieze1988algorithm} Alan M. Frieze, \newblock An algorithm for finding hamilton cycles in random directed graphs, \newblock {\em J. Algorithms}, 9(2):181--204, 1988. \bibitem{HJ} A. W. Hales and R. I. Jewett, \newblock Regularity and positional games, \newblock {\em Trans. Amer. Math. Soc.}, 106:222--229, 1963. \bibitem{hefetz2009fast} Dan Hefetz, Michael Krivelevich, Milo{\v{s}} Stojakovi{\'c} and Tibor Szab{\'o}, \newblock Fast winning strategies in Maker--Breaker games, \newblock{\em J. Combin. Theory, Ser. B}, 99(1):39--47, 2009. \bibitem{janson2011random} Svante Janson, Tomasz Luczak and Andrzej Rucinskij, \newblock {\em Random graphs}, Wiley-Interscience Ser. Disc. Math. Optim. {\bf45}, \newblock Wiley, 2011. \bibitem{krivelevich2009equitable} Michael Krivelevich and Bal{\'a}zs Patk{\'o}s, \newblock Equitable coloring of random graphs, \newblock{\em Random Structures \& Algorithms}, 35(1):83--99, 2009. \bibitem{west2001introduction} Douglas B. West, \newblock {\em Introduction to graph theory} (2nd ed.), \newblock Prentice Hall, Upper Saddle River, 2001. \end{thebibliography} \end{document}