Mathematics – Combinatorics
Scientific paper
2005-03-22
Mathematics
Combinatorics
13 pages, 7 figures
Scientific paper
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 $\ZZ^d$, 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).
Kiwi Marcos
Loebl Martin
No associations
LandOfFree
Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-684557