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.
Description
We apply the row-space compiler to the relay counter (counting down through the addresses, , with every decrement realized by a one-way gate), for . Unit propagation reaches a conflict (), so Spoiler wins and -WL distinguishes the graphs. A weight argument shows that every contradiction tree has more than nodes (); with item 4 of the compiler this bounds every witness by . The size parameter is (), so the graphs have vertices, giving the bound with . Finally : the conflict round is at least , since a conflict in round yields a contradiction tree with fewer than nodes; Duplicator survives until then, while -WL distinguishes within rounds (), so .