Resilience forces large disjoint packings of violating proper witnesses: (29) (Erdős 624)
ProvedErdos624.resilient_packing_boundLet be a finite set, a finite set of colours, , , with , and . The proper minimal witnesses of a colour inside are the with , and for all ; a certificate is with on every such . Assume is resilient: for every with , the proper minimal witnesses of in admit no certificate. Then for every form there is a family of pairwise disjoint proper minimal witnesses of with and
(Here is truncated natural-number subtraction; no lower bound on is needed.)
Context: Erdős Problem 624 asks whether , where is the least such that some with satisfies for all . This is an auxiliary finite statement from Sol's Round 12 Step 17 cross-review / resilience analysis of the two-track (PAIR) case. It does not settle Erdős Problem 624, PAIR or Step 17.
import Mathlib open Finset
namespace Erdos624
theorem resilient_packing_bound {U : Type*} [Fintype U] [DecidableEq U]
{C : Type*} [Fintype C] [DecidableEq C] (k : ℕ) (g0 g1 : Finset U → C) (V : Finset U) (u : C)
(hres : ∀ R ⊆ V, 256 * k * #R ≤ #V → ¬ ∃ w : U → ZMod 2, ∀ A ⊆ V \ R, 0 < #A → #A < k →
u ∈ ({g0 A, g1 A} : Finset C) → (∀ B ⊂ A, u ∉ ({g0 B, g1 B} : Finset C)) →
∑ x ∈ A, w x = 1)
(w : U → ZMod 2) :
∃ P : Finset (Finset U),
(∀ A ∈ P, A ⊆ V ∧ 0 < #A ∧ #A < k ∧ u ∈ ({g0 A, g1 A} : Finset C) ∧
(∀ B ⊂ A, u ∉ ({g0 B, g1 B} : Finset C)) ∧ ∑ x ∈ A, w x = 0) ∧
(∀ A ∈ P, ∀ B ∈ P, A ≠ B → Disjoint A B) ∧
#V < 256 * k * (k - 1) * #P := by sorry
end Erdos624