Locally infinite graphs and symmetries

Locally infinite graphs and symmetries

Sébastien Martineau – GJM, Volume 2, Issue 2 (2017), 42-50.

When one studies geometric properties of graphs, local finiteness is a common implicit assumption, while that of transitivity is a more explicit one. By compactness arguments, local finiteness guarantees several regularity properties (see Section 1.2). It is generally easy to find counterexamples to such regularity results when the assumption of local finiteness is dropped. The present work focuses on the following problem: determining whether these regularity properties still hold when local finiteness is replaced by an assumption of transitivity.

After recalling the locally finite situation, we show that there are Cayley graphs of  \bigoplus_{n\geq2} {\mathbb Z}/n{\mathbb Z} and \mathbb Z (with infinite generating systems) that have infinite diameter but do not contain any infinite geodesic ray. We also introduce a notion of generalised diameter. The generalised diameter of a graph is either an ordinal or $\infty$ and captures the extension properties of geodesic paths. It is a finite ordinal if and only if the usual diameter is finite, and in that case the two notions agree. Besides, the generalised diameter is \infty if and only if the considered graph contains an infinite geodesic ray. We show that there exist Cayley graphs of abelian groups of arbitrary generalised diameter.

Finally, we build Cayley graphs of abelian groups that have isomorphic balls of radius n for every n but are not globally isomorphic. This enables us to construct a non-transitive graph in which any two balls of the same radius are isomorphic.

Categories: Issue2, 2017


Received: 27 September 2017
Accepted: 22 December 2017


Sébastien Martineau
Laboratoire de Mathématiques d'Orsay, Université Paris-Sud, France.