A combinatorial model for series-parallel networks

Abstract:

The category of pregeometries with basepoint is defined and explored. In this category two important operations are extensively characterized: the series connection $S(G,H)$, and the parallel connection $P(G,H) = \tilde S(\tilde G,\tilde H)$; and the latter is shown to be the categorical direct sum. For graphical pregeometries, these notions coincide with the classical definitions. A pregeometry F is a nontrivial series (or parallel) connection relative to a basepoint p iff the deletion $F\backslash p$ (contraction $F/p$) is separable. Thus both connections are n-ary symmetric operators with identities and generate a free algebra. Elements of the subalgebra $A[{C_2}]$ generated by the two point circuit are defined as series-parallel networks, and this subalgebra is shown to be closed under arbitrary minors. Nonpointed series-parallel networks are characterized by a number of equivalent conditions: 1. They are in $A[{C_2}]$ relative to some point. 2. They are in $A[{C_2}]$ relative to any point. For any connected minor K of three or more points: 3. K is not the four point line or the lattice of partitions of a four element set. 4. K or $\tilde K$ is not a geometry. 5. For any point e in K, $K\backslash e$ or $K/e$ is separable. Series-parallel networks can also be characterized in a universally constructed ring of pregeometries generalized from previous work of W. Tutte and A. Grothendieck. In this Tutte-Grothendieck ring they are the pregeometries for which the Crapo invariant equals one. Several geometric invariants are directly calculated in this ring including the complexity and the chromatic polynomial. The latter gives algebraic proofs of the two and three color theorems.