Top-layer-free packing (29): colours with for every form (Erdős 624)
ProvedErdos624.top_layer_free_packingThroughout, 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 , with , and suppose the pair covers every -subset of . Then there is a set of colours with , all outside , such that for every and every form (chosen independently per colour) there is a family of pairwise disjoint proper minimal witnesses of , each with , and .
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_packing {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) ∧
∀ 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