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$.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\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$ Commented 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. ♦Commented Nov 9, 2023 at 6:28
-
$\begingroup$ @BernardoSubercaseaux Do you have any idea about when $p = O(1/n)$. $\endgroup$ Commented Nov 29, 2023 at 13:05