The brokencircuit complex
Author:
Tom Brylawski
Journal:
Trans. Amer. Math. Soc. 234 (1977), 417433
MSC:
Primary 05B35; Secondary 05B25, 05C15
MathSciNet review:
468931
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The brokencircuit complex introduced by H. Wilf (Which polynomials are chromatic?, Proc. Colloq. Combinational Theory (Rome, 1973)) of a matroid G is shown to be a cone over a related complex, the reduced brokencircuit complex . The topological structure of is studied, its Euler characteristic is computed, and joins and skeletons are shown to exist in the class of all such complexes. These computations and constructions are compared with analogous results in the theory of the independent set complex of a matroid. Reduced brokencircuit complexes are partially characterized by conditions concerning which subcomplexes are pure (i.e., have equicardinal maximal simplices). In particular, every matroid complex is a reduced brokencircuit complex. Three proofs are given that the simplex numbers of the cone of are the coefficients which appear in the characteristic polynomial of G. This relates the work of W. Tutte on externally inactive bases to that of H. Whitney on sets which do not contain broken circuits. One of these proofs gives a combinatorial correspondence between these sets. Properties of the characteristic polynomial are then given topological proofs.
 [1]
Norman
Biggs, Algebraic graph theory, Cambridge University Press,
London, 1974. Cambridge Tracts in Mathematics, No. 67. MR 0347649
(50 #151)
 [2]
Thomas
H. Brylawski, A combinatorial model for
seriesparallel networks, Trans. Amer. Math.
Soc. 154 (1971),
1–22. MR
0288039 (44 #5237), http://dx.doi.org/10.1090/S00029947197102880397
 [3]
Thomas
H. Brylawski, A decomposition for combinatorial
geometries, Trans. Amer. Math. Soc. 171 (1972), 235–282. MR 0309764
(46 #8869), http://dx.doi.org/10.1090/S00029947197203097646
 [4]
Tom
Brylawski and Douglas
G. Kelly, Matroids and combinatorial geometries, Studies in
combinatorics, Math. Assoc. America, Washington, D.C., 1978,
pp. 179–217. MAA Studies in Math., 17. MR 0505694
(58 #21724)
 [5]
Henry
H. Crapo, The Tutte polynomial, Aequationes Math.
3 (1969), 211–229. MR 0262095
(41 #6705)
 [6]
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)
 [7]
Thomas
A. Dowling and Richard
M. Wilson, Whitney number inequalities for
geometric lattices, Proc. Amer. Math. Soc.
47 (1975),
504–512. MR 0354422
(50 #6900), http://dx.doi.org/10.1090/S00029939197503544223
 [8]
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)
 [9]
Edwin
H. Spanier, Algebraic topology, McGrawHill Book Co., New
YorkToronto, Ont.London, 1966. MR 0210112
(35 #1007)
 [10]
Richard
P. Stanley, Acyclic orientations of graphs, Discrete Math.
5 (1973), 171–178. MR 0317988
(47 #6537)
 [11]
W.
T. Tutte, A contribution to the theory of chromatic
polynomials, Canadian J. Math. 6 (1954), 80–91.
MR
0061366 (15,814c)
 [12]
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
 [13]
Herbert
S. Wilf, Which polynomials are chromatic?, Colloquio
Internazionale sulle Teorie Combinatorie (Roma, 1973) Accad. Naz. Lincei,
Rome, 1976, pp. 247–256. Atti dei Convegni Lincei, No. 17
(English, with Italian summary). MR 0453579
(56 #11841)
 [14]
Tom
Brylawski, Modular constructions for
combinatorial geometries, Trans. Amer. Math.
Soc. 203 (1975),
1–44. MR
0357163 (50 #9631), http://dx.doi.org/10.1090/S00029947197503571636
 [1]
 N. Biggs, Algebraic graph theory, Cambridge Univ. Press, London, 1974. MR 50 #151. MR 0347649 (50:151)
 [2]
 T. H. Brylawski, A combinatorial model for seriesparallel networks, Trans. Amer. Math. Soc. 154 (1971), 122. MR 44 #5237. MR 0288039 (44:5237)
 [3]
 , A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 234282. MR 45 #8869. MR 0309764 (46:8869)
 [4]
 T. Brylawski and D. Kelly, Matroids and combinatorial geometries, Studies in Combinatorial Theory (G.C. Rota, editor), Math. Assoc. Amer. (to appear). MR 0505694 (58:21724)
 [5]
 H. H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969), 211229. MR 41 #6705. MR 0262095 (41:6705)
 [6]
 H. H. Crapo, and G. C. Rota, On the foundations of combinatorial theory: Combinatorial geometrics, Preliminary ed., M.I.T. Press, Cambridge, Mass, and London, 1970. MR 45 #74. MR 0290980 (45:74)
 [7]
 T. A. Dowling and R. M. Wilson, Whitney number inequalities for geometric lattices, Proc. Amer. Math. Soc. 47 (1975), 504512. MR 0354422 (50:6900)
 [8]
 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)
 [9]
 E. H. Spanier, Algebraic topology, McGrawHill, New York, 1966. MR 35 #1007. MR 0210112 (35:1007)
 [10]
 R. P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171178. MR 47 #6537. MR 0317988 (47:6537)
 [11]
 W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 8091. MR 15, 814. MR 0061366 (15:814c)
 [12]
 H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), 572579. MR 1562461
 [13]
 H. Wilf, Which polynomials are chromatic, Proc. Colloq. Combinatorial Theory, Rome, 1973 (to appear). MR 0453579 (56:11841)
 [14]
 T. Brylawski, Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc. 203 (1975), 144. MR 50 #9631. MR 0357163 (50:9631)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
05B35,
05B25,
05C15
Retrieve articles in all journals
with MSC:
05B35,
05B25,
05C15
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947197704689316
PII:
S 00029947(1977)04689316
Keywords:
Basis,
broken circuit,
brokencircuit complex,
characteristic polynomial,
chromatic polynomial,
combinatorial geometry,
Euler characteristic,
external activity,
graph,
internal activity,
matroid,
pure complex,
simplex numbers,
simplicial complex,
Whitney polynomial
Article copyright:
© Copyright 1977
American Mathematical Society
