bipartite_subset_min_uncolorable_ge_three
theoremverified
For every k at least 5, the least uncolorable threshold is at least 3.
Statement
theorem bipartite_subset_min_uncolorable_ge_three (k : ℕ) (hk : 5 ≤ k) : 3 ≤ bipartite_subset_min_uncolorable_r k- Source
- A direct consequence of the list-coloring construction for OP-861, arXiv:2610.42094.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_colorable_iff_below_thresholdFor positive k, the standard lists are colorable at threshold r exactly when r is less than the least uncolorable threshold.
- bipartite_subset_colorable_two_from_fiveFor every k at least 5, the bipartite subset graph with intersection threshold 2 is colorable from its standard lists.
- 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…
Lean source view module on GitHub
theorem bipartite_subset_min_uncolorable_ge_three (k : ℕ) (hk : 5 ≤ k) : 3 ≤ bipartite_subset_min_uncolorable_r k := by have h := (bipartite_subset_colorable_iff_below_threshold k 2 (by omega)).1 (bipartite_subset_colorable_two_from_five k hk) omega