Exposed circuits, linear quotients, and chordal clutters

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:177

Article

Dochtermann, Anton¹ 

[1] Texas State Univ, Dept Math, San Marcos, TX 78666 USA

关键词: Chordal graph;    Chordal clutter;    Monomial ideal;    Betti numbers;    Linear quotients;    Linear resolution;    Elementary collapse;    Shellable simplicial complex;   

DOI  :  10.1016/j.jcta.2020.105327

来源: Elsevier

【 摘 要 】

A graph G is said to be chordal if it has no induced cycles of length four or more. In a recent preprint Culbertson, Guralnik, and Stiller give a new characterization of chordal graphs in terms of sequences of what they call 'edge-erasures'. We show that these moves are in fact equivalent to a linear quotient ordering on I-(G) over bar, the edge ideal of the complement graph. Known results imply that I-(G) over bar has linear quotients if and only if G is chordal, and hence this recovers an algebraic proof of their characterization. We investigate higher-dimensional analogues of this result, and show that in fact linear quotients for more general circuit ideals of d-clutters can be characterized in terms of removing exposed circuits in the complement clutter. Restricting to properly exposed circuits can be characterized by a homological condition. This leads to a notion of higher dimensional chordal clutters which borrows from commutative algebra and simple homotopy theory. The interpretation of linear quotients in terms of shellability of simplicial complexes also has applications to a conjecture of Simon regarding the extendable shellability of k-skeleta of simplices. Other connections to combinatorial commutative algebra, chordal complexes, and hierarchical clustering algorithms are explored. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free