Proof of `Lovász's theorem` (1st statement)

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

Lovász's homomorphism matrix lemma. Every homomorphism FigFjF i →g F j factors as a strongly surjective homomorphism onto its image followed by an injective one; the image is isomorphic to a unique member FkF k of the family, and each homomorphism admits exactly aut(Fk)aut(F k) factorisations through FkF k. Counting gives M=SD1IM = S · D⁻¹ · I with SS the matrix of strongly surjective counts, DD the diagonal of automorphism counts and II the matrix of injective counts. Ordering the family by number of vertices, then by number of edges, makes SS lower and II upper triangular, both with positive diagonal, so all three factors are invertible and hence so is MM.