cayley_table_graph
The 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 (g₂, h₂) are adjacent if they share a row (g₁ = g₂), a column (h₁ = h₂), or a product symbol (g₁ * h₁ = g₂ * h₂).
Statement
def cayley_table_graph (G : Type*) [Mul G] : SimpleGraph (G × G)
- Defined in
- arXiv:2611.13274 Sec. 1
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Used by 6
- cayley_table_graph_exists_complete_mapping_of_transversalIf the Cayley table graph of a finite group G contains a transversal of cardinality |G|, then G admits a complete mapping.
- 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.
- cayley_table_graph_quaternion_chromatic_number_geFor every integer n ≥ 1, the chromatic number of the Cayley table graph of the generalized quaternion group QuaternionGroup (2 * n + 1) is…
- cayley_table_graph_indep_set_card_leIn the Latin square graph of the Cayley table of a finite group G, every independent set (partial transversal) has cardinality at most |G|.
- cayley_table_graph_chromatic_number_le_card_of_complete_mappingIf a finite group G admits a complete mapping, then the chromatic number of its Cayley table graph is at most |G|.
- cayley_table_graph_exists_transversal_of_chromatic_number_le_succIf the chromatic number of the Cayley table graph of a finite group G is at most |G| + 1, then the Cayley table has a transversal (an…
Read back from the Lean
Given a type G equipped with a multiplication operation ([Mul G]), cayley_table_graph G is the simple graph with vertex set G × G where two vertices u and v are adjacent if and only if u ≠ v and at least one of the following conditions holds:
1. u.1 = v.1 (they share the same first coordinate),
2. u.2 = v.2 (they share the same second coordinate), or
3. u.1 * u.2 = v.1 * v.2 (the product of the components of u equals the product of the components of v).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The Latin square graph of the Cayley table of a magma G, with vertices G × G and edges between distinct cells sharing row, column, or symbol. -/ def cayley_table_graph (G : Type*) [Mul G] : SimpleGraph (G × G) where Adj u v := u ≠ v ∧ (u.1 = v.1 ∨ u.2 = v.2 ∨ u.1 * u.2 = v.1 * v.2)