Minimal case of the proof of Theorem 1.1
ProvedCayleyErdosGyarfas.minimal_nonabelian_case_has_symmetric_figure_eightLet be a finite nonabelian group of odd order, and let be closed under inverses with . Suppose that is cyclic for every nontrivial abelian normal subgroup , and that contains two noncommuting elements that generate :
Then contains a symmetric figure-eight. Here has vertex set , distinct being adjacent when or for some , and a symmetric figure-eight is a pair of cycles of a common length , , that meet in exactly one vertex, one a left translate of the other up to the choice of starting vertex (definition CayleyErdosGyarfas_HasSymmetricFigureEight).
This is the situation to which the proof of Theorem 1.1 of the source paper reduces a minimal counterexample to the noncyclic claim (every Cayley graph of a noncyclic group of odd order has a symmetric figure-eight). Together with the induction on , it yields that claim.
Formalization Note The quotient hypothesis ranges over all subgroups A with [A.Normal], [IsMulCommutative A] and A ≠ ⊥. Nonabelianness is ¬ IsMulCommutative G. The set is not required to generate ; generation is assumed for the pair .
import Definitions.Def_CayleyErdosGyarfas_HasSymmetricFigureEight import Mathlib.GroupTheory.QuotientGroup.Basic import Mathlib.GroupTheory.SpecificGroups.Cyclic import Mathlib.SetTheory.Cardinal.Finite
namespace CayleyErdosGyarfas
theorem minimal_nonabelian_case_has_symmetric_figure_eight
{G : Type*} [Group G] [Finite G] (S : Set G)
(hodd : Odd (Nat.card G)) (hinv : ∀ s ∈ S, s⁻¹ ∈ S)
(_hone : (1 : G) ∉ S) (hncomm : ¬ IsMulCommutative G)
(hquot : ∀ (A : Subgroup G) [A.Normal] [IsMulCommutative A],
A ≠ ⊥ → IsCyclic (G ⧸ A))
{s t : G} (hs : s ∈ S) (ht : t ∈ S) (hst : ¬ Commute s t)
(hpair : Subgroup.closure ({s, t} : Set G) = ⊤) :
HasSymmetricFigureEight S := by sorry
end CayleyErdosGyarfas