# 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 at 21:36