canonical_permutation_negative_dependency_card_bound
For canonical permutation events with disjoint domains and ranges from a fixed injective partial assignment, multiplying the avoiding permutations that extend it by the relevant falling factorial bounds them by all avoiding permutations.
Statement
theorem canonical_permutation_negative_dependency_card_bound {α I : Type*} [Fintype α] [DecidableEq α] (D : Finset α) (f : α → α) (hf : Set.InjOn f (↑D : Set α)) (T : Finset I) (C : I → Finset α) (g : I → α → α) (hdom : ∀ i ∈ T, Disjoint D (C i)) (hran : ∀ i ∈ T, Disjoint (D.image f) ((C i).image (g i))) : (Fintype.card α).descFactorial D.card * ((Finset.univ.filter (fun τ : Equiv.Perm α => ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).filter (fun τ => ∀ a ∈ D, τ a = f a)).card ≤ (Finset.univ.filter (fun τ : Equiv.Perm α => ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).card
- Source
- Negative-dependency counting helper for OP-306; EJC 14 (2007) R63, DOI 10.37236/981, Theorem 1, specialized to the domain/range-overlap supergraph.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- permutation_partial_assignment_card_bound_of_switchingIf a finite set of permutations is closed under undoing any one forced assignment by an image swap, its number extending an injective…
- Used by 1
- canonical_permutation_avoidance_of_local_lemmaFor finitely many injective partial assignments on n points, if weights in [0,1) satisfy the asymmetric local-lemma inequalities for the…
The proof, explained
The theorem is proved by invoking `permutation_partial_assignment_card_bound_of_switching`, which reduces the negative dependency bound to showing that the set of pattern-avoiding permutations is closed under transposition switching of the form τ ↦ (swap y (f a)) * τ. Assuming for contradiction that the switched permutation agrees with some pattern g i on C i, the disjointness of domains and ranges ensures that the witness v ∈ C i (where the original permutation differed from g i) is fixed by the transposition and satisfies g i v ≠ y. This forces the original permutation to agree with g i at v, yielding a contradiction.
The bound reduces to verifying that the set of pattern-avoiding permutations is closed under transposition switching.
By `permutation_partial_assignment_card_bound_of_switching`, multiplying the number of pattern-avoiding permutations that extend the injective partial assignment f on D by the falling factorial (|α|)_{|D|} is bounded by the total number of pattern-avoiding permutations, provided that for every a ∈ D, every avoiding permutation τ with τ a = f a, and every y ∈ α, the switched permutation (swap y (f a)) * τ is also pattern-avoiding.
uses
permutation_partial_assignment_card_bound_of_switchingclassical apply permutation_partial_assignment_card_bound_of_switching D f hfTo show the switched permutation τ' = (swap y (f a)) * τ is avoiding, it suffices to find for each index i ∈ T an element v ∈ C i where τ' v ≠ g i v.
Fix a ∈ D, an avoiding permutation τ with τ a = f a, and an element y ∈ α. To show that τ' belongs to the filtered finset of permutations avoiding all patterns, we introduce an arbitrary index i ∈ T and aim to show that τ' differs from g i on at least one element of C i.
uses
Finset.mem_filter.mpr,Finset.mem_univintro a ha τ hτ hτa y apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ intro i hi
Assuming for contradiction that τ' agrees with g i everywhere on C i, the original avoiding permutation τ still provides a witness v ∈ C i where τ v ≠ g i v.
Assume for contradiction that τ' u = g i u for all u ∈ C i. Because the original permutation τ is in the avoiding set, extracting the avoidance condition for index i provides a witness v ∈ C i such that τ v ≠ g i v.
uses
Finset.mem_filter.mpby_contra h push Not at h obtain ⟨v, hv, hτv⟩ := (Finset.mem_filter.mp hτ).2 i hi
The witness v is distinct from a, and its assigned value g i v is distinct from f a.
Because D and C i are disjoint (by `hdom`), the elements a ∈ D and v ∈ C i cannot be equal. Similarly, because the image sets f(D) and (g i)(C i) are disjoint (by `hran`), f a ∈ f(D) and g i v ∈ (g i)(C i) cannot be equal.
uses
Finset.disjoint_left.mp,Finset.mem_image.mprhave hva : v ≠ a := by intro heq exact Finset.disjoint_left.mp (hdom i hi) ha (heq ▸ hv) have hgfa : g i v ≠ f a := by intro heq exact Finset.disjoint_left.mp (hran i hi) (Finset.mem_image.mpr ⟨a, ha, rfl⟩) (Finset.mem_image.mpr ⟨v, hv, heq⟩)
The assigned value g i v is distinct from y.
First, τ' a = (swap y (f a)) (τ a) = (swap y (f a)) (f a) = y. If g i v = y, then the contradiction hypothesis gives τ' v = g i v = y = τ' a. Because τ' is an injective permutation, this would force v = a, contradicting v ≠ a.
uses
Equiv.Perm.mul_applyhave hsva : (Equiv.swap y (f a) * τ) a = y := by simp [Equiv.Perm.mul_apply, hτa] have hgy : g i v ≠ y := by intro heq apply hva exact (Equiv.swap y (f a) * τ).injective ((h v hv).trans (heq.trans hsva.symm))
Applying the transposition (swap y (f a)) to τ' v = g i v implies τ v = g i v, which contradicts τ v ≠ g i v.
Applying the swap (swap y (f a)) to both sides of the assumption τ' v = g i v, the left-hand side simplifies to (swap y (f a)) ((swap y (f a)) (τ v)) = τ v because transpositions are involutions. The right-hand side simplifies to g i v because g i v is distinct from both swap points y and f a. This yields τ v = g i v, contradicting τ v ≠ g i v and completing the proof.
uses
congrArg,Equiv.Perm.mul_apply,Equiv.swap_apply_self,Equiv.swap_apply_of_ne_of_neapply hτv have hh := congrArg (Equiv.swap y (f a)) (h v hv) simpa only [Equiv.Perm.mul_apply, Equiv.swap_apply_self, Equiv.swap_apply_of_ne_of_ne hgy hgfa] using hh
permutation_partial_assignment_card_bound_of_switching- If an injective partial assignment f on D and a set of permutations A satisfy the switching property that (swap y (f a)) * τ ∈ A whenever τ ∈ A has τ a = f a, then (|α|)_{|D|} * |{τ ∈ A | τ|_D = f}| ≤ |A|.
Finset.mem_filter.mpr- An element x belongs to {y ∈ s | p y} if x ∈ s and p x holds.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_filter.mp- If x belongs to {y ∈ s | p y}, then x ∈ s and p x holds.
Finset.disjoint_left.mp- If two finsets are disjoint, then any element belonging to the first does not belong to the second.
Finset.mem_image.mpr- An element y belongs to the image f(s) if there exists x ∈ s such that f x = y.
Equiv.Perm.mul_apply- Multiplication of permutations acts by function composition: (f * g) x = f (g x).
congrArg- Applying a function to equal arguments yields equal values: if a₁ = a₂, then f a₁ = f a₂.
Equiv.swap_apply_self- Applying the transposition (swap i j) twice to any element returns that element: (swap i j) ((swap i j) a) = a.
Equiv.swap_apply_of_ne_of_ne- The transposition (swap a b) fixes any element x distinct from both a and b: if x ≠ a and x ≠ b, then (swap a b) x = x.
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 canonical_permutation_negative_dependency_card_bound {α I : Type*} [Fintype α] [DecidableEq α] (D : Finset α) (f : α → α) (hf : Set.InjOn f (↑D : Set α)) (T : Finset I) (C : I → Finset α) (g : I → α → α) (hdom : ∀ i ∈ T, Disjoint D (C i)) (hran : ∀ i ∈ T, Disjoint (D.image f) ((C i).image (g i))) : (Fintype.card α).descFactorial D.card * ((Finset.univ.filter (fun τ : Equiv.Perm α => ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).filter (fun τ => ∀ a ∈ D, τ a = f a)).card ≤ (Finset.univ.filter (fun τ : Equiv.Perm α => ∀ i ∈ T, ∃ v ∈ C i, τ v ≠ g i v)).card := by classical apply permutation_partial_assignment_card_bound_of_switching D f hf intro a ha τ hτ hτa y apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ intro i hi by_contra h push Not at h obtain ⟨v, hv, hτv⟩ := (Finset.mem_filter.mp hτ).2 i hi have hva : v ≠ a := by intro heq exact Finset.disjoint_left.mp (hdom i hi) ha (heq ▸ hv) have hgfa : g i v ≠ f a := by intro heq exact Finset.disjoint_left.mp (hran i hi) (Finset.mem_image.mpr ⟨a, ha, rfl⟩) (Finset.mem_image.mpr ⟨v, hv, heq⟩) have hsva : (Equiv.swap y (f a) * τ) a = y := by simp [Equiv.Perm.mul_apply, hτa] have hgy : g i v ≠ y := by intro heq apply hva exact (Equiv.swap y (f a) * τ).injective ((h v hv).trans (heq.trans hsva.symm)) apply hτv have hh := congrArg (Equiv.swap y (f a)) (h v hv) simpa only [Equiv.Perm.mul_apply, Equiv.swap_apply_self, Equiv.swap_apply_of_ne_of_ne hgy hgfa] using hh