2
$\begingroup$

We can put a metric on the set of isomorphism classes of connected, locally finite rooted graphs as follows:

Let $G$, $H$ be locally finite graphs, and let $u \in V(G)$ be a vertex of $G$, $v \in V(H)$ be a vertex of $H$. Define $R((G,u),(H,v))$ to be the largest number such that $(B_G(u,R),u)$ is isomorphic to $(B_H(v,R),v)$, where $B_G(u,R)$ is the subgraph of $G$ induced by the set of vertices that can be reached by starting at $u$ and traversing at most $R$ edges. We then define the distance between $(G,u),(H,v)$ to be

$$d((G,u),(H,v)) := 2^{-R((G,u),(H,v))}.$$

Let's call the topology on the set of isomorphism classes of rooted connected locally finite graphs induced by this metric the local topology.

Here is my question: for which connected locally finite graphs $G$ is the set $$ \{ (G,v) \}_{v \in V(G)} $$ compact in the local topology?

Some observations: It is easy to see that if a graph has unbounded degree, then the above set is not compact, so we may restrict ourselves to bounded degree graphs. It happens that for each $D$ the set of (isomorphism classes of) connected locally finite rooted graphs of maximum degree at most $D$ is compact in the local topology. So if $G$ is any bounded degree graph, the above set is precompact, so it actually suffices to see whether the set is closed in the local topology.

If $G$ is vertex-transitive (i.e. the action of $Aut(G)$ on $V$ has a single orbit), then the above set is actually a single point, hence compact. Similarly, if $G$ is "almost-vertex-transitive", that is, the action of $Aut(G)$ on $V$ has only finitely many orbits, then the above set is finite and hence compact. (The above set being finite is actually equivalent to almost-vertex-transitivity). So the only case left is if the above set is not finite but is still compact. (Note also that since $V(G)$ is countable, the above set is at most countable; when I first thought about this I wondered if some examples could come from aperiodic tilings or something, but these examples are quickly disqualified once you realize that the set of limit points is uncountable).

So, short of a complete classification, my question is whether there are any "interesting" examples. That is: Is there any (infinite, bounded degree) connected graph $G$ such that the set $\{(G,v)\}_{v \in V(G)}$ is countably infinite, but is still closed (hence compact) in the local topology?

Of course, if the answer to this question is "no" then it is a complete classification, and it would be quite interesting, but if the answer is "yes" I would be very interested to know any examples.

$\endgroup$

1 Answer 1

3
$\begingroup$

The answer is no.

The reason is that in such a graph, every vertex $v$ is a limit point in the local topology, and a nonempty closed set in which every point is a limit is uncountable. As the latter claim is standard, we only prove the former claim.

Let $u$ be a limit point in the local topology, as the local topology is compact. Let $v$ be any vertex in $G$ and let $D$ be the graph distance from $u$ to $v$.

As $u$ is a limit point, there exists a sequence of different vertices $u_1$, $u_2$, $...$ in $G$ and subgraph isomorphisms $f_1$, $f_2$, $...$ where $f_i : B_G(u_i,i) \rightarrow B_G(u,i)$. As the graph is locally finite, we can make the graph distance from $u_i$ to every vertex before it larger than $2D$ by taking a subsequence of the sequence $\{u_i\}$.

For $i>D$, let $v_i=f_i^{-1}(v)$. Then $f_i$, restricted on $B_G(v_i,i-D)$, is a subgraph isomorphism onto $B_G(v,i-D)$, and $d((G,v),(G,v_i)) \leq 2^{-(i-D)}$. If $v_i$ is the same as any vertex $v_j$ before it, then the graph distance between $u_i$ and $u_j$ will be at most $2D$, but this contradicts our assumption about $u_i$. So all the $v_i$s are pairwise different.

So $v$ has arbitrarily close vertices in the local topology and hence is a limit point.

$\endgroup$
2
  • $\begingroup$ Thank you, beautiful answer! (One thing, I think you have a typo and meant to write $v_i = f_i^{-1}(v)$, not $f_i^{-1}(u)$ right?) $\endgroup$ Jan 9, 2022 at 19:40
  • 1
    $\begingroup$ Yes, you are correct. $\endgroup$ Jan 9, 2022 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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