**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* ^{n}*)
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).