## A combinatorial model for series-parallel networks

HTML articles powered by AMS MathViewer

- by Thomas H. Brylawski
- Trans. Amer. Math. Soc.
**154**(1971), 1-22 - DOI: https://doi.org/10.1090/S0002-9947-1971-0288039-7
- PDF | Request permission

## 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

- George D. Birkhoff,
*A determinant formula for the number of ways of coloring a map*, Ann. of Math. (2)**14**(1912/13), no. 1-4, 42–46. MR**1502436**, DOI 10.2307/1967597
T. Brylawski, Thesis, Dartmouth College, Hanover, N. H.
- Henry H. Crapo,
*A higher invariant for matroids*, J. Combinatorial Theory**2**(1967), 406–417. MR**215744** - Henry H. Crapo,
*Möbius inversion in lattices*, Arch. Math. (Basel)**19**(1968), 595–607 (1969). MR**245483**, DOI 10.1007/BF01899388 - Henry H. Crapo,
*The Tutte polynomial*, Aequationes Math.**3**(1969), 211–229. MR**262095**, DOI 10.1007/BF01817442 - Henry H. Crapo,
*The Möbius function of a lattice*, J. Combinatorial Theory**1**(1966), 126–131. MR**193018** - Henry H. Crapo and Gian-Carlo Rota,
*On the foundations of combinatorial theory: Combinatorial geometries*, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR**0290980** - G. A. Dirac,
*A property of $4$-chromatic graphs and some remarks on critical graphs*, J. London Math. Soc.**27**(1952), 85–92. MR**45371**, DOI 10.1112/jlms/s1-27.1.85 - R. J. Duffin,
*Topology of series-parallel networks*, J. Math. Anal. Appl.**10**(1965), 303–318. MR**175809**, DOI 10.1016/0022-247X(65)90125-3
P. A. MacMahon, - John Riordan and C. E. Shannon,
*The number of two-terminal series-parallel networks*, J. Math. Phys. Mass. Inst. Tech.**21**(1942), 83–93. MR**7511**, DOI 10.1002/sapm194221183 - Gian-Carlo Rota,
*On the foundations of combinatorial theory. I. Theory of Möbius functions*, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete**2**(1964), 340–368 (1964). MR**174487**, DOI 10.1007/BF00531932
—, - W. T. Tutte,
*A ring in graph theory*, Proc. Cambridge Philos. Soc.**43**(1947), 26–40. MR**18406**, DOI 10.1017/s0305004100023173 - W. T. Tutte,
*Lectures on matroids*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 1–47. MR**179781** - Hassler Whitney,
*The coloring of graphs*, Ann. of Math. (2)**33**(1932), no. 4, 688–718. MR**1503085**, DOI 10.2307/1968214 - Hassler Whitney,
*A logical expansion in mathematics*, Bull. Amer. Math. Soc.**38**(1932), no. 8, 572–579. MR**1562461**, DOI 10.1090/S0002-9904-1932-05460-X - Hassler Whitney,
*On the Abstract Properties of Linear Dependence*, Amer. J. Math.**57**(1935), no. 3, 509–533. MR**1507091**, DOI 10.2307/2371182

*The combination of resistances*, Electrician

**28**(1892), 601-602.

*Combinatorial analysis as a theory*, Hedrick Lectures, Math. Assoc. of Amer., Summer Meeting, Toronto, 1967. C. E. Shannon,

*A symbolic analysis of relay switching circuits*, Trans. Amer. Inst. Elec. Engrs.

**57**(1938), 713-723.

## Bibliographic Information

- © Copyright 1971 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**154**(1971), 1-22 - MSC: Primary 05.35; Secondary 50.00
- DOI: https://doi.org/10.1090/S0002-9947-1971-0288039-7
- MathSciNet review: 0288039