Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs

Abstract

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 sub-graph (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 Z(d), and to the number of pairs of standard Young tableaux of the same shape and with a "descend-type" property. Our results are derived 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 the length of LISs, and key to the analytic attack on Ulam's problem). Finally, we generalize Gessel's identity. This enables us to count, for small values of d and r, the number of r-regular bipartite multi-graphs on n nodes per color class with maximum planar matchings of size d. Our work can also be viewed as a first step in the study of pattern avoidance in ordered bipartite multi-graphs.