AFTD Auto-Formalizing Theoretical Domains

is_k_tight

def

A 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.

Statement

def is_k_tight {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) : Prop
Defined in
arXiv:2610.17884 Sec. 1 -- The chromatic number of G-stable Kneser graphs
Verified
19 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 2
  • 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…
  • not_is_k_tight_emptyThe empty graph on 0 vertices is not k-tight for any k ≥ 2.

Read back from the Lean

Given a finite type V, a simple graph G on V, and a natural number k, is_k_tight G k asserts that the chromatic number of GStableKneser G k is equal to (Fintype.card V - 2 * k) + 2 (computed using natural number arithmetic and coerced to ℕ∞).

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

/-- A finite graph G on n vertices is k-tight if the chromatic number of its G-stable Kneser graph is n - 2*k + 2. -/
def is_k_tight {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ) : Prop := (GStableKneser G k).chromaticNumber = ((Fintype.card V - 2 * k + 2 : ℕ) : ℕ∞)
See it in the graphDiscuss this resultChallenge it