PaperlayerView exact revision on arXiv

Source-linked AI summary

Chordal and sequentially Cohen-Macaulay clutters

Russ Woodroofe

arXiv:0911.4697v4math.COmath.AC

TL;DR

The paper addresses extending chordality from graphs to clutters by introducing chordal clutters and proving properties of their independence complexes and circuit ideals. Their independence complexes are shellable and sequentially Cohen-Macaulay, and a uniform-complement result gives linear resolutions.

  • Problem

    The paper takes up extending chordality from graphs to clutters while seeking analogous algebraic and topological properties.

    Source: §1 · p. 2

  • Method

    The paper introduces chordal clutters, a family generalizing chordal graphs, matroid circuit clutters, and acyclic clutters.

    Source: §1 · p. 2

  • Results

    Chordal clutters have shellable, hence sequentially Cohen-Macaulay, independence complexes, and d-uniform ones have a linear-resolution circuit ideal for their d-uniform complement.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper provides a uniform proof of shellability for independence complexes of both chordal graphs and matroids.

    Source: §1 · p. 2

    Classifying circuit ideals with linear resolutions is equivalent to classifying all Cohen-Macaulay complexes, which is likely intractable.

    Source: §6.1 · p. 11

Abstract

from arXiv · show

We extend the definition of chordal from graphs to clutters. The resulting family generalizes both chordal graphs and matroids, and obeys many of the same algebraic and geometric properties. Specifically, the independence complex of a chordal clutter is shellable, hence sequentially Cohen-Macaulay; and the circuit ideal of a certain complement to such a clutter has a linear resolution. Minimal non-chordal clutters are also closely related to obstructions to shellability, and we give some general families of such obstructions, together with a classification by computation of all obstructions to shellability on 6 vertices.

1 Introduction

The paper introduces chordal clutters as a family extending chordal graphs and matroid circuit clutters, with shellability and algebraic properties analogous to those of chordal graphs. It proves shellability for their independence complexes and a linear-resolution result for circuit ideals of a uniform complement.

1 Introduction

  • Chordal clutters generalize chordal graphs, circuit clutters of matroids, and acyclic clutters.Source: §1 · p. 2
  • Chordal clutters have shellable independence complexes, which are therefore sequentially Cohen-Macaulay.Source: §1 · p. 2
  • The paper gives a uniform proof of shellability for independence complexes of chordal graphs and matroids.Source: §1 · p. 2
  • For a d-uniform chordal clutter, the circuit ideal of its d-uniform complement has a linear resolution.Source: §1 · p. 2
  • The introduction says a non-trivial description of circuit ideals with linear resolutions or linear quotients as a converse to the theorem is unlikely.Source: §1 · p. 2
  • The paper presents infinite families of forbidden-minor obstructions to shellability and computationally classifies those on six or fewer vertices that contain no non-shellable link.Source: §1 · p. 2

1.1 Notation

  • The notation uses C and D for clutters, G for graphs, and calligraphic letters for families of objects.Source: §1.1 · pp. 2–3

2 Background

The background establishes the correspondence between clutters and simplicial complexes, defines clutter operations and their relationship to complex operations, and reviews shellability and Cohen-Macaulay properties.

2.1 Simplicial complexes and clutters

  • An abstract simplicial complex is a family of faces closed under taking subsets, while a clutter is a family of inclusion-incomparable circuits; each determines the other through independence complexes and minimal non-faces.The paper considers finite clutters and simplicial complexes.Source: §2.1 · p. 3

2.2 Deletions and contractions, links

  • Clutter minors arise through repeated deletion or contraction, and matroid circuit clutters recover the usual matroid operations.Graph contraction as a clutter differs from matroid contraction; for general clutters, contraction cannot always be expressed through deletions.Source: §2.2 · pp. 4–5
  • Clutter deletion and contraction correspond respectively to simplicial-complex deletion and link operations on independence complexes.Specifically, I(C \ v) = I(C) \ v and I(C/v) = link_I(C) v.Source: §2.2 · p. 4

2.3 Shellable and Cohen-Macaulay complexes

  • Shellability is a combinatorial condition implying sequential Cohen-Macaulayness over any field, while Cohen-Macaulay complexes themselves are pure.Source: §2.3 · p. 5

3 k-decomposable complexes

The section extends k-decomposability to non-pure complexes and develops shedding faces as a route to shellability. It connects decomposability to shellability and applies the framework to independence complexes of chordal clutters.

3 k-decomposable complexes

  • The extension defines k-decomposability for non-pure complexes, generalizing earlier definitions for pure complexes and vertex decomposability.A complex is recursively k-decomposable when it is a simplex or has a shedding face of dimension at most k whose deletion and link are k-decomposable.Source: §3 · p. 6
  • A shedding face lets shellability be assembled from shellings of its deletion and link.The proof orders facets not containing the face first, followed by facets containing it in the link-shelling order.Source: §3 · p. 6
  • A d-dimensional complex is shellable exactly when it is d-decomposable, and k-decomposability forms a hierarchy up to that bound.Every k-decomposable complex is also (k + 1)-decomposable.Source: §3 · pp. 6–7
  • k-decomposability is preserved under links and under joins of two complexes.The join statement holds in both directions: the join is k-decomposable if and only if both component complexes are.Source: §3 · p. 7
  • For chordal clutters, k-decomposability supplies the framework used to prove that their independence complexes are shellable.The section identifies this as its main application.Source: §3 · p. 7
  • The section leaves open the smallest k guaranteed for shellable d-dimensional complexes whose non-face clutter has maximum circuit size m.It specifically asks whether every such complex is (m −1)-decomposable.Source: §3 · p. 8

4 Chordal clutters

The section defines chordal clutters through simplicial vertices in every minor, extending the graph notion. This family includes chordal graphs and matroid circuit clutters, with a stricter minor condition than a related uniform-clutter definition.

4 Chordal clutters

  • A clutter is chordal when every minor has a simplicial vertex, where a simplicial vertex satisfies a circuit-exchange condition.For graphs, this simplicial-vertex condition agrees with the usual one, and the minor definition specializes to graph chordality.Source: §4 · p. 8
  • Circuit clutters of matroids are chordal because the simplicial-vertex condition is the weak circuit exchange property at a vertex.Every vertex of a matroid circuit clutter is simplicial, and deletions and contractions remain matroids.Source: §4 · p. 8
  • Clutters with the free vertex property are chordal because a free vertex is simplicial.The passage also describes these clutters as the clutter of cliques of a chordal graph.Source: §4 · p. 9
  • Chordal clutters include examples beyond chordal graphs, matroid circuit clutters, and clutters with the free vertex property.The stated example is chordal but belongs to none of those three families.Source: §4 · p. 9
  • Unlike Emtander’s uniform-clutter definition, this definition requires simplicial vertices after both deletions and contractions.The section gives an example with simplicial vertices in every induced subclutter whose contractions leave a cyclic graph C4.Source: §4 · p. 9

5 Shellability of the independence complex

The section uses simplicial vertices and shedding faces to establish shellability for independence complexes of chordal clutters. A bound on circuit size further yields decomposability, and a graph specialization gives a vertex-decomposability condition.

5 Shellability of the independence complex

  • A neighborhood containment pair yields a shedding face, enabling the shellability argument to use simplicial vertices.For a pair (v, e), the shedding face is e\{v}; the proposition then applies when every proper contraction is shellable.Source: §5 · pp. 9–10
  • The proof removes faces associated with circuits containing the simplicial vertex, relating the links to contractions and leaving the contracted vertex isolated.The passage describes these faces as the circuits added when the vertex is contracted.Source: §5 · p. 10
  • If a clutter has maximum circuit cardinality k and every contraction has a simplicial vertex, its independence complex is (k−2)-decomposable, hence shellable and sequentially Cohen-Macaulay.For chordal clutters, this conclusion holds because every contraction is a minor.Source: §5 · p. 10
  • For graphs, if G \ N[A] has a simplicial vertex for every independent set A, then G is vertex decomposable.The section states that this graph family is considerably more general than chordal graphs.Source: §5 · p. 10

6 Linear resolutions and Alexander duality

This section extends the graph connection between chordality and linear resolutions to clutters using Alexander duality. It proves vertex decomposability for Alexander duals of complements to chordal clutters and derives linear quotients and linear resolutions, with a related result for clutters having complete-neighborhood vertices.

6 Linear resolutions and Alexander duality

  • The section generalizes the graph theorem’s implication from chordality to a linear resolution to chordal clutters, using Alexander duality to connect the algebraic and topological questions.The complement operation produces a d-uniform clutter even when the original clutter is not uniform.Source: §6 · p. 11, §6.2 · p. 12

6.1 Review of Alexander duality

  • Alexander duality characterizes linear resolutions by Cohen-Macaulayness of the dual complex, while classifying all such ideals is likely intractable.The dual complex uses facets that are complements of circuits of the non-face clutter.Source: §6.1 · p. 11

6.2 Alexander duals of complements to chordal clutters

  • When a clutter has a simplicial vertex and no circuits of size d−1, contraction commutes with taking the complement at the corresponding uniformity; a d-non-circuit after deletion makes the vertex shedding.The authors use these facts in the inductive vertex-decomposability proof.Source: §6.2 · p. 12
  • For a chordal clutter with minimum circuit size d, the Alexander dual of the independence complex of its complement is vertex decomposable, so the complement’s circuit ideal has linear quotients and a linear resolution.The proof proceeds by induction using a simplicial vertex and a shedding-vertex argument or deletion when no relevant d-non-circuit remains.Source: §6.2 · pp. 12–13
  • If every induced subclutter has a complete-neighborhood vertex, the complement’s Alexander dual is vertex decomposable and its circuit ideal has linear quotients and a linear resolution.This condition can hold even when the clutter is not chordal.Source: §6.2 · p. 13
  • For non-uniform clutters, the complement operation still outputs a d-uniform clutter, while extending the result to component-wise linear circuit ideals remains an open possibility raised by the authors.The dual of the independence complex need not be pure or Cohen-Macaulay, though it could be sequentially Cohen-Macaulay.Source: §6.2 · p. 14

7 Forbidden minors

The section frames shellability obstructions through deletion- and contraction-minimal clutters, gives infinite examples, and reports a computational classification on six vertices.

7.1 Obstructions to shellability

  • A dc-obstruction is non-shellable although every induced subcomplex and every link is shellable; d-obstructions require only induced subcomplexes to be shellable.The section notes that every pure c-obstruction is Buchsbaum.Source: §7.1 · p. 14

7.2 Examples of forbidden minors

  • Non-shellable forbidden subclutters to chordality are d-obstructions, while non-shellable forbidden minors are dc-obstructions, making forbidden minors a route to studying shellability obstructions.The authors ask whether every dc-obstruction is a forbidden minor to chordality and present infinite families that are both.Source: §7.2 · p. 15
  • The cyclic k-uniform clutters Z^k_n are forbidden subclutters to chordality unless k = n or n − 1; some are also forbidden minors, but Z^3_6 is not because it contracts to C_4.When ℓk ≤ n ≤ ℓ(k + 1) and k > 2, Z^k_n has a contraction isomorphic to Z^(k−1)_ℓ.Source: §7.2 · p. 15
  • For n > 1, X_n is a forbidden minor to chordality, and I(X_n) is a dc-obstruction: its circuits comprise the odd vertices, even vertices, and adjacent pairs starting at odd vertices.Deleting or contracting any vertex leaves the same clutter up to isomorphism, while deleting one of the two n-circuits gives a clutter with the free vertex property.Source: §7.2 · p. 16
  • For n > 1, Y_n is a forbidden minor to chordality and I(Y_n) a dc-obstruction; every proper minor of Y_n is chordal.I(Y_n) has all faces of dimension at most n − 2 and two disjoint (n − 1)-faces, so its pure (n − 1)-skeleton is disconnected.Source: §7.2 · p. 16

7.3 Computational results

  • On 6 vertices, computation found 294 forbidden minors to chordality, of which 21 are non-shellable and exactly the dc-obstructions to shellability.The 294 are isomorphism classes among 16,353 non-isomorphic clutters.Source: §7.3 · p. 16
  • None of the 21 non-shellable complexes is sequentially Cohen-Macaulay, since each has a pure top-dimensional skeleton that is a sphere of lower dimension than its top-dimensional face.The fourth column of Table 1 records the homotopy type of each pure top-dimensional skeleton.Source: §7.3 · p. 16
  • The first 16 table entries have two disjoint 2-faces with enough edges between them to prevent a non-shellable minor; entries 17–20 have an annulus of six 2-facets and additional 1-dimensional facets.Only entries 1 and 21 are of cyclic type.Source: §7.3 · pp. 16, 18
Loading 0911.4697v4…