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.
Description
(→) is the witness theorem : a distinction after rounds yields a colored graph of treewidth at most with different homomorphism counts.
(←) Let have treewidth at most , and take a one-vertex tree decomposition of width of it (Abramsky–Jakl–Paine): a rooted forest on where each vertex has a bag of at most vertices containing , the rest of which lies in the bag of the parent, and every edge lies in a bag. A map 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 , with the vertices outside given, yields the recursion "choose the image of , check the local condition at , and multiply the counts for the children of ". By induction from the leaves, the count for is a function of the round- WL color (for some ) of the -tuple formed by images of labels covering the rest of the bag of : the sum over 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 vertices besides ) by . At a root, the count is a sum over all -tuples of a WL-determined function, so it agrees for and when no round of -WL distinguishes them; is the product of these counts over the roots.