cayley_table_graph_indep_set_card_le
In the Latin square graph of the Cayley table of a finite group G, every independent set (partial transversal) has cardinality at most |G|.
Statement
theorem cayley_table_graph_indep_set_card_le (G : Type*) [Group G] [Fintype G] (s : Finset (G × G)) (h : (cayley_table_graph G).IsIndepSet (s : Set (G × G))) : s.card ≤ Fintype.card G
- Source
- arXiv:2611.13274 Section 1
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 1
- 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
For any finite group $G$ and any finite subset $s \subseteq G \times G$, if $s$ is an independent set in the graph cayley_table_graph G, then the cardinality of $s$ is less than or equal to the cardinality of $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 bound is proved by projecting the independent set s ⊆ G × G onto the first coordinate (the row index) in G. If two distinct vertices in s shared the same row, they would be adjacent in the Cayley table graph, contradicting the independence of s. Hence, this projection is injective, implying |s| ≤ |G|.
It suffices to show that the first-coordinate projection map is injective on s.
Rewriting the finset cardinality |s| as the cardinality of the subtype s using Fintype.card_coe, we apply Fintype.card_le_of_injective: constructing an injective map from s to G guarantees |s| ≤ |G|. The chosen map sends each element (r, c) ∈ s to its first coordinate (row) r ∈ G.
uses
Fintype.card_coe,Fintype.card_le_of_injectiverw [← Fintype.card_coe s] refine Fintype.card_le_of_injective (fun x : ↥s => (x.1).1) ?_
Assume for contradiction that two elements of s share the same row coordinate but are distinct.
Let x, y ∈ s and assume their first coordinates agree (x₁ = y₁). To establish injectivity, we assume for contradiction that x ≠ y as elements of the subtype s.
intro x y hxy simp only at hxy by_contra hne
The underlying coordinate pairs in G × G are distinct.
If the underlying pairs in G × G were equal, Subtype.ext would imply that x = y as subtype elements, directly contradicting x ≠ y.
uses
Subtype.exthave hne' : (x : G × G) ≠ (y : G × G) := by intro hh exact hne (Subtype.ext hh)
The two elements are adjacent in the graph, contradicting independence.
By definition, two distinct vertices in the Cayley table graph are adjacent if they share a row, a column, or a product value. Since the two pairs are distinct and share their first coordinate (via Or.inl), they are adjacent. However, both belong to the independent set s, which by definition cannot contain adjacent vertices, yielding a contradiction.
uses
Or.inlhave hadj : (cayley_table_graph G).Adj (x : G × G) (y : G × G) := ⟨hne', Or.inl hxy⟩ exact h x.2 y.2 hne' hadj
Fintype.card_coe- The cardinality of a finset viewed as a subtype type is equal to the cardinality of the finset itself.
Fintype.card_le_of_injective- An injective map between finite types implies that the cardinality of the domain is at most the cardinality of the codomain.
Subtype.ext- Two elements of a subtype are equal if and only if their underlying values are equal.
Or.inl- Given a proof of P, proves the disjunction P ∨ Q.
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.
/-- Every independent set in the Cayley table graph of a finite group has cardinality at most |G|. -/theorem cayley_table_graph_indep_set_card_le (G : Type*) [Group G] [Fintype G] (s : Finset (G × G)) (h : (cayley_table_graph G).IsIndepSet (s : Set (G × G))) : s.card ≤ Fintype.card G := by rw [← Fintype.card_coe s] refine Fintype.card_le_of_injective (fun x : ↥s => (x.1).1) ?_ intro x y hxy simp only at hxy by_contra hne have hne' : (x : G × G) ≠ (y : G × G) := by intro hh exact hne (Subtype.ext hh) have hadj : (cayley_table_graph G).Adj (x : G × G) (y : G × G) := ⟨hne', Or.inl hxy⟩ exact h x.2 y.2 hne' hadj