Richard Hammack
What makes a diagram commute?

Abstract: We are concerned with commutative diagrams in the usual sense: A diagram is a digraph whose vertices are objects in a category and whose arcs are morphisms between objects. A diagram commutes if any two route pairs from one vertex x to another vertex y compose to equal morphisms x→y.  We pose a simple question: How can one most efficiently determine if a diagram commutes?

For example, consider a diagram whose underlying digraph is the transitive tournament on n vertices, which has O(3ⁿ) route pairs. Does one have to check commutativity of these exponentially many route pairs before deciding that the diagram commutes? If not, how many? Which ones?

We introduce the idea of a so-called minimal CS-generating set for a diagram, a smallest set B of route pairs for which commutativity on the elements of B propagates to commutativity of the entire diagram. For a given diagram, all such sets have the same size, which is no greater than C(n-1, 2), for a diagram on n vertices (with equality holding precisely when the diagram is a transitive tournament).

This is a continuation of one of my earlier talks in VCU's Discrete Math Seminar, which addressed the same question in the groupoid category, that is, where all morphisms are bijective. There the generating set B was always a cycle basis. For general diagrams—like those discussed here—we must abandon independence of B.

This is joint work with Paul Kainen (Georgetown University).