path_cut_word_odd_run_ineq
For a four-partition A,B,C,D of the vertices of the path P_n, the sum of the numbers of maximal odd-length crossing runs for A, B, C and D is at most the corresponding sum for A ∪ B, A ∪ C and B ∪ C.
Statement
theorem path_cut_word_odd_run_ineq (n : ℕ) (A B C D : Finset (Fin n))
(hpart : is_four_partition A B C D) :
odd_run_count (path_cut_word n A) + odd_run_count (path_cut_word n B) +
odd_run_count (path_cut_word n C) + odd_run_count (path_cut_word n D) ≤
odd_run_count (path_cut_word n (A ∪ B)) + odd_run_count (path_cut_word n (A ∪ C)) +
odd_run_count (path_cut_word n (B ∪ C))- Source
- step towards claw_free_tree_graph_state_mmi
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- path_cut_word
path_cut_word n Sis the length-(n-1) boolean word whose j-th letter records whether the j-th edge of the pathpathGraph n(i.e. the… - odd_run_count
odd_run_count lis the number of maximal runs oftruein the boolean wordlwhose length is odd. The finalfalseis appended so… - path_cut_word_count_cancelFor a four-partition A,B,C,D of the vertices of the path P_n, the total number of edges crossing the cuts defined by A, B, C, D equals the…
- pathCertOddRunIneqFor any four-color path word, the signed sum of odd crossing-run counts for the seven masks is nonpositive.
- pathCertWordThe sequence of cut-crossing flags for one party-union mask along a colored vertex word.
- path_cert_word_eq_cut_wordThe Boolean edge word used by the finite-state certificate is the ordinary path cut word of the corresponding color mask.
- is_four_partitionGiven a finite type V with decidable equality and four finite subsets A, B, C, D : Finset V, is_four_partition A B C D is the proposition…
- odd_run_aux
odd_run_aux inRun oddLen lscans the boolean listlleft to right, keeping a flaginRun(currently inside a run oftrues) and… - pathCertSignThe signs of the seven terms in the tripartite cut-rank sum.
- pathCertMaskThe seven party-union masks for a four-color path word.
- path_cut_word
The proof, explained
The inequality is proved by reduction to pathCertOddRunIneq. The vertices of the path are 4-colored according to the partition A, B, C, D. The cut words for the relevant sets are identified with the words produced by pathCertWord, and the claim follows after simplifying the signs and using that the cut word of D equals that of the complement A ∪ B ∪ C.
A cut word is invariant under set complementation.
The cut word marks whether adjacent vertices differ in membership; negating both memberships does not change whether they differ.
unfold path_cut_word apply congrArg List.ofFn funext k simp only [Finset.mem_compl, decide_not] cases (decide ((⟨k.val, by omega⟩ : Fin n) ∈ S)) <;> cases (decide ((⟨k.val + 1, by omega⟩ : Fin n) ∈ S)) <;> decide
The main inequality holds.
It follows by reduction to the certificate inequality.
classical rcases hpart with ⟨hAB,hAC,hAD,hBC,hBD,hCD,hall⟩ have hD : D = (A ∪ B ∪ C)ᶜ := by ext v have hcover : v ∈ A ∨ v ∈ B ∨ v ∈ C ∨ v ∈ D := by have hh : v ∈ A ∪ B ∪ C ∪ D := by rw [hall]; simp simpa only [Finset.mem_union, or_assoc] using hh have hda := Finset.disjoint_left.mp hAD have hdb := Finset.disjoint_left.mp hBD have hdc := Finset.disjoint_left.mp hCD simp only [Finset.mem_compl, Finset.mem_union, not_or] constructor · intro hd exact ⟨⟨fun ha => hda ha hd, fun hb => hdb hb hd⟩, fun hc => hdc hc hd⟩ · intro h rcases h with ⟨⟨ha,hb⟩,hc⟩ rcases hcover with ha' | hb' | hc' | hd · exact False.elim (ha ha') · exact False.elim (hb hb') · exact False.elim (hc hc') · exact hd cases n with | zero => simp [path_cut_word, odd_run_count, odd_run_aux] | succ m => let color : Fin (m+1) → Fin 4 := fun v => if v ∈ A then 0 else if v ∈ B then 1 else if v ∈ C then 2 else 3 let sets : Fin 7 → Finset (Fin (m+1)) := ![A,B,C,A ∪ B,A ∪ C,B ∪ C,A ∪ B ∪ C] have hmask (j : Fin 7) : (Finset.univ.filter fun v => Nat.testBit (pathCertMask j) (color v).val) = sets j := by fin_cases j <;> ext v : 1 <;> simp only [Finset.mem_filter, Finset.mem_univ, true_and] <;> by_cases ha : v ∈ A <;> by_cases hb : v ∈ B <;> by_cases hc : v ∈ C <;> simp_all [sets, color, pathCertMask, Finset.disjoint_left] <;> decide have hm (j : Fin 7) : pathCertWord (color ⟨0, by omega⟩) (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩) j = path_cut_word (m+1) (sets j) := by rw [← hmask j] exact path_cert_word_eq_cut_word (m+1) (by omega) color j have hw := pathCertOddRunIneq (color ⟨0, by omega⟩) (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩) simp_rw [hm] at hw have hcomp : path_cut_word (m+1) D = path_cut_word (m+1) (A ∪ B ∪ C) := by rw [hD] exact cut_word_compl_scratch _ _ simp only [Finset.union_assoc] at hcomp simp [Fin.sum_univ_succ, pathCertSign, sets, ← hcomp] at hw omega
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.
open scoped Classical BigOperatorslemma cut_word_compl_scratch (n : ℕ) (S : Finset (Fin n)) : path_cut_word n Sᶜ = path_cut_word n S := by unfold path_cut_word apply congrArg List.ofFn funext k simp only [Finset.mem_compl, decide_not] cases (decide ((⟨k.val, by omega⟩ : Fin n) ∈ S)) <;> cases (decide ((⟨k.val + 1, by omega⟩ : Fin n) ∈ S)) <;> decide/-- Odd crossing runs of A,B,C,D are dominated by those of AB,AC,BC. -/theorem path_cut_word_odd_run_ineq (n : ℕ) (A B C D : Finset (Fin n)) (hpart : is_four_partition A B C D) : odd_run_count (path_cut_word n A) + odd_run_count (path_cut_word n B) + odd_run_count (path_cut_word n C) + odd_run_count (path_cut_word n D) ≤ odd_run_count (path_cut_word n (A ∪ B)) + odd_run_count (path_cut_word n (A ∪ C)) + odd_run_count (path_cut_word n (B ∪ C)) := by classical rcases hpart with ⟨hAB,hAC,hAD,hBC,hBD,hCD,hall⟩ have hD : D = (A ∪ B ∪ C)ᶜ := by ext v have hcover : v ∈ A ∨ v ∈ B ∨ v ∈ C ∨ v ∈ D := by have hh : v ∈ A ∪ B ∪ C ∪ D := by rw [hall]; simp simpa only [Finset.mem_union, or_assoc] using hh have hda := Finset.disjoint_left.mp hAD have hdb := Finset.disjoint_left.mp hBD have hdc := Finset.disjoint_left.mp hCD simp only [Finset.mem_compl, Finset.mem_union, not_or] constructor · intro hd exact ⟨⟨fun ha => hda ha hd, fun hb => hdb hb hd⟩, fun hc => hdc hc hd⟩ · intro h rcases h with ⟨⟨ha,hb⟩,hc⟩ rcases hcover with ha' | hb' | hc' | hd · exact False.elim (ha ha') · exact False.elim (hb hb') · exact False.elim (hc hc') · exact hd cases n with | zero => simp [path_cut_word, odd_run_count, odd_run_aux] | succ m => let color : Fin (m+1) → Fin 4 := fun v => if v ∈ A then 0 else if v ∈ B then 1 else if v ∈ C then 2 else 3 let sets : Fin 7 → Finset (Fin (m+1)) := ![A,B,C,A ∪ B,A ∪ C,B ∪ C,A ∪ B ∪ C] have hmask (j : Fin 7) : (Finset.univ.filter fun v => Nat.testBit (pathCertMask j) (color v).val) = sets j := by fin_cases j <;> ext v : 1 <;> simp only [Finset.mem_filter, Finset.mem_univ, true_and] <;> by_cases ha : v ∈ A <;> by_cases hb : v ∈ B <;> by_cases hc : v ∈ C <;> simp_all [sets, color, pathCertMask, Finset.disjoint_left] <;> decide have hm (j : Fin 7) : pathCertWord (color ⟨0, by omega⟩) (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩) j = path_cut_word (m+1) (sets j) := by rw [← hmask j] exact path_cert_word_eq_cut_word (m+1) (by omega) color j have hw := pathCertOddRunIneq (color ⟨0, by omega⟩) (List.ofFn fun k : Fin ((m+1)-1) => color ⟨k.val+1, by omega⟩) simp_rw [hm] at hw have hcomp : path_cut_word (m+1) D = path_cut_word (m+1) (A ∪ B ∪ C) := by rw [hD] exact cut_word_compl_scratch _ _ simp only [Finset.union_assoc] at hcomp simp [Fin.sum_univ_succ, pathCertSign, sets, ← hcomp] at hw omega