The complex of $r$-co-connected subgraphs, chordality and Fröberg's theorem

Abstract

We introduce a new family of pure simplicial complexes, called the $r$-co-connected complex of $G$ with respect to $A$, $\hat{I}{\pounds }_r(A,G)$, where $r\ge 1$ is a natural number, $G$ is a simple graph, and $A$ is a subset of vertices. Interestingly, when $A$ is empty, this complex is precisely the Alexander dual of the $r$-independence complex of $G$. We focus on uncovering the relationship between the topological and combinatorial properties of the complex and the algebraic and homological properties of the Stanley-Reisner ideal of the dual complex. First, we prove that $\hat{I}{\pounds }_r(A,G)$ is vertex decomposable whenever the induced subgraph $G[A]$ is connected and nonempty, yielding a versatile deletion-link calculus for higher independence via Alexander duality. Furthermore, when $A=\varnothing$ and $r\ge 2$, we establish that for several significant classes of graphs - including chordal, co-chordal, cographs, cycles, complements of cycles, and certain grid graphs - the properties of vertex decomposability, shellability, and Cohen-Macaulayness are equivalent and precisely characterized by the co-chordality of the associated clutter ${\mathrm{Con}}_r(G)$. These results extend Fröberg's theorem to the setting of $r$-connected ideals for these graph classes and motivate a conjecture concerning the linear resolution property of $r$-connected ideals in general. We also construct examples separating shellability from vertex decomposability.

35 pages, 3 figures. Comments are welcome