×

Dirac’s theorem on chordal graphs and Alexander duality. (English) Zbl 1062.05075

Dirac’s theorem is one of the fascinating results in classical graph theory. It states that a finite graph \(G\) is chordal (that is each cycle of length \(\geq 4\) has a chord) if and only if \(G\) has a perfect elimination ordering on its vertices. The authors give an algebraic proof of an equivalent form of Dirac’s theorem. Such a proof is not easier than the original proof, but it gives new insight into the possible relation trees of a perfect ideal of codimension \(2\). Moreover, this new approach allows one to formulate a “higher” Dirac theorem, which is used to prove that all powers of non-skeleton facet ideals of a quasi-tree have a linear resolution.

MSC:

05C38 Paths and cycles
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
13F55 Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bruns, W.; Herzog, J., Cohen-Macaulay Rings (1996), Cambridge University Press: Cambridge University Press Cambridge
[2] Bruns, W.; Herzog, J., On multigraded resolutions, Math. Proc. Cambridge Philos. Soc., 118, 245-257 (1995) · Zbl 0888.13004
[3] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 38, 71-76 (1961) · Zbl 0098.14703
[4] Faridi, S., The facet ideal of a simplicial complex, Manuscripta Math., 109, 159-174 (2002) · Zbl 1005.13006
[5] Eagon, J. A.; Reiner, V., Resolutions of Stanley-Reisner rings and Alexander duality, J. Pure Appl. Algebra, 130, 265-275 (1998) · Zbl 0941.13016
[6] Eisenbud, D., Commutative Algebra with a View towards Algraic Geometry (1995), Springer
[7] R. Fröberg, On Stanley-Reisner rings, in: Topics in Algebra, Banach Center Publications, 26 (2) (1990) 57-70; R. Fröberg, On Stanley-Reisner rings, in: Topics in Algebra, Banach Center Publications, 26 (2) (1990) 57-70
[8] J. Herzog, T. Hibi, X. Zheng, Monomial ideals whose powers have a linear resolution, 2002 (preprint); J. Herzog, T. Hibi, X. Zheng, Monomial ideals whose powers have a linear resolution, 2002 (preprint) · Zbl 1091.13013
[9] N. Terai, Generalization of Eagon-Reiner theorem and \(h\); N. Terai, Generalization of Eagon-Reiner theorem and \(h\)
[10] West, D., Introduction to Graph Theory (2001), Prentice-Hall
[11] X. Zheng, Resolutions of facet ideals, Comm. Algebra (in press); X. Zheng, Resolutions of facet ideals, Comm. Algebra (in press) · Zbl 1089.13014
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.