bipartite_subset_colorable_at_one
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.
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.
uses
Finset.card_map,Finset.card_le_univ,Fintype.card_fin,Finset.card_union_add_card_inter,Finset.card_pos.mplet 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)
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.
uses
Finset.mem_inter,Finset.mem_maprcases 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⟩
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.
uses
add_comm,add_sub_cancel_right,sub_self,congrArg,Fin.val_zero,Fin.val_one',Nat.mod_eq_of_ltintro 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
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.
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
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.
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_cardhave 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
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.
uses
False.elimhave 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
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.
uses
SimpleGraph.Coloring.mk,bipartite_subset_colorable_at_one_choose_color_speclet 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
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.
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