Proof of `Contracting edges and right lexicographic products` (1st statement)

groundedproofs/Lax871432Proofs/Results.lean · lax-871432

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.

Read the Lean proof on GitHub

Description

prop:lexprodcontractprop:lexprod-contract, (2) ⇔ (3). Forwards, take the right factor to be a complete graph on the vertices of FF: every coefficient hom(R𝓡,F[R],K)hom(∐ R ∈ 𝓡, F[R], K) is then positive, since the disjoint union of the classes is a graph on V(F)V(F) and maps into that complete graph. The formula therefore exhibits a linear combination of the counts from the quotients F/𝓡F / 𝓡 that [F]≡[\mathcal{F}] determines, and the lemma on determined linear combinations places each quotient in clFcl \mathcal{F}; every contraction is such a quotient. Backwards, (1) ⇒ (2) applied to clFcl \mathcal{F}.