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?
Thanks in advance! : )
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.