bipartite_subset_uncolorable_of_ge
For integers k ≥ 1 and r with k ≤ r, the bipartite subset graph bipartite_subset_graph k r has no proper coloring from its standard lists, that is, ¬ bipartite_subset_standard_list_colorable k r.
Statement
theorem bipartite_subset_uncolorable_of_ge (k r : ℕ) (hk : 1 ≤ k) (hr : k ≤ r) :
¬ bipartite_subset_standard_list_colorable k r- Source
- arXiv:2610.42094, Section 1.3
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_graphFor integers k ≥ 2 and r ≥ 0, G(k,r) is the bipartite graph on two disjoint copies of the family of k-element subsets of {1, ..., 2k-1},…
- Used by 1
- 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 all natural numbers $k$ and $r$, if $1 \le k$ and $k \le r$, then the bipartite subset graph with parameters $k$ and $r$ is not standard list colorable (that is, ¬ bipartite_subset_standard_list_colorable k r).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by contradiction: suppose there is a valid coloring c from the standard lists of size k over a universe of 2k - 1 colors. Let C_A be the set of colors assigned to vertices in the left partition. If |C_A| < k, its complement has at least k colors, yielding a left vertex whose chosen color must lie outside C_A, a contradiction; hence |C_A| ≥ k. We can then choose a right vertex T whose list is a k-subset of C_A, forcing its color c(T) to match that of some left vertex S. Because k ≤ r, S and T are adjacent in the graph, contradicting that c is a proper coloring.
Assume for contradiction that a standard list coloring c exists, and let C_A be the set of colors assigned to the left partition.
We assume for contradiction that there exists a valid list coloring c such that every vertex v receives a color from its assigned k-element list (hypothesis hc). We record 1 ≤ k in the local context and define C_A ⊆ Fin(2k - 1) to be the image under c of all vertices in the left partition A (the k-element subsets of Fin(2k - 1)).
have _ := hk intro ⟨c, hc⟩ let C_A : Finset (Fin (2 * k - 1)) := Finset.image (fun S : {S : Finset (Fin (2 * k - 1)) // S.card = k} => c (Sum.inl S)) Finset.univ
The set of colors C_A used on the left partition has cardinality at least k.
Suppose for contradiction that |C_A| < k. The complement univ \ C_A in the universe of 2k - 1 elements has size (2k - 1) - |C_A| by Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, and Fintype.card_fin. Since |C_A| < k and k ≥ 1, this size is at least k (via omega). By Finset.exists_subset_card_eq, there exists a k-element subset S ⊆ univ \ C_A. Regarded as a vertex in the left partition, the list coloring constraint requires c(S) ∈ S, which implies c(S) ∉ C_A by Finset.mem_sdiff.mp. However, by definition of C_A as the image of the left partition under c, c(S) ∈ C_A (using Finset.mem_image_of_mem and Finset.mem_univ). This contradiction proves k ≤ |C_A|.
uses
Finset.card_sdiff_of_subset,Finset.subset_univ,Finset.card_univ,Fintype.card_fin,Finset.exists_subset_card_eq,Finset.mem_sdiff.mp,Finset.mem_image_of_mem,Finset.mem_univhave h_ge : k ≤ C_A.card := by by_contra! h_lt have h_le : k ≤ (Finset.univ \ C_A).card := by rw [Finset.card_sdiff_of_subset (Finset.subset_univ C_A), Finset.card_univ, Fintype.card_fin] omega obtain ⟨S, hS_sub, hS_card⟩ := Finset.exists_subset_card_eq h_le let S_val : {S : Finset (Fin (2 * k - 1)) // S.card = k} := ⟨S, hS_card⟩ have hcS : c (Sum.inl S_val) ∈ S := hc (Sum.inl S_val) have h_not_mem : c (Sum.inl S_val) ∉ C_A := by have := hS_sub hcS exact (Finset.mem_sdiff.mp this).2 have h_mem : c (Sum.inl S_val) ∈ C_A := by apply Finset.mem_image_of_mem exact Finset.mem_univ S_val exact h_not_mem h_mem
There exists a vertex T in the right partition whose assigned color coincides with the color of some vertex S in the left partition.
Since |C_A| ≥ k, Finset.exists_subset_card_eq yields a subset T ⊆ C_A of cardinality k. Considering T as a vertex in the right partition, the coloring condition requires c(T) ∈ T ⊆ C_A. Because c(T) ∈ C_A, Finset.mem_image.mp ensures there is some left vertex S such that c(S) = c(T).
uses
Finset.exists_subset_card_eq,Finset.mem_image.mpobtain ⟨T, hT_sub, hT_card⟩ := Finset.exists_subset_card_eq h_ge let T_val : {T : Finset (Fin (2 * k - 1)) // T.card = k} := ⟨T, hT_card⟩ have hcT : c (Sum.inr T_val) ∈ T := hc (Sum.inr T_val) have h_mem : c (Sum.inr T_val) ∈ C_A := hT_sub hcT rcases Finset.mem_image.mp h_mem with ⟨S_val, -, hS_eq⟩
The vertices S and T are adjacent in the graph, contradicting that c is a proper coloring.
By definition of the bipartite subset graph, S and T are adjacent if and only if |S ∩ T| ≤ r. Since S ∩ T ⊆ S by Finset.inter_subset_left, we have |S ∩ T| ≤ |S| by Finset.card_le_card. Since |S| = k ≤ r, transitivity of inequality (le_trans) gives |S ∩ T| ≤ r, so S and T are adjacent. But adjacent vertices must have different colors in a proper coloring (c.valid), contradicting c(S) = c(T).
uses
le_trans,Finset.card_le_card,Finset.inter_subset_lefthave hadj : (bipartite_subset_graph k r).Adj (Sum.inl S_val) (Sum.inr T_val) := by change (S_val.1 ∩ T_val.1).card ≤ r exact le_trans (Finset.card_le_card Finset.inter_subset_left) (S_val.2.le.trans hr) exact c.valid hadj hS_eq
Finset.card_sdiff_of_subset- for finite sets s ⊆ t, the cardinality of t \ s is |t| - |s|
Finset.subset_univ- every finite set of elements of a finite type is a subset of the universal set
Finset.card_univ- the cardinality of the universal finset is the cardinality of the underlying finite type
Fintype.card_fin- the standard finite type Fin n has cardinality n
Finset.exists_subset_card_eq- a finite set with at least n elements has a subset of cardinality n
Finset.mem_sdiff.mp- an element of a set difference s \ t belongs to s and does not belong to t
Finset.mem_image_of_mem- if an element belongs to s, its value under f belongs to the image of s under f
Finset.mem_univ- every element of a finite type belongs to its universal set
Finset.mem_image.mp- an element in the image of s under f is of the form f(a) for some a ∈ s
le_trans- the inequality relation ≤ is transitive
Finset.card_le_card- if s ⊆ t, then |s| ≤ |t|
Finset.inter_subset_left- the intersection s₁ ∩ s₂ is a subset of s₁
- Line 4 (`have _ := hk`) is a formal bookkeeping step ensuring that the hypothesis 1 ≤ k is available in the local context for the later `omega` call.
- At line 12, `omega` automatically discharges the linear integer inequality (2*k - 1) - |C_A| ≥ k from the hypotheses 1 ≤ k and |C_A| < k.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- For r ≥ k, G(k,r) is complete bipartite and has no proper list coloring from standard lists. -/theorem bipartite_subset_uncolorable_of_ge (k r : ℕ) (hk : 1 ≤ k) (hr : k ≤ r) : ¬ bipartite_subset_standard_list_colorable k r := by have _ := hk intro ⟨c, hc⟩ let C_A : Finset (Fin (2 * k - 1)) := Finset.image (fun S : {S : Finset (Fin (2 * k - 1)) // S.card = k} => c (Sum.inl S)) Finset.univ have h_ge : k ≤ C_A.card := by by_contra! h_lt have h_le : k ≤ (Finset.univ \ C_A).card := by rw [Finset.card_sdiff_of_subset (Finset.subset_univ C_A), Finset.card_univ, Fintype.card_fin] omega obtain ⟨S, hS_sub, hS_card⟩ := Finset.exists_subset_card_eq h_le let S_val : {S : Finset (Fin (2 * k - 1)) // S.card = k} := ⟨S, hS_card⟩ have hcS : c (Sum.inl S_val) ∈ S := hc (Sum.inl S_val) have h_not_mem : c (Sum.inl S_val) ∉ C_A := by have := hS_sub hcS exact (Finset.mem_sdiff.mp this).2 have h_mem : c (Sum.inl S_val) ∈ C_A := by apply Finset.mem_image_of_mem exact Finset.mem_univ S_val exact h_not_mem h_mem obtain ⟨T, hT_sub, hT_card⟩ := Finset.exists_subset_card_eq h_ge let T_val : {T : Finset (Fin (2 * k - 1)) // T.card = k} := ⟨T, hT_card⟩ have hcT : c (Sum.inr T_val) ∈ T := hc (Sum.inr T_val) have h_mem : c (Sum.inr T_val) ∈ C_A := hT_sub hcT rcases Finset.mem_image.mp h_mem with ⟨S_val, -, hS_eq⟩ have hadj : (bipartite_subset_graph k r).Adj (Sum.inl S_val) (Sum.inr T_val) := by change (S_val.1 ∩ T_val.1).card ≤ r exact le_trans (Finset.card_le_card Finset.inter_subset_left) (S_val.2.le.trans hr) exact c.valid hadj hS_eq