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

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.

Read the Lean proof on GitHub

Description

By the stabilization bound (Döring–Neuen) there is CC such that kk-WL stabilizes on every colored graph with NN vertices after at most CNk−1C N^{k-1} rounds. For GG, HH with at most nn vertices, both are stable after r=max(rG,rH)≤Cnk−1r = max(r_G, r_H) ≤ C n^{k-1} rounds, so if kk-WL distinguishes them it does so after some R≤r+1R ≤ r + 1 rounds. Witnesses from rounds give a colored graph FF of treewidth at most kk with hom(F,G)≠hom(F,H)hom(F, G) ≠ hom(F, H) and ∣V(F)∣≤k(k(∣V(G)∣k+∣V(H)∣k))R≤k(2knk)Cnk−1+1|V(F)| ≤ k (k (|V(G)|^k + |V(H)|^k))^R ≤ k (2 k n^k)^{C n^{k-1} + 1}, which is at most 2C′nk−1⌊log2n⌋2^{C' n^{k-1} ⌊log₂ n⌋} for C′=k+(3k+1)(C+1)C' = k + (3k+1)(C+1), using n≤22⌊log2n⌋n ≤ 2^{2 ⌊log₂ n⌋}.