# probability that adding the ith random edge will increase the size of maximum matching by 1

In a random graph of $i-1$ edges, I need to find the probability that adding the $i$-th random edge will increase the size of maximum matching by 1. Is there any way to calculate this probability or is it very difficult to get a closed form solution for it?

-
Do you have reasons to expect that such a probability will be independent of the number of vertices ? Or the way you choose an edge to add ? –  Sasha Feb 17 '12 at 19:14
@Sasha: It clearly depends on $n$, since it heads to zero pretty faster after $i=2n\log n$ or so (this is a loose statement). I'd say its hard to do like this, since having an augmenting path is not a local property, but various structure theorems for the connectivity transition should give good estimates on the size of a maximum matching. –  Louis Feb 17 '12 at 21:10