bipartite_subset_min_uncolorable_r
For an integer k, bipartite_subset_min_uncolorable_r k is the least nonnegative integer r such that bipartite_subset_graph k r has no proper coloring from its standard lists, defined as the infimum (sInf) of the set of natural numbers r such that ¬ bipartite_subset_standard_list_colorable k r.
Statement
noncomputable def bipartite_subset_min_uncolorable_r (k : ℕ) : ℕ
- Defined in
- arXiv:2610.42094, after Corollary 1.4
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- 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…
- Used by 3
- bipartite_subset_min_uncolorable_ge_threeFor every k at least 5, the least uncolorable threshold is at least 3.
- bipartite_subset_min_uncolorable_monotoneFor positive k, the least uncolorable threshold is nondecreasing as k increases.
- 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.
Read back from the Lean
For a given natural number k, bipartite_subset_min_uncolorable_r k is defined as the infimum (the least natural number, or 0 if empty) of the set of all r : ℕ such that the bipartite subset graph with parameters k and r is not standard-list-colorable.
Here, standard-list-colorability means there exists a proper coloring of the graph with colors in Fin (2 * k - 1) such that every vertex—each representing a k-element subset of Fin (2 * k - 1)—is assigned a color belonging to its subset. The underlying graph has vertex set partitioned into two copies of all k-subsets of Fin (2 * k - 1), with an edge between a subset S in the first part and a subset T in the second part if and only if |S ∩ T| ≤ r.
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
/-- The least integer r ≥ 0 such that G(k,r) has no proper coloring from standard lists. -/ noncomputable def bipartite_subset_min_uncolorable_r (k : ℕ) : ℕ := sInf {r : ℕ | ¬ bipartite_subset_standard_list_colorable k r}