odd_antihole_colorable_of_common_palette
Theorem 8 of arXiv:2610.14241 for the odd antihole: for ℓ ≥ 3, if all lists of an (ℓ-1)-assignment of complement(C_{2ℓ-1}) are subsets of a common ℓ-set P and are not all identical, then the antihole is L-colorable.
Statement
theorem odd_antihole_colorable_of_common_palette (ℓ : ℕ) (hℓ : 3 ≤ ℓ) (P : Finset ℕ)
(hP : P.card = ℓ) (L : Fin (2 * ℓ - 1) → Finset ℕ) (hL : ∀ v, (L v).card = ℓ - 1)
(hLP : ∀ v, L v ⊆ P) (hne : ∃ u v, L u ≠ L v) :
∃ c : Fin (2 * ℓ - 1) → ℕ, (∀ v, c v ∈ L v) ∧
∀ u v, (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Adj u v → c u ≠ c v- Formalizes
- arXiv:2610.14241 (Restricting odd antiholes in critical graphs via list coloring), Theorem 8, specialized to G = complement of C_{2ℓ-1} (whose complement, the odd cycle, is hypomatchable); partial result for OP-216 (the conjecture with the common-palette assumption)
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
The proof, explained
For the odd antihole complement(C_{2ℓ-1}), independent sets correspond to cliques of C_{2ℓ-1}, which are singletons and adjacent edges; thus an ℓ-coloring partitions vertices into one singleton {s} and ℓ - 1 consecutive cycle pairs {s + 2j - 1, s + 2j}. Since each list L(v) has size ℓ - 1 from a common ℓ-set P, each L(v) excludes a single color μ(v) ∈ P, so finding a color for each of the ℓ classes reduces to a system of distinct representatives problem governed by Hall's Marriage Theorem. A base vertex s is called Good when its pairing satisfies Hall's condition; if no vertex were Good, a counting argument on the frequencies of excluded colors shows that three distinct colors would each appear at least ℓ - 1 times, exceeding the total number of vertices 2ℓ - 1. Therefore a Good base vertex s must exist, yielding an injective selector via Hall's theorem that properly colors the antihole.
Every vertex v can be assigned to a class j(v) = ((v - s).val + 1) / 2 < ℓ, yielding a candidate coloring c(v) = f(j(v)).
The offset (v - s).val is strictly less than 2ℓ - 1, which implies ((v - s).val + 1) / 2 < ℓ by linear integer arithmetic (omega). We define the candidate coloring c by evaluating the injective selector f on the class index j(v).
have hcls : ∀ v : Fin (2 * ℓ - 1), ((v - s).val + 1) / 2 < ℓ := by intro v have := (v - s).isLt omega refine ⟨fun v => f ⟨((v - s).val + 1) / 2, hcls v⟩, ?_, ?_⟩
The candidate coloring satisfies the list constraints: c(v) ∈ L(v) for every vertex v.
For any vertex v, 2 * j(v) is either (v - s).val or (v - s).val + 1, so (v - s).val is either 2 * j(v) - 1 or 2 * j(v). Since s + (v - s) = v, vertex v is one of s + 2*j(v) - 1 or s + 2*j(v). By the hypothesis on f, the color f(j(v)) belongs to both L(s + 2*j(v) - 1) and L(s + 2*j(v)), and therefore f(j(v)) ∈ L(v).
uses
Fin.cast_val_eq_self,Finset.mem_inter· intro v have hv : s + (((v - s).val : ℕ) : Fin (2 * ℓ - 1)) = v := by rw [Fin.cast_val_eq_self] abel have h := hft ⟨((v - s).val + 1) / 2, hcls v⟩ simp only [Finset.mem_inter] at h have key : 2 * (((v - s).val + 1) / 2) - 1 = (v - s).val ∨ 2 * (((v - s).val + 1) / 2) = (v - s).val := by omega rcases key with k | k · have h1 := h.1 rw [k, hv] at h1 exact h1 · have h2 := h.2 rw [k, hv] at h2 exact h2
The candidate coloring is a proper coloring of the antihole complement(C_{2ℓ-1}): if u and v are adjacent in the antihole, then c(u) ≠ c(v).
Two vertices are adjacent in the antihole if and only if they are distinct and not adjacent in the cycle C_{2ℓ-1}. If c(u) = c(v), injectivity of f implies j(u) = j(v). Because u ≠ v, their offsets (u - s).val and (v - s).val are distinct natural numbers with equal halves, forcing one to be the other plus 1. Therefore u - v = ±1 modulo 2ℓ - 1, meaning u and v are adjacent in C_{2ℓ-1}, contradicting antihole adjacency.
uses
SimpleGraph.compl_adj,SimpleGraph.cycleGraph_adj',Fin.ext,Fin.sub_def,Nat.add_mod_right,Nat.mod_eq_of_lt· intro u v hadj heq rw [SimpleGraph.compl_adj] at hadj obtain ⟨hne, hnadj⟩ := hadj apply hnadj have heq' := Fin.mk.inj_iff.mp (hf heq) rw [SimpleGraph.cycleGraph_adj'] have hij : (u - s).val ≠ (v - s).val := by intro h apply hne have : u - s = v - s := Fin.ext h simpa using this have hsub : u - v = (u - s) - (v - s) := by abel have hsub' : v - u = (v - s) - (u - s) := by abel rw [hsub, hsub'] have hu := (u - s).isLt have hv := (v - s).isLt rcases (show (u - s).val = (v - s).val + 1 ∨ (v - s).val = (u - s).val + 1 by omega) with h | h · left rw [Fin.sub_def] simp only rw [h, show 2 * ℓ - 1 - (v - s).val + ((v - s).val + 1) = 1 + (2 * ℓ - 1) by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)] · right rw [Fin.sub_def] simp only rw [h, show 2 * ℓ - 1 - (u - s).val + ((u - s).val + 1) = 1 + (2 * ℓ - 1) by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]
For each class index j, the set of available colors t(j) = P \ {a(j), b(j)} satisfies |t(j)| ≥ ℓ - 2, and the base class satisfies |t(0)| ≥ ℓ - 1.
Hall's Marriage Theorem (via Finset.all_card_le_biUnion_card_iff_exists_injective) reduces the existence of an injective selector f to checking |S| ≤ |⋃_{j ∈ S} t(j)| for all S ⊆ Fin ℓ. Removing at most two elements from P (which has size ℓ) leaves at least ℓ - 2 elements. At j = 0, since a(0) = b(0), only one element is removed, leaving at least ℓ - 1 elements.
uses
Finset.all_card_le_biUnion_card_iff_exists_injective,Finset.mem_erase,Finset.mem_inter,Finset.pred_card_le_card_erase,Finset.card_le_cardclassical set t : Fin ℓ → Finset ℕ := fun j => P.erase (a j.val) ∩ P.erase (b j.val) with ht_def apply (Finset.all_card_le_biUnion_card_iff_exists_injective t).mp have ht : ∀ j, ℓ - 2 ≤ (t j).card := by intro j have h1 : (P.erase (a j.val)).erase (b j.val) ⊆ t j := by intro x hx simp only [Finset.mem_erase] at hx simp only [ht_def, Finset.mem_inter, Finset.mem_erase] tauto have h2 := Finset.pred_card_le_card_erase (s := P.erase (a j.val)) (a := b j.val) have h3 := Finset.pred_card_le_card_erase (s := P) (a := a j.val) have h4 := Finset.card_le_card h1 omega have ht0 : ℓ - 1 ≤ (t ⟨0, by omega⟩).card := by have hsub : P.erase (a 0) ⊆ t ⟨0, by omega⟩ := by intro x hx simp only [ht_def, Finset.mem_inter] exact ⟨hx, by rw [← h0]; exact hx⟩ have := Finset.card_le_card hsub have := Finset.pred_card_le_card_erase (s := P) (a := a 0) omega
Hall's condition holds for all subsets S ⊆ Fin ℓ with |S| ≤ ℓ - 2, and for all S containing 0.
If |S| ≤ ℓ - 2, the condition is immediate: if S is nonempty, any single element j ∈ S already has |t(j)| ≥ ℓ - 2 ≥ |S|. If 0 ∈ S and |S| ≤ ℓ - 1, the single set t(0) already provides at least ℓ - 1 colors. If 0 ∈ S and |S| = ℓ, then S = Fin ℓ; any color x ∈ P with x ≠ a(0) is in t(0), while x = a(0) is in t(k) for some k by hypothesis hA. Thus P ⊆ ⋃_{j ∈ S} t(j), so the union has size ℓ = |S|.
uses
Finset.card_le_univ,Finset.card_le_card,Finset.subset_biUnion_of_mem,Finset.eq_univ_of_card,Finset.mem_biUnion,Finset.mem_erase,Finset.mem_inter,Finset.mem_univintro S have hSle : S.card ≤ ℓ := by simpa using Finset.card_le_univ S by_cases hS : S.card ≤ ℓ - 2 · rcases S.eq_empty_or_nonempty with rfl | ⟨j, hj⟩ · simp · exact hS.trans ((ht j).trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t hj))) by_cases h0S : (⟨0, by omega⟩ : Fin ℓ) ∈ S · by_cases hSf : S.card = ℓ · have hSu : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSf) have hPsub : P ⊆ S.biUnion t := by intro x hx rw [Finset.mem_biUnion] by_cases hx0 : x = a 0 · obtain ⟨k, hk1, hk2, hak, hbk⟩ := hA refine ⟨⟨k, hk2⟩, by rw [hSu]; exact Finset.mem_univ _, ?_⟩ simp only [ht_def, Finset.mem_inter, Finset.mem_erase] rw [hx0] at hx ⊢ exact ⟨⟨hak, hx⟩, ⟨hbk, hx⟩⟩ · refine ⟨⟨0, by omega⟩, h0S, ?_⟩ simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨⟨hx0, hx⟩, ⟨by rw [← h0]; exact hx0, hx⟩⟩ calc S.card = ℓ := hSf _ = P.card := hP.symm _ ≤ _ := Finset.card_le_card hPsub · have : S.card ≤ ℓ - 1 := by omega exact this.trans (ht0.trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t h0S)))
Hall's condition holds for S = (Fin ℓ) \ {0}, completing the proof of Hall's condition for all subsets S.
When 0 ∉ S and |S| ≥ ℓ - 1, S must be exactly the complement of {0}, so |S| = ℓ - 1, and the two indices k₁, k₂ from hypothesis hB both belong to S. Case analysis on hB shows that t(k₁) ∪ t(k₂) contains all of P except possibly one element: if a(k₁) = b(k₁), erasing a(k₁) gives a subset of t(k₁); if a(k₂) ∉ {a(k₁), b(k₁)}, erasing b(k₂) is contained in t(k₁) ∪ t(k₂); otherwise erasing a(k₂) is contained in the union. In every case, |⋃_{j ∈ S} t(j)| ≥ |P| - 1 = ℓ - 1 = |S|.
uses
Finset.mem_erase,Finset.mem_univ,Finset.eq_of_subset_of_card_le,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_fin,Fin.ext_iff,Finset.subset_biUnion_of_mem,Finset.mem_union_left,Finset.mem_union_right,Finset.mem_inter,Finset.union_subset,Finset.card_le_card,Finset.pred_card_le_card_erase· obtain ⟨k₁, k₂, hk1, hk1', hk2, hk2', hcase⟩ := hB have hSsub : S ⊆ Finset.univ.erase ⟨0, by omega⟩ := by intro j hj rw [Finset.mem_erase] exact ⟨fun h => h0S (h ▸ hj), Finset.mem_univ _⟩ have hSeq : S = Finset.univ.erase ⟨0, by omega⟩ := by apply Finset.eq_of_subset_of_card_le hSsub rw [Finset.card_erase_of_mem (Finset.mem_univ _)] simp only [Finset.card_univ, Fintype.card_fin] omega have hm1 : (⟨k₁, hk1'⟩ : Fin ℓ) ∈ S := by rw [hSeq, Finset.mem_erase] refine ⟨?_, Finset.mem_univ _⟩ intro h simp only [Fin.ext_iff] at h omega have hm2 : (⟨k₂, hk2'⟩ : Fin ℓ) ∈ S := by rw [hSeq, Finset.mem_erase] refine ⟨?_, Finset.mem_univ _⟩ intro h simp only [Fin.ext_iff] at h omega have hsub1 := Finset.subset_biUnion_of_mem t hm1 have hsub2 := Finset.subset_biUnion_of_mem t hm2 have key : ∃ m, P.erase m ⊆ t ⟨k₁, hk1'⟩ ∪ t ⟨k₂, hk2'⟩ := by rcases hcase with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ · refine ⟨a k₁, ?_⟩ intro x hx apply Finset.mem_union_left simp only [Finset.mem_erase] at hx simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨hx, ⟨by rw [← h]; exact hx.1, hx.2⟩⟩ · refine ⟨b k₂, ?_⟩ intro x hx simp only [Finset.mem_erase] at hx by_cases hxa : x = a k₂ · apply Finset.mem_union_left simp only [ht_def, Finset.mem_inter, Finset.mem_erase] rw [hxa] at hx ⊢ exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩ · apply Finset.mem_union_right simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨⟨hxa, hx.2⟩, hx⟩ · refine ⟨a k₂, ?_⟩ intro x hx simp only [Finset.mem_erase] at hx by_cases hxb : x = b k₂ · apply Finset.mem_union_left simp only [ht_def, Finset.mem_inter, Finset.mem_erase] rw [hxb] at hx ⊢ exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩ · apply Finset.mem_union_right simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨hx, ⟨hxb, hx.2⟩⟩ obtain ⟨m, hm⟩ := key have hScard : S.card = ℓ - 1 := by rw [hSeq, Finset.card_erase_of_mem (Finset.mem_univ _)] simp only [Finset.card_univ, Fintype.card_fin] have := Finset.card_le_card (hm.trans (Finset.union_subset hsub1 hsub2)) have := Finset.pred_card_le_card_erase (s := P) (a := m) omega
If a color c appears in every pairing class with index in [lo, ℓ), then at least ℓ - lo vertices have excluded color c.
Define a function g on the interval [lo, ℓ) that selects, for each index k, one vertex from {s + 2k - 1, s + 2k} with excluded color c. Because the classes are disjoint along the cycle, g is an injection into the set of vertices of color c. Therefore |{v | μ(v) = c}| ≥ |[lo, ℓ)| = ℓ - lo.
uses
add_left_cancel,congrArg,Fin.val_cast_of_lt,Finset.card_le_card_of_injOn,Finset.coe_Ico,Set.mem_Ico,Finset.coe_filter,Finset.mem_univ,true_and,Set.mem_ofPred_eq,Or.resolve_righthave hw : ∀ i j : ℕ, i < 2 * ℓ - 1 → j < 2 * ℓ - 1 → s + ((i : ℕ) : Fin (2 * ℓ - 1)) = s + ((j : ℕ) : Fin (2 * ℓ - 1)) → i = j := by intro i j hi hj hij have h' := add_left_cancel hij have := congrArg Fin.val h' rwa [Fin.val_cast_of_lt hi, Fin.val_cast_of_lt hj] at this let g : ℕ → Fin (2 * ℓ - 1) := fun k => if μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) = c then s + ((2 * k : ℕ) : Fin (2 * ℓ - 1)) else s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1)) have hle := Finset.card_le_card_of_injOn g (s := Finset.Ico lo ℓ) (t := Finset.univ.filter (fun v => μ v = c)) ?_ ?_ · simpa using hle · intro k hk simp only [Finset.coe_Ico, Set.mem_Ico] at hk simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq, g] split_ifs with h1 · exact h1 · exact (h k hk.1 hk.2).resolve_right h1 · intro k1 hk1 k2 hk2 heq simp only [Finset.coe_Ico, Set.mem_Ico] at hk1 hk2 simp only [g] at heq split_ifs at heq <;> (have := hw _ _ (by omega) (by omega) heq; omega)
Three pairwise distinct colors have at most 2ℓ - 1 vertices in total.
The fibers of three distinct colors under μ are pairwise disjoint subsets of the vertex set Fin (2ℓ - 1). The cardinality of their union is the sum of their individual cardinalities, which cannot exceed the total number of vertices 2ℓ - 1.
uses
Finset.disjoint_filter,Finset.disjoint_union_left,Finset.card_union_of_disjoint,Finset.card_le_univ,Fintype.card_finhave d1 : Disjoint (Finset.univ.filter (fun v => μ v = a)) (Finset.univ.filter (fun v => μ v = b)) := by rw [Finset.disjoint_filter] intro x _ h1 h2 exact hab (h1.symm.trans h2) have d2 : Disjoint (Finset.univ.filter (fun v => μ v = a) ∪ Finset.univ.filter (fun v => μ v = b)) (Finset.univ.filter (fun v => μ v = c)) := by rw [Finset.disjoint_union_left] constructor · rw [Finset.disjoint_filter] intro x _ h1 h2 exact hac (h1.symm.trans h2) · rw [Finset.disjoint_filter] intro x _ h1 h2 exact hbc (h1.symm.trans h2) have e1 := Finset.card_union_of_disjoint d1 have e2 := Finset.card_union_of_disjoint d2 have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪ Finset.univ.filter (fun v => μ v = b) ∪ Finset.univ.filter (fun v => μ v = c)) rw [Fintype.card_fin] at e3 omega
Two distinct colors have at most 2ℓ - 1 vertices in total.
The fibers of two distinct colors under μ are disjoint subsets of Fin (2ℓ - 1). Their combined size is the cardinality of their union, which is at most the total number of vertices 2ℓ - 1.
uses
Finset.disjoint_filter,Finset.card_union_of_disjoint,Finset.card_le_univ,Fintype.card_finhave d1 : Disjoint (Finset.univ.filter (fun v => μ v = a)) (Finset.univ.filter (fun v => μ v = b)) := by rw [Finset.disjoint_filter] intro x _ h1 h2 exact hab (h1.symm.trans h2) have e1 := Finset.card_union_of_disjoint d1 have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪ Finset.univ.filter (fun v => μ v = b)) rw [Fintype.card_fin] at e3 omega
Each list L(v) is P \ {μ(v)} for a unique color μ(v) ∈ P; we define the frequency F(c) and the class colors A(s, k), B(s, k).
Since each L(v) has size ℓ - 1 and is a subset of P of size ℓ, the relative complement P \ L(v) is a singleton {μ(v)}, so L(v) = P \ {μ(v)}. For any base vertex s and index k, A(s, k) and B(s, k) record the excluded colors at vertices s + 2k - 1 and s + 2k, with A(s, 0) = B(s, 0) = μ(s). F(c) is defined as the number of vertices v with μ(v) = c.
uses
Finset.card_sdiff_of_subset,Finset.card_eq_one,Finset.mem_singleton_self,Finset.mem_sdiff,Finset.mem_erase,Finset.mem_singletonclassical have : NeZero (2 * ℓ - 1) := ⟨by omega⟩ letI : NatCast (Fin (2 * ℓ - 1)) := Fin.NatCast.instNatCast (2 * ℓ - 1) -- each list is the palette minus one colour `μ v` have hμ : ∀ v, ∃ m, m ∈ P ∧ L v = P.erase m := by intro v have hc : (P \ L v).card = 1 := by rw [Finset.card_sdiff_of_subset (hLP v), hP, hL] omega obtain ⟨m, hm⟩ := Finset.card_eq_one.mp hc have hmP : m ∈ P ∧ m ∉ L v := by have : m ∈ P \ L v := by rw [hm]; exact Finset.mem_singleton_self m exact Finset.mem_sdiff.mp this refine ⟨m, hmP.1, ?_⟩ ext x rw [Finset.mem_erase] constructor · intro hx exact ⟨fun h => hmP.2 (h ▸ hx), hLP v hx⟩ · rintro ⟨hxm, hxP⟩ by_contra hxL have : x ∈ P \ L v := Finset.mem_sdiff.mpr ⟨hxP, hxL⟩ rw [hm, Finset.mem_singleton] at this exact hxm this choose μ _ hμL using hμ obtain ⟨F, hF⟩ : ∃ F : ℕ → ℕ, ∀ c, F c = (Finset.univ.filter (fun v => μ v = c)).card := ⟨_, fun _ => rfl⟩ obtain ⟨A, hA⟩ : ∃ A : Fin (2 * ℓ - 1) → ℕ → ℕ, ∀ s k, A s k = μ (s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩ obtain ⟨B, hB⟩ : ∃ B : Fin (2 * ℓ - 1) → ℕ → ℕ, ∀ s k, B s k = μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩ have hA0 : ∀ s, A s 0 = μ s := fun s => by rw [hA]; simp have hB0 : ∀ s, B s 0 = μ s := fun s => by rw [hB]; simp
The frequency function F satisfies positivity, sum bounds for two and three colors, and class-coverage lower bounds.
Every vertex v contributes to F(μ(v)), so F(μ(v)) ≥ 1. For distinct colors, the sum bounds F(a) + F(b) ≤ 2ℓ - 1 and F(a) + F(b) + F(c) ≤ 2ℓ - 1 follow directly from the disjointness lemmas. If a color c appears in every class from lo to ℓ - 1, the counting lemma implies ℓ - lo ≤ F(c).
uses
Finset.card_pos,odd_antihole_colorable_of_common_palette_sum2,odd_antihole_colorable_of_common_palette_sum3,odd_antihole_colorable_of_common_palette_counthave hF1 : ∀ v, 1 ≤ F (μ v) := by intro v rw [hF] exact Finset.card_pos.mpr ⟨v, by simp⟩ have hsum2 : ∀ a b, a ≠ b → F a + F b ≤ 2 * ℓ - 1 := by intro a b h rw [hF, hF] exact odd_antihole_colorable_of_common_palette_sum2 μ a b h have hsum3 : ∀ a b c, a ≠ b → a ≠ c → b ≠ c → F a + F b + F c ≤ 2 * ℓ - 1 := by intro a b c h1 h2 h3 rw [hF, hF, hF] exact odd_antihole_colorable_of_common_palette_sum3 μ a b c h1 h2 h3 have hcount : ∀ s c lo, (∀ k, lo ≤ k → k < ℓ → A s k = c ∨ B s k = c) → ℓ - lo ≤ F c := by intro s c lo h rw [hF] apply odd_antihole_colorable_of_common_palette_count ℓ hℓ μ s c lo intro k h1 h2 rw [← hA, ← hB] exact h k h1 h2 -- a pairing is good when Hall's condition holds for it
If a base vertex s is not Good, then either F(μ(s)) ≥ ℓ, or there is a color b such that μ(s), A(s, 1), and b are pairwise distinct and both F(A(s, 1)) ≥ ℓ - 1 and F(b) ≥ ℓ - 1.
A vertex s is Good if the pairing at s satisfies both hypotheses hA and hB of Hall's lemma. If hA fails, μ(s) appears in every class k ∈ [0, ℓ), so F(μ(s)) ≥ ℓ. If hB fails, every class k ∈ [1, ℓ) must have A(s, k) ≠ B(s, k) and must equal the pair {A(s, 1), B(s, 1)}. Hence both A(s, 1) and B(s, 1) appear in all ℓ - 1 classes, giving frequencies at least ℓ - 1. If μ(s) matches either of them, that color also appears in class 0, giving frequency at least ℓ; otherwise μ(s), A(s, 1), and b = B(s, 1) are three pairwise distinct colors.
uses
not_and_or,Ne.symm,le_refl,Or.inl,Or.inr,le_rfllet Good : Fin (2 * ℓ - 1) → Prop := fun s => (∃ k, 1 ≤ k ∧ k < ℓ ∧ A s 0 ≠ A s k ∧ A s 0 ≠ B s k) ∧ (∃ k₁ k₂, 1 ≤ k₁ ∧ k₁ < ℓ ∧ 1 ≤ k₂ ∧ k₂ < ℓ ∧ (A s k₁ = B s k₁ ∨ (A s k₂ ≠ A s k₁ ∧ A s k₂ ≠ B s k₁) ∨ (B s k₂ ≠ A s k₁ ∧ B s k₂ ≠ B s k₁))) have hmaj : ∀ s, ¬ Good s → ℓ ≤ F (μ s) ∨ ∃ b, A s 1 ≠ b ∧ μ s ≠ A s 1 ∧ μ s ≠ b ∧ ℓ - 1 ≤ F (A s 1) ∧ ℓ - 1 ≤ F b := by intro s hng rw [not_and_or] at hng rcases hng with hnA | hnB · left have := hcount s (μ s) 0 (by intro k _ hk by_cases hk0 : k = 0 · subst hk0 left exact hA0 s · by_contra hcon push_neg at hcon exact hnA ⟨k, by omega, hk, by rw [hA0]; exact Ne.symm hcon.1, by rw [hA0]; exact Ne.symm hcon.2⟩) simpa using this · have hmix : ∀ k, 1 ≤ k → k < ℓ → A s k ≠ B s k := fun k h1 h2 h => hnB ⟨k, 1, h1, h2, le_refl _, by omega, Or.inl h⟩ have hinA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ A s k = B s 1 := by intro k h1 h2 by_contra hc push_neg at hc exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inl hc)⟩ have hinB : ∀ k, 1 ≤ k → k < ℓ → B s k = A s 1 ∨ B s k = B s 1 := by intro k h1 h2 by_contra hc push_neg at hc exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inr hc)⟩ have hcA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ B s k = A s 1 := by intro k h1 h2 rcases hinA k h1 h2 with h | h · exact Or.inl h · rcases hinB k h1 h2 with h' | h' · exact Or.inr h' · exact absurd (h.trans h'.symm) (hmix k h1 h2) have hcB : ∀ k, 1 ≤ k → k < ℓ → A s k = B s 1 ∨ B s k = B s 1 := by intro k h1 h2 rcases hinB k h1 h2 with h | h · rcases hinA k h1 h2 with h' | h' · exact absurd (h'.trans h.symm) (hmix k h1 h2) · exact Or.inl h' · exact Or.inr h have hFa := hcount s (A s 1) 1 hcA have hFb := hcount s (B s 1) 1 hcB by_cases hsa : μ s = A s 1 · left have := hcount s (A s 1) 0 (by intro k _ hk by_cases hk0 : k = 0 · subst hk0 left rw [hA0] exact hsa · exact hcA k (by omega) hk) rw [hsa] simpa using this by_cases hsb : μ s = B s 1 · left have := hcount s (B s 1) 0 (by intro k _ hk by_cases hk0 : k = 0 · subst hk0 right rw [hB0] exact hsb · exact hcB k (by omega) hk) rw [hsb] simpa using this right exact ⟨B s 1, hmix 1 le_rfl (by omega), hsa, hsb, hFa, hFb⟩
There exists at least one base vertex s that is Good.
Suppose for contradiction that no vertex is Good. Because the lists are not all identical, there exist vertices u, v with μ(u) ≠ μ(v). Since F(μ(u)) + F(μ(v)) ≤ 2ℓ - 1, at least one vertex s has F(μ(s)) < ℓ. Applying the classification of bad bases to s yields a color b distinct from μ(s) and A(s, 1) with F(A(s, 1)) ≥ ℓ - 1 and F(b) ≥ ℓ - 1. The three-color sum bound forces F(A(s, 1)) < ℓ. Setting t = s + 1 gives μ(t) = A(s, 1), so F(μ(t)) < ℓ. Applying the classification to t yields another color b' such that A(s, 1), A(t, 1), and b' are pairwise distinct with frequencies at least ℓ - 1. Their sum is at least 3(ℓ - 1) ≥ 2ℓ > 2ℓ - 1, contradicting the three-color sum bound.
have hgood : ∃ s, Good s := by by_contra hno have hno' : ∀ s, ¬ Good s := fun s hs => hno ⟨s, hs⟩ obtain ⟨u, v, huv⟩ := hne have hμuv : μ u ≠ μ v := by intro h apply huv rw [hμL u, hμL v, h] obtain ⟨s, hs⟩ : ∃ s, F (μ s) < ℓ := by by_contra hc push_neg at hc have := hsum2 _ _ hμuv have := hc u have := hc v omega rcases hmaj s (hno' s) with h | ⟨b, hab, hsa, hsb, hFa, hFb⟩ · omega · have hFa' : F (A s 1) < ℓ := by by_contra hc push_neg at hc have := hsum3 (μ s) (A s 1) b hsa hsb hab have := hF1 s omega obtain ⟨t, ht⟩ : ∃ t, t = s + ((2 * 1 - 1 : ℕ) : Fin (2 * ℓ - 1)) := ⟨_, rfl⟩ have hAt : A s 1 = μ t := by rw [hA, ht] rcases hmaj t (hno' t) with h | ⟨b', hab', hta, htb, hFa'', hFb'⟩ · rw [← hAt] at h omega · rw [← hAt] at hta htb have := hsum3 (A s 1) (A t 1) b' hta htb hab' omega obtain ⟨s, hsA, hsB⟩ := hgood
The odd antihole complement(C_{2ℓ-1}) is L-colorable.
With a Good base vertex s in hand, Hall's marriage condition holds, so odd_antihole_colorable_of_common_palette_hall provides an injective representative function f choosing a color from L(s + 2j - 1) ∩ L(s + 2j) for each class j. Applying odd_antihole_colorable_of_common_palette_color with f yields a proper list coloring of the antihole.
uses
odd_antihole_colorable_of_common_palette_hall,odd_antihole_colorable_of_common_palette_colorobtain ⟨f, hf, hft⟩ := odd_antihole_colorable_of_common_palette_hall ℓ hℓ P hP (A s) (B s) (by rw [hA0, hB0]) hsA hsB apply odd_antihole_colorable_of_common_palette_color ℓ hℓ L s f hf intro j rw [hμL, hμL, ← hA, ← hB] exact hft j
Fin.cast_val_eq_self- Coercing an element of Fin n to ℕ and casting it back yields the original element.
Finset.mem_inter- An element belongs to the intersection of two finite sets if and only if it belongs to both.
SimpleGraph.compl_adj- Two vertices are adjacent in the graph complement if and only if they are distinct and not adjacent in the graph.
SimpleGraph.cycleGraph_adj'- Two vertices in a cycle graph of size n are adjacent if and only if their cyclic difference is 1 in either direction.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Fin.sub_def- Subtraction in Fin n is computed via modulo arithmetic: a - b = ⟨(n - b + a) % n, ...⟩.
Nat.add_mod_right- Adding a multiple of the modulus does not change the remainder: (x + z) % z = x % z.
Nat.mod_eq_of_lt- If a natural number is strictly less than the modulus, taking the remainder leaves it unchanged.
Finset.all_card_le_biUnion_card_iff_exists_injective- Hall's Marriage Theorem: an indexed family of finite sets admits a system of distinct representatives (an injective choice function) if and only if every subcollection S satisfies |S| ≤ |⋃_{x ∈ S} t(x)|.
Finset.mem_erase- An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
Finset.pred_card_le_card_erase- Erasing any element from a finite set decreases its cardinality by at most 1.
Finset.card_le_card- If s ⊆ t for finite sets, then |s| ≤ |t|.
Finset.card_le_univ- The cardinality of any subset of a finite type is at most the cardinality of the full type.
Finset.subset_biUnion_of_mem- Each member set t(x) is a subset of the union ⋃_{i ∈ s} t(i) for any index x ∈ s.
Finset.eq_univ_of_card- A subset of a finite type with the same cardinality as the type is the entire universal set.
Finset.mem_biUnion- An element belongs to a union of sets if and only if it belongs to at least one set in the family.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s|, then s = t.
Finset.card_erase_of_mem- Erasing an element that belongs to s decreases the cardinality by exactly 1.
Finset.card_univ- The cardinality of Finset.univ is the cardinality of the underlying finite type.
Fintype.card_fin- The cardinality of Fin n is n.
Fin.ext_iff- Two elements of Fin n are equal if and only if their values in ℕ are equal.
Finset.mem_union_left- An element of s belongs to the union s ∪ t.
Finset.mem_union_right- An element of t belongs to the union s ∪ t.
Finset.union_subset- If both s ⊆ u and t ⊆ u, then s ∪ t ⊆ u.
add_left_cancel- In an additive structure, a + b = a + c implies b = c.
congrArg- If two inputs are equal, a function maps them to equal outputs.
Fin.val_cast_of_lt- The natural-number value of casting a < n into Fin n is a.
Finset.card_le_card_of_injOn- If a function maps s into t and is injective on s, then |s| ≤ |t|.
Finset.coe_Ico- The coercion of the half-open interval Finset.Ico a b to a set is Set.Ico a b.
Set.mem_Ico- Membership in Set.Ico a b is equivalent to a ≤ x and x < b.
Finset.coe_filter- The coercion of a filtered finset is the set of elements satisfying the filter condition.
true_and- The proposition True ∧ p is equivalent to p.
Set.mem_ofPred_eq- Membership in a set defined by a predicate equals the predicate holding on that element.
Or.resolve_right- If a ∨ b holds and b is false, then a holds.
Finset.disjoint_filter- Two filtered sub-finsets of a set are disjoint if and only if no element satisfies both conditions.
Finset.disjoint_union_left- A union s ∪ t is disjoint from u if and only if both s and t are disjoint from u.
Finset.card_union_of_disjoint- The cardinality of the union of disjoint finite sets is the sum of their cardinalities.
Finset.card_sdiff_of_subset- If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_eq_one- A finite set has cardinality 1 if and only if it is a singleton.
Finset.mem_singleton_self- An element belongs to its own singleton set.
Finset.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and not to t.
Finset.mem_singleton- An element b belongs to {a} if and only if b = a.
Finset.card_pos- A finite set has positive cardinality if and only if it is nonempty.
odd_antihole_colorable_of_common_palette_sum2- The sum of the sizes of any two distinct color classes is at most the total number of vertices n.
odd_antihole_colorable_of_common_palette_sum3- The sum of the sizes of any three pairwise distinct color classes is at most the total number of vertices n.
odd_antihole_colorable_of_common_palette_count- If every pairing class with index in [lo, ℓ) contains a vertex of color c, then at least ℓ - lo vertices have color c.
not_and_or- Negation of a conjunction is the disjunction of the negations: ¬(a ∧ b) ↔ ¬a ∨ ¬b.
Ne.symm- Inequality is symmetric: a ≠ b implies b ≠ a.
le_refl- Reflexivity of the preorder relation: a ≤ a.
Or.inl- Left disjunction introduction: a implies a ∨ b.
Or.inr- Right disjunction introduction: b implies a ∨ b.
le_rfl- Reflexivity of inequality: a ≤ a.
odd_antihole_colorable_of_common_palette_hall- Under non-degeneracy conditions, Hall's condition holds for the pairing classes, yielding an injective color choice.
odd_antihole_colorable_of_common_palette_color- An injective choice function on the pairing classes yields a proper list coloring of the antihole.
- In natural number arithmetic on indices, 2 * 0 - 1 = 0, so the class for j = 0 represents the singleton {s}.
- Vertices of the cycle C_{2ℓ-1} and its complement are represented by Fin (2ℓ - 1), where independent sets of the antihole correspond to singletons and adjacent cycle pairs.
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.
Lean’s trace was cut to the first 400 of 419 tactics.
open Fin.NatCast in/-- Colouring from a system of distinct representatives of the classes`{s + (2j-1), s + 2j}`, `j < ℓ` (class `0` is the singleton `{s}`). -/theorem odd_antihole_colorable_of_common_palette_color (ℓ : ℕ) (hℓ : 3 ≤ ℓ) [NeZero (2 * ℓ - 1)] (L : Fin (2 * ℓ - 1) → Finset ℕ) (s : Fin (2 * ℓ - 1)) (f : Fin ℓ → ℕ) (hf : Function.Injective f) (hft : ∀ j : Fin ℓ, f j ∈ L (s + ((2 * j.val - 1 : ℕ) : Fin (2 * ℓ - 1))) ∩ L (s + ((2 * j.val : ℕ) : Fin (2 * ℓ - 1)))) : ∃ c : Fin (2 * ℓ - 1) → ℕ, (∀ v, c v ∈ L v) ∧ ∀ u v, (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Adj u v → c u ≠ c v := by have hcls : ∀ v : Fin (2 * ℓ - 1), ((v - s).val + 1) / 2 < ℓ := by intro v have := (v - s).isLt omega refine ⟨fun v => f ⟨((v - s).val + 1) / 2, hcls v⟩, ?_, ?_⟩ · intro v have hv : s + (((v - s).val : ℕ) : Fin (2 * ℓ - 1)) = v := by rw [Fin.cast_val_eq_self] abel have h := hft ⟨((v - s).val + 1) / 2, hcls v⟩ simp only [Finset.mem_inter] at h have key : 2 * (((v - s).val + 1) / 2) - 1 = (v - s).val ∨ 2 * (((v - s).val + 1) / 2) = (v - s).val := by omega rcases key with k | k · have h1 := h.1 rw [k, hv] at h1 exact h1 · have h2 := h.2 rw [k, hv] at h2 exact h2 · intro u v hadj heq rw [SimpleGraph.compl_adj] at hadj obtain ⟨hne, hnadj⟩ := hadj apply hnadj have heq' := Fin.mk.inj_iff.mp (hf heq) rw [SimpleGraph.cycleGraph_adj'] have hij : (u - s).val ≠ (v - s).val := by intro h apply hne have : u - s = v - s := Fin.ext h simpa using this have hsub : u - v = (u - s) - (v - s) := by abel have hsub' : v - u = (v - s) - (u - s) := by abel rw [hsub, hsub'] have hu := (u - s).isLt have hv := (v - s).isLt rcases (show (u - s).val = (v - s).val + 1 ∨ (v - s).val = (u - s).val + 1 by omega) with h | h · left rw [Fin.sub_def] simp only rw [h, show 2 * ℓ - 1 - (v - s).val + ((v - s).val + 1) = 1 + (2 * ℓ - 1) by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)] · right rw [Fin.sub_def] simp only rw [h, show 2 * ℓ - 1 - (u - s).val + ((u - s).val + 1) = 1 + (2 * ℓ - 1) by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)]/-- Hall's condition for the classes of one pairing. -/theorem odd_antihole_colorable_of_common_palette_hall (ℓ : ℕ) (hℓ : 3 ≤ ℓ) (P : Finset ℕ) (hP : P.card = ℓ) (a b : ℕ → ℕ) (h0 : a 0 = b 0) (hA : ∃ k, 1 ≤ k ∧ k < ℓ ∧ a 0 ≠ a k ∧ a 0 ≠ b k) (hB : ∃ k₁ k₂, 1 ≤ k₁ ∧ k₁ < ℓ ∧ 1 ≤ k₂ ∧ k₂ < ℓ ∧ (a k₁ = b k₁ ∨ (a k₂ ≠ a k₁ ∧ a k₂ ≠ b k₁) ∨ (b k₂ ≠ a k₁ ∧ b k₂ ≠ b k₁))) : ∃ f : Fin ℓ → ℕ, Function.Injective f ∧ ∀ j : Fin ℓ, f j ∈ P.erase (a j.val) ∩ P.erase (b j.val) := by classical set t : Fin ℓ → Finset ℕ := fun j => P.erase (a j.val) ∩ P.erase (b j.val) with ht_def apply (Finset.all_card_le_biUnion_card_iff_exists_injective t).mp have ht : ∀ j, ℓ - 2 ≤ (t j).card := by intro j have h1 : (P.erase (a j.val)).erase (b j.val) ⊆ t j := by intro x hx simp only [Finset.mem_erase] at hx simp only [ht_def, Finset.mem_inter, Finset.mem_erase] tauto have h2 := Finset.pred_card_le_card_erase (s := P.erase (a j.val)) (a := b j.val) have h3 := Finset.pred_card_le_card_erase (s := P) (a := a j.val) have h4 := Finset.card_le_card h1 omega have ht0 : ℓ - 1 ≤ (t ⟨0, by omega⟩).card := by have hsub : P.erase (a 0) ⊆ t ⟨0, by omega⟩ := by intro x hx simp only [ht_def, Finset.mem_inter] exact ⟨hx, by rw [← h0]; exact hx⟩ have := Finset.card_le_card hsub have := Finset.pred_card_le_card_erase (s := P) (a := a 0) omega intro S have hSle : S.card ≤ ℓ := by simpa using Finset.card_le_univ S by_cases hS : S.card ≤ ℓ - 2 · rcases S.eq_empty_or_nonempty with rfl | ⟨j, hj⟩ · simp · exact hS.trans ((ht j).trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t hj))) by_cases h0S : (⟨0, by omega⟩ : Fin ℓ) ∈ S · by_cases hSf : S.card = ℓ · have hSu : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSf) have hPsub : P ⊆ S.biUnion t := by intro x hx rw [Finset.mem_biUnion] by_cases hx0 : x = a 0 · obtain ⟨k, hk1, hk2, hak, hbk⟩ := hA refine ⟨⟨k, hk2⟩, by rw [hSu]; exact Finset.mem_univ _, ?_⟩ simp only [ht_def, Finset.mem_inter, Finset.mem_erase] rw [hx0] at hx ⊢ exact ⟨⟨hak, hx⟩, ⟨hbk, hx⟩⟩ · refine ⟨⟨0, by omega⟩, h0S, ?_⟩ simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨⟨hx0, hx⟩, ⟨by rw [← h0]; exact hx0, hx⟩⟩ calc S.card = ℓ := hSf _ = P.card := hP.symm _ ≤ _ := Finset.card_le_card hPsub · have : S.card ≤ ℓ - 1 := by omega exact this.trans (ht0.trans (Finset.card_le_card (Finset.subset_biUnion_of_mem t h0S))) · obtain ⟨k₁, k₂, hk1, hk1', hk2, hk2', hcase⟩ := hB have hSsub : S ⊆ Finset.univ.erase ⟨0, by omega⟩ := by intro j hj rw [Finset.mem_erase] exact ⟨fun h => h0S (h ▸ hj), Finset.mem_univ _⟩ have hSeq : S = Finset.univ.erase ⟨0, by omega⟩ := by apply Finset.eq_of_subset_of_card_le hSsub rw [Finset.card_erase_of_mem (Finset.mem_univ _)] simp only [Finset.card_univ, Fintype.card_fin] omega have hm1 : (⟨k₁, hk1'⟩ : Fin ℓ) ∈ S := by rw [hSeq, Finset.mem_erase] refine ⟨?_, Finset.mem_univ _⟩ intro h simp only [Fin.ext_iff] at h omega have hm2 : (⟨k₂, hk2'⟩ : Fin ℓ) ∈ S := by rw [hSeq, Finset.mem_erase] refine ⟨?_, Finset.mem_univ _⟩ intro h simp only [Fin.ext_iff] at h omega have hsub1 := Finset.subset_biUnion_of_mem t hm1 have hsub2 := Finset.subset_biUnion_of_mem t hm2 have key : ∃ m, P.erase m ⊆ t ⟨k₁, hk1'⟩ ∪ t ⟨k₂, hk2'⟩ := by rcases hcase with h | ⟨h1, h2⟩ | ⟨h1, h2⟩ · refine ⟨a k₁, ?_⟩ intro x hx apply Finset.mem_union_left simp only [Finset.mem_erase] at hx simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨hx, ⟨by rw [← h]; exact hx.1, hx.2⟩⟩ · refine ⟨b k₂, ?_⟩ intro x hx simp only [Finset.mem_erase] at hx by_cases hxa : x = a k₂ · apply Finset.mem_union_left simp only [ht_def, Finset.mem_inter, Finset.mem_erase] rw [hxa] at hx ⊢ exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩ · apply Finset.mem_union_right simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨⟨hxa, hx.2⟩, hx⟩ · refine ⟨a k₂, ?_⟩ intro x hx simp only [Finset.mem_erase] at hx by_cases hxb : x = b k₂ · apply Finset.mem_union_left simp only [ht_def, Finset.mem_inter, Finset.mem_erase] rw [hxb] at hx ⊢ exact ⟨⟨h1, hx.2⟩, ⟨h2, hx.2⟩⟩ · apply Finset.mem_union_right simp only [ht_def, Finset.mem_inter, Finset.mem_erase] exact ⟨hx, ⟨hxb, hx.2⟩⟩ obtain ⟨m, hm⟩ := key have hScard : S.card = ℓ - 1 := by rw [hSeq, Finset.card_erase_of_mem (Finset.mem_univ _)] simp only [Finset.card_univ, Fintype.card_fin] have := Finset.card_le_card (hm.trans (Finset.union_subset hsub1 hsub2)) have := Finset.pred_card_le_card_erase (s := P) (a := m) omegaopen Fin.NatCast in/-- If every class of the pairing at `s` with index in `[lo, ℓ)` contains a vertex ofcolour `c`, then at least `ℓ - lo` vertices have colour `c`. -/theorem odd_antihole_colorable_of_common_palette_count (ℓ : ℕ) (hℓ : 3 ≤ ℓ) [NeZero (2 * ℓ - 1)] (μ : Fin (2 * ℓ - 1) → ℕ) (s : Fin (2 * ℓ - 1)) (c lo : ℕ) (h : ∀ k, lo ≤ k → k < ℓ → μ (s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))) = c ∨ μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) = c) : ℓ - lo ≤ (Finset.univ.filter (fun v => μ v = c)).card := by have hw : ∀ i j : ℕ, i < 2 * ℓ - 1 → j < 2 * ℓ - 1 → s + ((i : ℕ) : Fin (2 * ℓ - 1)) = s + ((j : ℕ) : Fin (2 * ℓ - 1)) → i = j := by intro i j hi hj hij have h' := add_left_cancel hij have := congrArg Fin.val h' rwa [Fin.val_cast_of_lt hi, Fin.val_cast_of_lt hj] at this let g : ℕ → Fin (2 * ℓ - 1) := fun k => if μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) = c then s + ((2 * k : ℕ) : Fin (2 * ℓ - 1)) else s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1)) have hle := Finset.card_le_card_of_injOn g (s := Finset.Ico lo ℓ) (t := Finset.univ.filter (fun v => μ v = c)) ?_ ?_ · simpa using hle · intro k hk simp only [Finset.coe_Ico, Set.mem_Ico] at hk simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq, g] split_ifs with h1 · exact h1 · exact (h k hk.1 hk.2).resolve_right h1 · intro k1 hk1 k2 hk2 heq simp only [Finset.coe_Ico, Set.mem_Ico] at hk1 hk2 simp only [g] at heq split_ifs at heq <;> (have := hw _ _ (by omega) (by omega) heq; omega)/-- Three distinct colour classes have at most `n` vertices together. -/theorem odd_antihole_colorable_of_common_palette_sum3 {n : ℕ} (μ : Fin n → ℕ) (a b c : ℕ) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) : (Finset.univ.filter (fun v => μ v = a)).card + (Finset.univ.filter (fun v => μ v = b)).card + (Finset.univ.filter (fun v => μ v = c)).card ≤ n := by have d1 : Disjoint (Finset.univ.filter (fun v => μ v = a)) (Finset.univ.filter (fun v => μ v = b)) := by rw [Finset.disjoint_filter] intro x _ h1 h2 exact hab (h1.symm.trans h2) have d2 : Disjoint (Finset.univ.filter (fun v => μ v = a) ∪ Finset.univ.filter (fun v => μ v = b)) (Finset.univ.filter (fun v => μ v = c)) := by rw [Finset.disjoint_union_left] constructor · rw [Finset.disjoint_filter] intro x _ h1 h2 exact hac (h1.symm.trans h2) · rw [Finset.disjoint_filter] intro x _ h1 h2 exact hbc (h1.symm.trans h2) have e1 := Finset.card_union_of_disjoint d1 have e2 := Finset.card_union_of_disjoint d2 have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪ Finset.univ.filter (fun v => μ v = b) ∪ Finset.univ.filter (fun v => μ v = c)) rw [Fintype.card_fin] at e3 omega/-- Two distinct colour classes have at most `n` vertices together. -/theorem odd_antihole_colorable_of_common_palette_sum2 {n : ℕ} (μ : Fin n → ℕ) (a b : ℕ) (hab : a ≠ b) : (Finset.univ.filter (fun v => μ v = a)).card + (Finset.univ.filter (fun v => μ v = b)).card ≤ n := by have d1 : Disjoint (Finset.univ.filter (fun v => μ v = a)) (Finset.univ.filter (fun v => μ v = b)) := by rw [Finset.disjoint_filter] intro x _ h1 h2 exact hab (h1.symm.trans h2) have e1 := Finset.card_union_of_disjoint d1 have e3 := Finset.card_le_univ (Finset.univ.filter (fun v => μ v = a) ∪ Finset.univ.filter (fun v => μ v = b)) rw [Fintype.card_fin] at e3 omegatheorem odd_antihole_colorable_of_common_palette (ℓ : ℕ) (hℓ : 3 ≤ ℓ) (P : Finset ℕ) (hP : P.card = ℓ) (L : Fin (2 * ℓ - 1) → Finset ℕ) (hL : ∀ v, (L v).card = ℓ - 1) (hLP : ∀ v, L v ⊆ P) (hne : ∃ u v, L u ≠ L v) : ∃ c : Fin (2 * ℓ - 1) → ℕ, (∀ v, c v ∈ L v) ∧ ∀ u v, (SimpleGraph.cycleGraph (2 * ℓ - 1))ᶜ.Adj u v → c u ≠ c v := by classical have : NeZero (2 * ℓ - 1) := ⟨by omega⟩ letI : NatCast (Fin (2 * ℓ - 1)) := Fin.NatCast.instNatCast (2 * ℓ - 1) -- each list is the palette minus one colour `μ v` have hμ : ∀ v, ∃ m, m ∈ P ∧ L v = P.erase m := by intro v have hc : (P \ L v).card = 1 := by rw [Finset.card_sdiff_of_subset (hLP v), hP, hL] omega obtain ⟨m, hm⟩ := Finset.card_eq_one.mp hc have hmP : m ∈ P ∧ m ∉ L v := by have : m ∈ P \ L v := by rw [hm]; exact Finset.mem_singleton_self m exact Finset.mem_sdiff.mp this refine ⟨m, hmP.1, ?_⟩ ext x rw [Finset.mem_erase] constructor · intro hx exact ⟨fun h => hmP.2 (h ▸ hx), hLP v hx⟩ · rintro ⟨hxm, hxP⟩ by_contra hxL have : x ∈ P \ L v := Finset.mem_sdiff.mpr ⟨hxP, hxL⟩ rw [hm, Finset.mem_singleton] at this exact hxm this choose μ _ hμL using hμ obtain ⟨F, hF⟩ : ∃ F : ℕ → ℕ, ∀ c, F c = (Finset.univ.filter (fun v => μ v = c)).card := ⟨_, fun _ => rfl⟩ obtain ⟨A, hA⟩ : ∃ A : Fin (2 * ℓ - 1) → ℕ → ℕ, ∀ s k, A s k = μ (s + ((2 * k - 1 : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩ obtain ⟨B, hB⟩ : ∃ B : Fin (2 * ℓ - 1) → ℕ → ℕ, ∀ s k, B s k = μ (s + ((2 * k : ℕ) : Fin (2 * ℓ - 1))) := ⟨_, fun _ _ => rfl⟩ have hA0 : ∀ s, A s 0 = μ s := fun s => by rw [hA]; simp have hB0 : ∀ s, B s 0 = μ s := fun s => by rw [hB]; simp have hF1 : ∀ v, 1 ≤ F (μ v) := by intro v rw [hF] exact Finset.card_pos.mpr ⟨v, by simp⟩ have hsum2 : ∀ a b, a ≠ b → F a + F b ≤ 2 * ℓ - 1 := by intro a b h rw [hF, hF] exact odd_antihole_colorable_of_common_palette_sum2 μ a b h have hsum3 : ∀ a b c, a ≠ b → a ≠ c → b ≠ c → F a + F b + F c ≤ 2 * ℓ - 1 := by intro a b c h1 h2 h3 rw [hF, hF, hF] exact odd_antihole_colorable_of_common_palette_sum3 μ a b c h1 h2 h3 have hcount : ∀ s c lo, (∀ k, lo ≤ k → k < ℓ → A s k = c ∨ B s k = c) → ℓ - lo ≤ F c := by intro s c lo h rw [hF] apply odd_antihole_colorable_of_common_palette_count ℓ hℓ μ s c lo intro k h1 h2 rw [← hA, ← hB] exact h k h1 h2 -- a pairing is good when Hall's condition holds for it let Good : Fin (2 * ℓ - 1) → Prop := fun s => (∃ k, 1 ≤ k ∧ k < ℓ ∧ A s 0 ≠ A s k ∧ A s 0 ≠ B s k) ∧ (∃ k₁ k₂, 1 ≤ k₁ ∧ k₁ < ℓ ∧ 1 ≤ k₂ ∧ k₂ < ℓ ∧ (A s k₁ = B s k₁ ∨ (A s k₂ ≠ A s k₁ ∧ A s k₂ ≠ B s k₁) ∨ (B s k₂ ≠ A s k₁ ∧ B s k₂ ≠ B s k₁))) have hmaj : ∀ s, ¬ Good s → ℓ ≤ F (μ s) ∨ ∃ b, A s 1 ≠ b ∧ μ s ≠ A s 1 ∧ μ s ≠ b ∧ ℓ - 1 ≤ F (A s 1) ∧ ℓ - 1 ≤ F b := by intro s hng rw [not_and_or] at hng rcases hng with hnA | hnB · left have := hcount s (μ s) 0 (by intro k _ hk by_cases hk0 : k = 0 · subst hk0 left exact hA0 s · by_contra hcon push_neg at hcon exact hnA ⟨k, by omega, hk, by rw [hA0]; exact Ne.symm hcon.1, by rw [hA0]; exact Ne.symm hcon.2⟩) simpa using this · have hmix : ∀ k, 1 ≤ k → k < ℓ → A s k ≠ B s k := fun k h1 h2 h => hnB ⟨k, 1, h1, h2, le_refl _, by omega, Or.inl h⟩ have hinA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ A s k = B s 1 := by intro k h1 h2 by_contra hc push_neg at hc exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inl hc)⟩ have hinB : ∀ k, 1 ≤ k → k < ℓ → B s k = A s 1 ∨ B s k = B s 1 := by intro k h1 h2 by_contra hc push_neg at hc exact hnB ⟨1, k, le_refl _, by omega, h1, h2, Or.inr (Or.inr hc)⟩ have hcA : ∀ k, 1 ≤ k → k < ℓ → A s k = A s 1 ∨ B s k = A s 1 := by intro k h1 h2 rcases hinA k h1 h2 with h | h · exact Or.inl h · rcases hinB k h1 h2 with h' | h' · exact Or.inr h' · exact absurd (h.trans h'.symm) (hmix k h1 h2) have hcB : ∀ k, 1 ≤ k → k < ℓ → A s k = B s 1 ∨ B s k = B s 1 := by intro k h1 h2 rcases hinB k h1 h2 with h | h · rcases hinA k h1 h2 with h' | h' · exact absurd (h'.trans h.symm) (hmix k h1 h2) · exact Or.inl h' · exact Or.inr h have hFa := hcount s (A s 1) 1 hcA have hFb := hcount s (B s 1) 1 hcB by_cases hsa : μ s = A s 1 · left have := hcount s (A s 1) 0 (by intro k _ hk by_cases hk0 : k = 0 · subst hk0 left rw [hA0] exact hsa · exact hcA k (by omega) hk) rw [hsa] simpa using this by_cases hsb : μ s = B s 1 · left have := hcount s (B s 1) 0 (by intro k _ hk by_cases hk0 : k = 0 · subst hk0 right rw [hB0] exact hsb · exact hcB k (by omega) hk) rw [hsb] simpa using this right exact ⟨B s 1, hmix 1 le_rfl (by omega), hsa, hsb, hFa, hFb⟩ have hgood : ∃ s, Good s := by by_contra hno have hno' : ∀ s, ¬ Good s := fun s hs => hno ⟨s, hs⟩ obtain ⟨u, v, huv⟩ := hne have hμuv : μ u ≠ μ v := by intro h apply huv rw [hμL u, hμL v, h] obtain ⟨s, hs⟩ : ∃ s, F (μ s) < ℓ := by by_contra hc push_neg at hc have := hsum2 _ _ hμuv have := hc u have := hc v omega rcases hmaj s (hno' s) with h | ⟨b, hab, hsa, hsb, hFa, hFb⟩ · omega · have hFa' : F (A s 1) < ℓ := by by_contra hc push_neg at hc have := hsum3 (μ s) (A s 1) b hsa hsb hab have := hF1 s omega obtain ⟨t, ht⟩ : ∃ t, t = s + ((2 * 1 - 1 : ℕ) : Fin (2 * ℓ - 1)) := ⟨_, rfl⟩ have hAt : A s 1 = μ t := by rw [hA, ht] rcases hmaj t (hno' t) with h | ⟨b', hab', hta, htb, hFa'', hFb'⟩ · rw [← hAt] at h omega · rw [← hAt] at hta htb have := hsum3 (A s 1) (A t 1) b' hta htb hab' omega obtain ⟨s, hsA, hsB⟩ := hgood obtain ⟨f, hf, hft⟩ := odd_antihole_colorable_of_common_palette_hall ℓ hℓ P hP (A s) (B s) (by rw [hA0, hB0]) hsA hsB apply odd_antihole_colorable_of_common_palette_color ℓ hℓ L s f hf intro j rw [hμL, hμL, ← hA, ← hB] exact hft j