AFTD Auto-Formalizing Theoretical Domains

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⟩
See it in the graphDiscuss this resultChallenge it