Embedding the Infinite Binary Tree in Regular Tilings

Consider the regular tiling $(m,n)$ in which $m$ $n$-agons meet at each vertex. Most of the time this tilings have to "live" in the hyperbolic plane. The edges of its polygons define a graph where two vertices are adjacent if they share an edge of a polygon. I would like to prove that most of these graphs have the infinite binary tree as a subgraph.

Of course, it would be impossible to show this for the regular tiling $(4,4)$ because the amount of vertices at a given distance from a given vertex grows quadratically, not exponentially like in the binary tree. However, for most $(m,n)$ this growth is exponential and so the infinite binary tree could fit. By staring at images of these tilings this seems completely plausible, but I am having troubles formalizing it.

I have been able to prove that this indeed happens in $(4,5)$. I tried to use Cayley graph's arguments but got lost. So basically I have the following questions:

• How can I know if the graph I described for $(m,n)$ is the Cayley graph of a group? And if so, is it the Cayley graph of a well-known group?
• Is my Cayley argument too complicated and there is a simpler proof?
• Do you have any tips for drawing the $(m,n)$ tiling?
• Can you help me with this proof or point me to some theory that may help?

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.

• Hi joriki. Thank you for your answer. There are some very helpful remarks on it. However, I am having trouble with what do "they will not meet" means precisely. Thank you anyways, I will wait a bit more and probably mark your answer as accepted. – Leo Apr 26 '11 at 22:08

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?

• Thank you Matt. These remarks are helpful. Can you help me in saying precisely that "the region has an infinite L of squares as its boundary". I mean, visually is very convincing, but how can I prove that this L region is indeed infinite? I am a bit stuck with that. – Leo Apr 26 '11 at 22:16
• The centers of the squares are connected by two straight lines that themselves form an L, meeting at 90°. Two lines can intersect in at most one point, so we can be sure they don't meet again out in the distance. How can we be sure that the row of squares on one side of the L is in fact the boundary of the binary tree? This only requires local reasoning around each vertex, and has very little to do with hyperbolic geometry. Picking "the middle two vertices of the four options" directly extends the row of squares on both sides, while inserting a new L between them. – Matt Apr 26 '11 at 23:21