Alphabeta MathHow statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The Cayley graph of a group with respect to a subset
Definition
Let be a group with identity and let . The Cayley graph of with respect to is the simple graph
with vertex set and edge set
Equivalently, it is the underlying simple graph of The directed labelled Cayley graph of a group with respect to a subset after forgetting directions and labels and then deleting the loops coming from the identity. The exclusion of is load bearing: it is what keeps the Cayley graph a simple graph in the sense of Simple graphs on an arbitrary vertex set.
Depends on
- Simple graphs on an arbitrary vertex set
- The directed labelled Cayley graph of a group with respect to a subset
- Group and abelian group
- The subgroup $\langle S \rangle$ generated by a subset, the cyclic subgroup $\langle g \rangle$, and cyclic groups
- 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
Used by
- The Cayley graphs of ℤ/2 for {1} and of ℤ for {-1,1} are trees, and neither generating set is free Counterexample
- The Cayley graph of the free group on two generators is the tree in which every vertex has four neighbours Example
- The Cayley graph of ℤ for the generating set {1} is a line and its word metric is |m-n| Example
- The Cayley graph of ℤⁿ for the standard basis is the integer lattice, and its word metric is the sum of coordinate differences Example
- The dihedral group of order eight has Cayley graphs that are a cycle of length eight and a cube Example
- The infinite dihedral group is quasi-isometric to ℤ, and to ℤ×ℤ/2 Example
- FALSE: groups with isomorphic Cayley graphs are isomorphic False statement
- FALSE: the Cayley graph of a group is independent of the chosen generating set False statement
- A Cayley graph is connected if and only if the subset generates the group Lemma
- For a finite group the Cayley graph is a finite simple graph in the published sense and the two distances agree Lemma
- Cayley-graph neighbourhoods are equipotent, and local finiteness is equivalent to finiteness of the symmetrised subset Proposition
- If no product of two members of a generating set is the identity and the Cayley graph is a tree, the set is a free basis Theorem
- Left translation acts on a Cayley graph by label-preserving automorphisms, freely on vertices Theorem
- The Cayley graph of a free group with respect to a free basis is a tree Theorem
- The label-preserving automorphism action on a Cayley graph is the left regular representation of Cayley's theorem Theorem
- The word metric is a left-invariant metric and coincides with the path metric of the Cayley graph Theorem
Dependency tree · two levels
15 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- C. Loh, Geometric Group Theory: An Introduction (2015 course version), Section 3.2 (standard reference, not scraped)
- C. Drutu and M. Kapovich, Geometric Group Theory, Section 7.9 (standard reference, not scraped)