Premium
Largest planar matching in random bipartite graphs
Author(s) -
Kiwi Marcos,
Loebl Martin
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10048
Subject(s) - combinatorics , bipartite graph , subsequence , mathematics , longest common subsequence problem , matching (statistics) , longest increasing subsequence , planar graph , distribution (mathematics) , plane (geometry) , discrete mathematics , geometry , graph , statistics , mathematical analysis , bounded function
Abstract 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