The broken-circuit complex

Author:
Tom Brylawski

Journal:
Trans. Amer. Math. Soc. **234** (1977), 417-433

MSC:
Primary 05B35; Secondary 05B25, 05C15

DOI:
https://doi.org/10.1090/S0002-9947-1977-0468931-6

MathSciNet review:
468931

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The *broken-circuit 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 broken-circuit 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 broken-circuit 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 broken-circuit 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****[2]**Thomas H. Brylawski,*A combinatorial model for series-parallel networks*, Trans. Amer. Math. Soc.**154**(1971), 1–22. MR**0288039**, https://doi.org/10.1090/S0002-9947-1971-0288039-7**[3]**Thomas H. Brylawski,*A decomposition for combinatorial geometries*, Trans. Amer. Math. Soc.**171**(1972), 235–282. MR**0309764**, https://doi.org/10.1090/S0002-9947-1972-0309764-6**[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****[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 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****[7]**Thomas A. Dowling and Richard M. Wilson,*Whitney number inequalities for geometric lattices*, Proc. Amer. Math. Soc.**47**(1975), 504–512. MR**0354422**, https://doi.org/10.1090/S0002-9939-1975-0354422-3**[8]**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**[9]**Edwin H. Spanier,*Algebraic topology*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR**0210112****[10]**Richard P. Stanley,*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171–178. MR**0317988**, https://doi.org/10.1016/0012-365X(73)90108-8**[11]**W. T. Tutte,*A contribution to the theory of chromatic polynomials*, Canadian J. Math.**6**(1954), 80–91. MR**0061366****[12]**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**[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****[14]**Tom Brylawski,*Modular constructions for combinatorial geometries*, Trans. Amer. Math. Soc.**203**(1975), 1–44. MR**0357163**, https://doi.org/10.1090/S0002-9947-1975-0357163-6

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:
https://doi.org/10.1090/S0002-9947-1977-0468931-6

Keywords:
Basis,
broken circuit,
broken-circuit 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