wild_two_matchings_six_closed_family_bound
A finite family F of six-element subsets of U, closed under two involutions whose actions on each member are fixed-point-free and distinct at every vertex, satisfies 6*card(F)<=card(U). This follows from pairwise disjointness and finite union cardinality.
Statement
theorem wild_two_matchings_six_closed_family_bound {α : Type*} [DecidableEq α] (f g : α → α) (hf : Function.Involutive f) (hg : Function.Involutive g) (F : Finset (Finset α)) (U : Finset α) (hsize : ∀ S ∈ F, S.card = 6) (hsub : ∀ S ∈ F, S ⊆ U) (hc : ∀ S ∈ F, ∀ x ∈ S, f x ∈ S ∧ g x ∈ S) (hn : ∀ S ∈ F, ∀ x ∈ S, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) : 6 * F.card ≤ U.card
- Source
- IN-374 / OP-306, dependence estimates for the weighted partition route to https://arxiv.org/html/2610.22142v1. Elementary matching support consequence of the standard even-cycle decomposition of two disjoint perfect matchings; matching background https://dspacemainprd01.lib.uwaterloo.ca/server/api/core/bitstreams/9d33772f-c7dc-409f-a4ed-521da8d87890/content . Exact experiment9362 audits six saved15 arrays and cyclic9,13,21,27,39,61. No new wild-number bound, sharpness case or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- wild_two_matchings_small_closed_sets_disjoint_or_equalFor two involutions on a decidable type, finite sets S,T of cardinality at most7 that are closed under both maps are disjoint or equal,…
- Used by 1
- wild_normalized_array_common_six_seals_boundFor a symmetric idempotent row-injective array A on Fin n and two distinct colors a,b, let F consist of six-element sets S excluding a,b…
The proof, explained
The proof shows that any two distinct six-element sets in the family F must be disjoint, using an auxiliary theorem that classifies two small closed sets under fixed-point-free involutions as either disjoint or equal. Because F is pairwise disjoint and each of its members has six elements, the union of all sets in F contains exactly 6 * |F| elements. Since each set is contained in U, their union is also a subset of U, which implies 6 * |F| ≤ |U|.
The family F is pairwise disjoint.
Let S and T be any two distinct sets in F. Both have cardinality 6 ≤ 7 and are closed under f and g. Furthermore, every element x in S ∪ T lies in S or in T (by mem_union.mp), so f and g have no fixed points and do not coincide on S ∪ T. Applying wild_two_matchings_small_closed_sets_disjoint_or_equal shows that S and T are disjoint or identical; since S ≠ T, they must be disjoint.
uses
wild_two_matchings_small_closed_sets_disjoint_or_equal,mem_union.mphave hd : (F : Set (Finset α)).PairwiseDisjoint id := by intro S hS T hT hne have h := wild_two_matchings_small_closed_sets_disjoint_or_equal f g hf hg S T (by rw [hsize S hS]; omega) (by rw [hsize T hT]; omega) (hc S hS) (hc T hT) (by intro x hx rcases mem_union.mp hx with hx | hx · exact hn S hS x hx · exact hn T hT x hx) exact h.resolve_right hne
The union of all sets in F has cardinality 6 * |F|.
Because the sets in F are pairwise disjoint, Finset.card_biUnion equates the cardinality of the union to the sum of the cardinalities of the individual sets. Simplifying the identity mapping with id_eq gives ∑_{S ∈ F} |S|. Since every S ∈ F has cardinality 6, this sum evaluates by Finset.sum_const_nat to |F| * 6, which equals 6 * |F| by Nat.mul_comm.
uses
Finset.card_biUnion,id_eq,Finset.sum_const_nat,Nat.mul_commhave hcard : (F.biUnion id).card = 6 * F.card := by rw [Finset.card_biUnion hd] simp only [id_eq] rw [Finset.sum_const_nat hsize, Nat.mul_comm]
6 * |F| ≤ |U|.
Rewriting 6 * |F| as the cardinality of the union ⋃_{S ∈ F} S, it suffices by Finset.card_le_card to show this union is a subset of U. Any element x in the union belongs to some S ∈ F (by Finset.mem_biUnion.mp), and since every S ∈ F is a subset of U, x belongs to U.
uses
Finset.card_le_card,Finset.mem_biUnion.mprw [← hcard] apply Finset.card_le_card intro x hx obtain ⟨S, hS, hxS⟩ := Finset.mem_biUnion.mp hx exact hsub S hS hxS
wild_two_matchings_small_closed_sets_disjoint_or_equal- Two sets of cardinality at most 7 that are closed under two involutions f and g, where both involutions have no fixed points and are distinct at every point of the union, are either disjoint or identical.
mem_union.mp- If an element belongs to the union S ∪ T, then it belongs to S or to T.
Finset.card_biUnion- The cardinality of a pairwise disjoint union of finite sets is the sum of the cardinalities of the individual sets.
id_eq- The identity function applied to any element yields that element: id(a) = a.
Finset.sum_const_nat- The sum of a constant natural number c over a finite set s is equal to |s| * c.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.mem_biUnion.mp- If an element belongs to a indexed union ⋃_{a ∈ s} t(a), then it belongs to t(a) for some a ∈ s.
- The hypothesis that the sets have size at most 7, required by `wild_two_matchings_small_closed_sets_disjoint_or_equal`, is satisfied by the assumption that each member of F has size 6, verified via the integer arithmetic tactic `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 Finsettheorem wild_two_matchings_six_closed_family_bound {α : Type*} [DecidableEq α] (f g : α → α) (hf : Function.Involutive f) (hg : Function.Involutive g) (F : Finset (Finset α)) (U : Finset α) (hsize : ∀ S ∈ F, S.card = 6) (hsub : ∀ S ∈ F, S ⊆ U) (hc : ∀ S ∈ F, ∀ x ∈ S, f x ∈ S ∧ g x ∈ S) (hn : ∀ S ∈ F, ∀ x ∈ S, f x ≠ x ∧ g x ≠ x ∧ f x ≠ g x) : 6 * F.card ≤ U.card := by have hd : (F : Set (Finset α)).PairwiseDisjoint id := by intro S hS T hT hne have h := wild_two_matchings_small_closed_sets_disjoint_or_equal f g hf hg S T (by rw [hsize S hS]; omega) (by rw [hsize T hT]; omega) (hc S hS) (hc T hT) (by intro x hx rcases mem_union.mp hx with hx | hx · exact hn S hS x hx · exact hn T hT x hx) exact h.resolve_right hne have hcard : (F.biUnion id).card = 6 * F.card := by rw [Finset.card_biUnion hd] simp only [id_eq] rw [Finset.sum_const_nat hsize, Nat.mul_comm] rw [← hcard] apply Finset.card_le_card intro x hx obtain ⟨S, hS, hxS⟩ := Finset.mem_biUnion.mp hx exact hsub S hS hxS