Thomas Zaslavsky

Biased Graphs and the Associative Law

Abstract for the Combinatorics and Number Theory Seminar
2001 April 24

A quasigroup is like a group but without the identity, inverses, or associativity; all that is left is the multiplication table, which is an arbitrary Latin square. This is worth something: one has unique solvability of equations xy=z. Also, an identity can always be found. The crucial missing property is the associative law.

A biased graph is a graph together with a distinguished class of circles (a.k.a. circuits, cycles, polygons) that satisfies a certain combinatorial property. Each quasigroup with m elements gives rise to a kind of biased graph called an m-fold biased expansion of K3, the complete graph of order 3. Conversely, every m-fold biased expansion of K3 is obtained from a quasigroup. Trying to generalize this construction of quasigroups to Kn fails to be interesting because K4 implies the associative law, so that a biased expansion of Kn must come from a group if n > 3.

We explore this fact and possible ways of getting around it. For instance, an m-fold biased expansion of Cn , the circle of length n, encodes an n-dimensional Latin hypercube, which might be considered the multiplication table of an (n-1)-ary operation. Chords in the circle imply specific associative properties which get stronger and stronger until when all chords have been added (so the graph becomes Kn) there is complete associativity, making the operation a group operation. What happens in between is completely unknown.