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

@article{a05c589ee6ab4d82b6cdeabf99265648,
title = "Asymptotic Enumeration of Convex Polygons",
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.",
author = "Dudley Stark and Wormald, {Nicholas C.}",
year = "1997",
month = "11",
doi = "10.1006/jcta.1997.2802",
language = "English",
volume = "80",
pages = "196--217",
journal = "Journal of Combinatorial Theory - Series A",
issn = "0097-3165",
publisher = "Elsevier",
number = "2",

}

Asymptotic Enumeration of Convex Polygons. / Stark, Dudley; Wormald, Nicholas C.

In: Journal of Combinatorial Theory. Series A, Vol. 80, No. 2, 11.1997, p. 196-217.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Asymptotic Enumeration of Convex Polygons

AU - Stark, Dudley

AU - Wormald, Nicholas C.

PY - 1997/11

Y1 - 1997/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0038879441&partnerID=8YFLogxK

U2 - 10.1006/jcta.1997.2802

DO - 10.1006/jcta.1997.2802

M3 - Article

AN - SCOPUS:0038879441

VL - 80

SP - 196

EP - 217

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

IS - 2

ER -