Modification of matching Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and we output the largest matching $\mathcal{M}_{1}$. In stage 2 all edges are selected randomly again regardless of how they appeared before but this time we take the largest matching $\mathcal{M}_{2}$ which doesn't include any of the edges of $\mathcal{M}_{1}$ (alternatively we could assume the edges of $\mathcal{M}_{1}$ aren't present anymore and all others are selected randomly). Similarly in stage $i$ we select the largest matching $\mathcal{M}_{i}$ which doesn't include any of the edges in $\mathcal{M}_{1}\cup...\cup \mathcal{M}_{i-1}$. Is there a way we can gain some knowledge on the expected size of $\mathcal{M}_{1} \cup...\cup \mathcal{M}_{n}$?  
 A: Sudakov and Vu proved that, for $p \gg \log n / n$, $G_{n,p}$ has a perfect matching with high probability even after adversarially deleting $(1 - o(1))pn/2$ edges at each vertex.  The same argument works in the bipartite case (and can in fact be slightly simplified).  So for this range of $p$ you expect to be pulling out perfect matchings for at least the first $pn/2$ steps.  In fact, this will still be the case until almost $n/2$ matchings have been removed, as until then it is unlikely that you choose a random graph in which more than half of the edges at any vertex have been used at any previous stage.
Following the comments, here's a slightly more detailed explanation of why we expect to get perfect matchings until around time $n/2$.
At some stage in the process, let $G \sim G_{n,n,p}$ and let $H$ be the subgraph of $K_{n,n}$ consisting of the edges that have already been used.  For each $x \in V(G)$, let $d(x)$ be the degree of $x$ in $G \cap H$.  Let $\epsilon > 0$ and suppose that $n$ is sufficiently large.  We make the following claims.


*

*With probability at least $1-\epsilon$, $G$ is such that after deleting any subgraph of maximum degree at most $(1-\epsilon)pn/2$, the remainder $G'$ still has a perfect matching.

*For each $x \in V(G)$, with probability at least $1-\epsilon/2n$, $d(x) \leq (1+\epsilon)p\Delta(H)$.


The first part is Sudakov and Vu's result.  The second is an easy application of Chernoff's inequality.  It follows by a union bound that, with probablity at least $1-2\epsilon$, $G$ will have a perfect matching even after deleting every edge of $G \cap H$ provided $\Delta(H) < \frac {1-\epsilon} {1+\epsilon} \frac n 2$.
This is enough to tell you that one stage of your process is very likely to succeed, and by iterating that in expectation you will cover close to half of your graph by time $n/2$.  By analysing the failure probabilities more carefully you should be able to show that, with probability tending to $1$ as $n$ tends to infinity, you in fact pull out $(1-\epsilon)n/2$ perfect matchings in the first $(1-\epsilon)n/2$ steps.
