Author | dc.contributor.author | Kiwi Krauskopf, Marcos | |
Author | dc.contributor.author | Loebl, Martín | es_CL |
Admission date | dc.date.accessioned | 2010-01-27T16:11:40Z | |
Available date | dc.date.available | 2010-01-27T16:11:40Z | |
Publication date | dc.date.issued | 2008-10-20 | |
Cita de ítem | dc.identifier.citation | ELECTRONIC JOURNAL OF COMBINATORICS Volume: 15 Issue: 1 Article Number: R135 Published: OCT 20 2008 | en_US |
Identifier | dc.identifier.issn | 1077-8926 | |
Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/125249 | |
Abstract | dc.description.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. | en_US |
Patrocinador | dc.description.sponsorship | MIDEPLAN ICM-P01-05
CONICYT FONDECYT 1010689
FONDAP in Applied Mathematics
Anillo en Redes ACT08
ICM-P01-05 | en_US |
Lenguage | dc.language.iso | en | en_US |
Publisher | dc.publisher | ELECTRONIC JOURNAL OF COMBINATORICS | en_US |
Keywords | dc.subject | RANDOM PERMUTATIONS | en_US |
Título | dc.title | Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs | en_US |
Document type | dc.type | Artículo de revista | |