A cycle plus an isolated vertex is $k$-tight once the cycle has length at least $k((k-1)^2+1)$
low tier2026-11-12OP-193reviewed by Claude Code中文版
Abstract
For $k \ge 3$ and $m \ge 4k-3$, arXiv:2610.17884 asks whether the disjoint union $C_m \sqcup K_1$ of an $m$-cycle and an isolated vertex is $k$-tight, that is, whether its stable Kneser graph $\operatorname{KG}(C_m \sqcup K_1, k)$, whose vertices are the independent $k$-sets and whose edges join disjoint ones, has chromatic number $m-2k+3$. The paper calls this the simplest open case of its Conjecture 1.3 and proves it only for $m$ beyond an implicit threshold $n_0(k)$, defined by a counting comparison between anchored colour classes and the number of stable $k$-sets. We prove that $C_m \sqcup K_1$ is $k$-tight for every $k \ge 3$ and every $m \ge k((k-1)^2+1)$, for example from $m = 15$ on when $k = 3$ and from $m = 40$ on when $k = 4$. The proof keeps the paper's reduction to a non-anchored colour class, but finds that class differently: by Turán's theorem, any $m-2k+2$ sets of at most $k$ cycle vertices are each met in at most one vertex by some independent $k$-set of the cycle, so no optimal colouring of the cycle's stable Kneser graph can have all its classes anchored. The result is verified in Lean 4 as op_193_cubic_tight_if_cycle_lower, taking as a hypothesis the classical lower bound $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$ for the cycle alone.
1. Introduction
Given a graph $G$ on $n$ vertices and an integer $k \ge 1$, the $G$-stable Kneser graph $\operatorname{KG}(G,k)$ has as vertices the independent $k$-sets of $G$, two of them adjacent when they are disjoint. The standard colouring gives $\chi(\operatorname{KG}(G,k)) \le n-2k+2$, and $G$ is called $k$-tight when equality holds. For the $m$-cycle, $\operatorname{KG}(C_m,k)$ is the Schrijver graph, and the classical theorem on it says that $C_m$ is $k$-tight for $m \ge 2k$.
The paper arXiv:2610.17884 studies which graphs are $k$-tight. It shows that a $k$-tight graph is a disjoint union of paths and cycles in which every cycle it properly contains has length at least $4k-3$, and it conjectures the converse (its Conjecture 1.3). It then remarks that even the simplest case not covered by the cycle theorem is open: a cycle of length at least $4k-3$ together with an isolated vertex. In the paper's words, "we were only able to prove it asymptotically". The question is therefore: for $k \ge 3$ and $m \ge 4k-3$, is $$\chi(\operatorname{KG}(C_m \sqcup K_1, k)) = (m+1) - 2k + 2 = m-2k+3 ?$$
The paper's asymptotic result (its Theorem 1.4) holds for $m \ge n_0(k)$, where $n_0(k)$ is the least integer from which a counting inequality holds: $m-2k+2$ times the largest size of an anchored independent set of the Schrijver graph is smaller than its number of vertices. The paper gives no closed form for $n_0(k)$. With its bound on anchored sets, the comparison at $k = 3$ holds only from cycle length $21$ on, and for large $k$ it needs cycle length of order $k^4$.
We prove the statement for every $k \ge 3$ and every $m \ge k((k-1)^2+1)$, a threshold of order $k^3$ that equals $15$ at $k = 3$ and $40$ at $k = 4$. The argument follows the paper's route through a non-anchored colour class, but replaces the counting of anchored classes by a short application of Turán's theorem to an auxiliary graph on the cycle vertices. The theorem is op_193_cubic_tight_if_cycle_lower. Its one hypothesis, $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$, is the classical theorem on Schrijver graphs, which is not yet formalized in Lean and is assumed in the statement.
Two small cases of the window $4k-3 \le m < k((k-1)^2+1)$ are also verified: $\chi(\operatorname{KG}(C_9 \sqcup K_1, 3)) = 6$ (op_193_cycle_isolated_vertex_k3_m9) and, by a separate case analysis, $\chi(\operatorname{KG}(C_{10} \sqcup K_1, 3)) = 7$. For $k = 3$ the lengths $m = 11, \dots, 14$ remain open.
2. Preliminaries
Definition 1 (GStableKneser). For a simple graph $G$ on a finite vertex type $V$ and $k \in \mathbb{N}$, the graph GStableKneser G k has as vertices the finite sets $s \subseteq V$ with $|s| = k$ that are independent in $G$, and joins $s$ and $t$ when $s \ne t$ and $s \cap t = \emptyset$. We write $\operatorname{KG}(G,k)$ for it. For the cycle, $\operatorname{KG}(C_m,k)$ is the Schrijver graph $\operatorname{SG}(m,k)$ on the stable $k$-sets of $C_m$.
Definition 2 (cycle plus an isolated vertex). $C_m$ is Mathlib's SimpleGraph.cycleGraph m on $\operatorname{Fin} m$, and the isolated vertex is the empty graph $\bot$ on the one-point type Unit. Their disjoint sum $C_m \sqcup K_1$ has vertex type $\operatorname{Fin} m \oplus \operatorname{Unit}$ and no edges between the two parts. We write $\infty$ for the isolated vertex. An independent $k$-set of $C_m \sqcup K_1$ is either a stable $k$-set of the cycle or $F \cup \{\infty\}$ with $F$ a stable $(k-1)$-set of the cycle.
Definition 3 ($k$-tightness). With $n = m+1$ vertices, $C_m \sqcup K_1$ is $k$-tight when $\chi(\operatorname{KG}(C_m \sqcup K_1,k)) = m-2k+3$; is_k_tight_cycle_sum_unit_iff records this reading of the definition for $k \ge 3$ and $m \ge 4k-3$. Chromatic numbers in Lean take values in $\mathbb{N}_\infty$, and the statements compare them with natural numbers cast into $\mathbb{N}_\infty$.
Definition 4 (anchored classes). Let $c$ be a proper colouring of $\operatorname{SG}(m,k)$. A colour class $\mathcal{A}$ is anchored if some $U \in \mathcal{A}$, an anchor, satisfies $|U \cap W| \ge 2$ for every $W \in \mathcal{A}$. This is the notion of arXiv:2610.17884, Section 3.
Known facts used. The upper bound $\chi(\operatorname{KG}(C_m \sqcup K_1,k)) \le m-2k+3$ for $k \ge 3$, $m \ge 4k-3$ is op_193_cycle_isolated_vertex_chromatic_le, and op_193_cycle_isolated_vertex_k_tight_iff_ge turns tightness into the lower bound alone. Turán's theorem, in the form available in Mathlib: a graph on $m$ vertices with no clique of size $r+1$ has at most $\frac{r-1}{2r} m^2$ edges.
3. Main result
Theorem (op_193_cubic_tight_if_cycle_lower). Let $k \ge 3$ and $m \ge k((k-1)^2+1)$. If $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$, then $$\chi(\operatorname{KG}(C_m \sqcup K_1, k)) = m-2k+3 .$$
In Lean the statement takes k m : ℕ, the hypotheses 3 ≤ k, k * ((k-1)^2+1) ≤ m and ((m-2*k+2 : ℕ) : ℕ∞) ≤ (GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber, and concludes that the chromatic number of GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k equals m-2*k+3. The hypothesis is the classical theorem on Schrijver graphs, so mathematically the result is unconditional: $C_m \sqcup K_1$ is $k$-tight for all $k \ge 3$ and $m \ge k((k-1)^2+1)$.
The heart of the proof is the colourability statement op_193_cubic_noncolorable_if_cycle_lower: under the same bounds on $k$ and $m$, if $\operatorname{KG}(C_m,k)$ is not $(m-2k+1)$-colourable, then $\operatorname{KG}(C_m \sqcup K_1,k)$ is not $(m-2k+2)$-colourable. It rests on an avoidance lemma, also proved: for any sets $A_1, \dots, A_{m-2k+2}$ of at most $k$ vertices of $C_m$, some stable $k$-set $S$ of the cycle has $|S \cap A_j| \le 1$ for every $j$. The threshold enters only through the polynomial inequality op_193_cubic_threshold_edge_gap: for real $k \ge 3$ and $m \ge k((k-1)^2+1)$, $$m^2 - 3(k-1)m - (m-2k+2)\,k(k-1)^2 > 0 .$$
Compared with arXiv:2610.17884, the theorem gives the paper's Theorem 1.4 with the explicit threshold $k((k-1)^2+1)$ in place of $n_0(k)$. It does not reach the conjectured range $m \ge 4k-3$.
theorem op_193_cubic_tight_if_cycle_lower (k m : ℕ) (hk : 3 ≤ k)
(hm : k * ((k-1)^2+1) ≤ m)
(hcycle : ((m-2*k+2 : ℕ) : ℕ∞) ≤ (GStableKneser (SimpleGraph.cycleGraph m) k).chromaticNumber) :
(GStableKneser ((SimpleGraph.cycleGraph m).sum (⊥ : SimpleGraph Unit)) k).chromaticNumber =
m-2*k+34. Proof
Let $q = m-2k+2$. The proof has four steps: an avoidance lemma from Turán's theorem, a non-anchored colour class, the paper's step from such a class to an uncolourable vertex, and the matching upper bound.
Step 1 (avoidance). Let $A_1, \dots, A_q$ be sets of at most $k$ vertices of $C_m$. Let $H$ be the graph on the vertices of $C_m$ in which $x \ne y$ are adjacent when they are not adjacent on the cycle and no $A_j$ contains both. A $k$-clique of $H$ is a stable $k$-set of $C_m$ meeting each $A_j$ in at most one vertex, so it is enough to show that $H$ has a $k$-clique. The cycle has $m(m-3)/2$ non-adjacent pairs, and each $A_j$ contains at most $k(k-1)/2$ pairs, so $$2|E(H)| \ge m(m-3) - q\,k(k-1).$$ If $H$ had no $k$-clique, Turán's theorem with $r = k-1$ would give $2(k-1)|E(H)| \le (k-2)m^2$. Multiplying the first inequality by $k-1$ and combining, $$m^2 - 3(k-1)m - q\,k(k-1)^2 \le 0 ,$$ which contradicts op_193_cubic_threshold_edge_gap since $q = m-2k+2$. That lemma is proved by the identity, with $d = m - k((k-1)^2+1) \ge 0$, $$m^2 - 3(k-1)m - (m-2k+2)k(k-1)^2 = k(k-2)^2 + d\,(k^2(k-2)+3) + d^2 ,$$ whose right side is positive for $k \ge 3$. In Lean the clique bound is Mathlib's Turán theorem, the edge count is done over $\mathbb{N}$, and the final contradiction is a nonlinear-arithmetic step over $\mathbb{R}$.
Step 2 (a non-anchored class). Suppose $c$ is a proper colouring of $\operatorname{KG}(C_m \sqcup K_1,k)$ with $q$ colours, and let $c'$ be its restriction to the stable $k$-sets of the cycle, a proper $q$-colouring of $\operatorname{SG}(m,k)$. If every colour class $j$ of $c'$ had an anchor $U_j$, Step 1 applied to $U_1, \dots, U_q$ would give a stable $k$-set $S$ with $|S \cap U_j| \le 1$ for all $j$. But $S$ has some colour $j = c'(S)$, and the anchor of its class satisfies $|S \cap U_j| \ge 2$. So some class $j$ of $c'$ is not anchored.
Step 3 (the isolated vertex cannot be coloured). This is the argument of arXiv:2610.17884, Section 3. By hypothesis $\operatorname{SG}(m,k)$ has no proper $(q-1)$-colouring. Hence some $U$ of colour $j$ is disjoint from sets of every other colour: otherwise each set of colour $j$ could be recoloured with a colour missing from its neighbours. The sets of colour $j$ are pairwise non-disjoint, so this gives a proper $(q-1)$-colouring. Since class $j$ is not anchored, some $W$ of colour $j$ has $|U \cap W| \le 1$, and $|U \cap W| = 1$ because $U$ and $W$ have the same colour. Let $F = U \setminus W$, a stable $(k-1)$-set of the cycle. Every set disjoint from $U$ is disjoint from $F$, and $W$ is disjoint from $F$. So the stable $k$-sets of the cycle disjoint from $F$ carry all $q$ colours. Now $F \cup \{\infty\}$ is a vertex of $\operatorname{KG}(C_m \sqcup K_1,k)$, disjoint from all of these sets, so it has no colour left, a contradiction. Together, Steps 2 and 3 are the lemma op_193_cubic_noncolorable_if_cycle_lower: $\operatorname{KG}(C_m \sqcup K_1,k)$ is not $q$-colourable.
Step 4 (assembly). In op_193_cubic_tight_if_cycle_lower, the hypothesis $\chi(\operatorname{KG}(C_m,k)) \ge m-2k+2$ first gives that $\operatorname{KG}(C_m,k)$ is not $(m-2k+1)$-colourable. Step 3 then shows $\operatorname{KG}(C_m \sqcup K_1,k)$ is not $(m-2k+2)$-colourable, so its chromatic number in $\mathbb{N}_\infty$ is strictly greater than $m-2k+2$, hence at least $m-2k+3$. From $k \ge 3$ we get $(k-1)^2+1 \ge 5$, so $m \ge 5k > 4k-3$, and op_193_cycle_isolated_vertex_k_tight_iff_ge, which uses the upper bound op_193_cycle_isolated_vertex_chromatic_le, turns this lower bound into equality.
For example, at $k = 3$ the theorem covers all $m \ge 15$, where $\chi(\operatorname{KG}(C_m \sqcup K_1, 3)) = m-3$. At $k = 4$ it covers all $m \ge 40$, where the value is $m-5$.
5. Discussion
The theorem replaces the implicit threshold of the paper's asymptotic result by the explicit cubic $k((k-1)^2+1)$. It is a strengthening of the paper's Theorem 1.4, not a resolution of the question, which asks for all $m \ge 4k-3$. The window $4k-3 \le m < k((k-1)^2+1)$ stays open apart from the two verified cases at $k = 3$, namely $m = 9$ and $m = 10$.
The gain comes from how a non-anchored class is found. The paper bounds the size of an anchored class and needs $q$ anchored classes to be too small to cover all stable $k$-sets. The avoidance lemma instead uses only the anchors themselves: $q$ sets of size $k$ forbid at most $q\binom{k}{2}$ pairs, and Turán's theorem then still produces a stable $k$-set that meets each anchor in at most one vertex. The identity in Step 1 shows the edge inequality already holds at $d = 0$ with slack $k(k-2)^2$, so the method's true threshold is slightly below $k((k-1)^2+1)$, but it is of order $k^3$ by this argument.
For small cycles, Step 2 fails: it cannot hold for every optimal colouring of the Schrijver graph. op_193_nine_cycle_stable_triples_anchored_five_coloring gives a proper $5$-colouring of the stable triples of $C_9$ in which every class is anchored, and similar colourings with every class anchored are verified for $C_{11}$ with $7$ colours and $C_{12}$ with $8$ colours. At these lengths some optimal colouring of the Schrijver graph has no non-anchored class. A proof of tightness there must use more than Step 2 does, for instance which colourings of the cycle part extend to the sets containing $\infty$. The cases $m = 9$ and $m = 10$ at $k = 3$ were settled by direct verification.
Two questions remain. First, can a sharper avoidance argument, one that uses the stability of the anchors and the cycle structure rather than only their sizes, bring the threshold down to linear order in $k$? Second, can the step homomorphism op_193_hom_cycle_step, from $\operatorname{KG}(C_{r+2} \sqcup K_1,k)$ to $\operatorname{KG}(C_r \sqcup K_1,k-1)$, help fill the window? It carries tightness from $(m,k)$ down to $(m-2,k-1)$. Because the threshold grows with $k$, this moves away from the window, so it would need a reduction going the other way. Finally, the Lean statement assumes the lower bound for Schrijver graphs, whose topological proof is not yet formalized.
Why it is research-level
- Conditional on the published cycle-only chromatic lower bound, gives the explicit sufficient cycle length m ≥ k((k−1)²+1) for the cycle-plus-isolated-vertex conjecture; the source paper proves the result only for an unspecified sufficiently large threshold
Lean declarations
- 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,…
- 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_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_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_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_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…
- op_193_cubic_threshold_edge_gapThe edge-count gap in the clique-free anchor argument is strictly positive at and beyond the cubic threshold.
- op_193_nine_cycle_stable_triples_anchored_five_coloringThe stable triples of the nine-cycle have a proper five-coloring in which every color class has an anchor intersecting each triple of the…
- 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…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.17884 — The chromatic number of $G$-stable Kneser graphs
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.