2005/03/22 by Marcos Kiwi, Kiwi, Marcos, Martin Loebl +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #math.CO #math.PR
paper · pdf · doi:10.48550/arxiv.math/0503465
13 pages, 7 figures
arxiv created 2005/03/22 · openalex publication_date 2005/03/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We address the following question: When a randomly chosen regular bipartite multi--graph is drawn in the plane in the ``standard way'', what is the distribution of its maximum size planar matching (set of non--crossing disjoint edges) and maximum size planar subgraph (set of non--crossing edges which may share endpoints)? The problem is a generalization of the Longest Increasing Sequence (LIS) problem (also called Ulam's problem). We present combinatorial identities which relate the number of r-regular bipartite multi--graphs with maximum planar matching (maximum planar subgraph)of at most d edges to a signed sum of restricted lattice walks in \ZZd, and to the number of pairs of standard Young tableaux of the same shape and with a ``descend--type'' property. Our results are obtained via generalizations of two combinatorial proofs through which Gessel's identity can be obtained (an identity that is crucial in the derivation of a bivariate generating function associated to the distribution of LISs, and key to the analytic attack on Ulam's problem).