Proof of `Homomorphism counts into a full complement`

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

eq:complementeq:complement. A map V(F)V(X)V(F) → V(X) is a homomorphism into the full complement exactly when it avoids, for every edge of FF, the event that its endpoints are sent to an adjacent pair; inclusion–exclusion over those events counts the maps avoiding all of them, and the maps satisfying the events of a set ss of edges are the homomorphisms out of the spanning subgraph with edge set ss.