A Complete Classification of 2-Linear Neighborhood Complexes

Abstract

Let $G$ be a nonempty finite simple graph. We study when the Stanley-Reisner ideal of its neighborhood complex has a $2$-linear resolution. Combining Fröberg's theorem with the classical hypertree criterion, we obtain the following equivalent description in graph terms: $G$ is bipartite, its indexed open neighborhoods are Helly, and every induced cycle of length at least eight has a filling from each color class. This class properly contains the chordal bipartite graphs without isolated vertices. Hochster's formula gives all squarefree multigraded Betti numbers, while face counts determine the complete graded Betti table. If $G$ has $n$ vertices and $c$ connected components, then its Stanley-Reisner ring has terminal Betti number $2c-1$, projective dimension $n-1$, and depth one. We also determine the multiplicity and the initially Cohen-Macaulay and Cohen-Macaulay cases. A second formula separates degree data from overlaps caused by repeated common neighbors and yields closed expressions for bipartite graphs without $K_{2,3}$, cactus graphs, pseudoforests, and forests. For square cactus graphs, the Betti table recovers every degree multiplicity at least three; for forests, it recovers the complete degree sequence. Finally, the dominance complex has a $2$-linear Stanley-Reisner ideal precisely for nontrivial stars.

20 pages, 2 figures. Revised and corrected version. The principal characterization in the previous version has been replaced by the correct Helly and two-sided filling criterion