op_193_cycle_isolated_vertex_k_tight_iff_ge
For 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 equals m - 2*k + 3 if and only if it is at least m - 2*k + 3.
Statement
theorem op_193_cycle_isolated_vertex_k_tight_iff_ge
(k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) :
(GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber =
m - 2 * k + 3 ↔
(m - 2 * k + 3 : ℕ∞) ≤ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber- Source
- arXiv:2610.17884 Sec. 1 -- The chromatic number of G-stable Kneser graphs
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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…
- 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 1
- 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,…
Read back from the Lean
For any natural numbers $k$ and $m$ satisfying $k \ge 3$ and $m \ge 4k - 3$, the chromatic number of the generalized (stable) Kneser graph on the $k$-element independent sets of the disjoint union of the $m$-cycle graph and an isolated vertex (the edgeless graph on Unit) is equal to $m - 2k + 3$ if and only if its chromatic number is at least $m - 2k + 3$ (in $\mathbb{N}_\infty$).
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 theorem states that for k ≥ 3 and m ≥ 4*k - 3, the chromatic number of the G-stable Kneser graph of C_m ⊔ K_1 equals m - 2*k + 3 if and only if it is at least m - 2*k + 3. The forward direction is trivial by reflexivity of the order. The reverse direction combines the assumed lower bound with the established upper bound from `op_193_cycle_isolated_vertex_chromatic_le` using antisymmetry of ≤.
The natural arithmetic expression m - 2*k + 3 coerced to ℕ∞ equals the expression evaluated in ℕ∞.
Distribute the coercion from ℕ to ℕ∞ across the addition, subtraction, and multiplication using `ENat.natCast_add`, `ENat.natCast_sub`, and `ENat.natCast_mul`, and simplify the numerals with `norm_num`.
uses
ENat.natCast_add,ENat.natCast_sub,ENat.natCast_mulhave hN : ((m - 2 * k + 3 : ℕ) : ℕ∞) = (m : ℕ∞) - 2 * (k : ℕ∞) + 3 := by rw [ENat.natCast_add, ENat.natCast_sub, ENat.natCast_mul] norm_num
The equivalence reduces to proving each implication separately.
Split the if-and-only-if goal into the forward direction (equality implies the inequality) and the reverse direction (the inequality implies equality).
constructorIf the chromatic number equals m - 2*k + 3, then it is at least m - 2*k + 3.
Assume the chromatic number equals m - 2*k + 3. Rewriting by this assumption reduces the goal to reflexivity of ≤.
· intro h rw [h]
If the chromatic number is at least m - 2*k + 3, then it equals m - 2*k + 3.
Assume the lower bound h. The matching upper bound that the chromatic number is at most m - 2*k + 3 is given by `op_193_cycle_isolated_vertex_chromatic_le` (adjusted by `hN`). Combining the two inequalities via `le_antisymm` yields equality.
uses
le_antisymm,op_193_cycle_isolated_vertex_chromatic_le· intro h exact le_antisymm (by simpa [hN] using op_193_cycle_isolated_vertex_chromatic_le k m hk hm) h
ENat.natCast_add- The natural cast into ℕ∞ distributes over addition: ↑(m + n) = ↑m + ↑n.
ENat.natCast_sub- The natural cast into ℕ∞ distributes over subtraction: ↑(m - n) = ↑m - ↑n.
ENat.natCast_mul- The natural cast into ℕ∞ distributes over multiplication: ↑(m * n) = ↑m * ↑n.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
op_193_cycle_isolated_vertex_chromatic_le- For k ≥ 3 and m ≥ 4*k - 3, the chromatic number of the G-stable Kneser graph of C_m ⊔ K_1 is at most m - 2*k + 3.
- The auxiliary equality `hN` handles the formal coercion detail between arithmetic operations in ℕ cast into ℕ∞ and operations evaluated directly in ℕ∞.
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.
/-- The chromatic number of the G-stable Kneser graph of C_m ⊔ K_1 equals m - 2*k + 3 if and only if it is at least m - 2*k + 3. -/theorem op_193_cycle_isolated_vertex_k_tight_iff_ge (k m : ℕ) (hk : 3 ≤ k) (hm : 4 * k - 3 ≤ m) : (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber = m - 2 * k + 3 ↔ (m - 2 * k + 3 : ℕ∞) ≤ (GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber := by have hN : ((m - 2 * k + 3 : ℕ) : ℕ∞) = (m : ℕ∞) - 2 * (k : ℕ∞) + 3 := by rw [ENat.natCast_add, ENat.natCast_sub, ENat.natCast_mul] norm_num constructor · intro h rw [h] · intro h exact le_antisymm (by simpa [hN] using op_193_cycle_isolated_vertex_chromatic_le k m hk hm) h