Top-layer-free resilience (1): for covering pairs (Erdős 624)
ProvedErdos624.top_layer_free_resilienceThroughout, is a finite set of inputs, a finite set of colours with , and are two arbitrary maps (a pair); write for the list of colours at the input . Here also . For a pool with and a colour , the proper minimal witnesses of in are the sets with , and for every ; the family is affine-coherent if some has on every member. Let be the least , , such that the proper minimal witnesses of in are affine-coherent.
Theorem. Let , , and suppose the pair covers every -subset of : for each and each colour there is with . Then there is a set of colours with such that every satisfies and , i.e. for every with the proper minimal witnesses of in admit no certificate. Equivalently
(For the size hypothesis holds for all .)
Context: Erdős Problem 624 asks whether , where is the least such that some with satisfies for all . By an earlier track-amplification result it suffices to find common holes for fixed numbers of tracks; this is an auxiliary finite inequality from Sol's Round 10 analysis of the two-track case. It does not settle Erdős Problem 624, PAIR or Step 17.
import Mathlib open Finset
namespace Erdos624
theorem top_layer_free_resilience {U : Type*} [Fintype U] [DecidableEq U]
{C : Type*} [Fintype C] [DecidableEq C] (k : ℕ) (hk : 3 ≤ k)
(hU : Fintype.card U = 2 ^ k) (hC : Fintype.card C = 2 ^ k) (g0 g1 : Finset U → C)
(V : Finset U) (hV : 2 ^ 28 * k ^ 4 ≤ #V)
(hcov : ∀ Y ∈ powersetCard k V, ∀ 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 ⊆ 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 := by sorry
end Erdos624