Mathematics – Combinatorics
Scientific paper
2007-01-26
Mathematics
Combinatorics
38 pages, 22 figures
Scientific paper
We deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings, and ice models. The notion of orientations with out-degrees prescribed by a function $\aa:V\to \NN$ unifies many different combinatorial structures, including the afore mentioned. We call these orientations $\aa$-orientations. The main focus of this paper are bounds for the maximum number of $\aa$-orientations that a planar map with $n$ vertices can have, for different instances of $\aa$. We give examples of triangulations with $2.37^n$ Schnyder woods, 3-connected planar maps with $3.209^n$ Schnyder woods and inner triangulations with $2.91^n$ bipolar orientations. These lower bounds are accompanied by upper bounds of $3.56^n$, $8^n$ and $3.97^n$ respectively. We also show that for any planar map $M$ and any $\alpha$ the number of $\alpha$-orientations is bounded from above by $3.73^n$ and describe a family of maps which have at least $2.598^n$ $\alpha$-orientations.
Felsner Stefan
Zickfeld Florian
No associations
LandOfFree
On the Number of Planar Orientations with Prescribed Degrees 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 On the Number of Planar Orientations with Prescribed Degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Number of Planar Orientations with Prescribed Degrees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-568471