cayley_table_graph_chromatic_number_le_card_of_complete_mapping
If a finite group G admits a complete mapping, then the chromatic number of its Cayley table graph is at most |G|.
Statement
theorem cayley_table_graph_chromatic_number_le_card_of_complete_mapping (G : Type*) [Group G] [Fintype G] (θ : G → G) (hθ : group_is_complete_mapping θ) : (cayley_table_graph G).chromaticNumber ≤ Fintype.card G
- Formalizes
- arXiv:2611.13274 Theorem 2.10, Theorem 2.14
- 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 function $\theta : G \to G$, if $\theta$ is a complete mapping of $G$, then the chromatic number of the Cayley table graph of $G$ is less than or equal to the cardinality of $G$ (Fintype.card 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
The proof exhibits an explicit |G|-coloring of the Cayley table graph by coloring each cell (x, y) with (θ(x))⁻¹ * y ∈ G. To verify this coloring is proper, we show that adjacent cells cannot receive the same color. Adjacent cells share a row, a column, or a product value; in each case, assuming the colors match forces the cells to coincide using group cancellation, the injectivity of θ, or the bijectivity of x ↦ x * θ(x).
Extract the properties of the complete mapping θ and define a candidate |G|-coloring of the Cayley table.
By definition, the complete mapping θ and the map x ↦ x * θ(x) are both bijective. We define a coloring on the cells of the Cayley table by assigning each cell p = (x, y) to (θ(x))⁻¹ * y ∈ G, identified with an element of Fin(|G|) via `Fintype.equivFin G`.
uses
Fintype.equivFinobtain ⟨hθbij, hprod⟩ := hθ -- Color the cell (x, y) by (θ x)⁻¹ * y ∈ G. let color : G × G → Fin (Fintype.card G) := fun p => Fintype.equivFin G ((θ p.1)⁻¹ * p.2)
Two cells that have the same color and the same Cayley table product must coincide.
Suppose p = (p₁, p₂) and q = (q₁, q₂) satisfy (θ(p₁))⁻¹ * p₂ = (θ(q₁))⁻¹ * q₂ and p₁ * p₂ = q₁ * q₂. By group arithmetic, p₁ * θ(p₁) = (p₁ * p₂) * ((θ(p₁))⁻¹ * p₂)⁻¹, which equals q₁ * θ(q₁) by substituting the shared product and color. Because x ↦ x * θ(x) is injective, this implies p₁ = q₁. Then p₂ = θ(p₁) * ((θ(p₁))⁻¹ * p₂) = θ(q₁) * ((θ(q₁))⁻¹ * q₂) = q₂. Since both components agree, p = q by `Prod.ext`.
uses
Prod.ext-- Cells with the same color and the same product symbol coincide. have hkey : ∀ p q : G × G, (θ p.1)⁻¹ * p.2 = (θ q.1)⁻¹ * q.2 → p.1 * p.2 = q.1 * q.2 → p = q := by intro p q hc hp have h1 : p.1 * θ p.1 = q.1 * θ q.1 := by have e1 : p.1 * θ p.1 = p.1 * p.2 * ((θ p.1)⁻¹ * p.2)⁻¹ := by group have e2 : q.1 * θ q.1 = q.1 * q.2 * ((θ q.1)⁻¹ * q.2)⁻¹ := by group rw [e1, e2, hc, hp] have hx : p.1 = q.1 := hprod.injective h1 have hy : p.2 = q.2 := by have e1 : p.2 = θ p.1 * ((θ p.1)⁻¹ * p.2) := by group have e2 : q.2 = θ q.1 * ((θ q.1)⁻¹ * q.2) := by group rw [e1, e2, hc, hx] exact Prod.ext hx hy
To bound the chromatic number by |G|, it suffices to show that any two adjacent cells with the same color are equal, split across the three adjacency relations.
By `SimpleGraph.Colorable.chromaticNumber_le`, constructing a proper |G|-coloring bounds the chromatic number by |G|. We assume for contradiction that adjacent cells u and v have the same color. Since adjacent vertices are distinct (u ≠ v), deriving u = v produces the contradiction. Equality of colors means (θ(u₁))⁻¹ * u₂ = (θ(v₁))⁻¹ * v₂ by injectivity of `Fintype.equivFin G`. By definition of the Cayley table graph, u and v are adjacent because they share a row (u₁ = v₁), share a column (u₂ = v₂), or share a product symbol (u₁ * u₂ = v₁ * v₂).
uses
SimpleGraph.Colorable.chromaticNumber_le,Fintype.equivFinrefine SimpleGraph.Colorable.chromaticNumber_le ⟨⟨color, ?_⟩⟩ intro u v hadj hcol apply hadj.1 have hcu : (θ u.1)⁻¹ * u.2 = (θ v.1)⁻¹ * v.2 := (Fintype.equivFin G).injective hcol rcases hadj.2 with h | h | h
Adjacent cells in the same row cannot share the same color.
If u and v share a row, then u₁ = v₁. Expressing u₂ = θ(u₁) * ((θ(u₁))⁻¹ * u₂) and v₂ = θ(v₁) * ((θ(v₁))⁻¹ * v₂), substituting u₁ = v₁ and the equal color values yields u₂ = v₂. Combining the two coordinates via `Prod.ext` gives u = v.
uses
Prod.ext· -- common row: u.1 = v.1, cancel (θ u.1)⁻¹ have hy : u.2 = v.2 := by have e1 : u.2 = θ u.1 * ((θ u.1)⁻¹ * u.2) := by group have e2 : v.2 = θ v.1 * ((θ v.1)⁻¹ * v.2) := by group rw [e1, e2, hcu, h] exact Prod.ext h hy
Adjacent cells in the same column cannot share the same color.
If u and v share a column, then u₂ = v₂. Substituting this into the color equation gives (θ(u₁))⁻¹ * u₂ = (θ(v₁))⁻¹ * u₂. Canceling u₂ on the right with `mul_right_cancel` yields (θ(u₁))⁻¹ = (θ(v₁))⁻¹. Inversion is injective (`inv_injective`) and θ is injective, so u₁ = v₁. Thus u = v by `Prod.ext`.
uses
mul_right_cancel,inv_injective,Prod.ext· -- common column: u.2 = v.2, cancel u.2 on the right, then use injectivity of θ have hx : u.1 = v.1 := by have h2 : (θ u.1)⁻¹ = (θ v.1)⁻¹ := by rw [← h] at hcu exact mul_right_cancel hcu exact hθbij.injective (inv_injective h2) exact Prod.ext hx h
Adjacent cells with the same product symbol cannot share the same color, completing the proof.
If u and v share a product symbol (u₁ * u₂ = v₁ * v₂), they share both color and product, so the key lemma established earlier directly yields u = v, finishing the last case.
· -- common product symbol exact hkey u v hcu h
Fintype.equivFin- A bijection between any finite type α and `Fin (Fintype.card α)`.
Prod.ext- Two pairs (x₁, x₂) and (y₁, y₂) are equal if and only if x₁ = y₁ and x₂ = y₂.
SimpleGraph.Colorable.chromaticNumber_le- If a simple graph admits a proper n-coloring, then its chromatic number is at most n.
mul_right_cancel- Right multiplication in a group is cancellative: if a * b = c * b, then a = c.
inv_injective- Group inversion is injective: if x⁻¹ = y⁻¹, then x = y.
- The `group` tactic is used several times to automatically discharge routine algebraic identities in the group without manually citing associativity and inverse cancellation.
- The definition of coloring maps cells to `Fin (Fintype.card G)` by composing the group element `(θ x)⁻¹ * y` with the bijection `Fintype.equivFin G`, which is a type-theoretic encoding of coloring by elements of G.
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 complete mapping yields a proper |G|-coloring of the Cayley table graph. -/theorem cayley_table_graph_chromatic_number_le_card_of_complete_mapping (G : Type*) [Group G] [Fintype G] (θ : G → G) (hθ : group_is_complete_mapping θ) : (cayley_table_graph G).chromaticNumber ≤ Fintype.card G := by obtain ⟨hθbij, hprod⟩ := hθ -- Color the cell (x, y) by (θ x)⁻¹ * y ∈ G. let color : G × G → Fin (Fintype.card G) := fun p => Fintype.equivFin G ((θ p.1)⁻¹ * p.2) -- Cells with the same color and the same product symbol coincide. have hkey : ∀ p q : G × G, (θ p.1)⁻¹ * p.2 = (θ q.1)⁻¹ * q.2 → p.1 * p.2 = q.1 * q.2 → p = q := by intro p q hc hp have h1 : p.1 * θ p.1 = q.1 * θ q.1 := by have e1 : p.1 * θ p.1 = p.1 * p.2 * ((θ p.1)⁻¹ * p.2)⁻¹ := by group have e2 : q.1 * θ q.1 = q.1 * q.2 * ((θ q.1)⁻¹ * q.2)⁻¹ := by group rw [e1, e2, hc, hp] have hx : p.1 = q.1 := hprod.injective h1 have hy : p.2 = q.2 := by have e1 : p.2 = θ p.1 * ((θ p.1)⁻¹ * p.2) := by group have e2 : q.2 = θ q.1 * ((θ q.1)⁻¹ * q.2) := by group rw [e1, e2, hc, hx] exact Prod.ext hx hy refine SimpleGraph.Colorable.chromaticNumber_le ⟨⟨color, ?_⟩⟩ intro u v hadj hcol apply hadj.1 have hcu : (θ u.1)⁻¹ * u.2 = (θ v.1)⁻¹ * v.2 := (Fintype.equivFin G).injective hcol rcases hadj.2 with h | h | h · -- common row: u.1 = v.1, cancel (θ u.1)⁻¹ have hy : u.2 = v.2 := by have e1 : u.2 = θ u.1 * ((θ u.1)⁻¹ * u.2) := by group have e2 : v.2 = θ v.1 * ((θ v.1)⁻¹ * v.2) := by group rw [e1, e2, hcu, h] exact Prod.ext h hy · -- common column: u.2 = v.2, cancel u.2 on the right, then use injectivity of θ have hx : u.1 = v.1 := by have h2 : (θ u.1)⁻¹ = (θ v.1)⁻¹ := by rw [← h] at hcu exact mul_right_cancel hcu exact hθbij.injective (inv_injective h2) exact Prod.ext hx h · -- common product symbol exact hkey u v hcu h