Dirac’s theorem on simplicial matroids. (English) Zbl 1229.05064
Summary: We introduce the notion of \(k\)-hyperclique complexes, i.e., the largest simplicial complexes on the set \([n]\) with a fixed \(k\)-skeleton. These simplicial complexes are a higher-dimensional analogue of clique (or flag) complexes (case \(k=2\)) and they are a rich new class of simplicial complexes. We show that Dirac’s theorem on chordal graphs has a higher-dimensional analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and \(k\)-hyperclique complexes. We prove also a higher-dimensional analogue of Stanley’s reformulation of Dirac’s theorem on chordal graphs.
Keywords:
clique (flag) complexes; Dirac’s theorem on chordal graphs; simplicial matroids; \(k\)-hyperclique complexes; Helly dual \(k\)-property; strong triangulable simplicial matroidsReferences:
| [1] | A. Björner, Topological methods, In: Handbook of Combinatorics, R. Graham, M. Grötschel, and L. Lovász, Eds., Elsevier, Amsterdam, (1995) pp. 1819–1872. |
| [2] | Bolker E.D.: Simplicial geometry and transportation polytopes. Trans. Amer. Math. Soc. 217, 121–142 (1976) · Zbl 0322.55033 |
| [3] | Cordovil R., Las Vergnas M.: Géometries simpliciales unimodulaires. Discrete Math. 26(3), 213–217 (1979) · Zbl 0412.05027 · doi:10.1016/0012-365X(79)90026-8 |
| [4] | R. Cordovil and B. Lindström, Simplicial matroids, In: Combinatorial Geometries, Encyclopedia Math. Appl., Vol. 29, Cambridge University Press, Cambridge, (1987) pp. 98–113. |
| [5] | Cordovil R., Forge D., Klein S.: How is a chordal graph like a supersolvable binary matroid?. Discrete Math. 288(1-3), 167–172 (2004) · Zbl 1057.05021 · doi:10.1016/j.disc.2004.08.004 |
| [6] | H.H. Crapo and G.-C. Rota, Simplicial geometries, In: Combinatorics, Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., (1968) pp. 71–75. |
| [7] | H.H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, Preliminary Edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. · Zbl 0216.02101 |
| [8] | Dirac G.A.: On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg 25, 71–76 (1961) · Zbl 0098.14703 · doi:10.1007/BF02992776 |
| [9] | M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2nd Ed., Ann. Discrete Math., Vol. 57, Elsevier Science B.V., Amsterdam, 2004. · Zbl 1050.05002 |
| [10] | Herzog J., Hibi T., Zheng X.: Dirac’s theorem on chordal graphs and Alexander duality. European J. Combin. 25(7), 949–960 (2004) · Zbl 1062.05075 · doi:10.1016/j.ejc.2003.12.008 |
| [11] | Oxley J.G.: Matroid Theory. Oxford University Press, New York (1992) · Zbl 0784.05002 |
| [12] | Stanley R.P.: Supersolvable lattices. Algebra Universalis 2, 197–217 (1972) · Zbl 0256.06002 · doi:10.1007/BF02945028 |
| [13] | Tutte W.T.: Introduction to the Theory of Matroids. American Elsevier Publishing Co., Inc., New York (1971) · Zbl 0231.05027 |
| [14] | Welsh D.J.A.: Matroid Theory. Academic Press, London-New York (1976) |
| [15] | White N.: Theory of Matroids. Cambridge University Press, Cambridge (1986) · Zbl 0579.00001 |
| [16] | White N.: Combinatorial Geometries. Cambridge University Press, Cambridge (1987) · Zbl 0626.00007 |
| [17] | White N.: Matroid Applications. Cambridge University Press, Cambridge (1992) · Zbl 0742.00052 |
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.
