Proof of `Homomorphism witnesses from rounds`
groundedproofs/Lax119563Proofs/HomTensors/WitnessFromRounds.lean · lax-119563
What this proof establishes
no assumptions
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
Put , the number of -tuples of and . Labeled graphs carry edges, color predicates, equality constraints and labels; a good one has a rooted bag tree of width with all labels in the root bag. By induction on , each round- color-class indicator of -WL on is a linear combination of tensors of good labeled graphs with at most vertices besides the labels, where and : round zero and the step both use polynomial closure (degree at most ), with atoms for equalities, edges and colors in round zero, and gluing and extension for the step. Applying the functional "sum over minus sum over " to the indicator of a class of different sizes gives a good labeled graph with different homomorphism counts into and . Taking the quotient by the equality constraints, excluding loops, symmetrizing edges and splitting by the colorings compatible with the predicates yields a colored graph of treewidth at most with at most vertices distinguishing and .