canonical_permutation_avoidance_of_local_lemma
For finitely many injective partial assignments on n points, if weights in [0,1) satisfy the asymmetric local-lemma inequalities for the graph connecting assignments with overlapping domains or ranges, some permutation avoids every assignment.
Statement
theorem canonical_permutation_avoidance_of_local_lemma {I : Type*} [Fintype I] [DecidableEq I] (n : ℕ) (hn : 0 < n) (D : I → Finset (Fin n)) (f : I → Fin n → Fin n) (hD : ∀ i, (D i).Nonempty) (hf : ∀ i, Set.InjOn (f i) (↑(D i) : Set (Fin n))) (x : I → ℝ) (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1) (hprob : ∀ i, (1 : ℝ) / (n.descFactorial (D i).card : ℝ) ≤ x i * ∏ j ∈ Finset.univ.filter (fun j => j ≠ i ∧ (¬ Disjoint (D i) (D j) ∨ ¬ Disjoint ((D i).image (f i)) ((D j).image (f j)))), (1 - x j)) : ∃ σ : Equiv.Perm (Fin n), ∀ i, ∃ v ∈ D i, σ v ≠ f i v
- Formalizes
- Using Lovász Local Lemma in the Space of Random Injections, Electronic Journal of Combinatorics 14 (2007), R63, DOI 10.37236/981, Theorem 1 and Lemma 3. Specialization to permutations of Fin n and the domain/range-intersection supergraph of the canonical conflict graph; this is a statement only, not an imported proof.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- canonical_permutation_negative_dependency_card_boundFor canonical permutation events with disjoint domains and ranges from a fixed injective partial assignment, multiplying the avoiding…
- finite_lopsided_avoidance_of_card_boundIn a nonempty finite probability universe, finite bad events satisfying the negative-dependency cardinality inequalities and asymmetric…
- Used by 3
- wild_partition_of_resource_boundsLet n>0 and let a proper coloring of K_n use the color set Fin n. Fix a partition map b from the vertices onto q blocks, with a specified…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_triple_partition_mass_criterionFor an odd number q of triple blocks, q>=3, a proper edge coloring of K_(3q) with 3q colors and a bijection between colors and their…
The proof, explained
The proof applies the counting version of the asymmetric lopsided Lovász Local Lemma (`finite_lopsided_avoidance_of_card_bound`) to the uniform measure on permutations of n points. For each partial assignment, the bad event A_i consists of permutations that agree with the assignment on its entire domain. The key move is using negative dependency (`canonical_permutation_negative_dependency_card_bound`) to show that conditioning on avoiding non-interfering assignments leaves the conditional probability of A_i bounded by 1 / n^{\underline{|D_i|}}. The asymmetric local lemma conditions then guarantee the existence of a permutation avoiding all bad events simultaneously.
Define the bad sets of permutations A_i and the dependency neighborhoods N_i.
For each index i, let A_i be the set of permutations σ of Fin n that agree with f_i on all points of D_i. Define N(i) to be the set of indices j ≠ i whose domain or range intersects that of i, that is, D_i ∩ D_j ≠ ∅ or f_i(D_i) ∩ f_j(D_j) ≠ ∅.
classical let A : I → Finset (Equiv.Perm (Fin n)) := fun i => Finset.univ.filter (fun σ => ∀ v ∈ D i, σ v = f i v) let N : I → Finset I := fun i => Finset.univ.filter (fun j => j ≠ i ∧ (¬ Disjoint (D i) (D j) ∨ ¬ Disjoint ((D i).image (f i)) ((D j).image (f j))))
A permutation avoids the i-th partial assignment if and only if it does not belong to A_i.
A permutation σ belongs to A_i if and only if σ v = f_i v for all v ∈ D_i. Negating this universal quantification using `not_forall` shows that σ ∉ A_i is equivalent to the existence of some v ∈ D_i such that σ v ≠ f_i v.
uses
not_forallhave hmem : ∀ σ i, σ ∉ A i ↔ ∃ v ∈ D i, σ v ≠ f i v := by intro σ i simp [A, not_forall]
For any index i and any subset S disjoint from N(i) with i ∉ S, every j ∈ S has domain and range disjoint from those of i.
Assume i ∉ S and S is disjoint from N(i). For any j ∈ S, j cannot belong to N(i). Because j ≠ i, the condition defining N(i) implies that neither the domains nor the ranges of i and j can overlap, so D_i is disjoint from D_j and f_i(D_i) is disjoint from f_j(D_j).
uses
Finset.disjoint_left.mp,Finset.mem_filter.mpr,Finset.mem_univhave hdep : ∀ i (S : Finset I), i ∉ S → Disjoint S (N i) → ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤ (1 : ℝ) / (n.descFactorial (D i).card : ℝ) * ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by intro i S hi hd have hnon : ∀ j ∈ S, Disjoint (D i) (D j) ∧ Disjoint ((D i).image (f i)) ((D j).image (f j)) := by intro j hj have hjN : j ∉ N i := fun h => Finset.disjoint_left.mp hd hj h have hji : j ≠ i := fun h => hi (h ▸ hj) have hh : ¬ (¬ Disjoint (D i) (D j) ∨ ¬ Disjoint ((D i).image (f i)) ((D j).image (f j))) := by intro h exact hjN (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hji, h⟩) tauto
The number of permutations extending f_i while avoiding all assignments in S, scaled by the falling factorial n^{\underline{|D_i|}}, is bounded by the total number of permutations avoiding S.
Because assignment i has domain and range disjoint from every assignment in S, the negative dependency lemma `canonical_permutation_negative_dependency_card_bound` applies. Rewriting and simplifying the set membership conditions shows that the intersection A_i ∩ {σ | ∀ j ∈ S, σ ∉ A_j} corresponds precisely to permutations avoiding S that agree with f_i on D_i, establishing n^{\underline{|D_i|}} * |A_i ∩ ⋂_{j ∈ S} A_jᶜ| ≤ |⋂_{j ∈ S} A_jᶜ|.
uses
canonical_permutation_negative_dependency_card_bound,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_inter,not_forall,_root_.not_imp,exists_prophave hc := canonical_permutation_negative_dependency_card_bound (D i) (f i) (hf i) S D f (fun j hj => (hnon j hj).1) (fun j hj => (hnon j hj).2) have hc0 : n.descFactorial (D i).card * (A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card ≤ (Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card := by convert hc using 1 · congr 1 · simp · congr 1 ext σ simp only [A, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_inter, not_forall, _root_.not_imp, exists_prop] tauto · congr 1 ext σ simp only [Finset.mem_filter, Finset.mem_univ, true_and, hmem]
The conditional avoidance bound required by the lopsided local lemma holds: |A_i ∩ ⋂_{j ∈ S} A_jᶜ| ≤ (1 / n^{\underline{|D_i|}}) * |⋂_{j ∈ S} A_jᶜ|.
Since D_i is a subset of Fin n, its cardinality is at most n, which implies by `Nat.descFactorial_pos.mpr` that the falling factorial n^{\underline{|D_i|}} is strictly positive. Casting the cardinality inequality to the reals and dividing by n^{\underline{|D_i|}} gives the required conditional bound for the lopsided local lemma.
uses
Nat.descFactorial_pos.mpr,Finset.card_le_univ,le_div_iff₀,mul_comm,div_eq_mul_inv,one_mul,mul_onehave hdpos : 0 < (n.descFactorial (D i).card : ℝ) := by exact_mod_cast Nat.descFactorial_pos.mpr (show (D i).card ≤ n by simpa using Finset.card_le_univ (D i)) have hc' : (n.descFactorial (D i).card : ℝ) * ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤ ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by exact_mod_cast hc0 have hdiv : ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤ ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) / (n.descFactorial (D i).card : ℝ) := (le_div_iff₀ hdpos).mpr (by simpa [mul_comm] using hc') simpa only [div_eq_mul_inv, one_mul, mul_one, mul_comm] using hdiv
There exists a permutation σ avoiding all bad sets A_i.
We invoke `finite_lopsided_avoidance_of_card_bound` on the sample space of permutations of Fin n, the bad events A_i, and the dependency graph N_i, using upper bounds p_i = 1 / n^{\underline{|D_i|}}. The conditional upper bound `hdep` and the hypothesis `hprob` satisfy the asymmetric local-lemma inequalities, yielding a permutation σ with σ ∉ A_i for all i.
uses
finite_lopsided_avoidance_of_card_boundobtain ⟨σ, hσ⟩ := finite_lopsided_avoidance_of_card_bound A N (fun i => (1 : ℝ) / (n.descFactorial (D i).card : ℝ)) x hx0 hx1 hdep hprob
The permutation σ avoids every partial assignment f_i on D_i.
Using the equivalence proved earlier (σ ∉ A_i ↔ ∃ v ∈ D_i, σ v ≠ f_i v), the fact that σ avoids every A_i means that for every i, there is some v ∈ D_i such that σ v ≠ f_i v.
exact ⟨σ, fun i => (hmem σ i).mp (hσ i)⟩
finite_lopsided_avoidance_of_card_bound- The finite lopsided Lovász Local Lemma: given bad subsets A_i of a finite set Ω with conditional upper bounds p_i outside their neighborhood graphs N(i) and weights x_i in [0, 1) satisfying p_i ≤ x_i ∏_{j ∈ N(i)} (1 - x_j), there exists an outcome in Ω avoiding all A_i.
canonical_permutation_negative_dependency_card_bound- If a partial injection on a finite set has domain and range disjoint from a family of partial injections, the number of permutations extending it while avoiding the family, times the falling factorial of the domain size, is at most the total number of permutations avoiding the family.
not_forall- Negating a universal statement is equivalent to an existential statement of the negation: (¬∀ x, P x) ↔ ∃ x, ¬P x.
_root_.not_imp- The negation of an implication ¬(a → b) is equivalent to a ∧ ¬b.
exists_prop- An existential quantifier over a proposition (∃ (_ : a), b) is equivalent to the conjunction a ∧ b.
Finset.disjoint_left.mp- If two sets are disjoint, any element of the first set is not in the second set.
Finset.mem_filter.mpr- An element belongs to a filtered finset if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
Finset.mem_inter- An element belongs to the intersection of two finsets if and only if it belongs to both.
true_and- The conjunction True ∧ p simplifies to p.
Nat.descFactorial_pos.mpr- The falling factorial n^{\underline{k}} is strictly positive whenever k ≤ n.
Finset.card_le_univ- The cardinality of any finset of a finite type is at most the total cardinality of the type.
le_div_iff₀- For positive c in a division structure, a ≤ b / c is equivalent to a * c ≤ b.
mul_comm- Multiplication is commutative: a * b = b * a.
div_eq_mul_inv- Division is multiplication by the reciprocal: a / b = a * b⁻¹.
one_mul- Multiplication by 1 on the left is the identity: 1 * a = a.
mul_one- Multiplication by 1 on the right is the identity: a * 1 = a.
- The proof uses a combinatorial (cardinality-based) formulation of the lopsided Lovász Local Lemma (`finite_lopsided_avoidance_of_card_bound`) rather than a measure-theoretic probability space, expressing conditional probabilities directly as ratios of set cardinalities.
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_avoidance_of_local_lemma {I : Type*} [Fintype I] [DecidableEq I] (n : ℕ) (hn : 0 < n) (D : I → Finset (Fin n)) (f : I → Fin n → Fin n) (hD : ∀ i, (D i).Nonempty) (hf : ∀ i, Set.InjOn (f i) (↑(D i) : Set (Fin n))) (x : I → ℝ) (hx0 : ∀ i, 0 ≤ x i) (hx1 : ∀ i, x i < 1) (hprob : ∀ i, (1 : ℝ) / (n.descFactorial (D i).card : ℝ) ≤ x i * ∏ j ∈ Finset.univ.filter (fun j => j ≠ i ∧ (¬ Disjoint (D i) (D j) ∨ ¬ Disjoint ((D i).image (f i)) ((D j).image (f j)))), (1 - x j)) : ∃ σ : Equiv.Perm (Fin n), ∀ i, ∃ v ∈ D i, σ v ≠ f i v := by classical let A : I → Finset (Equiv.Perm (Fin n)) := fun i => Finset.univ.filter (fun σ => ∀ v ∈ D i, σ v = f i v) let N : I → Finset I := fun i => Finset.univ.filter (fun j => j ≠ i ∧ (¬ Disjoint (D i) (D j) ∨ ¬ Disjoint ((D i).image (f i)) ((D j).image (f j)))) have hmem : ∀ σ i, σ ∉ A i ↔ ∃ v ∈ D i, σ v ≠ f i v := by intro σ i simp [A, not_forall] have hdep : ∀ i (S : Finset I), i ∉ S → Disjoint S (N i) → ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤ (1 : ℝ) / (n.descFactorial (D i).card : ℝ) * ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by intro i S hi hd have hnon : ∀ j ∈ S, Disjoint (D i) (D j) ∧ Disjoint ((D i).image (f i)) ((D j).image (f j)) := by intro j hj have hjN : j ∉ N i := fun h => Finset.disjoint_left.mp hd hj h have hji : j ≠ i := fun h => hi (h ▸ hj) have hh : ¬ (¬ Disjoint (D i) (D j) ∨ ¬ Disjoint ((D i).image (f i)) ((D j).image (f j))) := by intro h exact hjN (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hji, h⟩) tauto have hc := canonical_permutation_negative_dependency_card_bound (D i) (f i) (hf i) S D f (fun j hj => (hnon j hj).1) (fun j hj => (hnon j hj).2) have hc0 : n.descFactorial (D i).card * (A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card ≤ (Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card := by convert hc using 1 · congr 1 · simp · congr 1 ext σ simp only [A, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_inter, not_forall, _root_.not_imp, exists_prop] tauto · congr 1 ext σ simp only [Finset.mem_filter, Finset.mem_univ, true_and, hmem] have hdpos : 0 < (n.descFactorial (D i).card : ℝ) := by exact_mod_cast Nat.descFactorial_pos.mpr (show (D i).card ≤ n by simpa using Finset.card_le_univ (D i)) have hc' : (n.descFactorial (D i).card : ℝ) * ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤ ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) := by exact_mod_cast hc0 have hdiv : ((A i ∩ Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) ≤ ((Finset.univ.filter (fun σ => ∀ j ∈ S, σ ∉ A j)).card : ℝ) / (n.descFactorial (D i).card : ℝ) := (le_div_iff₀ hdpos).mpr (by simpa [mul_comm] using hc') simpa only [div_eq_mul_inv, one_mul, mul_one, mul_comm] using hdiv obtain ⟨σ, hσ⟩ := finite_lopsided_avoidance_of_card_bound A N (fun i => (1 : ℝ) / (n.descFactorial (D i).card : ℝ)) x hx0 hx1 hdep hprob exact ⟨σ, fun i => (hmem σ i).mp (hσ i)⟩