{"id":"dc3ec112-56fd-43e0-b571-5a7211846b86","arxiv_id":"2505.08755","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A graph-based algorithm computes minimal projective presentations and a projective implicit representation of persistent homology for arbitrary finite poset towers over Z2.","lead":"This paper gives an algorithm that turns any finite 'poset tower', a family of simplicial complexes connected by simplicial maps, into a projective matrix representation whose homology is the tower's persistent homology. It generalizes persistence computations beyond filtrations, zigzags, and grids, and could provide the algebraic foundation for efficient algorithms on arbitrary posets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Generator routine processes new simplices before their faces are active; if a simplex and a face are born at the same grade, Boundary can compute an incorrect fℓ when the face is processed later.","rationale":"The paper's central claim is that the presented algorithm computes a projective implicit representation of persistent homology for poset towers. I traced the correctness proofs for p1, p2, and fℓ. The proofs for p1 and p2 are detailed and rely on Z2 graph incidence in a way that is explicitly scoped to Z2, which the reader correctly identified as the weakest assumption. After further analysis, I found a more concrete and load-bearing gap in the pseudocode: the Generator routine calls Boundary for each new generator immediately after adding it, before all generators at that grade are added. If a simplex and one of its faces are both born at the same grade, and the face is processed later in the iteration, Boundary cannot find an active representative for that face. This causes fℓ to be computed incorrectly, and Proposition 21's proof fails because its premise (that the needed active representatives exist) is not guaranteed. This is not a theoretical subtlety: it occurs on the minimal example of a single grade containing a vertex and an edge. The fix is straightforward—process generators by nondecreasing dimension—but the paper does not state it. Therefore the algorithm as written is underspecified, and the correctness claim is conditional on this ordering choice. The reader's Z2 concern remains valid as a scoping limitation, but it is not the most load-bearing issue for the paper's central algorithmic claim.","tokens_in":33041,"tokens_out":35756,"duration_ms":346607,"concrete_test":"Take P={x0} and K(x0) consisting of vertices v,w and edge e=vw, with S={g^x0_v, g^x0_w, g^x0_e}. Run Presentation with Generator iterating S in alphabetical order (e before v,w). Inspect f_1: if the column for g^x0_e is zero instead of having 1s in rows g^x0_v and g^x0_w, the boundary lift is wrong; the PiRep homology will then differ from the true persistent homology over Z2. Re-run with the only change being that S is sorted by dimension (v,w before e) and confirm the column becomes (1,1) and the homology matches. This isolates the ordering assumption.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The Generator routine (Section 3) adds new generators at a grade x in an unspecified order: 'For all g^x_σ∈S add (σ,g^x_σ) to L^x_act ... Call Boundary(x, σ)'. Boundary looks up the faces of σ in the current active set L^x_act. If a face τ of σ is also born at x, it is added to L^x_act only when its own iteration is reached. If the iteration order processes σ before τ, τ is not yet active, and Boundary cannot find a representative for that face. Consequently fℓ(g^x_σ) omits the boundary term, so the lift fℓ of ∂ℓ is wrong. Proposition 21's proof assumes these active representatives exist at the time of the call, but the pseudocode does not guarantee this invariant. This is not a coefficient-field issue; it affects the Z2 case the paper targets. The fix is to iterate over S in nondecreasing simplex dimension (or to call Boundary only after all generators at x are added), but the paper states neither. As written, the algorithm is underspecified and can produce an incorrect PiRep on inputs where a simplex and a face appear at the same grade.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a framework for computing a projective implicit representation (PiRep) of the persistent homology of a poset tower K:P->SCpx over a finite poset P and over the field Z2. It represents each chain module C_l(K) by a minimal presentation p1_l, lifts the boundary maps d_l to maps f_l on the projective generators, computes an asymptotically minimal second term p2_l via relations among relations, and then assembles a two-term PiRep using correction maps gamma and vartheta that are obtained by solving linear systems whose coefficient matrices have at most two non-zero entries per column. The main complexity claims are O(nt log n) for p1, O(n^2 t) for the construction of p2 via RelRel, and O(n^2 t0^2) for the full PiRep computation.","tokens_in":1074,"tokens_out":1009,"duration_ms":178791,"significance":"If the correctness issues are resolved, this is a substantive and original contribution. The graph-theoretic interpretation of presentations and the linear-time solver for multigraph incidence systems are elegant and likely to be useful beyond the specific setting of poset towers. The paper is largely self-contained, and the diagram-chasing proofs for Propositions 39-40 and Theorem 41 are detailed and credible. The authors are also explicit that the entire development is over Z2, which is a scope limitation but not a hidden flaw. However, the pseudocode has a load-bearing underspecification in the Generator/Boundary ordering that currently prevents the algorithm from being correct as written; this is fixable with a local modification.","major_comments":[{"comment":"The iteration order in Generator step 1 is unspecified, but correctness of the boundary lift depends on it. The pseudocode adds each new generator (sigma,g^x_sigma) to L^x_act and immediately calls Boundary(x,sigma). If a face tau of sigma is also born at grade x, its representative (tau,g^x_tau) is added only when the loop reaches tau. In an arbitrary order with sigma before tau, Boundary(x,sigma) cannot find tau in L^x_act, so the column for g^x_sigma in f_l omits the boundary term tau. Proposition 21 asserts that Boundary finds active representatives of d_sigma, but no invariant or ordering in the algorithm guarantees this. This is load-bearing: f_l is the lift used in equations (5), (13), and Theorem 41, so on inputs where a simplex and a face share a birth grade, the computed PiRep can be wrong. The fix is local: insert all new generators into L^x_act before calling Boundary, or iterate S in nondecreasing simplex dimension; the existing proofs then apply.","section":"Section 3, Algorithm Generator and Boundary; Section 4.1, Proposition 21"}],"minor_comments":[{"comment":"Proposition 19 has a typo: the statement 'Let g^y_sigma in and y <= x in P' is missing the set S_l.","section":"Proposition 19"},{"comment":"Section 5.1 refers to 'Appendix 5' for the proofs of the PiRep results; the proofs actually appear in Appendix A.","section":"Section 5.1"},{"comment":"The field Z2 is fixed only in Section 2, but the abstract describes vector spaces without specifying the field; since all incidence computations and projective-cover arguments are characteristic-2 specific, the abstract should state this scope.","section":"Abstract and Section 2"},{"comment":"The pseudocode for the pair loop in Generator step 2 should state explicitly whether the loop iterates over L^x_act as it is at entry or as it is updated by deletions; the worked example suggests a specific semantics, but the pseudocode as written is ambiguous.","section":"Algorithm Generator, step 2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a solid contribution conditional on fixing the Generator/Boundary ordering issue. I do not see grounds for rejection; the needed fix is local and can be verified by rerunning the existing proofs. I would be comfortable with acceptance after a careful revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this paper. First, it is a genuine theoretical step forward: it gives the first fully general way to turn an arbitrary finite poset tower into a projective implicit representation (PiRep), which is what existing minimal-presentation algorithms need as input. The observation that the presentation matrix of Cℓ(K) is almost a P-filtered graph boundary matrix, and the use of graph incidence structure to solve lift equations in linear time per column, are clever and worth borrowing. Second, there is a real bug in the pseudocode. In the Generator routine, new generators at a grade x are added to the active set one by one, and Boundary for a simplex σ is called immediately. If a face τ of σ is also born at x, and the iteration over S reaches σ before τ, then τ is not yet in Lx_act. Boundary cannot find it, so fℓ(gx_σ) omits the boundary term. Proposition 21's proof assumes the needed representatives are active at the time of the call, but the algorithm as written does not guarantee this. This is not a coefficient-field nuance; it breaks the lift fℓ, and since the PiRep construction depends on fℓ, Theorem 41 is compromised on those inputs. The fix is straightforward—sort S by nondecreasing simplex dimension, or add all generators at x to Lx_act before computing boundaries—but the paper states neither. As written, the algorithm is underspecified and can produce an incorrect PiRep.\n\nWhat the paper does well: it is self-contained, the algebraic framework over Z2 is cleanly set up, and the proofs of p1 minimality and p2 exactness are detailed. The linear-system solver for γ and ϑ via tree incidence matrices is a nice and nontrivial simplification. The complexity claims are explicit and plausible. The Z2-only scope is stated clearly and is acceptable for a theory paper, though it means the graph solver does not transfer to other fields.\n\nMinor soft spots: no implementation, which is normal here, and the RelRel/Reduce complexity discussion is compressed but not obviously wrong. The generator-ordering issue is the load-bearing one.\n\nWho this is for: researchers working on multiparameter, zigzag, or general poset persistence who need algebraic input for minimal-presentation algorithms. With the bug fixed, this is a solid contribution worth having. As it stands, I would not trust the algorithm on inputs where a simplex and a face are born at the same grade.\n\nRecommendation: send to peer review, but ask the authors to fix the Generator ordering and re-prove Proposition 21 accordingly. I would want to see the revision before accepting.","headline":"Genuinely new and mostly sound algorithm for projective implicit representations of poset towers, but the Generator routine as written has a same-grade face-ordering bug that can break the boundary lift; fixable, but a revision is needed.","tokens_in":33765,"tokens_out":3190,"would_cite":false,"duration_ms":32858,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["55N31","55U10","06A07"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that the persistent homology of any poset tower—simplicial complexes connected by arbitrary simplicial maps over a finite poset—can be represented by projective modules and graded matrices computed from graph-structured…","keywords":["persistent homology","poset tower","projective resolution","minimal presentation","P-graded matrices","simplicial maps","multiparameter persistence","graph incidence"],"falsifier":"Run the algorithm on the paper's own working example, the tower in Figure 11 where two copies of a vertex are identified at two grades and then the two relations become dependent, and compare grade by grade the homology of the PiRep with the direct homology of the simplicial complexes $H_\\ell(K(x))$; any grade where $\\ker d_\\ell / \\operatorname{im} d_{\\ell+1}$ has the wrong dimension would refute Theorem 41. A second check is to verify that for a tower with two incomparable joins followed by a later join, every cycle-closing relation is omitted from $p^1_\\ell$, so the number of columns equals the minimal number of relations.","tokens_in":32861,"feed_emoji":"🧮","tokens_out":7584,"duration_ms":74407,"temperature":0.7,"pith_summary":"Persistent homology is usually computed from filtrations, where each chain module is free and boundary maps are graded matrices. The paper treats poset towers—simplicial complexes linked by arbitrary simplicial maps over any finite poset—where chain modules can be non-projective and carry relations, so no such matrix representation exists. It claims that a short chain complex of projective modules and $P$-graded matrices, called a projective implicit representation (PiRep), can be built directly from the tower and has the same homology. The construction is combinatorial: simplex generators and the relations that identify or kill them are read off from a graph, and the paper gives algorithms whose complexity is near-quadratic in the tower size rather than cubic in the output matrices. If correct, this supplies the missing algebraic input that lets existing minimal-presentation algorithms run on arbitrary finite poset towers.","feed_headline":"A relation graph turns poset towers into persistence matrices","feed_subtitle":"Graph-shaped resolutions let existing minimal-presentation algorithms run on arbitrary poset towers, not just filtrations.","key_machinery":"The load-bearing object is a $P$-filtered graph whose vertices are the simplex generators plus one distinguished `graveyard' vertex $\\Omega$, and whose edges are the relations: identifying two copies of a simplex, or killing a simplex that collapses to a lower dimension. Because every column of the presentation matrix $p^1_\\ell$ has one or two non-zero entries, the matrix is the incidence matrix of this graph. Minimality of the presentation is enforced by adding an edge only when it closes no cycle, so the chosen relations form a spanning forest; cycles in the relation graph become the relations-of-relations matrix $p^2_\\ell$. The same graph structure makes the correction maps $\\gamma$ and $\\vartheta$ computable by solving linear systems whose coefficient matrix is a graph incidence matrix, which the paper solves in linear time per system by leaf elimination on trees. This converts what would be cubic algebraic reduction into graph algorithms on forests.","core_discovery":"On its own terms, the paper establishes that for every poset tower over a finite poset $P$, the homology $H_\\ell(K)$ is isomorphic to the homology of a short chain complex of projective modules $D_{\\ell-1} \\xleftarrow{d_\\ell} D_\\ell \\xleftarrow{d_{\\ell+1}} D_{\\ell+1}$ whose maps are represented by $P$-graded matrices (Theorem 41). The construction starts from minimal projective presentations of each chain module $C_\\ell(K)$: generators are the simplex generators of the tower, relations are recorded in a matrix $p^1_\\ell$ whose columns are edges of a $P$-filtered graph, and the second-level relations form $p^2_\\ell$. The boundary maps of the simplicial chain complex are lifted to these resolutions, and two correction maps $\\gamma$ and $\\vartheta$ are added to repair the failure of the lifts to compose to zero. The result is a diagram that plays the role of the classical graded boundary matrix for one-parameter persistence, and it is computed in $O(n^2 t_0^2)$ time for a tower of size $n$ over a poset with $t_0$ elements.","pith_inferences":["The graph-forest viewpoint suggests that for structured posets such as $d$-dimensional grids or zigzag grids, the same relation cycles may be computable with specialized union-find or dynamic-connectivity data structures, potentially shaving the $t_0$ factors in the $O(n^2 t_0^2)$ bound.","If the method is adapted to finite fields of odd characteristic, the incidence-graph picture would need oriented edges and signed columns; the characteristic-$2$ symmetry that makes two-entry columns sufficient would break, so a different encoding of killing relations would be required.","The PiRep construction may also give a route to computing bigraded Betti numbers or other homological invariants of multiparameter persistence for towers with multi-critical simplices, not just presentations of homology, by reading ranks of the matrices at each grade.","Since the relation graph's spanning forest encodes a minimal set of simplex identifications, it could be reused across all dimensions: the $0$-dimensional relations determine vertex collapses that constrain higher-dimensional generators, which the paper exploits but does not fully develop into a single-pass multi-degree algorithm."],"forward_implications":["Any poset tower, including multifiltrations with multi-critical simplices, zigzag towers, and arbitrary simplicial maps, can be fed into existing minimal-presentation algorithms once a PiRep is computed.","The PiRep of $H_\\ell$ has size governed by the first two Betti numbers of the resolution: $p^1_\\ell$ has $O(n t_0)$ columns and $p^2_\\ell$ has $O(n t_1)$ columns, so downstream presentation algorithms start from asymptotically minimal input.","The computation runs in $O(n^2 t_0^2)$ time dominated by the correction lifts, instead of the cubic-in-output time of general matrix reduction; the relation graph itself costs $O(n t \\log n)$.","Over $\\mathbb{Z}_2$, the algorithms are fully general over arbitrary finite posets, not restricted to grids or one-critical filtrations.","A computed PiRep can be converted to a minimal presentation of $H_\\ell$ by an existing exactification routine, with only superfluous relations to remove."],"supporting_citations":[{"why":"Supplies the MakeExact procedure and the injective-resolution framework that turns a PiRep into a minimal presentation of $H_\\ell$ and justifies projective-cover minimality.","marker":"[4]"},{"why":"Provides the free implicit representation concept that PiRep adapts by replacing free with projective modules, and gives a bi-graded minimal-presentation algorithm consuming such input.","marker":"[19]"},{"why":"Gives the two-parameter minimal-presentation algorithm whose input requirements motivate needing a free/projective implicit representation.","marker":"[22]"},{"why":"Introduces simplicial towers and their interval-module chain modules, the setting that poset towers generalize.","marker":"[9]"},{"why":"Offers the earlier combinatorial conversion of multifiltrations to free implicit representations, the direct predecessor for grid-indexed inputs.","marker":"[7]"},{"why":"Provides graph-based minimal presentation algorithms for zero-dimensional persistent homology over posets, the case that $p^1_\\ell$ exploits.","marker":"[24]"},{"why":"Supplies the union-find data structure used for cycle detection in the relation graph, supporting the near-linear complexity claims.","marker":"[8]"}],"fun_headline_variants":["PiRep: a graph path to persistence on any poset","Graph-shaped resolutions make poset persistence computable","New algorithm turns any poset tower into persistence matrices","Projective implicit representations for general persistence","From towers to matrices: a graph-based shortcut for homology"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction is carried out over the two-element field $\\mathbb{Z}_2$: a relation is encoded as a sum of two generator symbols, and the graph incidence picture relies on the fact that every column has one or two entries with signs collapsed.","fun_headline_variants_meta":{"raw":{"variants":["PiRep: a graph path to persistence on any poset","Graph-shaped resolutions make poset persistence computable","New algorithm turns any poset tower into persistence matrices","Projective implicit representations for general persistence","From towers to matrices: a graph-based shortcut for homology"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000307,"raw_usage":{"total_tokens":1864,"prompt_tokens":1157,"completion_tokens":707,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":773,"completion_tokens_details":{"reasoning_tokens":632}},"tokens_in":773,"tokens_out":707,"duration_ms":7012,"temperature":1.0,"reasoning_tokens":632,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:48:02.089129+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm on the paper's own working example, the tower in Figure 11 where two copies of a vertex are identified at two grades and then the two relations become dependent, and compare grade by grade the homology of the PiRep with the direct homology of the simplicial complexes $H_\\ell(K(x))$; any grade where $\\ker d_\\ell / \\operatorname{im} d_{\\ell+1}$ has the wrong dimension would refute Theorem 41. A second check is to verify that for a tower with two incomparable joins followed by a later join, every cycle-closing relation is omitted from $p^1_\\ell$, so the number of columns equals the minimal number of relations.","supporting_citations":[{"cited_title":"Discrete Microlocal Morse Theory","cited_arxiv_id":"2209.14993","evidence_quote":"Supplies the MakeExact procedure and the injective-resolution framework that turns a PiRep into a minimal presentation of $H_\\ell$ and justifies projective-cover minimality."},{"cited_title":"Fast minimal presentations of bi-graded persistence modules","cited_arxiv_id":null,"evidence_quote":"Provides the free implicit representation concept that PiRep adapts by replacing free with projective modules, and gives a bi-graded minimal-presentation algorithm consuming such input."},{"cited_title":"Computing minimal presentations and bigraded betti numbers of 2-parameter persistent homology","cited_arxiv_id":null,"evidence_quote":"Gives the two-parameter minimal-presentation algorithm whose input requirements motivate needing a free/projective implicit representation."},{"cited_title":"Computing topological persistence for simplicial maps","cited_arxiv_id":null,"evidence_quote":"Introduces simplicial towers and their interval-module chain modules, the setting that poset towers generalize."},{"cited_title":"Combinatorial presentation of multidimensional persistent homology","cited_arxiv_id":null,"evidence_quote":"Offers the earlier combinatorial conversion of multifiltrations to free implicit representations, the direct predecessor for grid-indexed inputs."},{"cited_title":"Computing betti tables and minimal presentations of zero-dimensional persistent homology","cited_arxiv_id":null,"evidence_quote":"Provides graph-based minimal presentation algorithms for zero-dimensional persistent homology over posets, the case that $p^1_\\ell$ exploits."}],"review_version":1}