Largest planar matching in random bipartite graphs

For a distribution over labeled bipartite (multi) graphs G = ( W, M, E ), | W | = | M | = n , let L ( n ) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n ) behavior of L ( n ) for different distributions . Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where is the uniform distribution over the k ‐regular bipartite graphs on W and M . For k = o ( n 1/4 ), we establish that \documentclass{article}\pagestyle{empty}\begin{document}$L(n) \slash \sqrt{kn}$\end{document} tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n 2 possible edges between W and M are chosen independently with probability 0 < p < 1, then L ( n )/ n tends to a constant γ p in probability and in mean when n → ∞. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 162–181, 2002