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

Proof of `The homomorphism characterization of Weisfeiler–Leman`

groundedproofs/Lax119563Proofs/HomChar/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

(→) is the witness theorem witnessfromroundswitness_from_rounds: a distinction after rr rounds yields a colored graph of treewidth at most kk with different homomorphism counts.

(←) Let FF have treewidth at most kk, and take a one-vertex tree decomposition of width kk of it (Abramsky–Jakl–Paine): a rooted forest on V(F)V(F) where each vertex vv has a bag of at most k+1k + 1 vertices containing vv, the rest of which lies in the bag of the parent, and every edge lies in a bag. A map V(F)→V(G)V(F) → V(G) is a homomorphism if and only if every vertex satisfies its local condition (color, and edges to the rest of its bag). Counting the maps on the subtree of a vertex cc, with the vertices outside given, yields the recursion "choose the image xx of cc, check the local condition at cc, and multiply the counts for the children of cc". By induction from the leaves, the count for cc is a function of the round-rr WL color (for some rr) of the kk-tuple formed by images of labels ℓℓ covering the rest of the bag of cc: the sum over xx is a WL refinement step, in which every child either keeps the labels ℓℓ or replaces one position (not needed for the rest of its bag; it exists since that rest has at most k−1k - 1 vertices besides cc) by cc. At a root, the count is a sum over all kk-tuples of a WL-determined function, so it agrees for GG and HH when no round of kk-WL distinguishes them; hom(F,⋅)hom(F, ·) is the product of these counts over the roots.