Proof of `Homomorphism counts into a lexicographic product`

groundedproofs/Lax871432Proofs/Results.lean · lax-871432

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

thm:lexprodhomthm:lexprod-hom. A homomorphism f:FGHf : F → G ⋅ H induces the partition of V(F)V(F) whose classes are the connected components of the subgraphs induced on the fibres of the first coordinate of ff; it is the unique partition into connected parts with which ff is compatible, in the sense that it refines those fibres and that no edge inside a fibre crosses two of its classes. Splitting the hom-set along this partition and pairing the two coordinates of ff with a homomorphism out of the quotient and one out of the disjoint union of the classes gives the bijection.