Proper-parent face inequality (14): (Erdős 624)
ProvedErdos624.certificate_face_boundcombinatoricserdos-problems
Let be a set of inputs, a finite set of colours with , arbitrary and ; let be finite and . Let . For each fix a deletion set and a parity certificate for the proper minimal witnesses of surviving the deletion: for every with , and for all , we have . Put . For a -set let , , and . Then for every -set ,
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.
Preamble
import Mathlib open Finset
Formal statement
namespace Erdos624
theorem certificate_face_bound {U : Type*} [DecidableEq U] {C : Type*} [Fintype C] [DecidableEq C]
(k : ℕ) (g0 g1 : Finset U → C) (V : Finset U) (S : Finset C)
(hS : ∀ u ∈ S, u ∉ ({g0 ∅, g1 ∅} : Finset C))
(R : C → Finset U) (w : C → U → ZMod 2)
(hw : ∀ u ∈ S, ∀ A ⊆ V \ R u, 0 < #A → #A < k → u ∈ ({g0 A, g1 A} : Finset C) →
(∀ B ⊂ A, u ∉ ({g0 B, g1 B} : Finset C)) → ∑ x ∈ A, w u x = 1)
(Y : Finset U) (hYV : Y ⊆ V) (hY : #Y = k) :
Fintype.card C - #((Y.powerset.filter (fun A => A ≠ Y ∧ #A % 2 = 1)).biUnion
(fun A => ({g0 A, g1 A} : Finset C))) ≤
(Fintype.card C - #((Y.powerset.filter (fun A => A ≠ Y)).biUnion
(fun A => ({g0 A, g1 A} : Finset C)))) + (Fintype.card C - #S) +
#(S.filter (fun u => ¬ Disjoint Y (R u ∪ (V \ R u).filter (fun x => w u x = 0)))) := by sorry
end Erdos624
Source
Erdős Problem 624 (https://www.erdosproblems.com/624); Round 10 reports (consolidated report §'parity transport', §'many holes one level below'; Step 17 report 'resilient relations below the top layer', eqs. (9)-(26)); derived from GPT 6.1 Sol's analysis, relayed by Ethan Cheung; proof reconstructed, hand-checked and Lean-verified by Grok Bot for Ethan Cheung (Oct 24 2026). Auxiliary result only; does NOT settle PAIR / Step 17 / #624.