Enumerating 2-convex self-avoiding polygons

by Will James

Institution: Department of Mathematics & Statistics, The University of Melbourne
Date: Thu 14th December 2006
Time: 3:15 PM
Location: Room 213, Richard Berry Building, The University of Melbourne

Abstract: Polygons are described as almost-convex if their perimeter differs from the perimeter of their minimum bounding rectangle by twice
their concavity index', $m$. Such polygons are called \emph{$m$-convex} polygons. James and Guttmann (Adv Appl Math 34(4) 2005) enumerated
1-convex polygons exactly using theinclusion-exclusion' principle. Around 5 years ago, Jensen and Guttmann calculated the generating function for 2-convex polygons from numerical series. In this seminar, I present the exact enumeration, which confirms Jensen and Guttmann's result.

I will first present the Hadamard product, which allows one to build objects by joining blocks together. I will then show how 2-convex
polygons are enumerated by splitting them at their indentations. The
inclusion-exclusion methodology in used to enumerate the individual
blocks.

For More Information: Dr. Iwan Jensen Phone: +61 3 8344 5214 I.Jensen@ms.unimelb.edu.au