Symmetric figure-eight in a Cayley graph
DefinitionCayleyErdosGyarfas_HasSymmetricFigureEightLet be a group and . The Cayley graph has vertex set , and distinct are adjacent when or for some . A cycle of length is a closed walk with whose vertices are pairwise distinct.
contains a symmetric figure-eight if there are , a vertex , an element and two cycles of length based at ,
such that
- the sequence is a cyclic rotation of , so that is the left translate up to the choice of starting vertex; and
- is the only vertex lying on both and .
This is the paper's symmetric figure-eight: a pair of power-of-two-length simple cycles that meet in exactly one vertex, one a -translate of the other up to change of basepoint. It is the configuration that Lemma 1.2 lifts through quotients by abelian normal subgroups, and either of its cycles is a cycle of power-of-two length.
Formalization Note The graph is Mathlib's SimpleGraph.mulCayley S and the cycles are walks satisfying SimpleGraph.Walk.IsCycle. Basing both cycles at their common vertex loses no generality. For a cycle, support.tail lists each vertex once in traversal order, and the translate condition is List.IsRotated (α.support.tail.map (g * ·)) β.support.tail. Only rotations are allowed, not reversals; the reverse of a cycle is a cycle on the same vertices, so this does not change which graphs contain a figure-eight. The bound is redundant, since cycles have length at least , and is kept to match the paper. The declaration is identical, up to the spelling of the namespace, to CayleyErdősGyárfás.HasSymmetricFigureEight in the Challenge of Palomar entry PALOMAR-2026-11-04-000015. The paper uses this notion only for finite and inverse-closed generating sets (§1.1); the predicate is stated for an arbitrary group and subset, agrees with the paper's notion in that setting, and the theorems that use it carry those conventions as hypotheses.
import Mathlib.Combinatorics.SimpleGraph.Cayley
import Mathlib.Combinatorics.SimpleGraph.Paths
/-!
# Symmetric figure-eights in Cayley graphs
Michael C. Burkhart, *Odd-ordered Cayley graphs satisfy Erdős–Gyárfás*,
arXiv:2611.05060v1, §1, p. 1 (the paragraph after Theorem 1.1).
`SimpleGraph.mulCayley S` is Mathlib's Cayley graph on the group `G`: distinct
vertices `g` and `h` are adjacent exactly when `h = g * s` or `g = h * s` for some
`s ∈ S`. A closed walk `c` with `c.IsCycle` is a simple cycle, `c.length` counts its
edges, and `c.support` lists its vertices in traversal order, the base vertex
appearing at both ends.
-/
namespace CayleyErdosGyarfas
/-- Two simple cycles of length `2 ^ n`, based at their unique common vertex `v`.
Left multiplication by `g` carries the first to the second up to a cyclic change of
basepoint: for a simple cycle, `support.tail` lists its vertices in traversal order
with one occurrence of each vertex, and `List.IsRotated` allows the traversal of the
translate to start at a different vertex. -/
def HasSymmetricFigureEight {G : Type*} [Group G] (S : Set G) : Prop :=
∃ (n : ℕ) (v : G) (α β : (SimpleGraph.mulCayley S).Walk v v),
2 ≤ n ∧ α.IsCycle ∧ β.IsCycle ∧
α.length = 2 ^ n ∧ β.length = 2 ^ n ∧
(∃ g : G, List.IsRotated (α.support.tail.map (g * ·)) β.support.tail) ∧
∀ w : G, (w ∈ α.support ∧ w ∈ β.support) ↔ w = v
end CayleyErdosGyarfas
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be an arbitrary group, possibly infinite and possibly non-abelian, with no further assumptions. Let be an arbitrary subset. need not be finite, need not be closed under inverses and need not generate , and it may contain the identity . The definition introduces a proposition .
The graph. Write for the Cayley graph as defined in Mathlib. It is the simple graph (undirected, with no loops and no multiple edges) whose vertex set is all of , with adjacency
So the edges are exactly the pairs (right multiplication) with and ; an element adds nothing. Replacing by , or gives the same graph, so the proposition depends on only through . If , then has no edges and the proposition is false. Adjacency depends only on , so every left translation is an automorphism of ; right translations in general are not.
The definition. holds if and only if there exist a natural number , a vertex (any element, not necessarily ), and two closed walks in from to ,
such that the four clauses below hold. Consecutive vertices of each walk are adjacent in , and the length of a walk is its number of steps.
-
.
-
and are cycles, and each has length exactly . "Cycle" is the Mathlib notion, which has three parts:
- the closed walk has at least one step;
- no undirected edge occurs twice;
- the vertex list with the initial vertex removed, , has no repetitions.
These conditions force length . For the edge condition follows from the vertex condition. So here () being a cycle just means that are pairwise distinct, and likewise .
-
There is some , not required to lie in , with the following property. Take the vertex list of with its initial entry removed (it still ends with ) and multiply every entry by on the left. The resulting list is a cyclic rotation of the list . Concretely, for some with ,
where indices of are read modulo (consistent because ).
- Being a rotation is a symmetric relation, so it does not matter which list is rotated into which.
- Only rotations are allowed, not reversals, so goes round the translated cycle in the same direction as . The reverse of is again a cycle at with the same vertices, so this does not affect whether such a configuration exists.
- For every : is a vertex of both and if and only if . Since lies on both, this says exactly that . In particular, and share no edge.
Consequences and edge cases.
- Clause 1 follows from clause 2: a cycle has length at least , and if and only if . So the possible lengths are .
- Clause 3, together with the conditions on , already forces to have length and to be a cycle.
- The witness is impossible. It would make the vertex sets of and equal, so all vertices would be shared, contradicting clause 4.
- Taking in clause 3 gives , so with . Hence is a vertex of , and is a vertex of .
Equivalently, the proposition says the following. For some there are a cycle of length in , a vertex of , and some , such that the left translate (again a cycle of ) passes through and has no vertex other than in common with .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.