finite_single_outside_packing_replacement
theoremverified
Replacing each of a finite family of sets by one with a distinct fresh outside vertex preserves the size and pairwise at-most-one intersection of an existing packing, provided the inside intersections stay at most one.
Statement
theorem finite_single_outside_packing_replacement {ι V : Type*} [Fintype ι] [DecidableEq V] (S : Finset V) (P : Finset (Finset V)) (T : ι → Finset V) (f : ι → V) (hP : (P : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1)) (hout : ∀ i, T i \ S = {f i}) (hfinj : Function.Injective f) (hfresh : ∀ i, f i ∉ P.biUnion id) (hwithin : ∀ i j, i ≠ j → ((T i ∩ T j) ∩ S).card ≤ 1) (hbetween : ∀ q ∈ P, ∀ i, ((q ∩ T i) ∩ S).card ≤ 1) : (P ∪ Finset.univ.image T).card = P.card + Fintype.card ι ∧ ((P ∪ Finset.univ.image T : Finset (Finset V)) : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1)
- Source
- Simultaneous remapping step for simple_graph_triangle_packing_pair_deletion_forcing_quadratic_kernel.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Lean source view module on GitHub
theorem finite_single_outside_packing_replacement {ι V : Type*} [Fintype ι] [DecidableEq V] (S : Finset V) (P : Finset (Finset V)) (T : ι → Finset V) (f : ι → V) (hP : (P : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1)) (hout : ∀ i, T i \ S = {f i}) (hfinj : Function.Injective f) (hfresh : ∀ i, f i ∉ P.biUnion id) (hwithin : ∀ i j, i ≠ j → ((T i ∩ T j) ∩ S).card ≤ 1) (hbetween : ∀ q ∈ P, ∀ i, ((q ∩ T i) ∩ S).card ≤ 1) : (P ∪ Finset.univ.image T).card = P.card + Fintype.card ι ∧ ((P ∪ Finset.univ.image T : Finset (Finset V)) : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1) := by classical have hout_iff : ∀ i v, v ∈ T i → v ∉ S → v = f i := by intro i v hv hs have hm : v ∈ T i \ S := Finset.mem_sdiff.mpr ⟨hv,hs⟩ rw [hout i] at hm simpa using hm have hfm : ∀ i, f i ∈ T i := by intro i have hm : f i ∈ T i \ S := by rw [hout i]; simp exact (Finset.mem_sdiff.mp hm).1 have hTin : Function.Injective T := by intro i j heq have hset := congrArg (fun A : Finset V => A \ S) heq rw [hout i, hout j] at hset exact hfinj (Finset.singleton_injective hset) have hnotP : ∀ i, T i ∉ P := by intro i hi apply hfresh i exact Finset.mem_biUnion.mpr ⟨T i,hi,hfm i⟩ have hdis : Disjoint P (Finset.univ.image T) := by apply Finset.disjoint_left.mpr intro q hq hqim obtain ⟨i,_,rfl⟩ := Finset.mem_image.mp hqim exact hnotP i hq have hcard : (P ∪ Finset.univ.image T).card = P.card + Fintype.card ι := by rw [Finset.card_union_of_disjoint hdis, Finset.card_image_of_injective _ hTin, Finset.card_univ] refine ⟨hcard, ?_⟩ intro q hq r hr hqr simp only [Finset.mem_coe, Finset.mem_union] at hq hr rcases hq with hq | hq <;> rcases hr with hr | hr · exact hP hq hr hqr · obtain ⟨j,_,rfl⟩ := Finset.mem_image.mp hr have hs : q ∩ T j ⊆ S := by intro v hv obtain ⟨hvq,hvt⟩ := Finset.mem_inter.mp hv by_contra hvs have hvf := hout_iff j v hvt hvs apply hfresh j exact Finset.mem_biUnion.mpr ⟨q,hq,hvf ▸ hvq⟩ have heq : (q ∩ T j) ∩ S = q ∩ T j := Finset.inter_eq_left.mpr hs simpa [heq] using hbetween q hq j · obtain ⟨i,_,rfl⟩ := Finset.mem_image.mp hq have hs : r ∩ T i ⊆ S := by intro v hv obtain ⟨hvr,hvt⟩ := Finset.mem_inter.mp hv by_contra hvs have hvf := hout_iff i v hvt hvs apply hfresh i exact Finset.mem_biUnion.mpr ⟨r,hr,hvf ▸ hvr⟩ have heq : (r ∩ T i) ∩ S = r ∩ T i := Finset.inter_eq_left.mpr hs have hh : (r ∩ T i).card ≤ 1 := by simpa [heq] using hbetween r hr i simpa [Finset.inter_comm] using hh · obtain ⟨i,_,rfl⟩ := Finset.mem_image.mp hq obtain ⟨j,_,rfl⟩ := Finset.mem_image.mp hr have hij : i ≠ j := fun h => hqr (by rw [h]) have hs : T i ∩ T j ⊆ S := by intro v hv obtain ⟨hvi,hvj⟩ := Finset.mem_inter.mp hv by_contra hvs have hi := hout_iff i v hvi hvs have hj := hout_iff j v hvj hvs exact hij (hfinj (hi.symm.trans hj)) have heq : (T i ∩ T j) ∩ S = T i ∩ T j := Finset.inter_eq_left.mpr hs simpa [heq] using hwithin i j hij