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 : ℕ) : ℕ∞)