Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A combinatorial model for series-parallel networks

Author: Thomas H. Brylawski
Journal: Trans. Amer. Math. Soc. 154 (1971), 1-22
MSC: Primary 05.35; Secondary 50.00
MathSciNet review: 0288039
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05.35, 50.00

Retrieve articles in all journals with MSC: 05.35, 50.00

Additional Information

Keywords: Matroid, pointed pregeometry, basepoint, isthmus, loop, contraction, deletion, series connection, parallel connection, pointed direct sum, pushout, complexity, Möbius function, Crapo invariant, chromatic polynomial, graph coloring, Hadwiger conjecture, two color theorem, Tutte polynomial, Tutte-Grothendieck ring, series-parallel network, essentially series, essentially parallel, series-parallel irreducible
Article copyright: © Copyright 1971 American Mathematical Society

American Mathematical Society