Top-layer-free resilience on the full domain, (Erdős 624)
ProvedErdos624.top_layer_free_resilience_full_domainThroughout, is a finite set of inputs, a finite set of colours with , and two arbitrary maps; . Here . The proper minimal witnesses of a colour inside are the with , and for all ; a certificate is with on every such . Theorem. Let and suppose the pair covers every -subset of . Then there is a set of colours with such that each lies outside and, for every with , the proper minimal witnesses of disjoint from admit no certificate (i.e. ).
Sol states the threshold ; the exact threshold for the needed inequality is (it fails at ), which is what is proved here.
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 top_layer_free_resilience_full_domain {U : Type*} [Fintype U] [DecidableEq U]
{C : Type*} [Fintype C] [DecidableEq C] (k : ℕ) (hk : 51 ≤ k) (hU : Fintype.card U = 2 ^ k)
(hC : Fintype.card C = 2 ^ k) (g0 g1 : Finset U → C)
(hcov : ∀ Y : Finset U, #Y = k → ∀ u : C, ∃ A ⊆ Y, u ∈ ({g0 A, g1 A} : Finset C)) :
∃ H : Finset C, 2 ^ k ≤ 64 * #H ∧ ∀ u ∈ H, u ∉ ({g0 ∅, g1 ∅} : Finset C) ∧
∀ R : Finset U, 256 * k * #R ≤ 2 ^ k → ¬ ∃ w : U → ZMod 2, ∀ A : Finset U, Disjoint A 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 := by sorry
end Erdos624