Embedding the Infinite Binary Tree in Regular Tilings

Solution 1:

I'm not sure of this and I don't have a formal proof, but I think the answer should be that this is impossible iff $m\le3$ or $m=n=4$.

For $m\le3$, look at this image. (Note that their ${p,q}$ is reversed with respect to your $(m,n)$.) If you put the root at some vertex (say, the one in the centre), all choices for the two first branches are equivalent. From then on, there are no choices left, and you're forced to go around one of the $n$-gons until two leaves coincide. This will be the case whenever $m=3$. Obviously the situation is even worse for $m=2$.

For $m=n=4$, you already pointed out why it's impossible. So it remains to be shown that it's possible if $m>4$ or $n>4$.

For $m>4$, look at this image. Starting at the vertex in the centre, choose two adjacent edges, and then always choose the middle two vertices of the four options. It seems clear from the image that these branches can't collide, and I think it shouldn't be too difficult to prove it formally by adding up the angles or something like that. Things can only get better if you increase $m$ further, since that will just generate more branchings in between the chosen ones, and increasing $n$ will squash things into a smaller angle range but shouldn't reduce the options for the branches. (I'm aware some of this is quite handwaving, but it feels right and could point the way towards a formal proof.)

For $n>4$, look at this image. (This is the one that you've already proved possible.) Starting at the vertex in the centre, choose any two adjacent edges. When you reach a vertex, always choose the edge that continues straight and the one that makes a turn towards the sibling branch. (Imagine a street sign "Right branch turns left". :-) Here, too, it seems clear that these branches won't meet, and that increasing $n$ or $m$ can't close off this option.

Solution 2:

Just to finish joriki's solution...

Both of these algorithms have the property that the region between the left subtree and the right subtree is the same shape at every vertex of the tree. So we just need to prove that this region is infinite, i.e. that the two subtrees don't collide.

In the first picture, for example, the region has an infinite L of squares as its boundary.

To prove that things only get better with larger m or n, consider the path connecting the centers of the polygons touching the boundary (with even a vertex). Increasing m or n will only add turns in the "safe" direction (making the region between the subtrees even bigger).

The same approach works for the m≥4, n>4 algorithm. When n=5, the two branches of the L start out the same (the angle is 0°), but they soon start angling in the safe direction. (Even if they didn't, the single strip of n-gons would suffice for separating the two subtrees.)

Further questions:

This question could be could be asked not just for binary trees but for q-ary trees.

Are there any (m,n,q) combinations for which the tree "just fits", i.e. there is not enough space between subtrees to place an infinite line?