# Reconstructing a Monthly problem: tree growth on the 2D integer lattice

I'm trying to reconstruct a problem I saw in the Monthly, years ago. Perhaps it'll look familiar to someone.

In the integer lattice in the plane, we grow a tree in the following natural way: Initially the tree is just the origin. At each step, we find the set of lattice points that are neighbors (distance 1) to precisely one vertex of our tree, and add them (simultaneously) to the tree.

Thus on day 0 the tree is $\{(0,0)\}$; on day 1 it contains $\{(0,0), (1,0), (-1,0),(0,1),(0,-1)\}$; on day 2 it contains those vertices along with $(2,0),(-2,0),(0,2)$ and $(0,-2)$ (note that $(1,1)$ is not added because it has two neighbors already in the tree), and on day 3 we add 12 new vertices. It looks like a pretty familiar fractal.

The thing I'm not sure of is what exactly was asked of that tree... Possible candidates include its asymptotic density, some sort of simple formula to determine which lattice points ultimately make it into the tree and the # of vertices added on day $n$. There are lots of interesting questions and I'm happy to try and solve them but I prefer to work on the ones that were actually posed!

-

I think I got it. It seems to be problem 10360, originally published in 1994 (volume 101, issue 1, page 76), proposed by Richard Stanley. I'm looking at the JSTOR page of the solution (by Robin Chapman), which appeared in October 1998, volume 105, no 8, pages 769-771).

Here is the statement of the problem:

Let $L$ be the integer lattice in $\mathbb{R}^d$, i.e., the $L$ is the set of points $(x_1,x_2,\ldots,x_d)$ with all $x_j\in\mathbb{Z}$. Consider $L$ as a graph by declaring two lattice points to be adjacent if the distance between them is $1$. Define a sequence $S_0$, $S_1,\ldots$ of subsets of $L$ inductively as follows: \begin{align*} S_0 &= \Bigl\{ (0,0,\ldots,0)\Bigr\}\\ S_{n} &= \Bigl\{ P\in L-\mathop{\cup}\limits_{0\leq k\lt n}S_k\ \Bigm|\ \text{$P$ is adjacent to exactly one element of $\mathop{\cup}\limits_{0\leq k\lt n}S_k$}\Bigr\}. \end{align*} Let $S$ be the subgraph of $L$ whose vertices are $\cup S_n$. Thus, $P\in S$ is adjacent to $P'\in S$ if the distance between $P$ and $P'$ is $1$.

1. Find a simple condition for a point of $L$ to belong to $S$.
2. For $P\in S$, find a simple rule to determine $i$ such that $P\in S_i$.
3. How many elements are in $S_i$?
4. How many $P\in S_i$ are adjacent to no points in $S_{i+1}$?
5. Show that $S$ is a tree.
6. Investigate the (vertex) density of $S$ in $L$, and compare it to the largest density of a subset of $L$ for which the induced subgraph is a tree.
-
You seem to have linked to the UL Lafayette proxy for JSTOR. The actual link is jstor.org/pss/2589004 – Rahul Nov 27 '10 at 6:10
@Rahul Narain: Oops; thanks for the heads up. I fixed it. I logged in remotely through the UL proxy, as I'm not in my office, hence the wrong link. – Arturo Magidin Nov 27 '10 at 6:12
That's it! Thanks Arturo! – Alon Amit Nov 28 '10 at 2:58