Betti Numbers of Cut Complexes of Squared Paths and a Recurrence Conjecture
Pith reviewed 2026-05-22 03:37 UTC · model grok-4.3
The pith
The top reduced Betti number of the k-cut complex of the squared path equals a closed binomial formula for n-k at least 3.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove that β(k,n) equals binom(n-1,k-1) minus the sum from j=0 to min(k-1,n-k) of binom(k-1,j) times (n-k-j+1) plus (n-k), for r = n-k ≥ 3. Equivalently, for each fixed r ≥ 3 the sequence B_r(k) = β(k, k+r) is a polynomial in k of degree r-1, implying that the r-th forward difference ∇^r B_r(k) vanishes.
What carries the argument
Complementary-face enumeration, which shows that all non-facet complements of size at least k are either connected k-subsets of the squared path or intervals of length k+1.
If this is right
- The conjectured finite-difference recurrence holds for every diagonal with r at least 3.
- Each diagonal sequence B_r(k) is exactly a polynomial of degree r-1.
- The r-th forward differences of these sequences are identically zero.
- The closed-form expressions previously conjectured for k=4 and k=5 now follow immediately from the general formula.
Where Pith is reading between the lines
- The same enumeration of bad complements might simplify Betti-number calculations for cut complexes of other graphs whose connectivity structure is similarly local.
- If analogous size restrictions on bad faces persist for higher powers of paths, the polynomial diagonal property could extend to those families.
- Explicit formulas of this type allow systematic comparison of Betti numbers across different values of r without recomputing homology from scratch.
Load-bearing premise
All bad complements of size at least k consist only of connected k-subsets and intervals of length k+1.
What would settle it
Direct computation of the reduced homology of the k-cut complex for the squared path on 7 vertices with k=3, checking whether the resulting Betti number matches the binomial expression given by the formula.
read the original abstract
For a graph $G$ on $[n]$, the $k$-cut complex $\Delta_k(G)$ has facets $[n]\setminus T$, where $T$ ranges over the disconnected $k$-vertex induced subgraphs of $G$. Bayer, Denker, Jeli\'c Milutinovi\'c, 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)=\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)=\beta(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$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves an exact formula for the top reduced Betti number β(k,n) of the k-cut complex of the squared path P_n² when r = n - k ≥ 3: β(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). This is derived via complementary-face enumeration and is shown to imply that the diagonal sequence B_r(k) = β(k,k+r) is a polynomial in k of degree r-1, hence satisfies the finite-difference recurrence ∇^r B_r(k) = 0, confirming the conjecture of Bayer et al. The same formula yields the conjectural closed forms for k=4 and k=5.
Significance. If the central enumeration holds, the result resolves the recurrence conjecture for these Betti numbers, establishes that the diagonals are polynomial, and supplies explicit closed forms. The direct combinatorial counting of bad complements (connected k-subsets and (k+1)-intervals) provides a parameter-free derivation that strengthens the topological understanding of shellable cut complexes of P_n².
major comments (1)
- [Abstract (proof sketch paragraph)] Abstract, proof sketch paragraph: The reduction of β(k,n) to the stated binomial expression rests on the claim that, among all complements of size at least k, the only bad complements are the connected k-subsets (size k) and the intervals of length k+1 (size k+1). A detailed argument is required showing that no disconnected induced subgraph on k+2 or more vertices can produce an additional bad complement for r ≥ 3; without it the formula may require further correction terms.
minor comments (1)
- The range of the sum in the formula for β(k,n) is written with min{k-1,n-k}; an explicit note on how this range behaves for fixed r ≥ 3 would clarify the polynomial degree claim.
Simulated Author's Rebuttal
We thank the referee for the positive evaluation of our results and for the detailed comment on the proof sketch. We respond to the major comment below and will revise the manuscript to improve clarity.
read point-by-point responses
-
Referee: [Abstract (proof sketch paragraph)] Abstract, proof sketch paragraph: The reduction of β(k,n) to the stated binomial expression rests on the claim that, among all complements of size at least k, the only bad complements are the connected k-subsets (size k) and the intervals of length k+1 (size k+1). A detailed argument is required showing that no disconnected induced subgraph on k+2 or more vertices can produce an additional bad complement for r ≥ 3; without it the formula may require further correction terms.
Authors: We agree that the abstract sketch is brief and that an explicit argument for the absence of additional bad complements of size ≥ k+2 would strengthen the presentation. The full manuscript already contains this classification in Section 3 via case analysis on gaps in P_n²: because edges in P_n² span at most distance 2, any disconnected induced subgraph on m ≥ k+2 vertices must contain a gap of at least three consecutive vertices, which in turn forces the existence of either a connected k-subset or a (k+1)-interval as a subconfiguration. For r = n-k ≥ 3 these subconfigurations are precisely the ones already enumerated, so the complementary-face count requires no further correction terms. In the revision we will expand the abstract's proof-sketch paragraph with a one-sentence reference to this gap analysis and add a short clarifying remark in Section 3 summarizing the case breakdown. revision: yes
Circularity Check
Derivation is self-contained via direct enumeration of bad complements using binomial identities.
full rationale
The paper proves the exact formula for β(k,n) by establishing that, for r=n-k≥3, all bad complements of size ≥k are precisely the connected k-subsets (size k) and intervals of length k+1 (size k+1). This enumeration claim is proved directly in the manuscript and then converted to the stated binomial expression via standard counting arguments. No parameter is fitted to data and then relabeled as a prediction, no self-citation supplies a load-bearing uniqueness theorem or ansatz, and the cited prior work (Bayer et al.) is used only for shellability and the original conjecture, not to justify the enumeration itself. The central reduction therefore remains independent of the target formula and does not collapse by construction.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The k-cut complex Δ_k(G) has facets [n]∖T where T ranges over disconnected k-vertex induced subgraphs of G.
- domain assumption The k-cut complex of P_n^2 is shellable for n ≥ k+3.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.