Simplicial cycles and the computation of simplicial trees

DOI10.1016/J.JSC.2006.03.004MaRDI QIDQ2457409zbMATH OpenOpenAlexFDO

Authors Massimo Caboara, Sara Faridi, Peter Selinger

Publication date 23 October 2007

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0606375

zbMATH Keywords

Facet idealsimplicial cyclesimplicial tree

Mathematics Subject Classification ID

Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Analysis of algorithms and problem complexity (68Q25)

Abstract: We generalize the concept of a cycle from graphs to simplicial complexes. We show that a simplicial cycle is either a sequence of facets connected in the shape of a circle, or is a cone over such a structure. We show that a simplicial tree is a connected cycle-free simplicial complex, and use this characterization to produce an algorithm that checks in polynomial time whether a simplicial complex is a tree. We also present an efficient algorithm for checking whether a simplicial complex is grafted, and therefore Cohen-Macaulay.

Recommendations

• Tree checking for sparse complexes
• Simplicial Cohen-Macaulay complexes
• On the complexity of the representation of simplicial complexes by trees
• Cores of simplicial complexes
• Simplicial trees are sequentially Cohen-Macaulay

Cites work

• Cohen-Macaulay graphs
• Cohen-Macaulay properties of square-free monomial ideals
• Homological properties of monomial ideals associated to quasi-trees and lattices
• scientific article; zbMATH DE number 2236739 (Why is no real title available?)
• On the ideal theory of graphs
• Simplicial trees are sequentially Cohen-Macaulay
• The facet ideal of a simplicial complex
• Tree checking for sparse complexes

Cited in

(8)

• Complexes of injective words and their commutation classes
• Steinitz' theorem analogue for two-dimensional Cohen-Macaulay complexes
• Cohen-Macaulay growing graphs
• On a class of squarefree monomial ideals of linear type
• Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers
• Monomial resolutions supported by simplicial trees
• Tree checking for sparse complexes
• Square-free powers of Cohen-Macaulay simplicial forests

This page was built for publication: Simplicial cycles and the computation of simplicial trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2457409)