Broken circuit complexes of series-parallel networks. (English) Zbl 1321.05037
Summary: Let \((h_0, h_1, \ldots, h_s)\) with \(h_s \neq 0\) be the \(h\)-vector of the broken circuit complex of a series-parallel network \(M\). Let \(G\) be a graph whose cycle matroid is \(M\). We give a formula for the difference \(h_{s - 1} - h_1\) in terms of an ear decomposition of \(G\). A number of applications of this formula are provided, including several bounds for \(h_{s - 1} - h_1\), a characterization of outerplanar graphs, and a solution to a conjecture on \(A\)-graphs posed by N. E. Fenton [Q. J. Math., Oxf. II. Ser. 34, 49–60 (1983; Zbl 0507.05016)]. We also prove that \(h_{s - 2} \geq h_2\) when \(s \geq 4\).
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
Citations:
Zbl 0507.05016References:
| [1] | Björner, A., The homology and shellability of matroids and geometric lattices, (Matroid Applications. Matroid Applications, Encyclopedia Math. Appl., vol. 40 (1992), Cambridge University Press: Cambridge University Press Cambridge), 226-283 · Zbl 0772.05027 |
| [2] | Björner, A.; Ziegler, G., Broken circuit complexes: factorizations and generalizations, J. Combin. Theory Ser. B, 51, 1, 96-126 (1991) · Zbl 0753.05019 |
| [3] | Bondy, J. A., Transversal matroids, base-orderable matroids, and graphs, Q. J. Math. Ox. Ser. (2), 23, 81-89 (1972) · Zbl 0236.05125 |
| [4] | Brown, J. I., Chromatic polynomials and order ideals of monomials, Discrete Math., 189, 1-3, 43-68 (1998) · Zbl 0957.05042 |
| [5] | Brylawski, T., A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc., 154, 1-22 (1971) · Zbl 0215.33702 |
| [6] | Brylawski, T., The broken-circuit complex, Trans. Amer. Math. Soc., 234, 417-433 (1977) · Zbl 0368.05022 |
| [7] | Brylawski, T., The Tutte polynomial. I. General theory, (Matroid Theory and its Applications (1982), Liguori: Liguori Naples), 125-275 · Zbl 1302.05023 |
| [8] | Brylawski, T., Constructions, (Theory of Matroids. Theory of Matroids, Encyclopedia Math. Appl., vol. 26 (1986), Cambridge University Press Press: Cambridge University Press Press Cambridge), 127-223 · Zbl 0596.05013 |
| [9] | Brylawski, T.; Oxley, J., The broken-circuit complex: its structure and factorizations, European J. Combin., 2, 2, 107-121 (1981) · Zbl 0466.05027 |
| [10] | Brylawski, T.; Oxley, J., The Tutte polynomial and its applications, (Matroid Applications. Matroid Applications, Encyclopedia Math. Appl., vol. 40 (1992), Cambridge University Press: Cambridge University Press Cambridge), 123-225 · Zbl 0769.05026 |
| [11] | Chari, M. K., Two decompositions in topological combinatorics with applications to matroid complexes, Trans. Amer. Math. Soc., 349, 3925-3943 (1997) · Zbl 0889.52013 |
| [12] | Chartrand, G.; Harary, F., Planar permutation graphs, Ann. Inst. H. Poincaré B (N.S.), 3, 433-438 (1967) · Zbl 0162.27605 |
| [13] | Crapo, H., A higher invariant for matroids, J. Combin. Theory, 2, 406-417 (1967) · Zbl 0168.26203 |
| [14] | de Sousa, J.; Welsh, D. J.A., A characterisation of binary transversal structures, J. Math. Anal. Appl., 40, 55-59 (1972) · Zbl 0197.28802 |
| [15] | Eisenbud, D.; Popescu, S.; Yuzvinsky, S., Hyperplane arrangement cohomology and monomials in the exterior algebra, Trans. Amer. Math. Soc., 355, 4365-4383 (2003) · Zbl 1034.52019 |
| [16] | Eppstein, D., Parallel recognition of series-parallel graphs, Inform. Comput., 98, 1, 41-55 (1992) · Zbl 0754.68056 |
| [17] | Fenton, N., Characterization of atomic matroids, Q. J. Math. Ox. Ser. (2), 34, 133, 49-60 (1983) · Zbl 0507.05016 |
| [18] | Goodall, A. J.; de Mier, A.; Noble, S. D.; Noy, M., The Tutte polynomial characterizes simple outerplanar graphs, Combin. Probab. Comput., 20, 4, 609-616 (2011) · Zbl 1223.05126 |
| [19] | Hibi, T., What can be said about pure O-sequences?, J. Combin. Theory Ser. A, 50, 319-322 (1989) · Zbl 0667.05004 |
| [20] | Hibi, T., Face number inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices, Pacific J. Math., 154, 253-264 (1992) · Zbl 0784.05020 |
| [21] | Huh, J., \(h\)-vectors of matroids and logarithmic concavity, Adv. Math., 270, 49-59 (2015) · Zbl 1304.05013 |
| [22] | Kämpf, G.; Römer, T., Homological properties of Orlik-Solomon algebras, Manuscripta Math., 129, 181-210 (2009) · Zbl 1209.05042 |
| [23] | Le, D. V., On the Gorensteinness of broken circuit complexes and Orlik-Terao ideals, J. Combin. Theory Ser. A, 123, 1, 169-185 (2014) · Zbl 1281.05042 |
| [24] | Le, D. V.; Römer, T., Broken circuit complexes and hyperplane arrangements, J. Algebraic Combin., 38, 4, 989-1016 (2013) · Zbl 1285.52014 |
| [25] | McKee, T., Induced cycle structure and outerplanarity, Discrete Math., 223, 1-3, 387-392 (2000) · Zbl 0972.05027 |
| [26] | Oxley, J., On Crapo’s beta invariant for matroids, Stud. Appl. Math., 66, 3, 267-277 (1982) · Zbl 0485.05022 |
| [27] | Oxley, J., (Matroid theory. Matroid theory, Oxford Graduate Texts in Mathematics, vol. 3 (2006), Oxford University Press: Oxford University Press London) · Zbl 1115.05001 |
| [28] | Provan, J. S., Decompositions, shellings, and diameters of simplicial complexes and convex polyhedra (1977), Cornell University: Cornell University Ithaca, NY, (Thesis) |
| [29] | Rota, G.-C., On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheor. Verwandte Geb., 2, 340-368 (1964) · Zbl 0121.02406 |
| [30] | Stanley, R. P., Cohen-Macaulay complexes, (Higher Combinatorics (1977), Reidel: Reidel Dordrecht), 51-62 · Zbl 0376.55007 |
| [31] | Stanley, R. P., (Combinatorics and Commutative Algebra. Combinatorics and Commutative Algebra, Progress in Mathematics, vol. 41 (1996), Birkhäuser: Birkhäuser Boston) · Zbl 0838.13008 |
| [32] | Swartz, E., \(g\)-elements of matroid complexes, J. Combin. Theory Ser. B, 88, 2, 369-375 (2003) · Zbl 1033.52011 |
| [33] | Whitney, H., A logical expansion in mathematics, Bull. Amer. Math. Soc., 38, 572-579 (1932) · JFM 58.0605.08 |
| [34] | Whitney, H., Non-separable and planar graphs, Trans. Amer. Math. Soc., 34, 2, 339-362 (1932) · JFM 58.0608.01 |
| [35] | Wilf, H., Which polynomials are chromatic?, (Proc. 1973 Rome International Colloq. Combinatorial Theory I (1976), Accademia Nazionale dei Lincei: Accademia Nazionale dei Lincei Rome), 247-257 · Zbl 0352.05031 |
| [36] | Zaslavsky, T., The Möbius function and the characteristic polynomial, (Combinatorial Geometries. Combinatorial Geometries, Encyclopedia Math. Appl., vol. 29 (1987), Cambridge University Press: Cambridge University Press Cambridge), 114-138 · Zbl 0632.05017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
