bipartite_subset_colorable_five_at_two
theoremverified
The standard lists color the bipartite subset graph at k = 5 and intersection threshold 2.
Statement
theorem bipartite_subset_colorable_five_at_two : bipartite_subset_standard_list_colorable 5 2- Source
- A finite base case for the two-color lifting route to OP-861, with explicit selector found in experiment 22164.
- 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},…
- Used by 1
- bipartite_subset_colorable_two_from_fiveFor every k at least 5, the bipartite subset graph with intersection threshold 2 is colorable from its standard lists.
Lean source view module on GitHub
def op861_five_near (i : Fin 9) : Finset (Fin 9) := {i+2, i+3, i+4, i+5} set_option maxRecDepth 16384 set_option maxHeartbeats 2000000 theorem op861_five_cover : ∀ S : Finset (Fin 9), S.card = 5 → ∃ i ∈ S, 3 ≤ (S ∩ op861_five_near i).card := by decide theorem op861_five_near_card (i : Fin 9) : (op861_five_near i).card = 4 := by fin_cases i <;> decide theorem op861_five_not_near (i : Fin 9) : i ∉ op861_five_near i := by fin_cases i <;> decide theorem op861_five_common (S T : Finset (Fin 9)) (i : Fin 9) (hiS : i ∈ S) (hiT : i ∈ T) (hS : 3 ≤ (S ∩ op861_five_near i).card) (hT : 3 ≤ (T ∩ op861_five_near i).card) : 3 ≤ (S ∩ T).card := by let A := S ∩ op861_five_near i let B := T ∩ op861_five_near i have hsub : A ∪ B ⊆ op861_five_near i := by intro x hx simp only [Finset.mem_union, Finset.mem_inter, A, B] at hx tauto have hcard := Finset.card_le_card hsub rw [op861_five_near_card] at hcard have heq := Finset.card_union_add_card_inter A B have hAB : 2 ≤ (A ∩ B).card := by dsimp [A, B] at heq dsimp [A, B] at hcard dsimp [A, B] omega have hinot : i ∉ A ∩ B := by intro hi have hiQ : i ∈ op861_five_near i := (Finset.mem_inter.mp (Finset.mem_inter.mp hi).1).2 exact op861_five_not_near i hiQ have hsub' : insert i (A ∩ B) ⊆ S ∩ T := by intro x hx simp only [Finset.mem_insert, Finset.mem_inter] at hx ⊢ rcases hx with rfl | ⟨hxA, hxB⟩ · exact ⟨hiS, hiT⟩ · exact ⟨(Finset.mem_inter.mp hxA).1, (Finset.mem_inter.mp hxB).1⟩ have hbound := Finset.card_le_card hsub' rw [Finset.card_insert_of_notMem hinot] at hbound omega noncomputable def op861_five_pick (S : {S : Finset (Fin 9) // S.card = 5}) : Fin 9 := Classical.choose (op861_five_cover S.1 S.2) theorem op861_five_pick_spec (S : {S : Finset (Fin 9) // S.card = 5}) : op861_five_pick S ∈ S.1 ∧ 3 ≤ (S.1 ∩ op861_five_near (op861_five_pick S)).card := Classical.choose_spec (op861_five_cover S.1 S.2) theorem bipartite_subset_colorable_five_at_two : bipartite_subset_standard_list_colorable 5 2 := by let col : ({S : Finset (Fin 9) // S.card = 5} ⊕ {T : Finset (Fin 9) // T.card = 5}) → Fin 9 := Sum.elim op861_five_pick op861_five_pick have hc : ∀ (S T : {S : Finset (Fin 9) // S.card = 5}), (S.1 ∩ T.1).card ≤ 2 → op861_five_pick S ≠ op861_five_pick T := by intro S T hadj heq have hs := op861_five_pick_spec S have ht := op861_five_pick_spec T rw [← heq] at ht have hlarge := op861_five_common S.1 T.1 (op861_five_pick S) hs.1 ht.1 hs.2 ht.2 omega have hv : ∀ {v w}, (bipartite_subset_graph 5 2).Adj v w → col v ≠ col w := by intro v w hv cases v with | inl S => cases w with | inl T => exact False.elim hv | inr T => exact hc S T hv | inr T => cases w with | inl S => exact (hc S T hv).symm | inr U => exact False.elim hv let C : (bipartite_subset_graph 5 2).Coloring (Fin 9) := SimpleGraph.Coloring.mk col hv refine ⟨C, ?_⟩ intro v cases v with | inl S => exact (op861_five_pick_spec S).1 | inr T => exact (op861_five_pick_spec T).1