% 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<p\leq 1$ be a fixed constant. Then, w.h.p., a graph $G \sim G(n,p)$ is such that the following holds: 
There exists a partition $V(G)=V_1 \cup \cdots \cup V_t$ of $G$ into disjoint subsets such that for all $1\leq i \leq t$ we have:
\begin{enumerate}
\item[$i)$] $G[V_i]$ is a clique
\item[$ii)$] $|V_i| = \Theta(\ln^{\frac{1}{3}}n)$
\item[$iii)$] $|V_i|$ is even for all $1 \leq i \leq t-1$
\end{enumerate}
\end{theorem}

The proof of this theorem closely follows a nice argument of Krivelevich and Patk\'os from the proof of Theorem 1.2 in \cite{krivelevich2009equitable}.

\begin{proof}
We follow the following greedy algorithm: Let $k = \lceil n / \ln^{\frac{1}{3}}n \rceil$. If $\lceil \frac{n}{k} \rceil$ is even, we define $r := \lceil \frac{n}{k} \rceil$ and otherwise, we define $r := \lceil \frac{n}{k} \rceil - 1$ (so that $r$ is even in any case). Now, partition the vertex set $V(G)=U_1 \cup \cdots \cup U_{r-2} \cup W$ such that $|U_1|=|U_2|=\cdots= |U_{r-2}| = k$ and $W = V \setminus \bigcup_{j=1}^{r-2} U_j$. Note that $k \leq|W| \leq 3k$ and that $r \leq \ln^{\frac{1}{3}}n$.

We build the $k$ cliques in $r$ rounds by starting with cliques of size
1 and, for all $2 \leq i \leq r-2$,  adding in the  $i$th
round one vertex of $U_i$ to each clique. In the last two rounds, we
add the vertices of $W$ `smartly' to ensure that all but one of
the cliques are of even size. We denote the $k$ cliques obtained
after the $i$th round of the algorithm by
$C^1_i,\dots,C^k_i$. In the first $(r-2)$ rounds the algorithm works
as follows: For $i=1$ we simply define $ \lbrace
C^1_1,\dots,C^k_1 \rbrace := U_1$, and hence $C^1_1,\dots,C^k_1$ is a
collection of $k$ cliques, each of size 1. For $2 \leq i
\leq r-2$, in the $i^{\emph{th}}$ round we expose all edges between
$U_i$ and $\bigcup_{j=1}^{i-1}U_j$. To find the extension of the
cliques, we define an auxiliary random bipartite graph $B_i = A_i
\cup U_i$ on $2k$ vertices, where $A_i = \lbrace
C^1_{i-1},\dots,C^k_{i-1} \rbrace$. That is, $A_i$ represents the
already formed cliques of size $(i-1)$ and the other part stands for
the new vertices we want to add to those cliques. For $C\in A_i$ and
$x\in U_i$, we add the edge $Cx$ to $E(B_i)$ if and only if $x$ is
connected (in $G$) to all the vertices of $C$. Hence, any perfect
matching of $B_i$ corresponds to an extension of the cliques
$C^1_{i-1},\dots,C^k_{i-1}$ by one vertex each. Note that the
auxiliary graph $B_i$ has edge probability $p_i= p^{i-1}$. It is
shown below that w.h.p. there exists a perfect matching in $B_i$ for all $1 \leq i \leq r-2$. 

For the last rounds of the algorithm, let us assume that after $(r-2)$ rounds we have $k$ cliques $C^1_{r-2},\dots,C^k_{r-2}$ of even size $(r-2)$. Now, we need to define the algorithm to extend these cliques with the vertices of $W$ such that all but at most one of the cliques $C^1_r,\dots,C^k_r$ are of even size. To this end we act as follows:

Partition $W = X_1 \cup Y_1 \cup X_2 \cup Y_2$ into four sets of size  $\lfloor |W| / 4 \rfloor$ or $\lfloor |W| / 4 \rfloor +1$ such that $|X_1| = |Y_1|$ and $||X_2| - |Y_2|| \leq 1$.  Then, for $i= 1,2$ expose all the edges within $W_i := X_i \cup Y_i$. Assume without lose of generality that $|X_2| \leq |Y_2| = k_2$ and let  $|X_1| = |Y_1| = k_1$. Note that in any case we have that $k /4 \leq k_1 \leq k_2 \leq k$. Define the auxiliary random bipartite graph $B_{W_i} = X_i \cup Y_i$ with edge probability $p_{W_i}=p$ (note that we forget about all the edges exposed inside $X_i$ and $Y_i$). Let $Z_1 := \{ (x_1,y_1),\dots,(x_{k_1},y_{k_1}) \}$ be the vertices of $X_1$ and $Y_1$ which are paired up by a perfect matching in $B_{W_1}$ and let $(x'_1,y'_1),\dots,(x'_{k_2 -1},y'_{k_2 -1})$ be the vertices which are paired up by a perfect matching in $B_{W_2}$. We then define the set $Z_2=\{ z'_1,\dots,z'_{k_2} \}$ by $z'_i:= (x'_i,y'_i)$ for all $ 1 \leq i \leq k_2-1$ and $z'_{k_2}=(x'_{k_2},y'_{k_2})$ if $|X_2|=|Y_2|$, respectively $z'_{k_2}=y'_{k_2}$ if $|X_2|=|Y_2|-1$. Again, it is shown below that there exists a perfect matching in $B_{W_1}$ and $B_{W_2}$.

In the second last round, the algorithm exposes all edges between $W_1$ and $V \setminus W$. We define the auxiliary random bipartite graph $B_{r-1} = A_{r-1} \cup Z_1$ on $2k_1$ vertices, with $A_{r-1} = \lbrace C^1_{r-2},\dots,C^{k_1}_{r-2} \rbrace$. An edge between $z_i$ and $C^j_{r-2}$ is present in $E(B_{r-1})$ if and only if all edges between $x_i$ and $C^j_{r-2}$ as well as all edges between $y_i$ and $C^j_{r-2}$ are present. Hence we obtain an edge probability $p_{r-1} = p^{2(r-2)}$.
If there exists a perfect matching in $B_{r-1}$, the algorithm extends the cliques $C^1_{r-2},\dots,C^{k'}_{r-2}$ by the corresponding vertex-pair in $Z_1$ and therewith obtains $k$ cliques $C^1_{r-1},\dots,C^k_{r-1}$ of even size.

Then, in the last round, the algorithm exposes all edges between $W_2$ and $V \setminus W_2$. We define the auxiliary random bipartite graph $B_{r} = A_{r} \cup Z_2$ on $2k_2$ vertices, with $A_{r} = \lbrace C^1_{r-1},\dots,C^{k_2}_{r-1} \rbrace$. An edge between $z'_i$ and $C^j_{r-1}$ is present in $E(B_{r})$ if and only if all edges between $x'_i$ and $C^j_{r-1}$ as well as all edges between $y'_i$ and $C^j_{r-1}$ are present. Hence we obtain an edge probability $p_{r} = p^{2r}$ (we achieve equality in the edge probability by flipping additional coins with the `missing' success-probability $q_e$ for all edges $e$ incident to $C^j_{r-1}$ with $k_1 < j \leq k$ and,  if $z'_{k_2} = y'_{k_2}$, for all edges incident to $z'_{k_2}$).
If there exists a perfect matching in $B_{r}$, the algorithm extends the cliques $C^1_{r-1},\dots,C^{k_2}_{r-1}$ by the corresponding vertex-pair in $Z_2$ and therewith obtains $k$ cliques $C^1_r,\dots,C^k_r$ of which all but at most one (namely $C_r^{k_2}$) are of even size. Furthermore, $|C^i_r - C^j_r| \leq 4$ for all $i,j \in [k]$.

Thus, after reordering, the algorithm outputs a partition $V(G)=V_1 \cup \cdots \cup V_k$ into $k$ disjoint subsets of size $\Theta(\ln^{\frac{1}{3}}n)$, such that $G[V_i]$ is a clique for all $i \in [k]$ and $|V_i|$ is even for all $1 \leq i \leq k-1$.

It remains to prove that the algorithm succeeds w.h.p., i.e. that the algorithm can find a perfect matching in all the auxiliary bipartite graphs. Note that all the edge probabilities of these auxiliary graphs are at least $p^{2r}$. Since $0<p<1$ is a constant, we have that $p^{2r} \geq p^{2\ln^{\frac{1}{3}}n} = \Omega(n^{{\alpha}-1})$ for some $0< \alpha < 1$. By Remark 4.3 in Chapter 4 in \cite{janson2011random}, we know that the probability that there is no perfect matching in a random bipartite graph $G \sim G(n,n,p)$ on two sets of size $n$ with edge probability $p$ is $O(ne^{-np})$. Therefore, the probability that the Algorithm fails is upper bounded by $(r+2) O(ke^{-\frac{k}{4} p^{2r}}) = O(ne^{-n^{\alpha} / \ln^{\frac{1}{3}}n}) = o(1)$. All in all, the algorithm succeeds with high probability and outputs $t$ cliques with the desired properties.
\end{proof}

Using the above theorem, we prove the following lemma which ensures
us a partitioning of a random graph $G \sim G(n,p)$ into disjoint
complete subgraphs which can be cyclically ordered in such a way that
the union of any two consecutive cliques is a clique as well.

\begin{lemma} \label{partitioning_lemma}
Let $0<p\leq 1$ be a fixed constant. Then, w.h.p., a graph $G \sim G(n,p)$ is such that the following holds: 
There exists a partition $V(G)=V_1 \cup \cdots \cup V_t$ of $G$ into disjoint subsets such that for all $1\leq i \leq t$ we have the following:
\begin{enumerate}
\item[$i)$] $G[V_{i}\cup V_{i+1}]$ is a clique (we consider $t+1$ to be 1)
\item[$ii)$] $|V_i| = \Theta(\log^{\frac{1}{3}}n)$
\item[$iii)$] $|V_i|$ is even for all $1 \leq i \leq t-1$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $q$ be a constant such that $1-p=(1-q)^2$. Present $G=G_1 \cup G_2$, where $G_1,G_2 \sim G(n,q)$ (for more details about this `multiple exposure' trick, see \cite{bollobas2001random}). Let $V(G_1)=U_1 \cup \cdots \cup U_l$ be the partition of $G_1$ into disjoint subsets obtained by applying Theorem \ref{thm:auxiliary}. Hence we have that $|U_i|$ is even for all $1 \leq i \leq l-1$.

Further, partition each subset $U_i=L_i \cup R_i$ into two halves such that
\begin{enumerate}
\item[$i)$] $||L_i|-|R_i|| \leq 2$ for all $1 \leq i \leq l$
\item[$ii)$] $|L_i|$ and $|R_i|$ are even for all $1 \leq i \leq l-1$
\item[$iii)$]  $|L_l|$ is even.
\end{enumerate}
Hence, all subsets but $R_l$ are of even size and, for all $1 \leq i \leq l$, we have that $L_i$ and $R_i$  are of size  $\Theta(\log^{\frac{1}{3}}n)$.

Before exposing $G_2$, define an auxiliary digraph $D=(V,E)$ such that the set of vertices is defined by $V(D) := \lbrace (L_i,R_i) | 1 \leq i \leq l \rbrace$. Furthermore, let $R_iL_j$ be the directed edge from $(L_i,R_i)$ to $(L_j,R_j)$, which is present if and only if all edges between $R_i$ and $L_j$ appear in~$G_2$.

Note that 
$$\Pr[R_iL_j \in E(D)]=q^{|R_i||L_j|} = q^{\Theta(\log^{\frac{2}{3}}n)} = \omega\left(\frac{\ln^2 n}{n}\right) = \omega\left(\frac{\ln(|V(D)|)}{|V(D)|}\right),$$ since $|V(D)|\approx n / \ln^{\frac{1}{3}}n$. Using the main result of \cite{frieze1988algorithm}, we know that the digraph $D$ contains a directed Hamilton cycle. By relabelling we may assume that $(L_1,R_1)(L_2,R_2)\cdots(L_l,R_l)$ is a directed Hamilton cycle. By defining $V_1, V_2,\ldots,V_t := L_{1},R_{1},L_{2},R_{2},L_{3},\dots,R_{l}$ we hence obtain our partition $V(G) = V_1 \cup \ldots \cup V_t$ with the desired properties.
\end{proof}


\subsection{The perfect matching game on the complete graph $K_n$} \label{sec: PM game on Kn}

The main tools used in the proof of Theorem
\ref{thm:perfect_matching} are the following two strategies
concerning the perfect matching game on the complete graph $K_n$.
One is the strategy described in the proof of Theorem 1.2 in
\cite{hefetz2009fast} which ensures that Maker can win the weak
perfect matching game on $K_n$ in at most $n/2+1$ moves if $n$ is even, respectively in $\lfloor n/2 \rfloor$ moves if $n$ is odd. We will
henceforth denote this strategy by $\mathcal{S}^{weak}_n$. The
second strategy is a slight alteration of the strategy which ensures that Red can win the strong perfect matching game on $K_n$, as
described in the proof of Theorem 1.3 in \cite{ferber2011winning}. The basic idea of this strategy is that Red makes sure of two things: on one hand, she fully claims a perfect matching `fast', and on the other hand, she ensures not to `waste more moves' than Blue. Thus, since all perfect matchings are of the same size, Blue cannot fully occupy a perfect matching before Red does, and hence Red wins the game (note that this idea works in general for all strong games with winning sets of the same size).

%Before describing this strategy we need the following definitions.
%For any matching $M \in G$, let $e(M)$ be the number of edges in this matching and let $M_G := \max \lbrace e(M) : M \subset G \emph{ is a matching in G} \rbrace$ denote the size of a maximum matching in G. When a strong perfect matching game is in progress, recall that $R$ is the graph spanned by Red's edges and $B$ is the graph spanned by Blue's edges. We denote by $w_B := e(B) - M_B$, respectively $w_R := e(R) - M_R$, the number of wasted moves of Blue, respectively Red.

%%Note that the basic idea for Red to win the strong perfect matching game is that Red manages to completely claim a winning set while ensuring that $w_R \leq w_B$ at any point during the game. Thus, since all winning sets are of the same size, Blue cannot fully occupy a winning set before Red does, and hence Red wins the game. Note that at any point in the perfect matching game $d_B(v) - 1 \leq w_B$ for all $v \in V$. Thus, a natural lower bound on the number of wasted moves in Blue's graph is $\Delta(B) - 1$.

% we propose a slight alteration of the strong perfect matching game, which we call the \emph{almost strong perfect matching} game.
%Let $H = K_n$ and let $G \supseteq H$ be a graph on $n' \geq n$ vertices. In the almost strong perfect matching game, the goal of Red is to claim a perfect matching on $H$, while the goal of Blue is to claim a perfect matching on the graph $H'$, where $H \subseteq H' \subseteq G$. To even out the disadvantage of Blue (she needs to claim more edges than Red to win), Red will give Blue a head start. More precise, Red only starts claiming edges after Blue claimed her first edge in $E(H')$ which is incident to a vertex $u \in V(H)$. From this moment on, both players claim exactly one edge of $E(G)$ in each round. Recall that, when a (almost) strong perfect matching game is in progress, $R$ is the graph spanned by Red's edges and $B$ is the graph spanned by Blue's edges. Thus, when Red starts claiming edges, there exists a vertex $u \in V(H)$ with $d_{B[V(H')]}(u) = 1$, but Blue claimed at most one edge $uv$ in $E(H)$.

To describe our altered version of the strategy, let us introduce the notion of `wasted moves'. For any graph $H = (V(H), E(H))$ and a matching $M \subset E(H)$, let $e(M)$ be the number of edges in this matching and let 
$$M_H := \max \lbrace e(M) \mid M \subset E(H) \text{ is a matching in H} \rbrace$$ denote the size of a maximum matching in $H$.  Recall that whenever a strong perfect matching game on the edge set of a graph $G = (V, E)$ is in progress, $R$ is the graph spanned by Red's edges and $B$ is the graph spanned by Blue's edges. Let us denote by $w_{B} := e(B) - M_B$ and $w_R := e(R) - M_R$, the \emph{number of wasted moves} of Blue and  Red respectively. Furthermore, for any set of vertices $V' \subset V$ let $w_{B[V']} := e(B[V']) - M_{B[V']}$, respectively $w_{R[V']}:= e(R[V']) - M_{R[V']}$, be the number of wasted moves of Blue, respectively Red, on the edge set of the induced subgraph $G[V']$.

A simple but crucial observation on the number of wasted moves is that it can be bounded from below by the degree of any vertex, since at any time in a perfect matching game we have that $d_B(v) - 1 \leq w_B$ for all vertices $v \in V$. %Note that this is a very rough bound usually (it is tight for the `middle' vertex of a star graph, but also arbitrarily bad for any vertex in a path), nevertheless, it

We now describe how Red achieves the following:
\begin{lemma} \label{lemma:strategy_strong}
Assume that a strong perfect matching game on the edge set of a graph $G = (V, E)$ is in progress. Let $H$ be a subgraph of $G$ such that $G[V(H)]$ is a clique on $n$ vertices and $d_R(v) = 0$ for all vertices $v \in V(H)$. Then the following holds:
\begin{enumerate}
\item[(i)] If $B[H]$ contains exactly one edge, then Red can build a perfect matching on $H$ in at most $n /2 +2$ moves while ensuring that $w_{R[V(H)]} \leq w_{B[V(H)]}$ at any time.
\item[(ii)] If $e(B[V(H)]) = 0$ but there exists a vertex $u \in V(H)$ with $d_B(u) \geq 1$, then Red can build a perfect matching on $H$ in at most $n /2 +2$ moves while ensuring that $w_{R[V(H)]} \leq w_{B[V(H)]}$ or at least that $w_{R[H]} = d_{B[H]}(u)$ at any time.
\end{enumerate}

%Let $H = K_n$ and let $G \supseteq H$ be a graph on $n' \geq n$ vertices.  Assume that Red and Blue play the almost strong perfect matching game on $E(G)$. Let $H \subseteq H' \subseteq G$ be the graph on which Blue wants to build a perfect matching. Then Red can build a perfect matching on $H$ in at most $n/2+2$ moves, while ensuring that at any time during the game $w_{R[V(H)]} \leq w_{B[V(H')]}$ holds.
\end{lemma}


In the above Lemma, one can think of $E(H)$ as the `subboard' where Red's focus is momentarily fixed on. Assuming that Blue claimed at most one edge of $E(H)$ before Red starts claiming her edges, it then holds that Red can build a perfect matching on $H$ `fast' (at most 2 edges more than necessary). Note that we do not claim that Red finishes her perfect matching on $H$ before Blue does (which is not possible because Blue can already have claimed an edge in $E(H)$). But in terms of the number of wasted moves, $(i)$ and $(ii)$ ensure that Red builds a perfect matching on $H$ `as fast as' Blue, i.e. Blue wastes at least as many moves as Red on the `subboard' $E(H)$, respectively at the vertex $u$ ($w_{R[H]} = d_{B[H]}(u)$ together with $d_B(u) \geq 1$ in the beginning means that $w_{R[H]} \leq d_B(u) - 1$. Thus, seen on the whole graph, Blue `wasted' at least as many moves as Red). Thus one can think of the strategy as an `almost' strong strategy.

In the strategy described below, the main idea of Red is to assure that there exists what we call a \emph{trap vertex}, i.e. a vertex $u \in V(H)$ with $d_{R}(u) = 0$ and $d_{B}(u) \geq 1$. Then, whenever Red claimed a matching of size $n/2 -1$ on $H$, which she can do in $n/2 -1$ moves (details in the proof), and therefore misses only one edge to complete her perfect matching, it holds that this missing edge is incident to a vertex $u$ with  $d_{B}(u) \geq 1$. Hence, if Blue claims $uv$, therewith preventing Red from building a perfect matching in $n/2$ moves, it holds that $w_B \geq d_{B}(u) -1 \geq 1$. But this in turns allows Red to `waste a move' herself and build a perfect matching in at most two additional moves (while keeping Blue `forced' to claim edges incident to $u$).

The proof of Lemma \ref{lemma:strategy_strong} closely follows the lines of Theorem 1.3 in \cite{ferber2011winning}.

\begin{proof}[Proof of Lemma \ref{lemma:strategy_strong}]
In what follows, we present a strategy for Red and then prove that,
by following it, Red can build a perfect matching on $H$ in at most
$n/2+2$ moves ensuring that the statements of Lemma \ref{lemma:strategy_strong} are true.
\medskip

Assume first that $n$ is odd. Following Maker's strategy $\mathcal{S}^{weak}_n$ on $E(H)$, Red can build a perfect matching on $H$ in $\lfloor n/2 \rfloor$ moves, which is optimal (note that a perfect matching on an odd number of vertices is a matching covering all but 1 vertex).
\medskip

Else, if $n$ is even, Red's strategy is divided into the following three stages:
\medskip

\textbf{Stage I:} In her first move, depending on whether Blue
claimed an edge in $E(H)$ or not, Red distinguishes between the
following two cases:
\begin{description}
\item[Case 1:] Blue claimed an edge $xy \in E(H)$.\\
Then Red claims a free edge $xz$ for some arbitrary $z \neq y \in
V(H)$, defines the set  $U:=V(H)$ and skips to Stage II.
\item[Case 2:] $e(B[V(H)]) = 0$, but there exists a vertex $u \in H$ with $d_B(u) \geq 1$.\\
Red defines the set $U:=V(H) \setminus \lbrace u \rbrace$ to ensure that she does not claim edges incident to the designated trap vertex $u$, claims an arbitrary free edge in $E(G[U])$ and skips to Stage II.
\end{description}

To describe Stage II, we need to introduce more notation. A vertex $v \in V(H)$ is called $\mathit{V(H)}$\emph{-distinct}, if $d_{B[V(H)]}(v) \geq 1$ and $d_{R[V(H)]}(v)=0$. Moreover, we denote by $D_j$ the number of $V(H)$-distinct vertices immediately \emph{after} Red's $j$th move and by ${D'}_j$ be the number of $V(H)$-distinct vertices immediately \emph{before} Red's $j$th move. Note that whenever Blue creates a $V(H)$-distinct vertex, it may take over the role of the designated trap vertex (and thus the vertex $u$ of Stage I, Case 2 will be `reintegrated' into the game).
\medskip

\textbf{Stage II:} For every $2 \leq j \leq n/4+2$, 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 can even ensure that, if $D_k = 1$ for some $1 \leq k \leq n/2-1$, then $D_j = 1$ for all $k \leq j \leq n/2-1$. Hence, let $2 \leq k \leq n/2-1$ be the smallest integer such that $D_k = 1$. Then Red updates $U := V(H)$ in her $k$th move, since she does no longer need the trap vertex $u \in V(H)$.

If $\Delta(B[V(H)]) > 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}
