Cayley Graphs, Word Metrics and Quasi-Isometry

Given: The hypotheses of the Statement.

A simple graph is a pair $(V,E)$ with $V$ any set and $E$ a set of two-element subsets of $V$ (Simple graphs on an arbitrary vertex set).

A walk of length $\mathrm{\ell }$ in a simple graph is a finite vertex list $(v_0,\dots ,v_{\mathrm{\ell }})$ with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

Every nonempty subset $S\subseteq \mathbb{N}$ has a least element: there is $\mathrm{\ell }\in S$ with $\mathrm{\ell }\le s$ for all $s\in S$. (The well-ordering principle).

Given: The hypotheses of the Statement.

The path metric of a connected simple graph assigns to two vertices the least length of a path joining them (The path metric of a connected simple graph).

A walk of length $\mathrm{\ell }$ in a simple graph is a finite vertex list $(v_0,\dots ,v_{\mathrm{\ell }})$ with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

Every walk in a simple graph contains a path with the same endpoints and of no greater length (Every walk contains a path between the same endpoints, of no greater length).

A metric on a set satisfies separation, symmetry and the triangle inequality (Metric space: $d(x,y)=0$ iff $x=y$, symmetry, and the triangle inequality; pseudometric and ultrametric).

A simple graph is a pair $(V,E)$ with $V$ any set and $E$ a set of two-element subsets of $V$ (Simple graphs on an arbitrary vertex set).

Given: Connected simple graphs $G,H$ and a bijection $\phi :V(G)\to V(H)$.

A simple graph is a pair $(V,E)$ with $V$ any set and $E$ a set of two-element subsets of $V$ (Simple graphs on an arbitrary vertex set).

A walk of length $\mathrm{\ell }$ in a simple graph is a finite vertex list $(v_0,\dots ,v_{\mathrm{\ell }})$ with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

The path metric of a connected simple graph assigns to two vertices the least length of a path joining them (The path metric of a connected simple graph).

The path metric of a connected simple graph is a metric on its vertex set (The path metric of a connected simple graph is a metric on its vertex set).

A function $f:X\to Y$ is an isometric embedding when it preserves every distance, and it is an isometry when it is also bijective (Isometry, isometric embedding, and the subspace metric on a subset).

A graph isomorphism is a vertex bijection $\phi :V\to W$ such that $\{u,v\}$ is an edge exactly when $\{\phi (u),\phi (v)\}$ is an edge, for all distinct $u,v$ (Graph isomorphisms, automorphisms and graph complements).

Given: The hypotheses of the Statement.

A simple graph is a pair $(V,E)$ with $V$ any set and $E$ a set of two-element subsets of $V$ (Simple graphs on an arbitrary vertex set).

A walk of length $\mathrm{\ell }$ in a simple graph is a finite vertex list $(v_0,\dots ,v_{\mathrm{\ell }})$ with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

$E\subseteq [V{]}^2:=\{\{u,v\}\subseteq V:u\mathrm{\ne }v\}\mathrm{.}$ (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

A walk of length $\mathrm{\ell }$ is a finite vertex list (Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges).

Vertices $u$ and $v$ of a graph $G$ are connected, or reachable from one another, when a path in $G$ has endpoints $u$ and $v$. Equivalently, a walk joins them, because turns such a walk into a path. (Connected graphs and connected components defined by the existence of vertex paths).

For vertices $u,v$ in one connected component, the published graph distance is the least length of a path joining them (Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention).

These are the metric axioms, so shortest-path distance is a metric on $C$. (Shortest-path distance is a metric on every connected component).

By deleting zero or more closed segments from its vertex list, one obtains a path from $v_0$ to $v_{\mathrm{\ell }}$ of length at most $\mathrm{\ell }$. If $W$ repeats a vertex, the resulting path can be chosen to have length strictly less than $\mathrm{\ell }$. (Every walk between two vertices contains a path between the same endpoints).

The path metric of a connected simple graph assigns to two vertices the least length of a path joining them (The path metric of a connected simple graph).

The path metric of a connected simple graph is a metric on its vertex set (The path metric of a connected simple graph is a metric on its vertex set).

Every walk in a simple graph contains a path with the same endpoints and of no greater length (Every walk contains a path between the same endpoints, of no greater length).

Given: The hypotheses of the Statement.

A graph is locally finite when every vertex has finitely many neighbours (Locally finite graphs and vertex degree without a finiteness hypothesis).

The path metric of a connected simple graph assigns to two vertices the least length of a path joining them (The path metric of a connected simple graph).

$B(x,r)$ is the open ball, $\bar{B}(x,r)$ the closed ball and $S(x,r)$ the sphere of centre $x$ and radius $r$. The radius is always a strictly positive real; a ball of radius $0$ or of negative radius is never written in this library. (Open ball, closed ball and sphere in a metric space).

A walk of length $\mathrm{\ell }$ in a simple graph is a finite vertex list $(v_0,\dots ,v_{\mathrm{\ell }})$ with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

A set $A$ is finite when $A\approx n$ for some $n\in \mathbb{N}$. (The cardinality $\mid A\mid$ of a finite set).

Every complete ordered field is Archimedean: for every real $x$ there is a natural number $n\ge 1$ with $x<n$ (Every complete ordered field is Archimedean).

A subset of a finite set is finite (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$).

Given: A nonempty simple graph.

A cycle is a closed walk of length at least three with distinct vertices apart from its endpoints; a forest is a simple graph with no cycle and a tree is a connected forest (Cycles, trees and forests in a simple graph on an arbitrary vertex set).

A walk of length $\mathrm{\ell }$ in a simple graph is a finite vertex list $(v_0,\dots ,v_{\mathrm{\ell }})$ with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

A simple graph is a pair $(V,E)$ with $V$ any set and $E$ a set of two-element subsets of $V$ (Simple graphs on an arbitrary vertex set).

Every walk in a simple graph contains a path with the same endpoints and of no greater length (Every walk contains a path between the same endpoints, of no greater length).

Given: The hypotheses of the Statement.

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

A walk of length $\mathrm{\ell }$ in a simple graph is a finite vertex list $(v_0,\dots ,v_{\mathrm{\ell }})$ with consecutive vertices adjacent; a path is a walk with distinct vertices; the graph is connected when it is nonempty and every two vertices are joined by a path (Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set).

$⟨S⟩:=\bigcap \{H:H\le G\text{ and }S\subseteq H\}\mathrm{.}$ (The subgroup $⟨S⟩$ generated by a subset, the cyclic subgroup $⟨g⟩$, and cyclic groups).

An elementary cancellation deletes two adjacent letters $x{x}^{-1}$ or $x^{-1}x$. A word is reduced if no elementary cancellation applies. (Words in an alphabet with formal inverses, elementary cancellation, and reduced words).

Given: A group $G$, a subset $S\subseteq G$, and $S^{\pm }=(S\cup S^{-1})\setminus \{e\}$.

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

A graph is locally finite when every vertex has finitely many neighbours (Locally finite graphs and vertex degree without a finiteness hypothesis).

The degree of $v$ is ${\mathrm{deg}}_G(v):=\mathrm{\mid }{N}_G(v)\mathrm{\mid }$, equivalently the number of edges incident with $v$. A graph is $r$-regular when every vertex has degree $r$; it is cubic when it is $3$-regular. (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

A set $A$ is finite when $A\approx n$ for some $n\in \mathbb{N}$. (The cardinality $\mid A\mid$ of a finite set).

Given: The hypotheses of the Statement.

The directed labelled Cayley graph of a group $G$ and a subset $S$ has vertex set $G$ and an arc from $g$ to $gs$ labelled $s$ for each $g\in G$ and $s\in S$ (The directed labelled Cayley graph of a group with respect to a subset).

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

A labelled directed graph is a vertex set with a set of arcs each carrying a label, and a labelled isomorphism is a vertex bijection preserving arcs and labels (Labelled directed graphs, their underlying simple graphs, and label-preserving isomorphisms).

A left action of $G$ on $X$ is a function $G\times X\to X$, written $(g,x)\mapsto g\cdot x$, such that (Left group actions, transitive actions, and faithful actions).

A left action of a group $G$ on a set $X$ is free when (A free group action has no nonidentity element fixing a point).

Given: The hypotheses of the Statement.

Left translation acts on a Cayley graph by label-preserving automorphisms, freely on vertices (Left translation acts on a Cayley graph by label-preserving automorphisms, freely on vertices).

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

Every group $G$ is isomorphic to the subgroup of $\mathrm{Sym}(G)$ formed by its left translations ${\lambda }_g:x\mapsto gx$. (Cayley's theorem: every group $G$ is isomorphic to a subgroup of $\mathrm{Sym}(G)$).

A left action of $G$ on $X$ is a function $G\times X\to X$, written $(g,x)\mapsto g\cdot x$, such that (Left group actions, transitive actions, and faithful actions).

Group isomorphisms, automorphisms and the set $\mathrm{Aut}(G)$. (Group isomorphisms, automorphisms and the set $\mathrm{Aut}(G)$).

Given: A finite group $G$ and a finite generating set $S$.

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

On a finite vertex set these graph notions are the published ones and the path metric is the published graph distance (On a finite vertex set the graph notions agree, and on connected graphs the two path distances agree).

The path metric of a connected simple graph assigns to two vertices the least length of a path joining them (The path metric of a connected simple graph).

$E\subseteq [V{]}^2:=\{\{u,v\}\subseteq V:u\mathrm{\ne }v\}\mathrm{.}$ (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

Let $u$ and $v$ lie in the same connected component of a graph $G$. Their distance is (Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention).

A set $A$ is finite when $A\approx n$ for some $n\in \mathbb{N}$. (The cardinality $\mid A\mid$ of a finite set).

Given: The hypotheses of the Statement.

The word length $\mathrm{\mid }g{\mathrm{\mid }}_S$ is the least $n$ such that $g$ is a product of $n$ elements of $S\cup S^{-1}$ (Word length of a group element with respect to a generating set).

$⟨S⟩:=\bigcap \{H:H\le G\text{ and }S\subseteq H\}\mathrm{.}$ (The subgroup $⟨S⟩$ generated by a subset, the cyclic subgroup $⟨g⟩$, and cyclic groups).

Every nonempty subset $S\subseteq \mathbb{N}$ has a least element: there is $\mathrm{\ell }\in S$ with $\mathrm{\ell }\le s$ for all $s\in S$. (The well-ordering principle).

$(gh{)}^{-1}=h^{-1}{g}^{-1}$; 4. (In a group $e^{-1}=e$, $(g^{-1}{)}^{-1}=g$ and $(gh{)}^{-1}=h^{-1}{g}^{-1}$, the order of the last product being essential).

Given: The hypotheses of the Statement.

The word metric of $G$ with respect to $S$ is $d_S(g,h)=\mathrm{\mid }{g}^{-1}h{\mathrm{\mid }}_S$ (The word metric of a group with respect to a generating set).

Word length is defined on every element and satisfies $\mathrm{\mid }gh{\mathrm{\mid }}_S\le \mathrm{\mid }g{\mathrm{\mid }}_S+\mathrm{\mid }h{\mathrm{\mid }}_S$, $\mathrm{\mid }{g}^{-1}{\mathrm{\mid }}_S=\mathrm{\mid }g{\mathrm{\mid }}_S$, and $\mathrm{\mid }g{\mathrm{\mid }}_S=0$ exactly when $g$ is the identity (Word length is defined on every element and satisfies the subadditivity, inversion and vanishing laws).

The word length $\mathrm{\mid }g{\mathrm{\mid }}_S$ is the least $n$ such that $g$ is a product of $n$ elements of $S\cup S^{-1}$ (Word length of a group element with respect to a generating set).

A metric on a set satisfies separation, symmetry and the triangle inequality (Metric space: $d(x,y)=0$ iff $x=y$, symmetry, and the triangle inequality; pseudometric and ultrametric).

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

A Cayley graph is connected if and only if its defining subset generates the group (A Cayley graph is connected if and only if the subset generates the group).

The path metric of a connected simple graph assigns to two vertices the least length of a path joining them (The path metric of a connected simple graph).

The path metric of a connected simple graph is a metric on its vertex set (The path metric of a connected simple graph is a metric on its vertex set).

Given: The hypotheses of the Statement.

The word metric of $G$ with respect to $S$ is $d_S(g,h)=\mathrm{\mid }{g}^{-1}h{\mathrm{\mid }}_S$ (The word metric of a group with respect to a generating set).

The word length $\mathrm{\mid }g{\mathrm{\mid }}_S$ is the least $n$ such that $g$ is a product of $n$ elements of $S\cup S^{-1}$ (Word length of a group element with respect to a generating set).

The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph (The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph).

In a locally finite connected graph every ball of the path metric is finite (In a connected locally finite graph every ball of the path metric is finite).

Every vertex of a Cayley graph has the same degree, and the graph is locally finite exactly when the symmetrised generating set is finite (Cayley-graph neighbourhoods are equipotent, and local finiteness is equivalent to finiteness of the symmetrised subset).

$B(x,r)$ is the open ball, $\bar{B}(x,r)$ the closed ball and $S(x,r)$ the sphere of centre $x$ and radius $r$. The radius is always a strictly positive real; a ball of radius $0$ or of negative radius is never written in this library. (Open ball, closed ball and sphere in a metric space).

A set $A$ is finite when $A\approx n$ for some $n\in \mathbb{N}$. (The cardinality $\mid A\mid$ of a finite set).

A group is finitely generated when some finite subset generates it (Finitely generated groups).

Write ${\prod }_{i<m}{A}_i:=\{f:f\text{ is a function with domain }m\text{ and }f(i)\in A_i\text{ for every }i<m\}\mathrm{.}$ Then ${\prod }_{i<m}{A}_i$ is finite and $\mid {\prod }_{i<m}{A}_i\mid ={\prod }_{i<m}\mid A_i\mid$, the right-hand product being the $\mathbb{N}$-valued one of. (The product rule: $\mid A\times B\mid =\mid A\mid \mid B\mid$, and $\mid {\prod }_{i<m}{A}_i\mid ={\prod }_{i<m}\mid A_i\mid$).

Given: The hypotheses of the Statement.

The word metric of $G$ with respect to $S$ is $d_S(g,h)=\mathrm{\mid }{g}^{-1}h{\mathrm{\mid }}_S$ (The word metric of a group with respect to a generating set).

The word length $\mathrm{\mid }g{\mathrm{\mid }}_S$ is the least $n$ such that $g$ is a product of $n$ elements of $S\cup S^{-1}$ (Word length of a group element with respect to a generating set).

Word length is defined on every element and satisfies $\mathrm{\mid }gh{\mathrm{\mid }}_S\le \mathrm{\mid }g{\mathrm{\mid }}_S+\mathrm{\mid }h{\mathrm{\mid }}_S$, $\mathrm{\mid }{g}^{-1}{\mathrm{\mid }}_S=\mathrm{\mid }g{\mathrm{\mid }}_S$, and $\mathrm{\mid }g{\mathrm{\mid }}_S=0$ exactly when $g$ is the identity (Word length is defined on every element and satisfies the subadditivity, inversion and vanishing laws).

The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph (The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph).

Every metric satisfies the triangle inequality (Metric space: $d(x,y)=0$ iff $x=y$, symmetry, and the triangle inequality; pseudometric and ultrametric).

Given: The hypotheses of the Statement.

The word metric of $G$ with respect to $S$ is $d_S(g,h)=\mathrm{\mid }{g}^{-1}h{\mathrm{\mid }}_S$ (The word metric of a group with respect to a generating set).

The word length $\mathrm{\mid }g{\mathrm{\mid }}_S$ is the least $n$ such that $g$ is a product of $n$ elements of $S\cup S^{-1}$ (Word length of a group element with respect to a generating set).

The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph (The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph).

Given: The hypotheses of the Statement.

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

A Cayley graph is connected if and only if its defining subset generates the group (A Cayley graph is connected if and only if the subset generates the group).

A cycle is a closed walk of length at least three with distinct vertices apart from its endpoints; a forest is a simple graph with no cycle and a tree is a connected forest (Cycles, trees and forests in a simple graph on an arbitrary vertex set).

A simple graph is a tree if and only if every two of its vertices are joined by exactly one path (A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path).

A free group on a set $X$ is a group $F(X)$ together with a map $i:X\to F(X)$ such that, for every group $G$ and every function $u:X\to G$, there is a unique group homomorphism $\widehat{u}:F(X)\to G$ satisfying (Free group on a set of generators).

The subset $B$ is a free basis of $F$ if $(F,i)$ is a free group on the set $B$ in the sense of. (A free basis of a group).

An elementary cancellation deletes two adjacent letters $x{x}^{-1}$ or $x^{-1}x$. A word is reduced if no elementary cancellation applies. (Words in an alphabet with formal inverses, elementary cancellation, and reduced words).

The reduced words on $X\bigsqcup X^{-1}$ form a group when the product of reduced words is their concatenation followed by free reduction. (Reduced words form the free group on an alphabet).

Every class in $W(X)\mathrm{/}\sim$ contains exactly one reduced word. (Every class in $W(X)\mathrm{/}\sim$ contains exactly one reduced word).

Given: The hypotheses of the Statement.

The word length $\mathrm{\mid }g{\mathrm{\mid }}_S$ is the least $n$ such that $g$ is a product of $n$ elements of $S\cup S^{-1}$ (Word length of a group element with respect to a generating set).

Word length is defined on every element and satisfies $\mathrm{\mid }gh{\mathrm{\mid }}_S\le \mathrm{\mid }g{\mathrm{\mid }}_S+\mathrm{\mid }h{\mathrm{\mid }}_S$, $\mathrm{\mid }{g}^{-1}{\mathrm{\mid }}_S=\mathrm{\mid }g{\mathrm{\mid }}_S$, and $\mathrm{\mid }g{\mathrm{\mid }}_S=0$ exactly when $g$ is the identity (Word length is defined on every element and satisfies the subadditivity, inversion and vanishing laws).

The Cayley graph of a free group with respect to a free basis is a tree (The Cayley graph of a free group with respect to a free basis is a tree).

An elementary cancellation deletes two adjacent letters $x{x}^{-1}$ or $x^{-1}x$. A word is reduced if no elementary cancellation applies. (Words in an alphabet with formal inverses, elementary cancellation, and reduced words).

The reduced words on $X\bigsqcup X^{-1}$ form a group when the product of reduced words is their concatenation followed by free reduction. (Reduced words form the free group on an alphabet).

Every class in $W(X)\mathrm{/}\sim$ contains exactly one reduced word. (Every class in $W(X)\mathrm{/}\sim$ contains exactly one reduced word).

The subset $B$ is a free basis of $F$ if $(F,i)$ is a free group on the set $B$ in the sense of. (A free basis of a group).

Given: The hypotheses of the Statement.

The Cayley graph of a group $G$ with respect to a subset $S$ has vertex set $G$ and edge set $\{\{g,gs\}:g\in G,s\in (S\cup S^{-1})\setminus \{e\}\}$ (The Cayley graph of a group with respect to a subset).

A cycle is a closed walk of length at least three with distinct vertices apart from its endpoints; a forest is a simple graph with no cycle and a tree is a connected forest (Cycles, trees and forests in a simple graph on an arbitrary vertex set).

A simple graph is a tree if and only if every two of its vertices are joined by exactly one path (A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path).

The Cayley graph of a free group with respect to a free basis is a tree (The Cayley graph of a free group with respect to a free basis is a tree).

A free group on a set $X$ is a group $F(X)$ together with a map $i:X\to F(X)$ such that, for every group $G$ and every function $u:X\to G$, there is a unique group homomorphism $\widehat{u}:F(X)\to G$ satisfying (Free group on a set of generators).

The subset $B$ is a free basis of $F$ if $(F,i)$ is a free group on the set $B$ in the sense of. (A free basis of a group).

The reduced words on $X\bigsqcup X^{-1}$ form a group when the product of reduced words is their concatenation followed by free reduction. (Reduced words form the free group on an alphabet).

Every class in $W(X)\mathrm{/}\sim$ contains exactly one reduced word. (Every class in $W(X)\mathrm{/}\sim$ contains exactly one reduced word).

An elementary cancellation deletes two adjacent letters $x{x}^{-1}$ or $x^{-1}x$. A word is reduced if no elementary cancellation applies. (Words in an alphabet with formal inverses, elementary cancellation, and reduced words).

Given: The hypotheses of the Statement.

Two maps into a metric space are at bounded distance when the distance between their values is bounded uniformly (Bounded distance between two maps into a metric space).

A map is $(L,C)$-coarse Lipschitz when $d(f(x),f(x^{\mathrm{\prime }}))\le Ld(x,x^{\mathrm{\prime }})+C$, and an $(L,C)$-quasi-isometric embedding when in addition $L^{-1}d(x,x^{\mathrm{\prime }})-C\le d(f(x),f(x^{\mathrm{\prime }}))$ (Coarse Lipschitz maps and quasi-isometric embeddings).