Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs
| dc.creator | Kiwi, Marcos | |
| dc.creator | Loebl, Martin | |
| dc.date | 2005-03-22 | |
| dc.date.accessioned | 2026-07-07T05:18:14Z | |
| dc.date.available | 2026-07-07T05:18:14Z | |
| dc.description | 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). | |
| dc.description | 13 pages, 7 figures | |
| dc.identifier | https://arxiv.org/abs/math/0503465 | |
| dc.identifier | http://arxiv.org/abs/math/0503465 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/74589 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.title | Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs | |
| dc.type | text |