Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected matching?
[Math] Expected matching in a bipartite graph
bipartite-graphsco.combinatoricsgraph theorypr.probabilityrandom-graphs
Best Answer
If $p$ is fixed and does not depend on $n$, then by a result of Frieze and Melsted (http://www.math.cmu.edu/~af1p/Texfiles/cuckoo2.pdf), the probability that there exists a perfect matching is 1-o(1). In another word, the size of the maximal matching is $n$ with high probability.
The paper of Frieze and Melsted has the following theorem: Let $\Gamma$ be a bipartite graph chosen uniformly from the sets of graphs with bipartition $L$, $R$, $|L| = n$,$|R| = m$ such that each vertex of $L$ has degree $d \ge 3$ and each vertex of $R$ has degree at least two. Then with high probability, the size of the maximum matching in $\Gamma$ is $\min \{m, n\}$.
Though the above theorem does not directly answer the question here, in our setting we have $m = n$ and the mean degree of each vertex is $pn \gg 3$. So the conditions of the theorem should be satisfied with high probability and there exists a perfect matching.