op_193_kneser_hom_sum_inl
For any simple graphs G and H and any natural number k, there exists a graph homomorphism from the G-stable Kneser graph KG(G, k) to the (G ⊔ H)-stable Kneser graph KG(G ⊔ H, k).
Statement
theorem op_193_kneser_hom_sum_inl {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (k : ℕ) : Nonempty (GStableKneser G k →g GStableKneser (G.sum H) k)
- Source
- Mathlib.Combinatorics.SimpleGraph.Sum
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- GStableKneserFor a simple graph G and a natural number k, the G-stable Kneser graph KG(G, k) is the simple graph whose vertices are the independent…
- g_stable_kneser_adjTwo independent k-sets s and t in the G-stable Kneser graph KG(G, k) are adjacent if and only if their underlying vertex sets are disjoint…
- Used by 1
- op_193_cycle_isolated_vertex_chromatic_ge_cycleFor any natural numbers k and m, the chromatic number of the G-stable Kneser graph of the disjoint union of an m-cycle and an isolated…
Read back from the Lean
For any types $V$ and $W$, any simple graphs $G$ on $V$ and $H$ on $W$, and any natural number $k$, there exists a graph homomorphism from the stable Kneser graph GStableKneser G k to GStableKneser (G.sum H) k (where G.sum H is the disjoint union graph of $G$ and $H$ on $V \oplus W$).
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 constructs a graph homomorphism from KG(G, k) to KG(G ⊕ H, k) by mapping each independent k-set s of G to its image under the canonical inclusion inl : V ↪ V ⊕ W. Because inl is an embedding and there are no edges between summands in the graph sum G ⊕ H, the image inl(s) is an independent set of size k. Furthermore, inl preserves disjointness and injectivity on finite sets, ensuring that adjacent vertices in KG(G, k) map to adjacent vertices in KG(G ⊕ H, k).
Define the candidate vertex map f sending each independent k-set s of G to its image under the canonical inclusion into V ⊕ W, reducing well-definedness to verifying independence and cardinality.
We define the vertex map f by applying the canonical embedding inl : V ↪ V ⊕ W to the underlying finite set of each independent k-set s of G. To show that inl(s) is a valid vertex of KG(G ⊕ H, k), we split the IsNIndepSet condition into two subgoals: proving that inl(s) is an independent set in G ⊕ H, and proving that its cardinality is k.
let f : { s : Finset V // G.IsNIndepSet k s } → { t : Finset (V ⊕ W) // (G.sum H).IsNIndepSet k t } := fun s => ⟨s.1.map Function.Embedding.inl, by refine ⟨?_, ?_⟩
The image inl(s) is an independent set in the graph sum G ⊕ H.
Rewriting the finset image as a set image using Finset.coe_map, consider two distinct elements in inl(s), which must be of the form inl(u) and inl(v) for some u, v ∈ s. Unfolding the definition of adjacency in the graph sum (SimpleGraph.sum), inl(u) and inl(v) are adjacent in G ⊕ H if and only if u and v are adjacent in G. Since u and v are distinct vertices in the independent set s, they cannot be adjacent in G, giving a contradiction.
uses
Finset.coe_map,SimpleGraph.sum· rw [Finset.coe_map] rintro _ ⟨u, hu, rfl⟩ _ ⟨v, hv, rfl⟩ hne dsimp [SimpleGraph.sum] intro h have : u ≠ v := by rintro rfl exact hne rfl exact s.2.isIndepSet hu hv this h
The image inl(s) has cardinality k, completing the definition of the vertex map f.
Because mapping along an injective embedding preserves the cardinality of a finite set (Finset.card_map), the cardinality of inl(s) equals the cardinality of s, which is k by the assumption that s is a k-independent set.
uses
Finset.card_map· rw [Finset.card_map] exact s.2.card_eq⟩
To show that f defines a graph homomorphism, it suffices to show that f(s) ≠ f(t) for adjacent vertices s and t, as their disjointness is preserved.
We package f into a graph homomorphism. By g_stable_kneser_adj, adjacency in a stable Kneser graph means that two independent sets are disjoint and distinct. Given adjacent vertices s and t, their images f(s) and f(t) are disjoint because mapping along an embedding preserves disjointness (Finset.disjoint_map), leaving only the requirement to show that f(s) ≠ f(t).
uses
g_stable_kneser_adj,Finset.disjoint_maprefine ⟨⟨f, ?_⟩⟩ intro s t h rw [g_stable_kneser_adj] at h ⊢ rcases h with ⟨hdisj, hne⟩ refine ⟨(Finset.disjoint_map Function.Embedding.inl).mpr hdisj, ?_⟩
The images f(s) and f(t) are distinct, completing the proof that f is a graph homomorphism.
Suppose for contradiction that f(s) = f(t). Then their underlying finite sets inl(s) and inl(t) are equal. Since inl is injective, Finset.map_injective implies s = t, which contradicts the hypothesis that s and t are distinct. Thus f(s) ≠ f(t).
uses
Finset.map_injectiveintro h_eq apply hne ext1 have h1 : (f s).1 = (f t).1 := by rw [h_eq] exact Finset.map_injective Function.Embedding.inl h1
Finset.coe_map- The coercion to a set of the image of a finite set under an embedding equals the set-theoretic image under that embedding.
SimpleGraph.sum- The disjoint union of two graphs, where vertices within each summand retain their original adjacency and vertices in different summands are never adjacent.
Finset.card_map- Mapping a finite set along an injective embedding preserves its cardinality.
g_stable_kneser_adj- Two vertices in a stable Kneser graph are adjacent if and only if their underlying independent sets are disjoint and distinct.
Finset.disjoint_map- Two finite sets are disjoint if and only if their images under an injective embedding are disjoint.
Finset.map_injective- Mapping finite sets along an injective embedding is an injective operation on finite sets.
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.
/-- Canonical embedding homomorphism from KG(G, k) into KG(G ⊔ H, k). -/theorem op_193_kneser_hom_sum_inl {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (k : ℕ) : Nonempty (GStableKneser G k →g GStableKneser (G.sum H) k) := by let f : { s : Finset V // G.IsNIndepSet k s } → { t : Finset (V ⊕ W) // (G.sum H).IsNIndepSet k t } := fun s => ⟨s.1.map Function.Embedding.inl, by refine ⟨?_, ?_⟩ · rw [Finset.coe_map] rintro _ ⟨u, hu, rfl⟩ _ ⟨v, hv, rfl⟩ hne dsimp [SimpleGraph.sum] intro h have : u ≠ v := by rintro rfl exact hne rfl exact s.2.isIndepSet hu hv this h · rw [Finset.card_map] exact s.2.card_eq⟩ refine ⟨⟨f, ?_⟩⟩ intro s t h rw [g_stable_kneser_adj] at h ⊢ rcases h with ⟨hdisj, hne⟩ refine ⟨(Finset.disjoint_map Function.Embedding.inl).mpr hdisj, ?_⟩ intro h_eq apply hne ext1 have h1 : (f s).1 = (f t).1 := by rw [h_eq] exact Finset.map_injective Function.Embedding.inl h1