cayley_table_graph_exists_complete_mapping_of_transversal
If the Cayley table graph of a finite group G contains a transversal of cardinality |G|, then G admits a complete mapping.
Statement
theorem cayley_table_graph_exists_complete_mapping_of_transversal (G : Type*) [Group G] [Fintype G] (s : Finset (G × G)) (hindep : (cayley_table_graph G).IsIndepSet (s : Set (G × G))) (hcard : s.card = Fintype.card G) : ∃ θ : G → G, group_is_complete_mapping θ
- Formalizes
- arXiv:2611.13274 Theorem 2.12
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cayley_table_graphThe Latin square graph of the Cayley table of a magma G is the simple graph with vertex set G × G where two distinct vertices (g₁, h₁) and…
- group_is_complete_mappingA complete mapping of a group G is a permutation θ of G such that x ↦ xθ(x) is also a permutation of G.
- Used by 1
- group_cayley_table_chromatic_number_ne_succFor every finite group G, the chromatic number of its Cayley table Latin square graph is not equal to |G| + 1.
Read back from the Lean
For any finite group $G$ and any finite subset $s \subseteq G \times G$, if $s$ is an independent set in the Cayley table graph of $G$ and the cardinality of $s$ equals the cardinality of $G$, then there exists a complete mapping $\theta : G \to G$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
An independent set of size |G| in the Cayley table graph cannot contain two pairs that share a row, a column, or a Cayley table product. Because no two pairs share their first coordinate, the first projection maps the set injectively—and hence bijectively by cardinality—onto G, defining a function θ : G → G whose graph is the independent set. Since elements of the set cannot share a second coordinate or a product, both θ and x ↦ x * θ(x) are injective. On a finite group, injectivity implies bijectivity, so θ is a complete mapping.
No two distinct pairs in s share their first coordinate.
Let p and q be pairs in s with p.1 = q.1. Suppose for contradiction that p ≠ q. By definition of the Cayley table graph, two distinct vertices that agree on their first coordinate are adjacent. But s is an independent set, so no two vertices in s can be adjacent, a contradiction.
uses
Or.inlclassical have hfst : ∀ p ∈ s, ∀ q ∈ s, p.1 = q.1 → p = q := by intro p hp q hq h by_contra hne exact hindep hp hq hne ⟨hne, Or.inl h⟩
No two distinct pairs in s share their second coordinate.
Similarly, suppose p, q ∈ s have p.2 = q.2 but p ≠ q. Then p and q are adjacent in the Cayley table graph because they share their second coordinate, which contradicts s being an independent set.
uses
Or.inr,Or.inlhave hsnd : ∀ p ∈ s, ∀ q ∈ s, p.2 = q.2 → p = q := by intro p hp q hq h by_contra hne exact hindep hp hq hne ⟨hne, Or.inr (Or.inl h)⟩
The projection of s onto the first coordinate is the whole group G.
Because the first projection is injective on s, the cardinality of its image equals |s| = |G| by Finset.card_image_of_injOn. Since G is finite and the image has cardinality |G|, Finset.eq_univ_of_card implies the image is all of G.
uses
Finset.eq_univ_of_card,Finset.card_image_of_injOnhave himg : s.image (fun p : G × G => p.1) = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn, hcard] intro p hp q hq h exact hfst p hp q hq h
Every x ∈ G appears as the first component of some pair in s.
Since the image of the first projection is all of G, any given x ∈ G lies in this image. By definition of image (Finset.mem_image), there exists a pair p ∈ s whose first component is x, which means (x, p.2) ∈ s.
uses
Finset.mem_imagehave hex : ∀ x : G, ∃ y : G, (x, y) ∈ s := by intro x have : x ∈ s.image (fun p : G × G => p.1) := by rw [himg]; simp rw [Finset.mem_image] at this obtain ⟨p, hp, hpx⟩ := this exact ⟨p.2, by rw [← hpx]; exact hp⟩
Defining θ(x) as the second component of the pair with first component x yields (x, θ(x)) ∈ s for every x ∈ G.
We define θ(x) by choosing the witness y such that (x, y) ∈ s. Since such a y exists for every x, the dependent conditional evaluates via dif_pos to this chosen witness, guaranteeing that (x, θ(x)) ∈ s.
uses
dif_poslet θ : G → G := fun x => if h : ∃ y, (x, y) ∈ s then h.choose else 1 have hmem : ∀ x : G, (x, θ x) ∈ s := by intro x have h := hex x simp only [θ] rw [dif_pos h] exact h.choose_spec
The map θ is injective.
Suppose θ(x) = θ(y). The pairs (x, θ(x)) and (y, θ(y)) both lie in s and share their second coordinate. Since pairs in s with equal second coordinates are identical, (x, θ(x)) = (y, θ(y)), and taking first components yields x = y.
have hθinj : Function.Injective θ := by intro x y hxy have hp := hmem x have hq := hmem y have hpq : (x, θ x) = (y, θ y) := hsnd _ hp _ hq hxy have : (x, θ x).1 = (y, θ y).1 := by rw [hpq] simpa using this
The map x ↦ x * θ(x) is injective.
Suppose x * θ(x) = y * θ(y), and suppose for contradiction that x ≠ y. The pairs p = (x, θ(x)) and q = (y, θ(y)) are distinct elements of s whose products p.1 * p.2 and q.1 * q.2 are equal. By definition of the Cayley table graph, two distinct vertices with the same product are adjacent, which contradicts the independence of s. Hence x = y.
uses
Prod.ext_iff.mp,Or.inrhave hψinj : Function.Injective (fun x => x * θ x) := by intro x y hxy by_contra hne have hp := hmem x have hq := hmem y have hpq : (x, θ x) ≠ (y, θ y) := by intro h exact hne (Prod.ext_iff.mp h).1 exact hindep hp hq hpq ⟨hpq, Or.inr (Or.inr hxy)⟩
θ is a complete mapping of G.
A complete mapping is a bijection θ such that x ↦ x * θ(x) is also a bijection. On a finite set, injectivity implies bijectivity; since both θ and x ↦ x * θ(x) are injective, both are bijections, completing the proof.
refine ⟨θ, hθinj.bijective_of_finite, hψinj.bijective_of_finite⟩
Or.inl- If a proposition a holds, then the disjunction a ∨ b holds.
Or.inr- If a proposition b holds, then the disjunction a ∨ b holds.
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals the cardinality of the type is the universal set.
Finset.card_image_of_injOn- If a function is injective on a finite set, the cardinality of its image equals the cardinality of the set.
Finset.mem_image- An element belongs to the image of a finite set under a function if and only if it is the image of some element in that set.
dif_pos- When the condition c is true, a dependent if-then-else expression evaluates to its then-branch.
Prod.ext_iff.mp- If two ordered pairs are equal, their first components are equal and their second components are equal.
- On a finite group, bijectivity follows automatically from injectivity (via the pigeonhole principle, formalized as `bijective_of_finite`), so the proof only needs to establish that θ and x ↦ x * θ x are injective.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- A transversal of cardinality |G| in the Cayley table graph gives a complete mapping of G. -/theorem cayley_table_graph_exists_complete_mapping_of_transversal (G : Type*) [Group G] [Fintype G] (s : Finset (G × G)) (hindep : (cayley_table_graph G).IsIndepSet (s : Set (G × G))) (hcard : s.card = Fintype.card G) : ∃ θ : G → G, group_is_complete_mapping θ := by classical have hfst : ∀ p ∈ s, ∀ q ∈ s, p.1 = q.1 → p = q := by intro p hp q hq h by_contra hne exact hindep hp hq hne ⟨hne, Or.inl h⟩ have hsnd : ∀ p ∈ s, ∀ q ∈ s, p.2 = q.2 → p = q := by intro p hp q hq h by_contra hne exact hindep hp hq hne ⟨hne, Or.inr (Or.inl h)⟩ have himg : s.image (fun p : G × G => p.1) = Finset.univ := by apply Finset.eq_univ_of_card rw [Finset.card_image_of_injOn, hcard] intro p hp q hq h exact hfst p hp q hq h have hex : ∀ x : G, ∃ y : G, (x, y) ∈ s := by intro x have : x ∈ s.image (fun p : G × G => p.1) := by rw [himg]; simp rw [Finset.mem_image] at this obtain ⟨p, hp, hpx⟩ := this exact ⟨p.2, by rw [← hpx]; exact hp⟩ let θ : G → G := fun x => if h : ∃ y, (x, y) ∈ s then h.choose else 1 have hmem : ∀ x : G, (x, θ x) ∈ s := by intro x have h := hex x simp only [θ] rw [dif_pos h] exact h.choose_spec have hθinj : Function.Injective θ := by intro x y hxy have hp := hmem x have hq := hmem y have hpq : (x, θ x) = (y, θ y) := hsnd _ hp _ hq hxy have : (x, θ x).1 = (y, θ y).1 := by rw [hpq] simpa using this have hψinj : Function.Injective (fun x => x * θ x) := by intro x y hxy by_contra hne have hp := hmem x have hq := hmem y have hpq : (x, θ x) ≠ (y, θ y) := by intro h exact hne (Prod.ext_iff.mp h).1 exact hindep hp hq hpq ⟨hpq, Or.inr (Or.inr hxy)⟩ refine ⟨θ, hθinj.bijective_of_finite, hψinj.bijective_of_finite⟩