Random "topology"

This dynamic picture shows the result in paper #43.

In paper #40, various other random division rules are studied. For example, if polygons are always divided by joining two adjacent sides (the choice of which from the k possibilities being equally likely), then for a randomly-sampled polygon, Sn-3 converges in distribution to a geometric distribution on {0,1,2,...} with mean 1. If the sampled polygon is on the original boundary, then S-3 converges to a geometric distribution on the same set with mean 2.16258. There is no convergence of S-3 for corner polygons.

Other division rules in #40 involve avoidance of, or liking for, polygons of x sides; then very subtle cliques of different polygonal types come into the analysis.

The main tools in this work (and in the problems mentioned below) are from the theory of multi-type branching processes.


Polygons can be divided up randomly in another interesting way. Choose a vertex of the polygon randomly and then join this vertex to a randomly-chosen side (excluding the two sides which are incident at the chosen vertex). Keep going, dividing all polygons in all generations. Eventually, only triangles and quadrilaterals are left. After this happens, the number of quadrilaterals remains static as the generation number n increases, whilst the number of triangles grows like 2n, dominating the quadrilaterals.

So let us simply start with k=3, namely, a triangle at generation 0. Divide it by choosing a vertex randomly (equally-likely choice). Join the vertex to the opposite side with a line. Then divide the two daughter triangles in the same random way, and so on. Ensure that, when the joining line hits the opposite side, the new vertex is a topological T, not a topological X as it could be if a joining line from another triangle hit at the same point. (Use some offset if two new lines are to abutt an existing one.)

What is the order of a randomly chosen vertex of the "tessellation" after n generations? Freshly generated vertices (with the initial T structure) have order 3, but the order of vertices increases whenever that vertex is chosen as the vertex-endpoint of a new dividing line. So, orders of 3, 4, 5, ... can be created, the population of vertices being constantly fed by fresh vertices of order 3. This question and others are answered in paper #74.


In paper #65, faces of a planar graph are "divided" randomly by the creation of new edges of the graph. A face (excluding the unbounded one) is said to be of type k  (k = 1, 2, ...) if the boundary of that face contains k edges. A journey around that boundary has k encounters with vertices, though these may not in general be k distinct vertices of the graph (due to the possibility of loops at a given vertex). We refer to the k encounters as the k "ports" of that face.

Each face is divided by a random rule whereby two ports of the face are randomly sampled with replacement. The two ports are then joined by a new edge; if the same port is sampled twice then the new edge is a loop.

The process can go on indefinitely. If, after n generations, a face is sampled and the type X observed, we find that as n gets large, X has the probability mass function

Curiously, X - 1 has a distribution which is the convolution of independent Poisson(1/2) and Bernoulli(1/2) variates.

Other random rules are considered in the paper.


Back to my random geometry page