Proof of `An upper bound on the size of homomorphism witnesses`
groundedproofs/Lax119563Proofs/UpperBound/WitnessUpperBound.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
By the stabilization bound (Döring–Neuen) there is such that -WL stabilizes on every colored graph with vertices after at most rounds. For , with at most vertices, both are stable after rounds, so if -WL distinguishes them it does so after some rounds. Witnesses from rounds give a colored graph of treewidth at most with and , which is at most for , using .