Betti Numbers of Cut Complexes of Squared Paths and a Recurrence Conjecture

Abstract

For a graph $G$ on $[n]$, the $k$-cut complex ${\Delta }_k(G)$ has facets $[n]\setminus T$, where $T$ ranges over the $k$-subsets that induce disconnected subgraphs of $G$. Bayer, Denker, Jelić Milutinović, Sundaram, and Xue proved that ${\Delta }_k(P_n^2)$ is shellable for $n\ge k+3$ and conjectured a finite-difference recurrence for its top reduced Betti number along each diagonal $n-k=r$. We prove the exact formula \[ β(k,n)=\binom{n-1}{k-1} -\sum_{j=0}^{\min\{k-1,n-k\}}\binom{k-1}{j}(n-k-j+1)+(n-k) \] for $k\ge 2$ and $n\ge k+3$. The proof rests on a complete classification of complements of cardinality at least $k$ that contain no disconnected $k$-subset: every such complement has size $k$ or $k+1$ and is, respectively, a connected $k$-subset of $P_n^2$ or an interval of $k+1$ consecutive vertices. For fixed $r\ge 3$, the formula is the restriction of a polynomial in $k$ of degree exactly $r-1$. Hence its $r$th backward difference vanishes identically and its $(r-1)$st backward difference is the constant $r-2$. On the topologically defined sequence, these identities hold for $k\ge r+2$ and $k\ge r+1$, respectively. We also obtain the conjectured closed forms for $k=4,5$, the complete face enumerator, and the associated $h$-polynomial and Stanley--Reisner Hilbert series.