A combinatorial model for seriesparallel networks
Author:
Thomas H. Brylawski
Journal:
Trans. Amer. Math. Soc. 154 (1971), 122
MSC:
Primary 05.35; Secondary 50.00
MathSciNet review:
0288039
Fulltext PDF Free Access
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 nary symmetric operators with identities and generate a free algebra. Elements of the subalgebra generated by the two point circuit are defined as seriesparallel networks, and this subalgebra is shown to be closed under arbitrary minors. Nonpointed seriesparallel 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. Seriesparallel networks can also be characterized in a universally constructed ring of pregeometries generalized from previous work of W. Tutte and A. Grothendieck. In this TutteGrothendieck 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. 14, 42–46. MR
1502436, http://dx.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
(35 #6579)
 [4]
Henry
H. Crapo, Möbius inversion in lattices, Arch. Math.
(Basel) 19 (1968), 595–607 (1969). MR 0245483
(39 #6791)
 [5]
Henry
H. Crapo, The Tutte polynomial, Aequationes Math.
3 (1969), 211–229. MR 0262095
(41 #6705)
 [6]
Henry
H. Crapo, The Möbius function of a lattice, J.
Combinatorial Theory 1 (1966), 126–131. MR 0193018
(33 #1240)
 [7]
Henry
H. Crapo and GianCarlo
Rota, On the foundations of combinatorial theory: Combinatorial
geometries, Preliminary edition, The M.I.T. Press, Cambridge,
Mass.London, 1970. MR 0290980
(45 #74)
 [8]
G.
A. Dirac, A property of 4chromatic graphs and some remarks on
critical graphs, J. London Math. Soc. 27 (1952),
85–92. MR
0045371 (13,572f)
 [9]
R.
J. Duffin, Topology of seriesparallel networks, J. Math.
Anal. Appl. 10 (1965), 303–318. MR 0175809
(31 #85)
 [10]
P. A. MacMahon, The combination of resistances, Electrician 28 (1892), 601602.
 [11]
John
Riordan and C.
E. Shannon, The number of twoterminal seriesparallel
networks, J. Math. Phys. Mass. Inst. Tech. 21 (1942),
83–93. MR
0007511 (4,151c)
 [12]
GianCarlo
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
(30 #4688)
 [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), 713723.
 [15]
W.
T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc.
43 (1947), 26–40. MR 0018406
(8,284k)
 [16]
W.
T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards
Sect. B 69B (1965), 1–47. MR 0179781
(31 #4023)
 [17]
Hassler
Whitney, The coloring of graphs, Ann. of Math. (2)
33 (1932), no. 4, 688–718. MR
1503085, http://dx.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, http://dx.doi.org/10.1090/S00029904193205460X
 [19]
Hassler
Whitney, On the Abstract Properties of Linear Dependence,
Amer. J. Math. 57 (1935), no. 3, 509–533. MR
1507091, http://dx.doi.org/10.2307/2371182
 [1]
 G. D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1913), 4246. MR 1502436
 [2]
 T. Brylawski, Thesis, Dartmouth College, Hanover, N. H.
 [3]
 H. Crapo, A higher invariant for matroids, J. Combinatorial Theory 2 (1967), 406417. MR 35 #6579. MR 0215744 (35:6579)
 [4]
 , Möbius inversion in lattices, Arch. Math. 19 (1968), 595607. MR 0245483 (39:6791)
 [5]
 , The Tutte polynomial, Aequationes Math. 3 (1970). MR 0262095 (41:6705)
 [6]
 , The Möbius function of a lattice, J. Combinatorial Theory 1 (1966), 126131. MR 33 #1240. MR 0193018 (33:1240)
 [7]
 H. Crapo and G.C. Rota, Combinatorial geometries, preliminary ed., M.I.T. Press, Cambridge, Mass., 1970. MR 0290980 (45:74)
 [8]
 G. Dirac, A property of 4chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952), 8592. MR 13, 572. MR 0045371 (13:572f)
 [9]
 R. Duffin, Topology of seriesparallel networks, J. Math. Anal. Appl. 10 (1965), 303318. MR 31 #85. MR 0175809 (31:85)
 [10]
 P. A. MacMahon, The combination of resistances, Electrician 28 (1892), 601602.
 [11]
 J. Riordan and C. E. Shannon, The number of twoterminal seriesparallel networks, J. Math. Phys. Mass. Inst. Tech. 21 (1942), 8393. MR 4, 151. MR 0007511 (4:151c)
 [12]
 G.C. Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340368. MR 30 #4688. MR 0174487 (30:4688)
 [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), 713723.
 [15]
 W. T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947), 2640. MR 8, 284. MR 0018406 (8:284k)
 [16]
 , Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 147. MR 31 #4023. MR 0179781 (31:4023)
 [17]
 H. Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), 688718. MR 1503085
 [18]
 , A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), 572579. MR 1562461
 [19]
 , On the abstract properties of linear dependence, Amer. J. Math. 57 (1935), 509533. MR 1507091
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
DOI:
http://dx.doi.org/10.1090/S00029947197102880397
PII:
S 00029947(1971)02880397
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,
TutteGrothendieck ring,
seriesparallel network,
essentially series,
essentially parallel,
seriesparallel irreducible
Article copyright:
© Copyright 1971
American Mathematical Society
