English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We address the following question: When a randomly chosen regular bipartitemulti--graph is drawn in the plane in the ``standard way'', what is thedistribution of its maximum size planar matching (set of non--crossing disjointedges) and maximum size planar subgraph (set of non--crossing edges which mayshare endpoints)? The problem is a generalization of the Longest IncreasingSequence (LIS) problem (also called Ulam's problem). We present combinatorialidentities which relate the number of r-regular bipartite multi--graphs withmaximum planar matching (maximum planar subgraph) of at most d edges to asigned sum of restricted lattice walks in Z^d, and to the number of pairs ofstandard Young tableaux of the same shape and with a ``descend--type''property. Our results are obtained via generalizations of two combinatorialproofs through which Gessel's identity can be obtained (an identity that iscrucial in the derivation of a bivariate generating function associated to thedistribution of LISs, and key to the analytic attack on Ulam's problem).  We also initiate the study of pattern avoidance in bipartite multigraphs andderive a generalized Gessel identity for the number of bipartite 2-regularmultigraphs avoiding a specific (monotone) pattern.

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