AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_min_uncolorable_r

def

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
Used by 3

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}
See it in the graphDiscuss this resultChallenge it