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}$?


1 Answer 1


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.

  1. 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.
  2. 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.

  • $\begingroup$ I'm just wondering if this models the same process i was describing, do they take a random graph and then destroy the edges? In my process i'm building a random graph $n$ times, i'm just wondering if their work touches on this idea? $\endgroup$ Jul 17, 2015 at 11:57
  • $\begingroup$ Could you perhaps explain how i can use their result each time i build a new bipartite graph? $\endgroup$ Jul 17, 2015 at 12:07
  • $\begingroup$ You take a genuinely random graph then pass to some subgraph. Sudakov and Vu say that provided you didn't throw away more than half of the edges at any vertex then you have a perfect matching in what's left. In your case, at each stage you generate a random graph then throw away the edges that have already been used in some matching. You have to check that this isn't more than half of the edges at any vertex, which it won't be if you have yet to use more than half the edges of $K_{n,n}$. $\endgroup$
    – Ben Barber
    Jul 17, 2015 at 13:20
  • $\begingroup$ Ahh ok this makes sense, so the edges i'm throwing away from my random graph need not be random themselves? I can 'pick' how i'd like to try and break the property but i'd still have no luck if i was breaking less than half of the edges. Is this what you're essentially saying? $\endgroup$ Jul 20, 2015 at 8:51
  • $\begingroup$ Exactly. If you throw away random edges then you're really just choosing a slightly smaller random graph in the first place. $\endgroup$
    – Ben Barber
    Jul 20, 2015 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.