AFTD Auto-Formalizing Theoretical Domains

bipartite_subset_colorable_at_one

theoremverified

For every k at least two, the bipartite subset graph with intersection threshold one is colorable from its standard lists.

Statement

theorem bipartite_subset_colorable_at_one (k : ℕ) (hk : 2 ≤ k) : bipartite_subset_standard_list_colorable k 1
Source
arXiv:2610.42094, Definition 1.2; elementary lower-bound step for OP-861.
Verified
11 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},…

The proof, explained

To list-color the bipartite subset graph from its standard lists, each k-subset S of Fin (2 * k - 1) is assigned a color x ∈ S such that x + 1 ∈ S, which exists by the pigeonhole principle because |S| + |S + 1| > 2 * k - 1. If two k-subsets S and T were assigned the same color x, their intersection would contain both x and x + 1, forcing |S ∩ T| ≥ 2 because x + 1 ≠ x. Since edges in the graph only exist between subsets whose intersection has size at most 1, no two adjacent vertices receive the same color, yielding a valid list coloring.

  1. For any k-subset S of Fin (2 * k - 1), the cyclic shift S + 1 has nonempty intersection with S.

    Let S' be the image of S under the cyclic shift map x ↦ x + 1. Since this map is a bijection, S' has cardinality k. The union S ∪ S' is contained in Fin (2 * k - 1) and thus has cardinality at most 2 * k - 1. By inclusion-exclusion, the intersection S ∩ S' has cardinality at least k + k - (2 * k - 1) = 1, so S ∩ S' is nonempty.

    lines 4–13

    uses Finset.card_map, Finset.card_le_univ, Fintype.card_fin, Finset.card_union_add_card_inter, Finset.card_pos.mp

      let e : Equiv.Perm (Fin (2 * k - 1)) := Equiv.addRight 1
      let S' := S.map e.toEmbedding
      have hS' : S'.card = k := by rw [Finset.card_map, hS]
      have h_union : (S ∪ S').card ≤ 2 * k - 1 := by
        calc (S ∪ S').card ≤ Fintype.card (Fin (2 * k - 1)) := Finset.card_le_univ (S ∪ S')
        _ = 2 * k - 1 := Fintype.card_fin (2 * k - 1)
      have h_inter : 1 ≤ (S ∩ S').card := by
        have h_sum := Finset.card_union_add_card_inter S S'
        omega
      have h_nonempty : (S ∩ S').Nonempty := Finset.card_pos.mp (by omega)
  2. There exists x ∈ S such that x + 1 ∈ S.

    Pick an element y in the nonempty intersection S ∩ S'. Because y ∈ S', y = x + 1 for some x ∈ S. Because y also belongs to S, we have x + 1 ∈ S, which provides the desired witness x.

    lines 14–19

    uses Finset.mem_inter, Finset.mem_map

      rcases h_nonempty with ⟨y, hy⟩
      rw [Finset.mem_inter, Finset.mem_map] at hy
      rcases hy with ⟨hyS, ⟨x, hxS, hxeq⟩⟩
      dsimp [e] at hxeq
      rw [← hxeq] at hyS
      exact ⟨x, hxS, hyS⟩
  3. In Fin n with 2 ≤ n, x + 1 ≠ x for every element x.

    Suppose x + 1 = x. Cancelling x gives 1 = 0 in Fin n. Taking canonical integer values gives 1 % n = 0. But since 2 ≤ n, 1 % n = 1, giving 1 = 0, a contradiction.

    lines 23–30

    uses add_comm, add_sub_cancel_right, sub_self, congrArg, Fin.val_zero, Fin.val_one', Nat.mod_eq_of_lt

      intro h
      have h1 : (1 : Fin n) = 0 := by
        have : (1 + x) - x = x - x := by rw [add_comm 1 x, h]
        rwa [add_sub_cancel_right, sub_self] at this
      have h2 : (1 : Fin n).val = (0 : Fin n).val := congrArg Fin.val h1
      rw [Fin.val_zero, Fin.val_one' n] at h2
      have : 1 % n = 1 := Nat.mod_eq_of_lt (by omega)
      omega
  4. We define a candidate coloring assigning to each k-subset S an element x ∈ S with x + 1 ∈ S.

    Because 2 ≤ k, 2 * k - 1 is nonzero and at least 2. Using the choice function, we assign each k-subset S (on either side of the bipartition) the chosen element x from S such that both x and x + 1 belong to S.

    lines 43–48

      have : NeZero (2 * k - 1) := ⟨by omega⟩
      have h_2le : 2 ≤ 2 * k - 1 := by omega
      let col (v : { S : Finset (Fin (2 * k - 1)) // S.card = k } ⊕ { T : Finset (Fin (2 * k - 1)) // T.card = k }) :
          Fin (2 * k - 1) :=
        Sum.elim (bipartite_subset_colorable_at_one_choose_color k hk)
                 (bipartite_subset_colorable_at_one_choose_color k hk) v
  5. Two k-subsets with intersection of size at most one cannot receive the same color.

    Suppose two k-subsets S and T satisfy |S ∩ T| ≤ 1 but receive the same color x. By the specification of the color choice, both x and x + 1 belong to S, and both x and x + 1 belong to T. Thus the pair {x, x + 1} is a subset of S ∩ T. Since 2 ≤ 2 * k - 1, x + 1 ≠ x, so {x, x + 1} has cardinality 2. But this implies |S ∩ T| ≥ 2, contradicting |S ∩ T| ≤ 1.

    lines 49–73

    uses bipartite_subset_colorable_at_one_choose_color_spec, Finset.card_pair, bipartite_subset_colorable_at_one_fin_add_one_ne_self, Finset.mem_insert, Finset.mem_singleton, Finset.mem_inter.mpr, Finset.card_le_card

      have h_cases : ∀ (S T : { S : Finset (Fin (2 * k - 1)) // S.card = k }),
          (S.1 ∩ T.1).card ≤ 1 →
            bipartite_subset_colorable_at_one_choose_color k hk S ≠
            bipartite_subset_colorable_at_one_choose_color k hk T := by
        intro S T hadj heq
        have hS := bipartite_subset_colorable_at_one_choose_color_spec k hk S
        have hT := bipartite_subset_colorable_at_one_choose_color_spec k hk T
        set x := bipartite_subset_colorable_at_one_choose_color k hk S
        have hxS : x ∈ S.1 := hS.1
        have hxS1 : x + 1 ∈ S.1 := hS.2
        have hxT : x ∈ T.1 := heq ▸ hT.1
        have hxT1 : x + 1 ∈ T.1 := heq ▸ hT.2
        let P : Finset (Fin (2 * k - 1)) := {x, x + 1}
        have hP_card : P.card = 2 := by
          rw [Finset.card_pair]
          exact (bipartite_subset_colorable_at_one_fin_add_one_ne_self (2 * k - 1) h_2le x).symm
        have hP_sub : P ⊆ S.1 ∩ T.1 := by
          intro y hy
          simp only [P, Finset.mem_insert, Finset.mem_singleton] at hy
          rcases hy with rfl | rfl
          · exact Finset.mem_inter.mpr ⟨hxS, hxT⟩
          · exact Finset.mem_inter.mpr ⟨hxS1, hxT1⟩
        have h_le := Finset.card_le_card hP_sub
        rw [hP_card] at h_le
        omega
  6. The candidate coloring is a proper coloring of the bipartite subset graph.

    Any edge in the graph connects a vertex from the left side to a vertex from the right side. By definition, two vertices on the same side cannot be adjacent. When an edge connects S on the left and T on the right, the definition of the graph requires |S ∩ T| ≤ 1, so the previous step guarantees that S and T receive distinct colors.

    lines 74–90

    uses False.elim

      have h_valid : ∀ {v w}, (bipartite_subset_graph k 1).Adj v w → col v ≠ col w := by
        intro v w hadj
        cases v with
        | inl S =>
          cases w with
          | inl S' => exact False.elim hadj
          | inr T =>
            dsimp [bipartite_subset_graph] at hadj
            dsimp [col]
            exact h_cases S T hadj
        | inr T =>
          cases w with
          | inr T' => exact False.elim hadj
          | inl S =>
            dsimp [bipartite_subset_graph] at hadj
            dsimp [col]
            exact (h_cases S T hadj).symm
  7. The coloring is a valid list coloring from the standard lists.

    We package the vertex coloring and validity proof into a graph coloring. For each vertex S, its assigned color was chosen to satisfy x ∈ S, so every vertex is assigned a color from its list S.

    lines 91–101

    uses SimpleGraph.Coloring.mk, bipartite_subset_colorable_at_one_choose_color_spec

      let c : (bipartite_subset_graph k 1).Coloring (Fin (2 * k - 1)) :=
        SimpleGraph.Coloring.mk col (fun {v w} => h_valid)
      use c
      intro v
      cases v with
      | inl S =>
        dsimp [c, col]
        exact (bipartite_subset_colorable_at_one_choose_color_spec k hk S).1
      | inr T =>
        dsimp [c, col]
        exact (bipartite_subset_colorable_at_one_choose_color_spec k hk T).1
Finset.card_map
Mapping a finite set by an embedding preserves its cardinality.
Finset.card_le_univ
The cardinality of a subset of a finite type is at most the cardinality of the type.
Fintype.card_fin
The cardinality of `Fin n` is `n`.
Finset.card_union_add_card_inter
For any two finite sets, the sum of their union size and intersection size equals the sum of their individual sizes.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.mem_inter
An element belongs to the intersection of two sets if and only if it belongs to both.
Finset.mem_map
An element is in the image of a set under an embedding if and only if it is the image of some element in that set.
add_comm
Addition is commutative.
add_sub_cancel_right
Subtracting an element after adding it cancels out: (a + b) - b = a.
sub_self
Subtracting an element from itself yields zero: a - a = 0.
congrArg
Applying a function to equal arguments produces equal results.
Fin.val_zero
The canonical integer value of 0 in `Fin n` is 0.
Fin.val_one'
The canonical integer value of 1 in `Fin n` is 1 % n.
Nat.mod_eq_of_lt
If a < b, then a % b = a.
bipartite_subset_colorable_at_one_choose_color_spec
The chosen color for a k-subset S is an element of S, and adding 1 to it also yields an element of S.
bipartite_subset_colorable_at_one_fin_add_one_ne_self
In `Fin n` with n ≥ 2, adding 1 to an element never equals the element itself.
Finset.card_pair
A set of two distinct elements has cardinality two.
Finset.mem_insert
An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_inter.mpr
If an element belongs to both sets, it belongs to their intersection.
Finset.card_le_card
If s is a subset of t, the cardinality of s is at most that of t.
False.elim
From a contradiction (False), any conclusion follows.
SimpleGraph.Coloring.mk
Constructs a proper coloring of a simple graph from a vertex coloring function and a proof that adjacent vertices receive distinct colors.

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

lemma bipartite_subset_colorable_at_one_exists_consec (k : ℕ) [NeZero (2 * k - 1)] (hk : 2 ≤ k)    (S : Finset (Fin (2 * k - 1))) (hS : S.card = k) :    ∃ x ∈ S, x + 1 ∈ S := by  let e : Equiv.Perm (Fin (2 * k - 1)) := Equiv.addRight 1  let S' := S.map e.toEmbedding  have hS' : S'.card = k := by rw [Finset.card_map, hS]  have h_union : (S ∪ S').card ≤ 2 * k - 1 := by    calc (S ∪ S').card ≤ Fintype.card (Fin (2 * k - 1)) := Finset.card_le_univ (S ∪ S')    _ = 2 * k - 1 := Fintype.card_fin (2 * k - 1)  have h_inter : 1 ≤ (S ∩ S').card := by    have h_sum := Finset.card_union_add_card_inter S S'    omega  have h_nonempty : (S ∩ S').Nonempty := Finset.card_pos.mp (by omega)  rcases h_nonempty with ⟨y, hy⟩  rw [Finset.mem_inter, Finset.mem_map] at hy  rcases hy with ⟨hyS, ⟨x, hxS, hxeq⟩⟩  dsimp [e] at hxeq  rw [← hxeq] at hyS  exact ⟨x, hxS, hyS⟩lemma bipartite_subset_colorable_at_one_fin_add_one_ne_self (n : ℕ) [NeZero n] (hn : 2 ≤ n) (x : Fin n) :    x + 1 ≠ x := by  intro h  have h1 : (1 : Fin n) = 0 := by    have : (1 + x) - x = x - x := by rw [add_comm 1 x, h]    rwa [add_sub_cancel_right, sub_self] at this  have h2 : (1 : Fin n).val = (0 : Fin n).val := congrArg Fin.val h1  rw [Fin.val_zero, Fin.val_one' n] at h2  have : 1 % n = 1 := Nat.mod_eq_of_lt (by omega)  omeganoncomputable def bipartite_subset_colorable_at_one_choose_color (k : ℕ) [NeZero (2 * k - 1)] (hk : 2 ≤ k)    (S : { S : Finset (Fin (2 * k - 1)) // S.card = k }) : Fin (2 * k - 1) :=  Classical.choose (bipartite_subset_colorable_at_one_exists_consec k hk S.1 S.2)lemma bipartite_subset_colorable_at_one_choose_color_spec (k : ℕ) [NeZero (2 * k - 1)] (hk : 2 ≤ k)    (S : { S : Finset (Fin (2 * k - 1)) // S.card = k }) :    bipartite_subset_colorable_at_one_choose_color k hk S ∈ S.1 ∧      bipartite_subset_colorable_at_one_choose_color k hk S + 1 ∈ S.1 :=  Classical.choose_spec (bipartite_subset_colorable_at_one_exists_consec k hk S.1 S.2)theorem bipartite_subset_colorable_at_one (k : ℕ) (hk : 2 ≤ k) : bipartite_subset_standard_list_colorable k 1 := by  have : NeZero (2 * k - 1) := ⟨by omega⟩  have h_2le : 2 ≤ 2 * k - 1 := by omega  let col (v : { S : Finset (Fin (2 * k - 1)) // S.card = k } ⊕ { T : Finset (Fin (2 * k - 1)) // T.card = k }) :      Fin (2 * k - 1) :=    Sum.elim (bipartite_subset_colorable_at_one_choose_color k hk)             (bipartite_subset_colorable_at_one_choose_color k hk) v  have h_cases : ∀ (S T : { S : Finset (Fin (2 * k - 1)) // S.card = k }),      (S.1 ∩ T.1).card ≤ 1 →        bipartite_subset_colorable_at_one_choose_color k hk S ≠        bipartite_subset_colorable_at_one_choose_color k hk T := by    intro S T hadj heq    have hS := bipartite_subset_colorable_at_one_choose_color_spec k hk S    have hT := bipartite_subset_colorable_at_one_choose_color_spec k hk T    set x := bipartite_subset_colorable_at_one_choose_color k hk S    have hxS : x ∈ S.1 := hS.1    have hxS1 : x + 1 ∈ S.1 := hS.2    have hxT : x ∈ T.1 := heq ▸ hT.1    have hxT1 : x + 1 ∈ T.1 := heq ▸ hT.2    let P : Finset (Fin (2 * k - 1)) := {x, x + 1}    have hP_card : P.card = 2 := by      rw [Finset.card_pair]      exact (bipartite_subset_colorable_at_one_fin_add_one_ne_self (2 * k - 1) h_2le x).symm    have hP_sub : P ⊆ S.1 ∩ T.1 := by      intro y hy      simp only [P, Finset.mem_insert, Finset.mem_singleton] at hy      rcases hy with rfl | rfl      · exact Finset.mem_inter.mpr ⟨hxS, hxT⟩      · exact Finset.mem_inter.mpr ⟨hxS1, hxT1⟩    have h_le := Finset.card_le_card hP_sub    rw [hP_card] at h_le    omega  have h_valid : ∀ {v w}, (bipartite_subset_graph k 1).Adj v w → col v ≠ col w := by    intro v w hadj    cases v with    | inl S =>      cases w with      | inl S' => exact False.elim hadj      | inr T =>        dsimp [bipartite_subset_graph] at hadj        dsimp [col]        exact h_cases S T hadj    | inr T =>      cases w with      | inr T' => exact False.elim hadj      | inl S =>        dsimp [bipartite_subset_graph] at hadj        dsimp [col]        exact (h_cases S T hadj).symm  let c : (bipartite_subset_graph k 1).Coloring (Fin (2 * k - 1)) :=    SimpleGraph.Coloring.mk col (fun {v w} => h_valid)  use c  intro v  cases v with  | inl S =>    dsimp [c, col]    exact (bipartite_subset_colorable_at_one_choose_color_spec k hk S).1  | inr T =>    dsimp [c, col]    exact (bipartite_subset_colorable_at_one_choose_color_spec k hk T).1
See it in the graphDiscuss this resultChallenge it