✦ LIBER ✦

Asymptotic Enumeration of Convex Polygons

✍ Scribed by Dudley Stark; Nicholas C. Wormald

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 413 KB
Volume: 80
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1997.2802

No coin nor oath required. For personal study only.

✦ Synopsis

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice Z d taking at least one step in every dimension. A polygon on Z d is said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number of d-dimensional convex polygons p n, d of length 2n with d(n) Ä is asymptotically

where r = r(n, d ) is the unique solution of r coth r = 2nÂd & 1 and b(r) = d(r coth r&r 2 Âsinh 2 r). The convergence is uniform over all d |(n) for any function |(n) Ä . When d is constant the exponential is replaced with (1&d &1 ) 2d .

These results are proved by asymptotically enumerating a larger class of combinatorial objects called convex proto-polygons by the saddle-point method and then finding the asymptotic probability a randomly chosen convex proto-polygon is a convex polygon.

📜 SIMILAR VOLUMES

Asymptotic enumeration of full graphs

✍ D. J. Kleitman; F. R. Lasaga; L. J. Cowen 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 539 KB

## Abstract A __full graph__ on __n__ vertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system of __n__ sets. It has an undirected edge between vertices representing intersecting sets, and a directed edge from __a__ to __b__ if the correspo

Entropy and Asymptotic Geometry of Non-S

Entropy and Asymptotic Geometry of Non-Symmetric Convex Bodies

✍ V.D. Milman; A. Pajor 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 171 KB

We extend to the general, not necessarily centrally symmetric setting a number of basic results of local theory which were known before for centrally symmetric bodies and were using very essentially the symmetry in their proofs. Some of these extensions look surprising. The main additional tool is a

An Optimal Algorithm for the Intersectio

An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons

✍ Shreesh Jadhav; Asish Mukhopadhyay; Binay Bhattacharya 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 224 KB

The intersection radius of a finite collection of geometrical objects in the plane is the radius of the smallest closed disk that intersects all the objects in the collection. Bhattacharya et al. showed how the intersection radius can be found in linear time for a collection of line segments in the

A Distributed Formation of Smallest Faul

A Distributed Formation of Smallest Faulty Orthogonal Convex Polygons in 2-D Meshes

✍ Jie Wu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 229 KB

The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant and deadlock-free routing algorithms in meshconnected multicomputers. The convexity of a rectangle facilitates simple and efficient ways to route messages around fault regions using relatively few v

Asymptotic enumeration of labeled multig

Asymptotic enumeration of labeled multigraphs by vertices, edges, and degree parities

✍ Edward A. Bender; L. Bruce Richmond 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

We show that the number of labeled (n, q)-multigraphs with some specified p vertices of odd degree is asymptotically independent of p and is in fact asymptotically 2'-" times the number of (n, q)-multigraphs. We determine the asymptotic number of (n, q)-multigraphs.

Asymptotic enumeration of tournaments wi

Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph

✍ Zhicheng Gao; Brendan D. McKay; Xiaoji Wang 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

This paper studies the probability that a random tournament with specified score sequence contains a specified subgraph. The exact asymptotic value is found in the case that the scores are not too far from regular and the subgraph is not too large. An ndimensional saddle-point method is used. As a s