Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 217–221
Imprimitivity of locally finite, 1-ended,
planar graphs
Jozef S̆irán̆
Department of Mathematics and Statistics, Open University
Milton Keynes, U.K. and
Department of Mathematics, SvF Slovak University of Technology
Bratislava, Slovakia
Mark E. Watkins
Department of Mathematics, Syracuse University
Syracuse, NY 13244-1150, USA
Received 10 June 2010, accepted 21 July 2011, published online 22 March 2012
Abstract
Using results from group theory, we offer a concise proof of the imprimitivity of lo-
cally finite, vertex-transitive, 1-ended planar graphs, a result previously established by
J .E. Graver and M. E. Watkins (2004) using graph-theoretical methods.
Keywords: Planar graph, end, primitive permutation group, residually finite group, co-compact
group.
Math. Subj. Class.: 05C25, 05C63, 20B15, 20B27
1 Introduction
Locally finite planar graphs whose automorphism group is primitive were characterized in
[14] as follows (by a lobe, we mean a maximal 2-connected subgraph):
1.1 The automorphism group of an infinite, locally finite, planar graph
Γ is primitive if and only if, for some integer m ≥ 2, every vertex of
Γ is incident with exactly m lobes and no separating edge. Moreover,
either all of the lobes are isomorphic to K4 or all are circuits of length
p for some fixed odd prime p.
E-mail addresses: jozef.siran@stuba.sk (Jozef S̆irán̆), mewatkin@syr.edu (Mark E. Watkins)
Copyright c© 2012 DMFA Slovenije
218 Ars Math. Contemp. 5 (2012) 217–221
The sufficiency of the condition, that the graphs described above are indeed primitive, had
been previously done in [10], and so the authors’ task in [14] was to prove that no other
infinite planar graphs with primitive automorphism group exist. The argument in [14]
that no 1-ended examples exist is particularly long, with a variety of cases and subcases
wherein nontrivial systems of imprimitivity were constructed by brute force. In this note,
using group-theoretical methods, we offer a concise proof of the imprimitivity of 1-ended
planar graphs.
2 Group-theoretic preliminaries
Let X be a nonempty set and let G be a group of permutations on X . We denote by ι the
identity of G. If W ⊆ X , and α ∈ G, then α(W ) is the subset {α(w) : w ∈ W}. We say
that G acts transitively on X if for all x, y ∈ X , there exists α ∈ G such that α(x) = y.
For x ∈ X , the stabilizer of x is the subgroup Gx = {α ∈ G : α(x) = x}.
A subset B ⊆ X is called a block (of imprimitivity) with respect to G when, for all
α ∈ G, either α(B) = B or α(B) ∩ B = ∅. Clearly ∅, X , and the singleton subsets of
X are blocks. If G acts transitively on X and admits only these so-called trivial blocks,
thenG is primitive onX; ifG acts transitively onX but admits nontrivial blocks, thenG is
imprimitive onX . A basic fact concerning imprimitive permutation groups is the following
(see, for example, [2], Theorem 1.7).
Proposition 2.1. A permutation group G acting transitively on a set X is imprimitive if
and only if, for any element x ∈ X , there exists a subgroup M such that Gx < M < G.
Note that the subgroup containment in Proposition 2.1 is proper.
Definition 2.2. An infinite group G is residually finite when for any α ∈ G\{ι} there
exists a subgroup N of G such that α /∈ N and [G : N ] <∞.
The following characterization of residual finiteness will be used.
Lemma 2.3. An infinite groupG is residually finite if and only if, for any finite set S ⊂ G,
there exists a normal subgroupN ofG such that S∩(N\{ι}) = ∅ and |S| < [G : N ] <∞.
Proof. Suppose that G is residually finite, and let S = {σ1, . . . , σm} ⊂ G. By Definition
2.2, for each i = 1, . . . ,m, there exists a subgroup Ki of G such that σi /∈ Ki \ {ι} and
[G : Ki] <∞. ThenK =
⋂m
i=1Ki is a subgroup ofG of finite index disjoint from S \{ι}.
If [G : K] > |S|, we let L = K; otherwise we proceed as follows.
Let α1 ∈ K \ {ι}. By Definition 2.2, there exists a subgroup L1 of G of finite index
that excludes α1, and therefore [G : K ∩ L1] > [G : K]. If [G : K ∩ L1] > |S|, then
we let L = K ∩ L1. Otherwise, choose α2 ∈ (K ∩ L1) \ {ι} and repeat this argument.
In finitely many steps, one arrives at a subgroup L such that S ∩ (L \ {ι}) = ∅ and
|S| < [G : L] <∞.
Finally, let N be the core of L, that is, let N be the intersection of all conjugates of L
in G. Since [G : L] is finite, there are only finitely many such conjugates. Hence [G : N ]
is finite as well, with [G : N ] ≥ [G : L]. Obviously, N is a normal subgroup of G with all
of the required properties.
The converse is immediate.
J. S̆irán̆ and M. E. Watkins: Imprimitivity of locally finite, 1-ended, planar graphs 219
Definition 2.4. A group G acting on the plane P is a planar discontinuous group if each
point p in the plane lies in a neighborhood O(p) such that, for all α ∈ G, either α(p) = p
or α(p) /∈ O(p). Such a group G is co-compact if the quotient space P/G is compact.
Lemma 2.5. Every co-compact planar discontinuous group is residually finite.
Proof. By Theorem 4.10.1 of [16], every co-compact planar discontinuous group has a
surface group of finite index, where a surface group is simply a fundamental group of some
compact orientable surface. Such groups are known to be residually finite (see e.g. [5]).
Since residual finiteness is a property that is hereditary upward to supergroups of finite
index, the result follows.
3 Graph-theoretic preliminaries
In this note, graphs and their subgraphs are denoted by capital Greek letters. We let Aut(Γ)
denote the automorphism group of the graph Γ. The graphs that we consider are locally
finite, i.e., all vertices have finite valence.
An end in an infinite graph is an equivalence class of rays (1-way infinite paths) whereby
two rays are in the same end if there exist infinitely many pairwise-disjoint finite paths join-
ing them. If Γ is locally finite and Aut(Γ) has finitely many orbits, then, by results in [6]
and [9], the set of ends of Γ has cardinality 1, 2 or 2ℵ0 . For a (locally finite) graph Γ with
exactly one end, the following simple characterization holds: for any finite subgraph Φ of
Γ, the subgraph Γ − Φ has exactly one infinite component. In this note, our interest is
confined principally to 1-ended graphs.
Proposition 3.1. ([1], Lemma 2.2) If a 1-ended graph is vertex-transitive, then it is 3-
connected.
Let M be the planar map induced by an embedding of a locally finite graph, and sup-
pose that every face ofM has finite covalence, that is, has finitely many edges in its bound-
ary. For each face ofM , an interior point of the surface may be designated as its center. As
usual in the theory of maps, we regard M as being composed of flags, which are (closed)
topological triangles whose three corners are a vertex v, the midpoint of an edge e incident
with v, and the center of a face incident with both v and e.
The following result is crucial for the present argument.
Lemma 3.2. The automorphism group of every infinite, locally finite, 1-ended, vertex-
transitive, planar graph is residually finite, and the stabilizer of every vertex is finite.
Proof. Let Γ be an infinite, locally finite, 1-ended, vertex-transitive, planar graph, and let
P denote the plane. Planarity, local finiteness, connectivity at least three (by Proposition
3.1) and 1-endedness imply, by Theorems 13 and 14 of [12], that there is a (topologically
as well as combinatorially) unique embedding θ : Γ → P such that every connected
component of P\θ(Γ) is homeomorphic to an open disc forming the interior of some face
of the embedding. Let M be the planar map induced by the embedding θ. The vertex-
transitivity and 1-endedness of Γ imply that every face of M has finite covalence. The two
cited theorems from [12] then imply the important fact that every point of P is contained
in a flag of M .
220 Ars Math. Contemp. 5 (2012) 217–221
Invoking an extension of H. Whitney’s result [15] for finite planar graphs to infinite
graphs (see [7] or [13]), every automorphism of Γ extends to a map automorphism of M .
As the converse is obvious, we have Aut(Γ) ∼= Aut(M). It is well known (cf. [4] Lemma
3.1) that the action of Aut(M) is semi-regular on the set of flags of M . Furthermore, it
follows from Theorem 5.4 and Proposition 5.5 of [8] (and their extensions to orientation-
reversing automorphisms) that the group Aut(M) is isomorphic to a group G acting on P
via an isomorphism that takes an automorphism α of Aut(M) to a unique homeomorphism
ᾱ of P with the property that ᾱ maps every flag x of M pointwise to the flag α(x).
Since M is locally finite with all covalences being finite, the stabilizer in Aut(M), and
hence in G, of any point on the boundary of a flag of M must be finite. Moreover, by
the semi-regularity of Aut(M) on flags, the stabilizer in G of any interior point of any
flag is trivial. Since every point of P lies in some flag of M , it follows that G is planar
discontinuous by Definition 2.4.
The local finiteness and vertex-transitivity of M further imply that the quotient space
P/G is an identification space formed by equivalence classes of flags incident with a fixed
vertex modulo its stabilizer in G. Hence P/G is compact and G is co-compact. The
conclusion now follows from Lemma 2.5.
We emphasize that our remark in the above proof about every point of P being con-
tained in some flag of M is by no means automatic and becomes invalid in general if one
drops the assumption either of vertex-transitivity or of one-endedness. In such cases one
may have accumulation points in P but not on θ(Γ), and these points of P would belong to
no flag of the embedding. Indeed, the primitive planar graphs described in statement 1.1 are
infinitely ended. More extreme examples of such a situation are presented in [11] where it is
shown that for every integer k there exists an infinitely-ended k-connected vertex-transitive
planar graph with each vertex lying on at least k faces bounded by a two-way infinite ray.
The union of all flags of such a map is P with a Cantor set removed, and arguments in our
proof would not apply to the points in the Cantor set. Vertex-transitive graphs with exactly
two ends have polynomial growth, and therefore are imprimitive (see [3], Theorem 4).
4 A short proof of the main result
Theorem 4.1. Let Γ be an infinite, locally finite, 1-ended planar graph, and let G be a
group of automorphisms that acts transitively on the vertex set of Γ. Then G is imprimitive.
Proof. Let Γ and G be as described in the hypothesis. It is sufficient to assume that Γ is
vertex-transitive and G = Aut(Γ). By Lemma 3.2, G is residually finite and the stabilizer
Gv of any vertex v of Γ is finite. By Lemma 2.3,G contains a normal subgroupN such that
N ∩ Gv = {ι} and [G : N ] > |Gv|. This implies that Gv < NGv < G. By Proposition
2.1, G is imprimitive.
Normality of N in G gives our main result an extra flavor. Namely, if M is a planar
map arising from the unique embedding of Γ in P as in the proof of Lemma 3.2, then the
quotient M/N is a finite map on a compact surface, possibly with boundary if N contains
orientation-reversing elements. Blocks of imprimitivity are then pre-images of individual
vertices in the natural covering M →M/N . Our construction also shows that such blocks
of imprimitivity can be chosen in infinitely many ways.
J. S̆irán̆ and M. E. Watkins: Imprimitivity of locally finite, 1-ended, planar graphs 221
Acknowledgement. The first author acknowledges support by the VEGA Research Grants
1/0489/08 and 1/0280/10, and the APVV Research Grants 0223-10 and 0104-07. The idea
for this note came about in late 2004 while the first author was affiliated with the University
of Auckland and the second author was visiting at the invitation of C. Paul Bonnington.
References
[1] C. P. Bonnington, W. Imrich and M. E. Watkins, Separating double rays in locally finite, planar
graphs, Discrete Math. 145 (1995), 61–72.
[2] P. J. Cameron, Permutation Groups, London Mathematical Society Student Texts 45, Cam-
bridge, U. K., 1999.
[3] C. D. Godsil, W. Imrich, N. Seifter, M. E. Watkins and W. Woess, A note on bounded automor-
phissms of graphs, Graphs and Combinatorics 5 (1989), 333–338.
[4] J. E. Graver and M. E. Watkins, Locally Finite, Planar, Edge-Transitive Graphs, Memoirs Amer.
Math. Soc., Vol. 126, No. 601, 1997.
[5] H. B. Griffiths, A covering-space approach to residual properties of groups, Michigan Math. J.
14 (1967), 335–348.
[6] R. Halin, Automorphisms and endomorphisms of infinite locally finite graphs, Abh. Math. Sem.
Univ. Hamburg (1973), 251–283.
[7] W. Imrich, On Whitney’s theorem on the unique embeddability of 3-connected planar graphs,
in: M. Fiedler (ed.) Recent Advances in Graphs Theory, Academia Praha, Prague, 1975, 303–
306.
[8] G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math.
Soc. 37 (1978), 373–397.
[9] H. A. Jung, A Note on fragments of infinite graphs, Combinatorica 1 (1981), 285–288.
[10] H. A. Jung and M. E. Watkins, On the structure of infinite vertex-transitive graphs, Discrete
Math. 18 (1977), 45–53.
[11] B. Mohar, Tree amalgamation of graphs and tessellations of the Cantor sphere, J. Combin.
Theory Ser. B 96 (2006), 740–753.
[12] R. B. Richter and C. Thomassen, 3-connected planar spaces uniquely embed in the sphere,
Trans. Amer. Math. Soc. 354 (2002), 4585–4595.
[13] C. Thomassen, Planarity and duality in infinite graphs, J. Combin. Theory Ser. B 29 (1980),
244–271.
[14] M. E. Watkins and J. E. Graver, A characterization of infinite planar primitive graphs, J. Com-
bin. Theory Ser. B 91 (2004), 87–104.
[15] H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.
[16] H. Zieschang, E. Vogt and H.-D. Coldewey, Surfaces and Planar Discontinuous Groups, Lecture
Notes in Math. 835, Springer-Verlag, 1980.