Thomas Zaslavsky (Binghamton)

Biased Expansion Graphs, Multary Quasigroups,
and the Associative Law (with Proofs)

Abstract for the Combinatorics and Number Theory Seminar
2003 October 24, 31, November 5

Short overall abstract:

A biased expansion Omega of a graph D is a kind of branched covering graph of D; that is, Omega has a projection map onto D that is bijective on vertices. If D is 2-connected, the fiber (inverse projection) of every edge has the same cardinality. If D is 3-connected, then Omega is a group expansion of D (a simple kind of biased expansion built from a group). If D is only 2-connected, it is built from describable parts.

A multary (or n-ary) quasigroup is a set with a multary operation that is like a group operation but with n arguments and without any analog of associativity. The 3-connectedness theorem implies that a multary quasigroup with enough factorizations must be a group in disguise. If it does not have enough factorizations, it is obtained by composition of multary operations from disguised groups and irreducible multary quasigroups.

The three parts of this series should be independent to a significant degree, as far as I can manage it.

Part I: Examples, Questions, Assertions

Part II: Fundamental Theorems and Proofs

Part III: Consequences for Biased Expansions and Multary Quasigroups

A biased expansion Omega of a graph D is a kind of branched covering graph of D; that is, Omega has a projection map onto D that is the identity on vertices. In a biased expansion, Omega is a biased graph, which means that each circle is called either ``balanced'' or ``unbalanced'' with the requirement that each theta subgraph contain 0, 1, or 3 balanced circles. One also requires a circle lifting property, that each lift (in Omega) of all but one edge e of a circle (in D) extends uniquely to a lift of the whole circle that is balanced. (``Lifting'' means any injective mapping from D to Omega that commutes with the covering projection.)

These are strong properties. For instance, if D is 2-connected, the fiber (inverse projection) of every edge has the same cardinality. If D is 3-connected, then Omega is a group expansion G·D. To define this, take any graph D and any group G. G·D has the same vertices as D, and its edges consist of one edge for each edge of D and each group element g. A circle in G·D is balanced if the product of the group elements of the edges of the circle multiply to 1. (I omit some essential technical details.)

A multary (or n-ary) quasigroup is a set with a multary operation that is like a group operation but with n arguments and without any analog of associativity. An n-ary quasigroup is ``really'' a biased expansion of a circle graph Cn+1. (Conversely, any biased expansion graph with a Hamiltonian circuit fixed -- if one exists -- is ``really'' a multary quasigroup.) In this way, the 3-connectedness theorem implies that a multary quasigroup with enough factorizations must be a group in disguise.

By Tutte's 3-decomposition theory of 2-connected graphs, the 3-connectedness theorem for biased expansions implies that all 2-connected biased expansions are built out of group expansions and circle expansions that correspond to irreducible multary (including binary) quasigroups. As for multary quasigroups, any one is obtained by composition of multary operations from disguised groups and irreducible multary quasigroups.

The proof of the 3-connectedness theorem consists of a few main lemmas. (1) Any biased expansion has a unique maximal extension on the same vertex set. (2) If Omega is a biased expansion of a theta graph D, then Omega extends to an edge joining the trivalent vertices of D. (3) If Omega, restricted to the covering of a circle C in D, extends to a chord e of D, then all of Omega extends to e. I will show how these lemmas are proved, with a reasonable amount of detail.

The assembly of 3-components of a biased expansion into a biased expansion of a 2-connected graph requires a theorem about how to assemble biased expansions along an edge and when such an ``amalgamation'' is a group expansion. I will show how this works.

A Dowling geometry is a kind of matroid associated with a group. Dowling geometries exist associated with quasigroups, but in a limited way. The question of whether there are other, similar generalized Dowling geometries is answered by finding the structure of biased expansion graphs.

The three parts of this series should be independent to a significant degree.