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

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.

Read the Lean proof on GitHub

Description

Put M=∣V(G)∣k+∣V(H)∣kM = |V(G)|^k + |V(H)|^k, the number of kk-tuples of GG and HH. Labeled graphs carry edges, color predicates, equality constraints and kk labels; a good one has a rooted bag tree of width kk with all labels in the root bag. By induction on rr, each round-rr color-class indicator of kk-WL on V(G)k⊔V(H)kV(G)^k ⊔ V(H)^k is a linear combination of tensors of good labeled graphs with at most νrν_r vertices besides the labels, where ν0=0ν_0 = 0 and νr+1=(M−1)(1+kνr)ν_{r+1} = (M - 1)(1 + k ν_r): round zero and the step both use polynomial closure (degree at most M−1M - 1), with atoms for equalities, edges and colors in round zero, and gluing and extension for the step. Applying the functional "sum over V(G)kV(G)^k minus sum over V(H)kV(H)^k" to the indicator of a class of different sizes gives a good labeled graph with different homomorphism counts into GG and HH. 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 kk with at most k+νr≤k(kM)rk + ν_r ≤ k (k M)^r vertices distinguishing GG and HH.