On a theorem of Halin

Abstract

This note presents a new, elementary proof of a generalization of a theorem of Halin to graphs with unbounded degrees, which is then applied to show that every connected, countably infinite graph G, with $\aleph _0 \le |{\text {Aut}}(G)| < 2^{\aleph _0}$ and subdegree-finite automorphism group, has a finite set F of vertices that is setwise stabilized only by the identity automorphism. A bound on the size of such sets, which are called distinguishing, is also provided. To put this theorem of Halin and its generalization into perspective, we also discuss several related non-elementary, independent results and their methods of proof.

1 Introduction

This is an homage to Halin and his seminal paper from 1973 on automorphisms and endomorphisms of infinite, locally finite graphs [9]. It focusses on Theorem 6 of that paper, which asserts that a locally finite, connected graph with infinite automorphism group has a finite base if and only if its automorphism group is countable.

Halin and most graphs theorists were seemingly not aware of the fact that stronger forms of this theorem, which did not need the assumption of local finiteness, had already been published in 1968 in the language of infinitary languages by Kueker ([11, Theorem 2.1]) and 1970 in the language of mathematical logic by Reyes ([12, Theorem 2.2.2]). In 1987, Evans ([8, Theorem 1.1]) published a version more accessible to graph theorists in Archiv der Mathematik. It implies that Halin’s Theorem 6 from [9] holds without the assumption of local finiteness. We formulate this as Theorem 2 and derive it with an elementary argument inspired by Halin’s original proof.

We then apply this result to show that every graph with a finite base and infinite automorphism group that is subdegree finite¹ contains a set that is (setwise) stabilized only by the identity automorphism² and that the size of this set is less than three times the size of the base, see Theorem 3. This generalizes [4, Theorem 3.2] from locally finite graphs to graphs of larger valence.

In the last section we discuss Evans’ and other approaches in more detail. These approaches take recourse to results about topological and metric spaces, including a theorem of Baire, and usually yield more general results.

We conclude with the problem of extending Halin’s theorem to uncountable graphs.

2 Preliminaries

We focus on connected, countably infinite graphs G with unbounded degrees and are interested in sets of vertices that are only (setwise) stabilized by the trivial automorphism. Such sets are called distinguishing. Not every graph has such a set, but if it does, then we call the minimum size of such a set the distinguishing cost $\rho (G)$ of G. There are large classes of infinite graphs that have such sets, and often $\rho (G)$ is finite. These are the graphs we are interested in.

The distinguishing cost was introduced and studied by Boutin [3] for finite graphs. Infinite graphs with finite cost were treated for the first time in [4]. These investigations did not cover graphs with infinite degrees, that is, they were restricted to locally finite graphs.

Recall that the set stabilizer of $S \subseteq V(G)$, denoted ${\text {Aut}}(G)_S$, is the set of all automorphisms $\varphi$ for which

$$\begin{aligned} \varphi (x) \in S \iff x\in S. \end{aligned}$$

We also say that S is invariant under $\varphi$, or that $\varphi$ preserves S, and write $\varphi (S)=S$. The point stabilizer of S, denoted by ${\text {Aut}}(G)_{(S)}$ is the set of all $\varphi \in {\text {Aut}}(G)$ for which $\varphi (x)=x$ for all $x\in S$. If A is a set of automorphisms and $x \in V(G)$, then the orbit A(x) of x under the action of A is the set $\{\varphi (x) : \varphi \in A\}$.

A base of ${\text {Aut}}(G)$ is a set of vertices S whose point stabilizer is trivial, and the determining number of the graph G, denoted by ${\det }(G)$, is the minimum size of a base of G. Clearly every distinguishing set also is a base. Theorem 3 below estimates the cost as a function of the size of $\det (G)$. It generalizes [4, Theorem 3.2] for locally finite graphs.

Notice that every base S has the property that whenever $\varphi , \psi \in {{\text {Aut}}}(G)$ so that $\varphi (x)=\psi (x)$ for all $x\in {S}$, then $\varphi =\psi$. Thus every automorphism of G is uniquely determined by its action on the vertices of a base.

Furthermore, for $F\subseteq V(G)$, an automorphism $\varphi \in {\text {Aut}}(G)_F$ can be thought of as a permutation in ${\text {Sym}}(F)$ by restricting the action of $\varphi$ to F, denoted $\varphi |F$. Thus we have a natural map ${\text {Aut}}(G)_F \rightarrow {\text {Aut}}(G)|F \le {\text {Sym}}(F)$. Note that this map is injective if and only if F is a base for G. In this case ${\text {Aut}}(G)_F \cong {\text {Aut}}(G)|F$. If F is a finite base for ${\text {Aut}}(G)$, then ${\text {Aut}}(G)_F$ is a finite group.

The class of connected, locally finite, infinite graphs is usually denoted by $\Gamma$. Graphs in $\Gamma$ have the property that the orbits of all point stabilizers are finite. Automorphism groups with this property are called subdegree-finite. We do not require subdegree-finiteness for Theorem 2, but for Theorem 3 it is essential.

The motion of an automorphism $\varphi \in {\text {Aut}}(G)$, denoted ${\text {m}}(\varphi )$, is the number of vertices moved by $\varphi$. The motion of the graph G, denoted by ${\text {m}}(G)$, is the minimum motion of the nontrivial elements of ${\text {Aut}}(G)$.

The vertices of a graph with a distinguishing set obviously admit a 2-coloring that is only preserved by the identity automorphism. Such a coloring is called a distinguishing 2-coloring. These colorings are a special case of distinguishing d-colorings, where the vertices of a graph G are labeled with the integers $1,\ldots , d$ in such a way that only the trivial automorphism preserves the colors. A graph with such a coloring is called d-distinguishable. This concept was introduced by Albertson and Collins [1] and initiated a wealth of results for both finite and infinite graphs. For infinite graphs, [10] gives a good introduction with numerous further references to finite and infinite graphs. But, we also wish to point out a paper of Babai [2] from 1977, in which he proves, in a different setting, deep results about distinguishing infinite graphs.

3 Halin’s theorem for graphs with unbounded degrees

In this section we extend Halin’s theorem, which is listed below, to countable, connected graphs that are not in $\Gamma$.

Theorem 1

(Halin [9]) A connected, locally finite, infinite graph G has uncountable ${\text {Aut}}(G)$ if and only if for every finite $F \subset V(G)$ there exists a nontrivial automorphism $\varphi$ of G such that $\varphi (v) = v$ for each $v \in F$.

In other words, this theorem says that a graph $G \in \Gamma$ has countable automorphism group if and only if it has a finite base. We are interested in graphs with infinite automorphism group and prove the following extension to Halin’s Theorem, which is the graph theoretic version of Kueker [11, Theorem 2.1] and Evans [8, Theorem 1.1]. Notice that Kueker’s result precedes that of Halin, but not the one of Evans. Interestingly, Evans’ paper also contains an outline of an elegant proof of Evans’ Theorem suggested by Theo Grundhöfer which invokes Baire’s Theorem (see Sect. 5).

We now give the extension of Theorem 1 and its elementary combinatorial proof.

Theorem 2

Let G be a graph with countably many vertices. Then ${\text {Aut}}(G)$ is countable or has cardinality $2^{\aleph _0}$, with ${\text {Aut}}(G)$ countable if and only if ${\text {Aut}}(G)$ has a finite base.

Proof

The theorem is obviously true if G is finite. Suppose $F \subseteq V(G)$. The set of images of F under ${\text {Aut}}(G)$ has cardinality $|{\text {Aut}}(G) : {\text {Aut}}(G)_F| \le \aleph _0$. If F is a finite base for ${\text {Aut}}(G)$, then ${\text {Aut}}(G)_F$ is a finite group and $|{\text {Aut}}(G)| = |{\text {Aut}}(G) : {\text {Aut}}(G)_F| \cdot |{\text {Aut}}(G)_F : {\text {Aut}}(G)_{(F)}|$. Hence ${\text {Aut}}(G)$ is countable.

Assume that ${\text {Aut}}(G)$ has no finite base, that is, to every finite set $F \subseteq V(G)$ there exists a nontrivial automorphism of G that fixes every element of F. Fix some enumeration $\{v_0, v_1, v_2, \ldots \}$ of V(G). Let E be the set of all infinite sequences $\{ \epsilon = (\epsilon _0, \epsilon _1, \epsilon _2, \ldots ) : \epsilon _i \in \{0, 1\} \}$.

We will presently be defining inductively, for each integer $i \ge 0$, a finite set $F_i$, a vertex $x_i$, and an automorphism $\varphi _i$ which fixes each vertex in $F_i$ but does not fix $x_i$. To simplify our notation, for each $\epsilon = (\epsilon _0, \epsilon _1, \ldots ) \in E$, let $\alpha _i^\epsilon$ denote the automorphism $\varphi _0^{\epsilon _0} \cdots \varphi _i^{\epsilon _i}$ and let $\alpha _i^{-\epsilon }$ denote the automorphism $\varphi _i^{-\epsilon _i} \cdots \varphi _0^{-\epsilon _0}$; write $\alpha _i^E := \{\alpha _i^\epsilon : \epsilon \in E\}$ and $\alpha _i^{-E} := \{\alpha _i^{-\epsilon } : \epsilon \in E\}$. Note that $\alpha _i^E$ and $\alpha _i^{-E}$ are finite sets of automorphisms and each set contains the identity automorphism. We will write $\alpha _i^E(F_i)$ (resp. $\alpha _i^{-E}(F_i)$) to denote the set of all images of vertices in $F_i$ under automorphisms in $\alpha _i^E$ (resp. $\alpha _i^{-E}$). Note that $\alpha _i^{E}(F_i)$ and $\alpha _i^{-E}(F_i)$ are also finite sets.

Let us now begin our inductive construction. Take $F_0$ to be any finite set of vertices containing $v_0$ and let $\varphi _0$ be an automorphism that fixes every vertex of $F_0$, but which is not the identity. Then there exists a vertex $x_0$ that is moved by $\varphi _0$.

Let $F_1$ be a finite set of vertices containing $\alpha ^E_0(F_0) \cup \alpha ^{-E}_0(F_0) \cup \{x_0, v_1\}$. By assumption, there exists an automorphism $\varphi _1$ which fixes every vertex in $F_1$ but does not fix some vertex $x_1$.

Suppose, in addition, that for all integers i satisfying $1 < i \le k$ we have chosen a finite set $F_i$ which contains $\alpha _{i-1}^E(F_{i-1}) \cup \alpha _{i-1}^{-E}(F_{i-1}) \cup \{x_{i-1}, v_{i}\}$, and we have chosen a nontrivial automorphism $\varphi _i$ which fixes every vertex in $F_i$ but does not fix $x_i$. Let $F_{k+1}$ be a finite set of vertices containing $\alpha _k^E(F_k) \cup \alpha _k^{-E}(F_k) \cup \{x_k, v_{k+1}\}$. By assumption, there exists an automorphism $\varphi _{k+1}$ which fixes every vertex in $F_{k+1}$ but does not fix some vertex $x_{k+1}$.

Thus, we have $v_k \in F_k$ for all $k \ge 0$, with $F_0 \subseteq F_1 \subseteq \cdots$ and $\bigcup _{k = 0}^\infty F_k = V(G)$. If $\ell > k \ge 0$ and $\epsilon \in E$, then for all $v \in F_k$ we have $\alpha _k^{\pm \epsilon }(v) \in F_{k+1} \subseteq F_\ell$. Hence, one may easily verify that

$$\begin{aligned} \alpha _k^\epsilon (v) = \alpha _\ell ^\epsilon (v) \quad \text {and} \quad \alpha _k^{-\epsilon }(v) = \alpha _\ell ^{-\epsilon }(v). \end{aligned}$$

We now define, for each $\epsilon \in E$, a map $\alpha ^\epsilon : V(G) \rightarrow V(G)$ via

$$\begin{aligned} \alpha ^\epsilon (v_k) := \alpha _k^\epsilon (v_k) \quad \quad \text {for all }k \ge 0. \end{aligned}$$

Each map is well-defined on its domain $V(G) = \{v_0, v_1, \ldots \}$. For all $v_k, v_\ell \in V(G)$ choose an integer $N > \max (k, \ell )$ and note that the following statements hold:

$$\begin{aligned} \alpha ^\epsilon (v_k) = \alpha _N^\epsilon (v_k), \quad \alpha ^\epsilon (v_\ell ) = \alpha _N^\epsilon (v_\ell ) . \end{aligned}$$

Since $\alpha _N^\epsilon \in {\text {Aut}}(G)$ it follows immediately that $\alpha ^\epsilon$ is injective. If $v_\ell = \alpha _k^{-\epsilon }(v_k)$, then $v_\ell = \alpha _N^{-\epsilon }(v_k)$ and so $\alpha ^\epsilon (v_\ell ) = \alpha _N^\epsilon (v_\ell ) = \alpha _N^\epsilon (\alpha _N^{-\epsilon }(v_k)) = v_k$. Hence $\alpha ^\epsilon$ is also surjective, and so we may be certain that $\alpha ^\epsilon$ is a permutation of V(G).

For any (finite) ordered n-tuple $(w_1, \ldots , w_n)$ of elements in V(G), there exists $N \in {\mathbb {N}}$ such that $\{w_1, \ldots , w_n\} \subseteq \{v_0, \ldots , v_N\}$, and so:

$$\begin{aligned} \alpha ^\epsilon \left( (w_1, \ldots , w_n) \right) = \alpha _m^\epsilon \left( (w_1, \ldots , w_n) \right) \quad \quad \text {for all }m > N. \end{aligned}$$

(1)

It is now easy to see that $\alpha ^\epsilon$ is an automorphism of G: the image of any edge or non-edge $\{w_1, w_2\}$ in G under $\alpha ^\epsilon$ is the same as its image under the automorphism $\alpha _{N+1}^\epsilon$.

Finally, we wish to show that $\alpha ^\pi \ne \alpha ^\epsilon$ for any pair $\epsilon , \pi$ of distinct elements in E. For, let k be the smallest index such that $\pi _k\ne \epsilon _k$. We can assume that $\varphi _k^{\epsilon _k} = \varphi _k$ and $\varphi _k^{\pi _k} = \mathrm{id}$.

We know that there is some $v \in F_{k+1}$ such that $v \ne \varphi _k(v) = \varphi _k^{\epsilon _k}(v)$. Now $v = v_\ell$ for some integer $\ell \ge 0$. Since $v_\ell \in F_\ell$, we must have $\ell > k$. Hence $\alpha ^\epsilon (v) = \alpha _\ell ^\epsilon (v) = \alpha _{k+1}^\epsilon (v)$. Because $v = \varphi _k^{\pi _k}(v)$ we infer

$$\begin{aligned} \alpha ^\epsilon (v)= & {} (\varphi _0^{\epsilon _0}\varphi _1^{\epsilon _1} \cdots \varphi _{k-1}^{\epsilon _{k-1}}) \varphi _{k}^{\epsilon _k}(v)\\= & {} (\varphi _0^{\pi _0}\varphi _1^{\pi _1} \cdots \varphi _{k-1}^{\pi _{k-1}})\varphi _{k}^{\epsilon _k}(v)\\\ne & {} (\varphi _0^{\pi _0}\varphi _1^{\pi _1} \cdots \varphi _{k-1}^{\pi _{k-1}})\varphi ^{\pi _k}(v)\\= & {} \alpha ^\pi (v) \end{aligned}$$

This means that the $2^{\aleph _0}$ automorphisms $\alpha ^\epsilon$, for $\epsilon \in E$, are all distinct. $\square$

We do not know how to extend Theorem 2 to graphs of higher cardinality although this may be feasible by the results of Kueker [11] and Reyes [12] (see Section 5.1).

4 A bound on the distinguishing cost

Given a graph with finite base it is not a priori clear whether it has finite 2-distinguishing cost. We show in Theorem 3 that this is the case for graphs that have subdegree-finite automorphisms groups.

We need several lemmas for the proof of Theorem 3. The first one is easy and well-known.

Lemma 1

If G has a finite base and if ${\text {Aut}}(G)$ is subdegree-finite, then all stabilizers of finite sets of vertices are finite.

Proof

Suppose F is a finite set of vertices. Clearly $|{\text {Aut}}(G)_F : {\text {Aut}}(G)_{(F)}|$ is finite, and so ${\text {Aut}}(G)_F$ is finite if and only if ${\text {Aut}}(G)_{(F)}$ is finite.

Let B be a finite base for G and suppose ${\text {Aut}}(G)$ is subdegree-finite. For any vertex v, the set $C = {\text {Aut}}(G)_v(B)$ is finite because all orbits of ${\text {Aut}}(G)_v$ are finite. Because C contains B, it is a base for G. Hence, distinct automorphisms in ${\text {Aut}}(G)_C$ cannot induce the same permutation of the finite set C, so ${\text {Aut}}(G)_C$ must be finite. Because C is stabilized by ${\text {Aut}}(G)_v$, it follows that ${\text {Aut}}(G)_v$ is finite. Therefore the point stabilizer ${\text {Aut}}(G)_{(F)}$ is finite.

$\square$

Lemma 2

Suppose G is a graph with a finite base. If the automorphism group of G is infinite, then it has an infinite orbit.

Proof

Let B be a finite base of G, and suppose all orbits of ${\text {Aut}}(G)$ are finite. Then $D:={\text {Aut}}(G)(B)$ is a finite set which is stabilized by ${\text {Aut}}(G)$. Moreover, D is a base for G because it contains B. Since no two distinct automorphisms in ${\text {Aut}}(G)$ can induce the same permutation of D, it follows immediately that ${\text {Aut}}(G)$ is finite. $\square$

The following two lemmas are similar to Lemma 2.1 and Theorem 3.4 (iii) of [10].

Lemma 3

If ${\text {Aut}}(G)$ is subdegree-finite and has an infinite orbit then, for any two finite sets of vertices Y, Z of G, there exists an element $\alpha \in {\text {Aut}}(G)$ such that $Y\cap \alpha (Z)=\emptyset$.

Proof

Suppose a vertex x lies in an infinite orbit of ${\text {Aut}}(G)$. Then there exists an infinite sequence $S=\{\alpha _i \in {\text {Aut}}(G) : i \in {\mathbb {N}}\} \subseteq {\text {Aut}}(G)$ such that $\alpha _i^{-1} x = \alpha _j^{-1} x$ if and only if $i = j$. Suppose there exist finite sets of vertices Y and Z such that $Y \cap \alpha _i (Z) \ne \emptyset$ for infinitely many $i\in {\mathbb {N}}$. Then there exist $y \in Y$ and $z \in Z$ and an infinite subsequence $\{\alpha _{i_j} : j \in {\mathbb {N}}\} \subseteq S$ such that $\alpha _{i_j}z = y$. For each $j\in {\mathbb {N}}$ define $\beta _j := \alpha _{i_1}a_{i_j}^{-1}$, and notice that $\beta _j$ belongs to the stabilizer ${\text {Aut}}(G)_y$. However, $\beta _j x = \beta _k x$ if and only if $j=k$, and so ${\text {Aut}}(G)_y$ has an infinite orbit, a contradiction. $\square$

Lemma 4

If G has a finite base and ${\text {Aut}}(G)$ is infinite and subdegree-finite, then G has infinite motion.

Proof

Let G be a graph with a finite base Y such that ${\text {Aut}}(G)$ is infinite and subdegree-finite. Suppose $\beta \in {\text {Aut}}(G)$ has finite motion. Then there exists a finite set Z of vertices such that $\beta$ fixes no element in Z and fixes (pointwise) every vertex not in Z. By Lemma 3, there is an $\alpha \in {\text {Aut}}(G)$ such that $\alpha (Z)\cap Y=\emptyset$. Hence $\alpha \beta \alpha ^{-1}$ fixes Y pointwise, and so $\beta$ is the identity. $\square$

Lemma 5

Suppose G is a graph with a finite base such that ${\text {Aut}}(G)$ is infinite and subdegree-finite. If Y is a finite set of at least two vertices whose stabilizer is nontrivial, then there exist infinitely many vertices v such that the stabilizer of $Y \cup \{v\}$ is a proper subgroup of the stabilizer of Y.

Proof

Let Y be a finite set of at least two vertices such that ${\text {Aut}}(G)_Y$ is nontrivial, and let $D := \{\alpha \in {\text {Aut}}(G) : \alpha (Y) \cap Y \not = \emptyset \}$. Suppose D is infinite. Then there exists $y \in Y$ and an infinite subset $\{\alpha _i\}_{i \in {\mathbb {N}}} \subseteq D$ such that $\alpha _i(y) = \alpha _j(y)$ for all $i, j \in {\mathbb {N}}$. The elements in $\{\alpha _i^{-1}\alpha _1\}_{i \in {\mathbb {N}}}$ are pairwise distinct automorphisms which stabilize y, and so the stabilizer of y is infinite. However, all stabilizers of finite sets are finite by Lemma 1. Hence D must be finite.

Let $X := \bigcup _{\alpha \in D} \alpha (Y)$, and note that X is a finite set which contains Y. By Lemma 4, ${\text {Aut}}(G)$ has infinite motion, and therefore there exists a vertex $v \not \in X$ such that $\alpha (v) \ne v$ for some nontrivial $\alpha \in {\text {Aut}}(G)_Y$. Note that we have infinitely many choices for v.

We show now that the stabilizer of $Y\cup \{v\}$ stabilizes Y. To see this, consider an automorphism $\gamma$ which stabilizes $Y\cup \{v\}$ but does not stabilize Y. Then $v \in \gamma (Y)$. The set $\gamma (Y) \cap Y$ is nonempty because Y has at least two vertices, and thus $\gamma (Y) \subseteq X$. But then $v \in X$, contrary to its choice.

From this we infer that the stabilizer of $Y \cup \{v\}$ is contained in the stabilizer of Y, and they cannot be equal since v is moved by the stabilizer of Y. $\square$

Theorem 3

Suppose G is a graph whose automorphism group is infinite and subdegree-finite. If G has a finite base B, then G has a finite distinguishing set with at most $\left\lceil \frac{5n}{2}\right\rceil - b(n) - 1$ elements, where $n = |B|$ and b(n) denotes the number of 1s in the base-2 representation of n.

Proof

Let B be a finite base of G of size n. If $n = 1$, then G has a finite distinguishing set of size 1 and the theorem holds. So, assume that B contains at least two vertices.

Let $Y_0 := B$ and note that either ${\text {Aut}}(G)_{Y_0}$ is trivial or, by Lemma 5, we can find a vertex $v_1 \not \in Y_0$ such that the set $Y_1 := Y_0 \cup \{v_1\}$ satisfies ${\text {Aut}}(G)_{Y_1} < {\text {Aut}}(G)_{Y_0}$. Since $Y_1$ contains at least two vertices, we may repeat this process. Since ${\text {Aut}}(G)_B$ is finite, we will eventually obtain a (possibly empty) finite set of vertices $\{v_1, \ldots , v_k\}$ such that the stabilizer of $Y_k = B \cup \{v_1, \ldots , v_k\}$ is trivial and

$$\begin{aligned} \{\mathrm{id}\} = {\text {Aut}}(G)_{Y_k}< \cdots< {\text {Aut}}(G)_{Y_1} < {\text {Aut}}(G)_{Y_0} = {\text {Aut}}(G)_{B}. \end{aligned}$$

Now we observe that ${\text {Aut}}(G)_B$ is a subgroup of the symmetric group ${\text {Sym}}(n)$ on n elements. By a theorem of Cameron et al. ([6]) the length of any chain of subgroups of ${\text {Sym}}(n)$ is bounded by $\left\lceil \frac{3n}{2}\right\rceil - b(n) - 1$, where b(n) denotes the number of 1s in the base-2 representation of n. Hence $k \le \left\lceil \frac{3n}{2}\right\rceil - b(n) - 1$ and therefore $|Y_k| \le \left\lceil \frac{5n}{2}\right\rceil - b(n) - 1$. $\square$

Despite the fact that we hold subdegree-finiteness to be essential for Theorem 3, we have no example of an infinite, connected graph with finite base and infinite distinguishing cost. We thus conclude this section with a question.

Question 4

Does there exist an infinite, connected graph with finite base and infinite distinguishing cost?

5 Non-elementary results and methods

Halin’s proof of Theorem 1 and our elementary proof of Theorem 2 rely on nested sets of subgraphs, and these arguments are essentially topological. Such nested sets are used in the definition of the permutation topology, which is utilized by Evans in [8]. We briefly describe this topology below.

Let X be a countably infinite set and ${\text {Sym}}(X)$ denote the symmetric group on X. Suppose $(X_i)_{i \ge 0}$ is a nested sequence of finite nonempty subsets of X that covers X. In other words, $X_i \subset X_{i+1}$ and $\bigcup _{i \ge 0}X_i = X$.

For distinct permutations $\alpha , \beta \in {\text {Sym}}(X)$ one defines the confluent of $\alpha , \beta$ as

$$\begin{aligned} {\text {conf}}(\alpha , \beta ) = \min \{i \in \mathbb {N} \, | \, \exists x \in X_i: \alpha x \ne \beta x\}. \end{aligned}$$

Hence, the confluent is the maximum i such that $\alpha$ and $\beta$ coincide on $X_i$, and it is zero if they differ on $X_0$. Observe that ${\text {conf}}$ depends on the choice of the sequence $X_i$.

Then we define a distance $d(\alpha , \beta )$ between $\alpha$ and $\beta$ by setting $d (\alpha , \beta ) = 0$ for $\alpha = \beta$ and $d (\alpha , \beta ) = 2^{-{\text {conf}}(\alpha , \beta )}$ otherwise. This is a well defined metric. In fact, it is an ultrametric (a metric where the triangle inequality has the form $d(\alpha , \gamma ) \le \max \{d(\alpha ,\beta ), d(\beta , \gamma )\}$).

All metrics of this kind define the same topology, the so-called permutation topology on ${\text {Sym}}(X)$, under which ${\text {Sym}}(X)$ is a topological group, and it makes sense to speak of closed subgroups.

A relation of arity n on X is a set of n-tuples of X. A finitary relational structure on X is a pair (X, R), where R is a set of relations of finite arity on X. The automorphism group of a relational structure (X, R) consists of those permutations $\alpha$ of X which satisfy: $\alpha (r) = r$ for all $r \in R$. Graphs and digraphs are both examples of finitary relational structures.

It is well-known, and easy to prove, that $A \le {\text {Sym}}(X)$ is closed if and only if A is the automorphism group of a finitary relational structure $\mathcal {R}$ on X (see [5, Theorem 2.6], for example). Hence, if in the proof of Theorem 2 we replace the word “edge” with the word “relation”, G with $\mathcal {R}$, V(G) with X, and ${\text {Aut}}(G)$ with A, then we obtain an elementary proof of the following theorem.

Theorem 5

Let X be a countable set and let A be a closed subgroup of ${\text {Sym}}(X)$. Then A is countable or has cardinality $2^{\aleph _0}$, with A countable if and only if A has a finite base.

This is how far we can go with elementary methods. A more general result of this kind is the following theorem of Evans.

Theorem 6

(Evans [8, Theorem 1.1]) Let X be a countably infinite set and G, H closed subgroups of ${\text {Sym}}(X)$ with $H \le G$. Then, either $|G:H| = 2^{\aleph _0}$ or H contains the pointwise stabilizer in G of some finite subset of X.

Theorem 5 is the special case of Theorem 6 for $H = \{\mathrm{id}\}$. The proof of Theorem 6 is not elementary. It uses the fact that the coset space (G : H) inherits a metric from the metric d on ${\text {Sym}}(X)$, then Evans proceeds to construct uncountably many convergent series of automorphisms in the coset space if there is no finite subset of X whose point stabilizer is contained in H. The construction involves binary trees, and closure is needed to assure that the limits are not in H.

Evans’ paper ([8]) also contains a short variant of this proof due to Theo Grundhöfer, which proves the slightly weaker assertion that H contains the pointwise stabilizer in G of some finite subset of X if $|G:H| \le \aleph _0$. It begins with the observation that $d^*(\alpha , \beta ) = d(\alpha , \beta ) + d(\alpha ^{-1}, \beta ^{-1})$ also is a metric on ${\text {Sym}}(X)$, which is complete with respect to $d^*$. Moreover, open balls in both the d- and the $d^*$-topology are the same and translation by an element in ${\text {Sym}}(X)$ is a homeomorphism of $({\text {Sym}}(X), d^*)$. If $|G:H| \le \aleph _0$, then the right cosets of H in G decompose into a countable number of closed subsets. Now one observes that by Baire’s Theorem the assumption that a non-empty complete metric space is the countable union of closed sets implies that one of these closed sets has non-empty interior. Hence, some coset of H has non-empty interior, and thus H contains some open ball in G around the identity. This, in turn, implies that H contains the pointwise stabilizer in G of some finite subset of X.

5.1 Uncountable graphs

It would be tempting to extend Theorem 2 to graphs with higher cardinalities. As we already mentioned this might be feasible by the results of Kueker [11] and Reyes [12].

The only result we know of in this direction is by Dixon et al. [7]. Not surprisingly, it needs the Generalized Continuum Hypothesis (GCH).

Theorem 7

(Dixon et al. [7, Theorem 2]) Let X be an infinite set of cardinality ${\mathfrak {n}}$ and G a subgroup of ${\text {Sym}}(X)$ with $|{\text {Sym}}(X):G| < 2^{\mathfrak {n}}$. Then, under the assumption of the GCH, there is a subset Y of X such that $|Y| < {\mathfrak {n}}$ and ${\text {Sym}}(X)_{(Y)} \le G$.

This theorem is a corollary to their main theorem, which pertains to countable graphs, and does not need the Continuum Hypothesis.

Theorem 8

(Dixon et al. [7, Theorem 1]) Let X be a countably infinite set and G a subgroup of ${\text {Sym}}(X)$ with $|{\text {Sym}}(X):G| < 2^{\aleph _0}$. Then there is a finite subset F of X such that

$$\begin{aligned} {\text {Sym}}(X)_{(F)} \le G \le {\text {Sym}}(X)_{\{F\}}, \end{aligned}$$

where ${\text {Sym}}(X)_{(F)}$ is the point-stabilizer of F and ${\text {Sym}}(X)_{\{F\}}$ the set stabilizer.

The proof of Theorem 8 uses moieties, where a moiety is a subset Y of X such that $|Y| = |X\setminus Y| = |X|$, and a theorem of Sierpiński which asserts that a countable set contains an almost disjoint family of $2^{\aleph _0}$ moieties, that is, the intersection of any two members of the family is finite.

Although the proof of Theorem 8 extends to the setting of Theorem 7, it does not seem to lend itself directly to a generalization of Theorem 2.