Asymptotic Enumeration of Convex Polygons

Dudley Stark, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

Abstract

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice Zdtaking at least one step in every dimension. A polygon on Zdis said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number ofd-dimensional convex polygonspn,dof length 2nwithd(n)→∞ is asymptoticallypn,d~exp-2(2n-d)2n-1(2n-1)!(2πb(r)) -1/2r-2n+dsinhdr,wherer=r(n,d) is the unique solution ofrcothr=2n/d-1andb(r)=d(rcothr-r2/sinh2r). The convergence is uniform over alld≥ω(n) for any functionω(n)→∞. Whendis constant the exponential is replaced with (1-d-1)2d. These results are proved by asymptotically enumerating a larger class of combinatorial objects calledconvex proto-polygonsby the saddle-point method and then finding the asymptotic probability a randomly chosen convex proto-polygon is a convex polygon.

Original languageEnglish
Pages (from-to)196-217
Number of pages22
JournalJournal of Combinatorial Theory. Series A
Volume80
Issue number2
DOIs
Publication statusPublished - Nov 1997
Externally publishedYes

Cite this