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
- 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_colorable_five_at_twoThe standard lists color the bipartite subset graph at k = 5 and intersection threshold 2.
- bipartite_subset_colorable_succFor every positive k and threshold r, colorability of the standard-list subset graph at k implies colorability at k+1 and the same…
- Used by 1
- bipartite_subset_min_uncolorable_ge_threeFor every k at least 5, the least uncolorable threshold is at least 3.
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