finite_maximum_packing_conflicts_satisfy_hall
Given a maximum packing P and any packing W of a finite set family, every subpacking X of W meets at least |X| members of P. Thus the bipartite intersection graph from W to P satisfies the matching condition.
Statement
theorem finite_maximum_packing_conflicts_satisfy_hall {α : Type*} [DecidableEq α] (F P W : Finset (Finset α)) (hnonempty : ∀ t ∈ F, t.Nonempty) (hPF : P ⊆ F) (hWF : W ⊆ F) (hPdis : (P : Set (Finset α)).Pairwise Disjoint) (hWdis : (W : Set (Finset α)).Pairwise Disjoint) (hmax : ∀ Q : Finset (Finset α), Q ⊆ F → (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card) : ∀ X : Finset (Finset α), X ⊆ W → X.card ≤ (P.filter fun s => ¬ Disjoint s (X.biUnion id)).card
- Source
- Elementary packing exchange and matching condition; related to the packing definitions in arXiv:2610.15539, Section 1.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- finite_maximum_packing_private_witnesses_intersectIn a finite set family with nonempty members, if P is a maximum pairwise-disjoint packing and two family members each avoid every member…
The proof, explained
To verify Hall's marriage condition for any subpacking X ⊆ W, we partition the maximum packing P into the subfamily P₀ of sets disjoint from ⋃ X and the neighborhood N of sets intersecting ⋃ X. The combined family P₀ ∪ X is shown to be a valid packing in F because P₀ and X are internally disjoint and cross-disjoint, and they share no common elements since all sets in F are nonempty. By the maximality of P, |P₀| + |X| = |P₀ ∪ X| ≤ |P| = |P₀| + |N|, which after cancelling |P₀| gives |X| ≤ |N|.
For any subpacking X ⊆ W, partitioning P into sets disjoint from and intersecting ⋃ X yields a candidate family P₀ ∪ X ⊆ F.
We fix an arbitrary subpacking X ⊆ W and partition P into P₀ (the elements of P disjoint from ⋃ X) and N (the elements intersecting ⋃ X). Since P ⊆ F and W ⊆ F, both P₀ and X are subfamilies of F, and therefore their union P₀ ∪ X is also contained in F.
uses
filter_subset,union_subsetopen Finset in intro X hXW let p := fun s : Finset α => Disjoint s (X.biUnion id) let P0 := P.filter p let N := P.filter (fun s => ¬ p s) have hP0F : P0 ⊆ F := (filter_subset p P).trans hPF have hXF : X ⊆ F := hXW.trans hWF have hQF : P0 ∪ X ⊆ F := union_subset hP0F hXF
The subfamilies P₀ and X are disjoint (P₀ ∩ X = ∅).
Suppose for contradiction that some set t belongs to both P₀ and X. By membership in P₀, t is disjoint from the union ⋃ X. By membership in X, t is a subset of ⋃ X. Being disjoint from a superset of itself implies that t is disjoint from itself, so t = ∅. But t ∈ X ⊆ F, and every member of F is assumed to be nonempty, a contradiction.
uses
disjoint_left,subset_biUnion_of_mem,Disjoint.mono_right,disjoint_self.mphave hdisj : Disjoint P0 X := by rw [disjoint_left] intro t htP0 htX have h1 : Disjoint t (X.biUnion id) := (mem_filter.mp htP0).2 have h2 : t ⊆ X.biUnion id := subset_biUnion_of_mem id htX have h3 : Disjoint t t := Disjoint.mono_right h2 h1 have h4 : t = ∅ := disjoint_self.mp h3 have h5 : t ∈ F := hXF htX have h6 : t.Nonempty := hnonempty t h5 exact h6.ne_empty h4
Every set in P₀ is disjoint from every set in X.
Given any a ∈ P₀ and b ∈ X, a is disjoint from the union ⋃ X by definition of P₀. Since b ⊆ ⋃ X, monotonicity of disjointness implies that a and b are disjoint.
uses
subset_biUnion_of_mem,Disjoint.mono_righthave hcross : ∀ a ∈ P0, ∀ b ∈ X, Disjoint a b := by intro a ha b hb have ha' : Disjoint a (X.biUnion id) := (mem_filter.mp ha).2 exact Disjoint.mono_right (subset_biUnion_of_mem id hb) ha'
The family P₀ ∪ X is a packing of pairwise disjoint sets.
Because P₀ ⊆ P and X ⊆ W, each subfamily consists of pairwise disjoint sets. For any two distinct members a, b ∈ P₀ ∪ X, if both belong to P₀ or both belong to X, they are disjoint by hypothesis; if one belongs to P₀ and the other to X, they are disjoint by the cross-disjointness established in the previous step.
uses
Set.Pairwise.mono,mem_coe,mem_unionhave hP0_pair : (P0 : Set (Finset α)).Pairwise Disjoint := Set.Pairwise.mono (coe_subset.mpr (filter_subset p P)) hPdis have hX_pair : (X : Set (Finset α)).Pairwise Disjoint := Set.Pairwise.mono (coe_subset.mpr hXW) hWdis have hQ_pair : ((P0 ∪ X : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by intro a ha b hb hab rw [mem_coe, mem_union] at ha hb rcases ha with ha | ha <;> rcases hb with hb | hb · exact hP0_pair ha hb hab · exact hcross a ha b hb · exact (hcross b hb a ha).symm · exact hX_pair ha hb hab
The size of X is at most the number of sets in P that intersect ⋃ X.
Since P₀ and X are disjoint families, the cardinality of their union is |P₀| + |X|. Because P₀ ∪ X is a packing in F and P is a maximum packing, |P₀| + |X| ≤ |P|. Since P is partitioned into P₀ and N, we also have |P| = |P₀| + |N|. Substituting this into the inequality gives |P₀| + |X| ≤ |P₀| + |N|, and cancelling |P₀| yields |X| ≤ |N|.
uses
card_union_of_disjoint,card_filter_add_card_filter_not,Nat.le_of_add_le_add_lefthave hQ_card : (P0 ∪ X).card = P0.card + X.card := card_union_of_disjoint hdisj have hle : (P0 ∪ X).card ≤ P.card := hmax (P0 ∪ X) hQF hQ_pair have hP_split : P0.card + N.card = P.card := by have := @card_filter_add_card_filter_not (Finset α) P p _ _ exact this rw [hQ_card] at hle rw [← hP_split] at hle exact Nat.le_of_add_le_add_left hle
filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
union_subset- If two finite sets are both subsets of a third set, their union is also a subset of that set.
disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
subset_biUnion_of_mem- For any element x of a finite set s, the set u(x) is a subset of the union of all u(y) for y ∈ s.
Disjoint.mono_right- If a is disjoint from c and b is a subset of c, then a is disjoint from b.
disjoint_self.mp- A set disjoint from itself is empty.
Set.Pairwise.mono- A relation that holds pairwise on a set also holds pairwise on any subset.
mem_coe- An element belongs to a finite set viewed as a set if and only if it belongs to the finite set.
mem_union- An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_filter_add_card_filter_not- The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the total cardinality of the set.
Nat.le_of_add_le_add_left- For natural numbers, a + b ≤ a + c implies b ≤ c.
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.
theorem finite_maximum_packing_conflicts_satisfy_hall {α : Type*} [DecidableEq α] (F P W : Finset (Finset α)) (hnonempty : ∀ t ∈ F, t.Nonempty) (hPF : P ⊆ F) (hWF : W ⊆ F) (hPdis : (P : Set (Finset α)).Pairwise Disjoint) (hWdis : (W : Set (Finset α)).Pairwise Disjoint) (hmax : ∀ Q : Finset (Finset α), Q ⊆ F → (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card) : ∀ X : Finset (Finset α), X ⊆ W → X.card ≤ (P.filter fun s => ¬ Disjoint s (X.biUnion id)).card := by open Finset in intro X hXW let p := fun s : Finset α => Disjoint s (X.biUnion id) let P0 := P.filter p let N := P.filter (fun s => ¬ p s) have hP0F : P0 ⊆ F := (filter_subset p P).trans hPF have hXF : X ⊆ F := hXW.trans hWF have hQF : P0 ∪ X ⊆ F := union_subset hP0F hXF have hdisj : Disjoint P0 X := by rw [disjoint_left] intro t htP0 htX have h1 : Disjoint t (X.biUnion id) := (mem_filter.mp htP0).2 have h2 : t ⊆ X.biUnion id := subset_biUnion_of_mem id htX have h3 : Disjoint t t := Disjoint.mono_right h2 h1 have h4 : t = ∅ := disjoint_self.mp h3 have h5 : t ∈ F := hXF htX have h6 : t.Nonempty := hnonempty t h5 exact h6.ne_empty h4 have hcross : ∀ a ∈ P0, ∀ b ∈ X, Disjoint a b := by intro a ha b hb have ha' : Disjoint a (X.biUnion id) := (mem_filter.mp ha).2 exact Disjoint.mono_right (subset_biUnion_of_mem id hb) ha' have hP0_pair : (P0 : Set (Finset α)).Pairwise Disjoint := Set.Pairwise.mono (coe_subset.mpr (filter_subset p P)) hPdis have hX_pair : (X : Set (Finset α)).Pairwise Disjoint := Set.Pairwise.mono (coe_subset.mpr hXW) hWdis have hQ_pair : ((P0 ∪ X : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by intro a ha b hb hab rw [mem_coe, mem_union] at ha hb rcases ha with ha | ha <;> rcases hb with hb | hb · exact hP0_pair ha hb hab · exact hcross a ha b hb · exact (hcross b hb a ha).symm · exact hX_pair ha hb hab have hQ_card : (P0 ∪ X).card = P0.card + X.card := card_union_of_disjoint hdisj have hle : (P0 ∪ X).card ≤ P.card := hmax (P0 ∪ X) hQF hQ_pair have hP_split : P0.card + N.card = P.card := by have := @card_filter_add_card_filter_not (Finset α) P p _ _ exact this rw [hQ_card] at hle rw [← hP_split] at hle exact Nat.le_of_add_le_add_left hle