GStableKneser
def
For 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 subsets of vertices of G of cardinality k, with an edge between two such sets if and only if they are disjoint and distinct.
Statement
def GStableKneser {V : Type*} (G : SimpleGraph V) (k : ℕ) : SimpleGraph { s : Finset V // G.IsNIndepSet k s }
- Defined in
- scout/2610-17884-the-chromatic-number-of-g-stable-kneser-graphs.md:108
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 16
- op_193_cubic_noncolorable_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), if the cycle-stable k-set graph is not (m-2k+1)-colorable, then adding an isolated vertex…
- is_k_tight_cycle_sum_unit_iffFor k ≥ 3 and m ≥ 4*k - 3, the disjoint sum of the m-cycle and an isolated vertex is k-tight if and only if the chromatic number of its…
- op_193_cycle_isolated_vertex_k3_m10The stable triple graph of the ten-cycle plus an isolated vertex has chromatic number seven.
- 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…
- op_193_hom_cycle_stepFor all integers k ≥ 2 and r ≥ 2 * k - 2, there exists a graph homomorphism from the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) to the…
- 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…
- op_193_cycle_isolated_vertex_k_tight_iff_geFor k ≥ 3 and m ≥ 4*k - 3, the chromatic number of the G-stable Kneser graph of the disjoint sum of the m-cycle and an isolated vertex…
- op_193_cubic_tight_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), the stable k-set graph of the m-cycle plus an isolated vertex has chromatic number m-2k+3,…
- not_is_k_tight_emptyThe empty graph on 0 vertices is not k-tight for any k ≥ 2.
- op_193_cycle_isolated_vertex_k3_m9The G-stable Kneser graph KG(C_9 ⊔ K_1, 3), where the base graph is the disjoint sum of the 9-cycle and an isolated vertex, has chromatic…
- is_k_tightA finite graph G on n vertices is k-tight if the chromatic number of its G-stable Kneser graph KG(G, k) equals n - 2*k + 2.
- op_193_cycle_isolated_vertex_chromatic_leFor any natural numbers k ≥ 3 and m ≥ 4 * k - 3, the chromatic number of the G-stable Kneser graph of the disjoint sum of the m-cycle and…
- op_193_chromaticNumber_le_cycle_stepFor all integers k ≥ 2 and r ≥ 2 * k - 2, the chromatic number of the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) is at most the chromatic…
- op_193_kneser_hom_sum_inlFor 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…
- op_193_covering_color_obstructionIf every proper q-coloring of the cycle-stable k-set graph has a stable (k-1)-set whose disjoint stable k-sets realize all q colors, then…
- op_193_noncolorable_if_stable_anchor_avoidanceIf the cycle-only stable k-set graph is not (m-2k+1)-colorable and every family of m-2k+2 stable k-sets can be met in at most one point by…
Read back from the Lean
For a type V, a simple graph G on V, and a natural number k, GStableKneser G k is the simple graph whose vertex type is the subtype of all s : Finset V such that s is an independent set of size k in G (G.IsNIndepSet k s). Two vertices s and t in this subtype are adjacent if and only if their underlying finite sets s.1 and t.1 are disjoint and s ≠ t.
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 G-stable Kneser graph KG(G, k), whose vertices are the independent k-sets of G and whose edges join disjoint independent sets. -/ def GStableKneser {V : Type*} (G : SimpleGraph V) (k : ℕ) : SimpleGraph { s : Finset V // G.IsNIndepSet k s } where Adj s t := Disjoint s.1 t.1 ∧ s ≠ t symm := ⟨fun _ _ h => ⟨h.1.symm, h.2.symm⟩⟩ loopless := ⟨fun _ h => h.2 rfl⟩