Proof of `Taking induced subgraphs and left 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:lexprodindsubprop:lexprod-indsub, (2) ⇔ (3). Forwards, take the left factor to be a complete graph on the vertices of FF: every coefficient hom(F/𝓡,K)hom(F / 𝓡, K) is then positive, since a quotient of FF has at most as many vertices as FF. The formula therefore exhibits a linear combination of the counts from the disjoint unions of the classes that [F]≡[\mathcal{F}] determines, and the lemma on determined linear combinations places each such disjoint union in clFcl \mathcal{F}. Applying this to the partition whose classes are those of F[U]F[U] together with a singleton for each vertex outside UU gives F[U]F[U] with isolated vertices attached; lem:minorslem:minors strips them off. Backwards, (1) ⇒ (2) applied to clFcl \mathcal{F}.