Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Symmetric figure-eight in a Cayley graph

Definition
CayleyErdosGyarfas_HasSymmetricFigureEight

by burkh4rt · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

cayley-graphscombinatoricscycleserdos-gyarfasgraph-theorygroup-theory

Let GGG be a group and S⊆GS \subseteq GS⊆G. The Cayley graph Cay⁡(G,S)\operatorname{Cay}(G,S)Cay(G,S) has vertex set GGG, and distinct g,h∈Gg, h \in Gg,h∈G are adjacent when h=gsh = gsh=gs or g=hsg = hsg=hs for some s∈Ss \in Ss∈S. A cycle of length kkk is a closed walk (v0,v1,…,vk=v0)(v_0, v_1, \dots, v_k = v_0)(v0​,v1​,…,vk​=v0​) with k≥3k \ge 3k≥3 whose vertices v1,…,vkv_1, \dots, v_kv1​,…,vk​ are pairwise distinct.

Cay⁡(G,S)\operatorname{Cay}(G,S)Cay(G,S) contains a symmetric figure-eight if there are n≥2n \ge 2n≥2, a vertex v∈Gv \in Gv∈G, an element g∈Gg \in Gg∈G and two cycles of length 2n2^n2n based at vvv,

α=(v,a1,…,a2n=v),β=(v,b1,…,b2n=v),\alpha = (v, a_1, \dots, a_{2^n} = v), \qquad \beta = (v, b_1, \dots, b_{2^n} = v),α=(v,a1​,…,a2n​=v),β=(v,b1​,…,b2n​=v),

such that

  1. the sequence (b1,…,b2n)(b_1, \dots, b_{2^n})(b1​,…,b2n​) is a cyclic rotation of (ga1,…,ga2n)(g a_1, \dots, g a_{2^n})(ga1​,…,ga2n​), so that β\betaβ is the left translate gαg\alphagα up to the choice of starting vertex; and
  2. vvv is the only vertex lying on both α\alphaα and β\betaβ.

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 GGG-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 n≥2n \ge 2n≥2 is redundant, since cycles have length at least 333, 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 GGG and inverse-closed generating sets S⊆G∖{1}S \subseteq G \setminus \{1\}S⊆G∖{1} (§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.

Definition code
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
Source
M. C. Burkhart, Odd-ordered Cayley graphs satisfy Erdős–Gyárfás, arXiv:2611.05060v1 (3 Nov 2026), https://arxiv.org/abs/2611.05060v1, §1, p. 1: definition of a symmetric figure-eight (paragraph following Theorem 1.1); conventions of §1.1 Preliminaries, p. 2. Lean declaration as in the Challenge of Palomar entry PALOMAR-2026-11-04-000015 (https://palomar-registry.org/entry?id=PALOMAR-2026-11-04-000015).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let GGG be an arbitrary group, possibly infinite and possibly non-abelian, with no further assumptions. Let S⊆GS \subseteq GS⊆G be an arbitrary subset. SSS need not be finite, need not be closed under inverses and need not generate GGG, and it may contain the identity 111. The definition introduces a proposition HasSymmetricFigureEight(S)\mathrm{HasSymmetricFigureEight}(S)HasSymmetricFigureEight(S).

The graph. Write Γ=Cay(G,S)\Gamma = \mathrm{Cay}(G,S)Γ=Cay(G,S) 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 GGG, with adjacency

x∼y  ⟺  x≠y  and  ∃ s∈S (xs=y  or  ys=x)  ⟺  x−1y∈(S∪S−1)∖{1}.x \sim y \iff x \neq y \ \text{ and } \ \exists\, s \in S \ \big(xs = y \ \text{ or } \ ys = x\big) \iff x^{-1}y \in (S \cup S^{-1}) \setminus \{1\}.x∼y⟺x=y  and  ∃s∈S (xs=y  or  ys=x)⟺x−1y∈(S∪S−1)∖{1}.

So the edges are exactly the pairs {x,xs}\{x, xs\}{x,xs} (right multiplication) with s∈Ss \in Ss∈S and s≠1s \neq 1s=1; an element 1∈S1 \in S1∈S adds nothing. Replacing SSS by S−1S^{-1}S−1, S∪S−1S \cup S^{-1}S∪S−1 or S∖{1}S \setminus \{1\}S∖{1} gives the same graph, so the proposition depends on SSS only through (S∪S−1)∖{1}(S \cup S^{-1}) \setminus \{1\}(S∪S−1)∖{1}. If S⊆{1}S \subseteq \{1\}S⊆{1}, then Γ\GammaΓ has no edges and the proposition is false. Adjacency depends only on x−1yx^{-1}yx−1y, so every left translation x↦gxx \mapsto gxx↦gx is an automorphism of Γ\GammaΓ; right translations in general are not.

The definition. HasSymmetricFigureEight(S)\mathrm{HasSymmetricFigureEight}(S)HasSymmetricFigureEight(S) holds if and only if there exist a natural number nnn, a vertex v∈Gv \in Gv∈G (any element, not necessarily 111), and two closed walks in Γ\GammaΓ from vvv to vvv,

α: v=a0,a1,…,aN=v,β: v=b0,b1,…,bN=v,\alpha:\ v = a_0, a_1, \dots, a_N = v, \qquad \beta:\ v = b_0, b_1, \dots, b_N = v,α: v=a0​,a1​,…,aN​=v,β: v=b0​,b1​,…,bN​=v,

such that the four clauses below hold. Consecutive vertices of each walk are adjacent in Γ\GammaΓ, and the length of a walk is its number of steps.

  1. n≥2n \ge 2n≥2.

  2. α\alphaα and β\betaβ are cycles, and each has length exactly N=2nN = 2^nN=2n. "Cycle" is the Mathlib notion, which has three parts:

    • the closed walk has at least one step;
    • no undirected edge {xi−1,xi}\{x_{i-1}, x_i\}{xi−1​,xi​} occurs twice;
    • the vertex list with the initial vertex removed, (x1,…,xN)(x_1, \dots, x_N)(x1​,…,xN​), has no repetitions.

    These conditions force length ≥3\ge 3≥3. For N≥3N \ge 3N≥3 the edge condition follows from the vertex condition. So here (N≥4N \ge 4N≥4) being a cycle just means that a0,…,aN−1a_0, \dots, a_{N-1}a0​,…,aN−1​ are pairwise distinct, and likewise b0,…,bN−1b_0, \dots, b_{N-1}b0​,…,bN−1​.

  3. There is some g∈Gg \in Gg∈G, not required to lie in SSS, with the following property. Take the vertex list of α\alphaα with its initial entry vvv removed (it still ends with aN=va_N = vaN​=v) and multiply every entry by ggg on the left. The resulting list (ga1,ga2,…,gaN)(g a_1, g a_2, \dots, g a_N)(ga1​,ga2​,…,gaN​) is a cyclic rotation of the list (b1,…,bN)(b_1, \dots, b_N)(b1​,…,bN​). Concretely, for some kkk with 0≤k<N0 \le k < N0≤k<N,

bi=g ai+k(1≤i≤N),b_i = g\,a_{i+k} \qquad (1 \le i \le N),bi​=gai+k​(1≤i≤N),

where indices of aaa are read modulo NNN (consistent because a0=aNa_0 = a_Na0​=aN​).

  • 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 β\betaβ goes round the translated cycle in the same direction as α\alphaα. The reverse of β\betaβ is again a cycle at vvv with the same vertices, so this does not affect whether such a configuration exists.
  1. For every w∈Gw \in Gw∈G: www is a vertex of both α\alphaα and β\betaβ if and only if w=vw = vw=v. Since vvv lies on both, this says exactly that {a0,…,aN−1}∩{b0,…,bN−1}={v}\{a_0, \dots, a_{N-1}\} \cap \{b_0, \dots, b_{N-1}\} = \{v\}{a0​,…,aN−1​}∩{b0​,…,bN−1​}={v}. In particular, α\alphaα and β\betaβ share no edge.

Consequences and edge cases.

  • Clause 1 follows from clause 2: a cycle has length at least 333, and 2n≥32^n \ge 32n≥3 if and only if n≥2n \ge 2n≥2. So the possible lengths are N=4,8,16,…N = 4, 8, 16, \dotsN=4,8,16,….
  • Clause 3, together with the conditions on α\alphaα, already forces β\betaβ to have length 2n2^n2n and to be a cycle.
  • The witness g=1g = 1g=1 is impossible. It would make the vertex sets of α\alphaα and β\betaβ equal, so all N≥4N \ge 4N≥4 vertices would be shared, contradicting clause 4.
  • Taking i=Ni = Ni=N in clause 3 gives v=g akv = g\,a_kv=gak​, so g=v ak−1g = v\,a_k^{-1}g=vak−1​ with 1≤k≤N−11 \le k \le N-11≤k≤N−1. Hence g−1v=ak≠vg^{-1}v = a_k \neq vg−1v=ak​=v is a vertex of α\alphaα, and gv=bN−k≠vgv = b_{N-k} \neq vgv=bN−k​=v is a vertex of β\betaβ.

Equivalently, the proposition says the following. For some n≥2n \ge 2n≥2 there are a cycle CCC of length 2n2^n2n in Γ\GammaΓ, a vertex vvv of CCC, and some g∈Gg \in Gg∈G, such that the left translate gCgCgC (again a cycle of Γ\GammaΓ) passes through vvv and has no vertex other than vvv in common with CCC.

Human review
  • Endorsed by Shuze Chen · Nov 12, 2026

    Confirmed by the moderator at approval.

  • Endorsed by burkh4rt · Nov 12, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me