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

Proof of `An upper bound on the size of homomorphism witnesses for uncolored graphs`

groundedproofs/Lax119563Proofs/UpperBound/UncoloredWitnessUpperBound.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

Give GG and HH the constant color 00 (on vertex sets Fin∣V∣Fin |V|, Fin∣W∣Fin |W|); homomorphism counts from graphs with constant color 00 are the uncolored ones. A graph FF of treewidth at most kk with hom(F,G)≠hom(F,H)hom(F, G) ≠ hom(F, H) therefore shows, via the homomorphism characterization of kk-WL, that kk-WL distinguishes the colored versions. The colored witness size upper bound yields a colored witness F′F' of treewidth at most kk with at most 2Cnk−1log2n2^{C n^{k-1} log₂ n} vertices. Every vertex of F′F' has color 00, since otherwise hom(F′,G)=0=hom(F′,H)hom(F', G) = 0 = hom(F', H); so the underlying graph of F′F' is the required witness.