# Expected maximum matching size in a random bipartite graphs

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$$.

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.

• 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)$. Nov 8, 2023 at 21:36
• @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?
– D.W.
Nov 9, 2023 at 6:28
• @BernardoSubercaseaux Do you have any idea about when $p = O(1/n)$. Nov 29, 2023 at 13:05