Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper presents an exhaustive census of connected graphs on 11 vertices to identify minimal examples of independence complexes exhibiting specific combinatorial properties. The research finds precisely two graphs whose independence complexes are Cohen-Macaulay but not shellable (over fields not of characteristic two), and six graphs where the complexes are shellable but not vertex decomposable. These findings establish concrete minimal instances of these complex combinatorial structures within graph theory.
Minimal graphs whose independence complexes are Cohen-Macaulay but not shellable are exceedingly rare, with only two identified instances.
We report on an exhaustive census of all 1,006,700,565 connected graphs on $11$ vertices to find the minimal examples of graphs whose independence complexes are Cohen-Macaulay but not shellable, or shellable but not vertex decomposable. In particular, there are exactly two graphs $G$ where ${\rm Ind}(G)$ is Cohen-Macaulay but not shellable, when the characteristic is not two, and exactly six graphs where ${\rm Ind}(G)$ is shellable but not vertex decomposable.