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

For a graph $G$ on $[n]$, the $k$-cut complex ${\mathrm{\Delta }}_k(G)$ has facets $[n]\setminus T$, where $T$ ranges over the disconnected $k$-vertex induced subgraphs of $G$. Bayer, Denker, Jelić Milutinović, Sundaram, and Xue proved that the $k$-cut complex of the squared path $P_n^2$ is shellable for $n\ge k+3$ and conjectured a finite-difference recurrence for its top reduced Betti number along every diagonal $n-k=r$. We prove the recurrence by giving the exact formula $\beta (k,n)=\left(\genfrac{}{}{0px}{}{n-1}{k-1}\right)-{\sum }_{j=0}^{\min \{k-1,n-k\}}\left(\genfrac{}{}{0px}{}{k-1}{j}\right)(n-k-j+1)+(n-k)$ for $r=n-k\ge 3$. Equivalently, for fixed $r\ge 3$, the diagonal sequence $B_r(k)=\beta (k,k+r)$ is a polynomial in $k$ of degree $r-1$, and therefore ${\mathrm{\nabla }}^r{B}_r(k)=0$. The proof uses a complementary-face enumeration: among complements with size at least $k$, all bad complements have size $k$ or $k+1$, and they are, respectively, connected $k$-subsets of $P_n^2$ and intervals of length $k+1$. The same formula also proves the conjectural closed forms for $k=4,5$.