AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_colorable_two_from_five

theoremverifiedoriginal

For every k at least 5, the bipartite subset graph with intersection threshold 2 is colorable from its standard lists.

Statement

theorem bipartite_subset_colorable_two_from_five (k : ℕ) (hk : 5 ≤ k) : bipartite_subset_standard_list_colorable k 2
Related work
A constant-threshold partial result toward OP-861 in arXiv:2610.42094; compare its upper bound on the least uncolorable threshold.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

For every natural number $k$ such that $5 \le k$, the property bipartite_subset_standard_list_colorable k 2 holds: that is, the bipartite graph whose two parts are both the family of all $k$-element subsets of $\mathrm{Fin}(2k - 1)$, with edges between sets intersecting in at most 2 elements, admits a proper vertex coloring from the color set $\mathrm{Fin}(2k - 1)$ such that each vertex is assigned a color from its own subset.

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

theorem bipartite_subset_colorable_two_from_five (k : ℕ) (hk : 5 ≤ k) : bipartite_subset_standard_list_colorable k 2 := by
  induction k, hk using Nat.le_induction with
  | base => exact bipartite_subset_colorable_five_at_two
  | succ k hk ih => exact bipartite_subset_colorable_succ k 2 (by omega) ih
See it in the graphDiscuss this resultChallenge it