Generalizations and Variants of the Largest Non-crossing Matching Problem in Random Bipartite Graphs

2011/05/03 by Marcos Kiwi, José A. Soto, Kiwi, Marcos +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1105.0474

32 pages, 5 figures

arxiv created 2011/05/03 · arxiv updated 2011/05/04

Abstract

We are interested in the statistics of the length of the longest increasing subsequence of 2-rowed lexicographically sorted arrays chosen according to distinct families of distributions D = (D_n)_n, and when n goes to infinity. This framework encompasses well studied problems such as the so called Longest Increasing Subsequence problem, the Longest Common Subsequence problem, problems concerning directed bond percolation models, among others. We define several natural families of distinct distributions and characterize the asymptotic behavior of the expected length of a longest increasing subsequence chosen according to them. In particular, we consider generalizations to d-rowed arrays as well as symmetry restricted two-rowed arrays.

Related

• Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs
• Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs
• Longest increasing subsequences in pattern-restricted permutations
• A Conjecture on random bipartite matching
• On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation