bipartite_subset_min_uncolorable_monotone
theoremverified
For positive k, the least uncolorable threshold is nondecreasing as k increases.
Statement
theorem bipartite_subset_min_uncolorable_monotone (k : ℕ) (hk : 1 ≤ k) : bipartite_subset_min_uncolorable_r k ≤ bipartite_subset_min_uncolorable_r (k+1)- 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_succFor every positive k and threshold r, colorability of the standard-list subset graph at k implies colorability at k+1 and the same…
- 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_monotone (k : ℕ) (hk : 1 ≤ k) : bipartite_subset_min_uncolorable_r k ≤ bipartite_subset_min_uncolorable_r (k+1) := by by_contra! h let r := bipartite_subset_min_uncolorable_r (k+1) have hc : bipartite_subset_standard_list_colorable k r := (bipartite_subset_colorable_iff_below_threshold k r hk).2 h have hcnew := bipartite_subset_colorable_succ k r hk hc have hh := (bipartite_subset_colorable_iff_below_threshold (k+1) r (by omega)).1 hcnew omega