<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 1" %>
Dirac's Theorem on Simplicial Matroids
Raul Cordovil1, Manoel Lemos2,Cl\'audia Linhares Sales3
1Departamento de Matem\'atica, Instituto Superior T\'ecnico, Av. Rovisco Pais, 1049-001 Lisboa, Portugal
2Departamento de Matem\'atica, Universidade Federal de Pernambuco, Recife, Pernambuco, CEP 50740-540, Brasil
3MDCC, Departamento de Computa\c c\~ao, Universidade Federal do Cear\'a - UFC, Campus do Pici, Bloco 910, Fortaleza, CE, Brasil
Annals of Combinatorics 13 (1) pp.53-63 March, 2009
AMS Subject Classification: 05B35; 05C17
We introduce the notion of $k$-hyper\-clique complexes, i.e., the largest simplicial complexes on the set $[n]$ with a fixed $k$-skeleton. These simplicial complexes are a higher-dimen\-sio\-nal 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-dimen\-sio\-nal analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and $k$-hyper\-clique complexes. We prove also a higher-dimen\-sio\-nal 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 matroids


1. A. Bj¨orner, Topological methods, In: Handbook of Combinatorics, R. Graham, M. Gr¨otschel, and L. Lov´asz, Eds., Elsevier, Amsterdam, (1995) pp. 1819-–1872.

2. E.D. Bolker, Simplicial geometry and transportation polytopes, Trans. Amer. Math. Soc. 217 (1976) 121–-142.

3. R. Cordovil and M. Las Vergnas, G´eometries simpliciales unimodulaires, Discrete Math. 26 (3) (1979) 213-–217.

4. R. Cordovil and B. Lindstr¨om, Simplicial matroids, In: Combinatorial Geometries, Encyclopedia Math. Appl., Vol. 29, Cambridge University Press, Cambridge, (1987) pp. 98-–113.

5. R. Cordovil, D. Forge, and S. Klein, How is a chordal graph like a supersolvable binary matroid?, Discrete Math. 288 (1-3) (2004) 167-–172.

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.

8. G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71–-76.

9. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2nd Ed., Ann. Discrete Math., Vol. 57, Elsevier Science B.V., Amsterdam, 2004.

10. J. Herzog, T. Hibi, and X. Zheng, Dirac's theorem on chordal graphs and Alexander duality, European J. Combin. 25 (7) (2004) 949–-960.

11. J.G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.

12. R.P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972) 197-–217.

13. W.T. Tutte, Introduction to the Theory of Matroids, American Elsevier Publishing Co., Inc., New York, 1971.

14. D.J.A. Welsh, Matroid Theory, Academic Press, London-New York, 1976.

15. N. White, Theory of Matroids, Cambridge University Press, Cambridge, 1986.

16. N. White, Combinatorial Geometries, Cambridge University Press, Cambridge, 1987.

17. N. White, Matroid Applications, Cambridge University Press, Cambridge, 1992.