Abstract

For a distribution script G sign 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 script G sign. 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 script G sign is the uniform distribution over the k-regular bipartite graphs on W and M. For k = o(n1/4), we establish that L(n)/?kn tends to 2 in probability when n ? ?. Convergence in mean is also studied. Furthermore, we show that if each of the n2 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.