Saturday, October 15, 2022

Congruence lattices of undirected graphs

Locus can now compute the congruence lattices of undirected graphs using topos theory. This uses the topos of quivers with involution.

P3
Here is the path graph on three elements: Here is its congruence lattice: K3
Here is the complete graph on three elements: Here is its corresponding congruence lattice: P4
Here is the path graph on four elements: Here is its congruence lattice: S4
This is the star graph on four elements: Here is its congruence lattice: C4
Here is the cycle graph on four elements: Here is its congruence lattice: This congruence lattice is already getting quite big so we can stop this here. Rest assured that every undirected graph, and indeed every mathematical structure, has a congruence lattice defined over it even if we can't see it.

No comments:

Post a Comment