Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.