Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2605.22808 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910266146422784 |
|---|---|
| author | Zhang, Yutong Yang, Yaoran |
| author_facet | Zhang, Yutong Yang, Yaoran |
| contents | For a graph $G$ on $[n]$, the $k$-cut complex $Δ_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 $β(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 $r=n-k\ge3$. Equivalently, for fixed $r\ge3$, the diagonal sequence $B_r(k)=β(k,k+r)$ is a polynomial in $k$ of degree $r-1$, and therefore $\nabla^rB_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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_22808 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Betti Numbers of Cut Complexes of Squared Paths and a Recurrence Conjecture Zhang, Yutong Yang, Yaoran Combinatorics For a graph $G$ on $[n]$, the $k$-cut complex $Δ_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 $β(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 $r=n-k\ge3$. Equivalently, for fixed $r\ge3$, the diagonal sequence $B_r(k)=β(k,k+r)$ is a polynomial in $k$ of degree $r-1$, and therefore $\nabla^rB_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$. |
| title | Betti Numbers of Cut Complexes of Squared Paths and a Recurrence Conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.22808 |