AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_uncolorable_of_ge

theoremverified

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

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.

  1. 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)).

    lines 4–7

      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
  2. 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|.

    lines 8–22

    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_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
  3. 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).

    lines 23–27

    uses Finset.exists_subset_card_eq, Finset.mem_image.mp

      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⟩
  4. 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).

    lines 28–31

    uses le_trans, Finset.card_le_card, Finset.inter_subset_left

      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
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₁

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

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