While this submission is a draft, it cannot be used by other submissions.

Proof of `A lower bound on the size of homomorphism witnesses`

groundedproofs/Lax119563Proofs/Witness/Main.lean · lax-119563

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

We apply the row-space compiler to the relay counter relaykℓrelay k ℓ (counting down through the 2m2^m addresses, m=(k−1)ℓm = (k-1)ℓ, with every decrement realized by a one-way gate), for ℓ=2n0k+k+3ℓ = 2 n₀^k + k + 3. Unit propagation reaches a conflict (relayhasConflictrelay_hasConflict), so Spoiler wins and kk-WL distinguishes the graphs. A weight argument shows that every contradiction tree has more than 2(2m−1)2^(2^m - 1) nodes (relaytreeboundrelay_tree_bound); with item 4 of the compiler this bounds every witness FF by 5∣V(F)∣+1>2(2m−1)5|V(F)| + 1 > 2^(2^m - 1). The size parameter is Ok(2ℓ)O_k(2^ℓ) (relaysizerelay_size), so the graphs have n=Ok(2ℓ)n = O_k(2^ℓ) vertices, giving the bound with C=5(Crs⋅sizeConstk+1)(k−1)C = 5 (C_rs · sizeConst k + 1)^(k-1). Finally n≥n0n ≥ n₀: the conflict round is at least 2m−22^m - 2, since a conflict in round ττ yields a contradiction tree with fewer than 2(τ+2)2^(τ+2) nodes; Duplicator survives until then, while kk-WL distinguishes within 2nk2 n^k rounds (existsdistinguishesAfterleexists_distinguishesAfter_le), so 2m<2nk+k+32^m < 2 n^k + k + 3.