bipartite_subset_colorable_iff_below_threshold
For positive k, the standard lists are colorable at threshold r exactly when r is less than the least uncolorable threshold.
Statement
theorem bipartite_subset_colorable_iff_below_threshold (k r : ℕ) (hk : 1 ≤ k) : bipartite_subset_standard_list_colorable k r ↔ r < bipartite_subset_min_uncolorable_r k- Source
- arXiv:2610.42094, Definition 1.2; monotonicity and least-threshold semantics for OP-861.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- bipartite_subset_standard_list_colorableFor integers k and r, bipartite_subset_standard_list_colorable k r asserts that the bipartite subset graph bipartite_subset_graph k r…
- bipartite_subset_graphFor integers k ≥ 2 and r ≥ 0, G(k,r) is the bipartite graph on two disjoint copies of the family of k-element subsets of {1, ..., 2k-1},…
- bipartite_subset_min_uncolorable_rFor an integer k, bipartite_subset_min_uncolorable_r k is the least nonnegative integer r such that bipartite_subset_graph k r has no…
- bipartite_subset_uncolorable_of_geFor integers k ≥ 1 and r with k ≤ r, the bipartite subset graph bipartite_subset_graph k r has no proper coloring from its standard lists,…
- Used by 2
- bipartite_subset_min_uncolorable_ge_threeFor every k at least 5, the least uncolorable threshold is at least 3.
- bipartite_subset_min_uncolorable_monotoneFor positive k, the least uncolorable threshold is nondecreasing as k increases.
The proof, explained
The equivalence is established by characterizing colorability in terms of the set A of uncolorable thresholds. First, colorability is shown to be monotone decreasing in the threshold: any valid list coloring at threshold s remains valid at threshold r ≤ s because the threshold-r graph is a subgraph of the threshold-s graph. The set A is nonempty because threshold k is uncolorable, and by well-ordering its infimum (the least uncolorable threshold) belongs to A and is uncolorable. Colorability at threshold r implies r is below this threshold, because otherwise monotonicity would force the minimum uncolorable threshold to be colorable; conversely, if r were uncolorable, it would belong to A and force the infimum to be at most r, a contradiction.
Colorability is monotone in the threshold: if r ≤ s and the graph is standard-list colorable at threshold s, it is also standard-list colorable at threshold r.
Given a valid list coloring C for threshold s (line 4), we show that C remains valid for threshold r (lines 5–8). An edge in the threshold-r graph connects subsets whose intersection has size at most r; since r ≤ s, their intersection is also at most s, so the edge already exists in the threshold-s graph, where C assigns distinct colors. Packaging C with this validity proof via SimpleGraph.Coloring.mk yields a coloring D of the threshold-r graph (lines 9–10) that satisfies the same list constraints (line 11).
uses
SimpleGraph.Coloring.mkobtain ⟨C, hC⟩ := h have hvalid : ∀ {v w}, (bipartite_subset_graph k r).Adj v w → C v ≠ C w := by intro v w hadj apply C.valid cases v <;> cases w <;> dsimp [bipartite_subset_graph] at hadj ⊢ <;> omega let D : (bipartite_subset_graph k r).Coloring (Fin (2*k-1)) := SimpleGraph.Coloring.mk (fun v => C v) hvalid exact ⟨D, hC⟩
The set A of uncolorable thresholds is nonempty, and its minimum is uncolorable.
Working classically (line 14), we define A ⊆ ℕ as the set of thresholds for which the graph is not standard-list colorable (line 15). Threshold k is uncolorable by bipartite_subset_uncolorable_of_ge with k ≤ k via le_rfl, so k ∈ A and A is nonempty (line 16). Since ℕ is well-ordered, the infimum of any nonempty subset belongs to the set (csInf_mem), so the minimum uncolorable threshold belongs to A and is therefore uncolorable (lines 17–19).
uses
bipartite_subset_uncolorable_of_ge,le_rfl,csInf_memclassical let A : Set ℕ := {s | ¬ bipartite_subset_standard_list_colorable k s} have hn : A.Nonempty := ⟨k, bipartite_subset_uncolorable_of_ge k k hk le_rfl⟩ have hbad : ¬ bipartite_subset_standard_list_colorable k (bipartite_subset_min_uncolorable_r k) := by change sInf A ∈ A exact csInf_mem hn
If the graph is standard-list colorable at threshold r, then r is strictly less than the minimum uncolorable threshold.
To establish the forward implication (line 20), assume the graph is colorable at threshold r (line 21). Suppose for contradiction that r is at least the minimum uncolorable threshold (lines 22–23). By monotonicity (op861_colorable_threshold_mono), the graph would also be colorable at the minimum uncolorable threshold, contradicting the fact that this threshold is uncolorable (line 24).
uses
op861_colorable_threshold_monoconstructor · intro hc by_contra hnot have hle : bipartite_subset_min_uncolorable_r k ≤ r := by omega exact hbad (op861_colorable_threshold_mono k _ r hle hc)
If r is strictly less than the minimum uncolorable threshold, then the graph is standard-list colorable at threshold r.
For the reverse implication, assume r is strictly less than the minimum uncolorable threshold (line 25). Suppose for contradiction that the graph is not colorable at threshold r (line 26). Then r belongs to A (line 27). By Nat.sInf_le, the infimum of A is at most r (lines 28–30), which directly contradicts r being strictly less than the infimum (line 31).
uses
Nat.sInf_le· intro hlt by_contra hbad' have hm : r ∈ A := hbad' have hle : bipartite_subset_min_uncolorable_r k ≤ r := by change sInf A ≤ r exact Nat.sInf_le hm omega
SimpleGraph.Coloring.mk- Constructs a graph coloring from a function assigning colors to vertices and a proof that adjacent vertices receive distinct colors.
bipartite_subset_uncolorable_of_ge- For k ≥ 1, if the threshold r is at least k, the bipartite subset graph is not standard-list colorable.
le_rfl- The partial order relation ≤ is reflexive: every element is less than or equal to itself.
csInf_mem- In a well-founded linearly ordered type such as ℕ, any nonempty set contains its infimum.
op861_colorable_threshold_mono- Standard-list colorability is monotone decreasing in the threshold: if r ≤ s and the graph is colorable at threshold s, it is also colorable at threshold r.
Nat.sInf_le- For any set s of natural numbers and any element m ∈ s, the infimum of s is at most m.
- In Step 1 (line 8), the inclusion of the edge set of the threshold-r graph into that of the threshold-s graph is proved by exhaustive case analysis on the bipartition followed by linear arithmetic (omega).
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.
theorem op861_colorable_threshold_mono (k r s : ℕ) (hrs : r ≤ s) (h : bipartite_subset_standard_list_colorable k s) : bipartite_subset_standard_list_colorable k r := by obtain ⟨C, hC⟩ := h have hvalid : ∀ {v w}, (bipartite_subset_graph k r).Adj v w → C v ≠ C w := by intro v w hadj apply C.valid cases v <;> cases w <;> dsimp [bipartite_subset_graph] at hadj ⊢ <;> omega let D : (bipartite_subset_graph k r).Coloring (Fin (2*k-1)) := SimpleGraph.Coloring.mk (fun v => C v) hvalid exact ⟨D, hC⟩theorem bipartite_subset_colorable_iff_below_threshold (k r : ℕ) (hk : 1 ≤ k) : bipartite_subset_standard_list_colorable k r ↔ r < bipartite_subset_min_uncolorable_r k := by classical let A : Set ℕ := {s | ¬ bipartite_subset_standard_list_colorable k s} have hn : A.Nonempty := ⟨k, bipartite_subset_uncolorable_of_ge k k hk le_rfl⟩ have hbad : ¬ bipartite_subset_standard_list_colorable k (bipartite_subset_min_uncolorable_r k) := by change sInf A ∈ A exact csInf_mem hn constructor · intro hc by_contra hnot have hle : bipartite_subset_min_uncolorable_r k ≤ r := by omega exact hbad (op861_colorable_threshold_mono k _ r hle hc) · intro hlt by_contra hbad' have hm : r ∈ A := hbad' have hle : bipartite_subset_min_uncolorable_r k ≤ r := by change sInf A ≤ r exact Nat.sInf_le hm omega