\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Marcos Kiwi and Martin Loebl}
%
%
\medskip
\noindent
%
%
{\bf Towards the Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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 ${\Bbb 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.

\bye

.
