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 $L(n) slash sqrt{kn}$ tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n² 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