1
$\begingroup$

What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed $p$. If a general formula doesn't exist how about for $p = 0.5$ or some other $p$.

$\endgroup$

1 Answer 1

2
$\begingroup$

There is not likely to be any exact formula, but we can investigate the asymptotic behavior. If $p$ is a little bit larger than $(\log n)/n$, then with high probability there exists a maximum matching, so the expected size of the maximum matching is close to $n$. See https://math.stackexchange.com/q/1267387/14578.

So the only interesting case is where $p < (\log n)/n$. I don't have an estimate for that case, but perhaps someone else will be able to handle that case.

$\endgroup$
3
  • $\begingroup$ Can we extend this to smaller values of $p$ as follows? Let $f(n)$ be the size of the expected maximum matching on a random $(n, n)$ bipartite graph where each cross-edge is present independently with probability $(\log n)/n$. It seems that $f(n) = n - o_n(1)$, right? Then split both $A$ and $B$ into $n/k$ parts of size $k$ each, with $k$ the smallest integer such that $p \geq (\log k)/k$. Now, the expected maximum matching for $(A, B)$ is at least $n/k$ times the expected maximum matching for $(A_1, B_1)$, and that is at least $f(k)$, so we get $n/k \cdot f(k) = n - n/k \cdot o_k(1)$. $\endgroup$ Nov 8, 2023 at 21:36
  • $\begingroup$ @BernardoSubercaseaux, ooh, that is clever! For what it is worth, that looks valid to me, as far as I can tell -- but I'm not an expert on this so I don't have great confidence in my own judgement. I like it. Thank you. Perhaps you might be interested to write your own answer with this improved bound? $\endgroup$
    – D.W.
    Nov 9, 2023 at 6:28
  • $\begingroup$ @BernardoSubercaseaux Do you have any idea about when $p = O(1/n)$. $\endgroup$
    – Anonymous
    Nov 29, 2023 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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