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

DOI:
https://doi.org/10.1090/S0002-9947-1971-0288039-7

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 , and the parallel connection ; 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 (contraction ) is separable. Thus both connections are *n*-ary symmetric operators with identities and generate a free algebra. Elements of the subalgebra 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 relative to some point.

2. They are in 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 is not a geometry.

5. For any point *e* in *K*, or 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.

**[1]**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**, https://doi.org/10.2307/1967597**[2]**T. Brylawski, Thesis, Dartmouth College, Hanover, N. H.**[3]**Henry H. Crapo,*A higher invariant for matroids*, J. Combinatorial Theory**2**(1967), 406–417. MR**0215744****[4]**Henry H. Crapo,*Möbius inversion in lattices*, Arch. Math. (Basel)**19**(1968), 595–607 (1969). MR**0245483**, https://doi.org/10.1007/BF01899388**[5]**Henry H. Crapo,*The Tutte polynomial*, Aequationes Math.**3**(1969), 211–229. MR**0262095**, https://doi.org/10.1007/BF01817442**[6]**Henry H. Crapo,*The Möbius function of a lattice*, J. Combinatorial Theory**1**(1966), 126–131. MR**0193018****[7]**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****[8]**G. A. Dirac,*A property of 4-chromatic graphs and some remarks on critical graphs*, J. London Math. Soc.**27**(1952), 85–92. MR**0045371**, https://doi.org/10.1112/jlms/s1-27.1.85**[9]**R. J. Duffin,*Topology of series-parallel networks*, J. Math. Anal. Appl.**10**(1965), 303–318. MR**0175809**, https://doi.org/10.1016/0022-247X(65)90125-3**[10]**P. A. MacMahon,*The combination of resistances*, Electrician**28**(1892), 601-602.**[11]**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**0007511**, https://doi.org/10.1002/sapm194221183**[12]**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**0174487**, https://doi.org/10.1007/BF00531932**[13]**-,*Combinatorial analysis as a theory*, Hedrick Lectures, Math. Assoc. of Amer., Summer Meeting, Toronto, 1967.**[14]**C. E. Shannon,*A symbolic analysis of relay switching circuits*, Trans. Amer. Inst. Elec. Engrs.**57**(1938), 713-723.**[15]**W. T. Tutte,*A ring in graph theory*, Proc. Cambridge Philos. Soc.**43**(1947), 26–40. MR**0018406****[16]**W. T. Tutte,*Lectures on matroids*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 1–47. MR**0179781****[17]**Hassler Whitney,*The coloring of graphs*, Ann. of Math. (2)**33**(1932), no. 4, 688–718. MR**1503085**, https://doi.org/10.2307/1968214**[18]**Hassler Whitney,*A logical expansion in mathematics*, Bull. Amer. Math. Soc.**38**(1932), no. 8, 572–579. MR**1562461**, https://doi.org/10.1090/S0002-9904-1932-05460-X**[19]**Hassler Whitney,*On the Abstract Properties of Linear Dependence*, Amer. J. Math.**57**(1935), no. 3, 509–533. MR**1507091**, https://doi.org/10.2307/2371182

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

DOI:
https://doi.org/10.1090/S0002-9947-1971-0288039-7

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