Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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.
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.