AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_colorable_iff_below_threshold

theoremverified

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

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.

  1. 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).

    lines 4–11

    uses SimpleGraph.Coloring.mk

      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⟩
  2. 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).

    lines 14–19

    uses bipartite_subset_uncolorable_of_ge, le_rfl, csInf_mem

      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
  3. 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).

    lines 20–24

    uses op861_colorable_threshold_mono

      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)
  4. 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).

    lines 25–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.

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

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
See it in the graphDiscuss this resultChallenge it