A Census of Vertices by Generations in Regular Tessellations of the Plane

Alice Paul, Nicholas Pippenger

Abstract


We consider regular tessellations of the plane as infinite graphs in which $q$ edges and $q$ faces meet at each vertex, and in which $p$ edges and $p$ vertices surround each face. For ${1/p + 1/q = 1/2}$, these are tilings of the Euclidean plane; for ${1/p + 1/q < 1/2}$, they are tilings of the hyperbolic plane. We choose a vertex as the origin, and classify vertices into generations according to their distance (as measured by the number of edges in a shortest path) from the origin. For all $p\ge 3$ and $q \ge 3$ with ${1/p + 1/q\le1/2}$, we give simple combinatorial derivations of the rational generating functions for the number of vertices in each generation.


Full Text: PDF ADDENDUM