{"id":"6157a1b4-eb59-48e7-a110-99e355b83abb","arxiv_id":"2607.07404","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Network realignment complexes over arbitrary connected graphs admit an equivariant deformation retraction onto a complete graph plus discrete space; for complete graphs, diameter bounds and Aut(X_n) ≅ S_n (n≥5) are established.","lead":"This paper extends network realignment complexes from complete graphs to arbitrary connected graphs, characterizing their topology, geometry, and symmetries. A generalist might read it to understand how the space of tree-reconfiguration moves changes when the underlying graph loses edges.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Proposition 2.20 case (b) acyclicity argument has a gap: a vertex specified away from the spine can later re-enter Act_Y via cospecification, breaking the monotonicity claim.","rationale":"The reader correctly identified the acyclicity argument in Proposition 2.20 case (b) as the weakest link. The concern is real and specific: the proof's claim that |B ∖ Act_Y| decreases monotonically along a putative cycle requires that no vertex can re-enter Act_Y after leaving it, but the argument does not rigorously establish this. The structural changes to the tree T under cospecifications of other active vertices could potentially cause a previously inactive vertex to become active. This is the single most load-bearing concern because Theorem 2.1 depends entirely on ∼ being a valid generalised Morse matching, which in turn requires acyclicity. If the acyclicity proof has a gap, the equivariant deformation retraction onto Y_G is not established, and the main topological result fails. The rest of the paper (diameter bounds, automorphism group computation) is largely independent of this specific argument, but the central topological claim is at risk. The concern could be settled by either a more rigorous proof that |B ∖ Act_Y| is strictly monotone (showing that the tree structural changes cannot cause re-entry into Act_Y), or by computational verification on small cases. Given that the argument is dense and the invariant is not obviously monotone under all possible operations, a conditional verdict is appropriate until this is clarified. The paper's other contributions (flag complex property, diameter bounds, Aut(X_n) ≅ S_n) appear to be on firmer ground and use independent methods.","tokens_in":42002,"tokens_out":1048,"duration_ms":286430,"concrete_test":"Construct a small explicit example (e.g., n=6 or n=7, base graph K_n with a few edges removed to create barriers) and search computationally for a cycle in the matching relation ∼. Specifically: enumerate all network realignments, compute the intervals [d_Y(N), u_Y(N)], build the directed graph where edges go from Ñ_{i+1} to N_i when they are in different equivalence classes with Ñ_{i+1} < N_i, and check for directed cycles. If a cycle is found, the matching is not acyclic and Theorem 2.1 fails. If no cycle is found for small cases, the monotonicity argument may hold but needs a more rigorous proof that tracks the invariant more carefully.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The acyclicity proof of the generalised Morse matching in Proposition 2.20 is the linchpin of Theorem 2.1. The proof argues by contradiction assuming a cycle exists. In case (b), a vertex v ∉ Act_Y(N_i) is specified, and the proof claims: 'Since v ∉ Act_Y(Ñ_i), it can never be cospecified later. Consequently, the sequence |B ∖ Act_Y| decreases along the cycle, preventing a return to Ñ_1.' The concern is that the claim 'it can never be cospecified later' conflates two distinct conditions. A vertex v is in Act_Y^-(N) when v is a leaf of T whose parent is an unoccupied leaf of Sp(N). The fact that v ∉ Act_Y(Ñ_i) at one point does not logically prevent v from entering Act_Y at a later step Ñ_j, because the tree structure changes under specifications and cospecifications by other vertices. Specifically, when other vertices are cospecified (moving from N_j to Ñ_{j+1} via u_Y), the tree T changes: vertices in Act_Y^-(N_j) are removed from T. This can alter which vertices are leaves of T and which leaves of the spine are unoccupied. A vertex v that was specified to an interior vertex of the spine (and hence not in Act_Y^-(Ñ_i) because it is not a leaf of T) could potentially become a leaf of T after other cospecifications remove vertices, and if its parent then becomes an unoccupied leaf of the spine, v would enter Act_Y^-. The proof's assertion that |B ∖ Act_Y| decreases monotonically requires that no vertex can transition from B ∖ Act_Y back into Act_Y at any point along the cycle. But the argument as written only shows that a specified vertex cannot be cospecified *at the moment it is specified*; it does not establish that the vertex cannot re-enter Act_Y later through structural changes caused by other operations. If such a re-entry is possible, the monotonic decrease of |B ∖ Act_Y| fails, and the cycle is not ruled out. The key question is: can a sequence of (co-)specifications of active vertices cause a previously inactive specified vertex to become active? The稠","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"The paper generalizes Kozlov's network realignment complexes from the complete graph $K_n$ to arbitrary connected base graphs $G$. The main results are: (1) an $Aut(G)$-equivariant strong deformation retraction of $X_G$ onto $K_{S_G} sqcup D_G$ (Theorem 2.1), where $S_G$ is the set of universal vertices and $D_G$ is a discrete $Aut(G)$-space; (2) explicit upper and lower bounds on the diameter of the network realignment graph $mathcal{G}_n$ (Theorem 3.3); (3) a proof that $X_n$ is a cubical flag complex (Lemma 4.3); and (4) a determination of $Aut(X_n) cong S_n$ for $n geq 5$ (Theorem 4.14). The proofs use equivariant generalized discrete Morse theory, combinatorial optimization, and 4-cycle completion arguments.","tokens_in":42337,"tokens_out":1367,"duration_ms":541011,"significance":"The paper makes substantial contributions to the topology and geometry of reconfiguration complexes. The equivariant Morse-theoretic framework (Theorem 2.1, Appendix A) extends Freij's theory to cubical complexes and yields a clean, parameter-free homotopy type for arbitrary base graphs. The diameter bounds (Theorem 3.3) partially answer an open question of Kozlov. The automorphism result (Theorem 4.14) is a strong rigidity statement. The cubical flag complex property (Lemma 4.3) and the 4-cycle completion argument (Proposition 4.11) are well-constructed. The matching distance lower bound (Proposition 3.22) is an elegant auxiliary tool. The paper is essentially self-contained.","major_comments":[{"comment":"Proposition 2.20, case (b): The acyclicity argument claims that a vertex $v notin Act_Y(N_i)$ 'can never be cospecified later,' and hence $|B setminus Act_Y|$ decreases monotonically along any putative cycle. This claim requires more careful justification. A vertex $v$ is in $Act_Y^-(N)$ when $v$ is a leaf of $T$ whose parent is an unoccupied leaf of $Sp(N)$. The fact that $v notin Act_Y(tilde{N}_i)$ at one step does not, by itself, prevent $v$ from entering $Act_Y$ at a later step $tilde{N}_j$: cospecifications of other vertices (via $u_Y$) modify the tree $T$ by removing vertices in $Act_Y^-(N_j)$, which can alter which vertices are leaves of $T$ and which spine leaves are unoccupied. A vertex specified to an interior vertex of the spine could potentially become a leaf of $T$ after such removals, and if its parent then becomes an unoccupied spine leaf, it would enter $Act_Y^-$. The mon","section":null},{"comment":"Proposition 2.20, case (b) (continued): monotonicity claim on $|B setminus Act_Y|$ is load-bearing for the acyclicity of the Morse matching, which in turn is the foundation of Theorem 2.1. The authors should either prove that the tree modifications along the cycle cannot reintroduce a vertex into $Act_Y$, or provide a more robust monotone quantity. Note that the analogous argument in Proposition 2.29 (for the matching on $M_G setminus Sigma_G$) uses a different, cleaner monotonicity argument based on $Act_M$ and equation (2.4), which does not appear to suffer from the same issue.","section":null}],"minor_comments":[{"comment":"Section 3.4, proof of Proposition 3.22: The proof is given only for $n=4k$. The modifications for the other congruence classes are described briefly. It would help the reader to at least state the matching $M$ and the trees $T_1, T_2$ explicitly for one odd case (e.g., $n=4k+1$), since the unmatched vertex introduces a subtlety.","section":null},{"comment":"Lemma 3.6, equation (3.1): The equality case for even $n$ is proved by a parity argument. The logic is sound but the exposition is slightly compressed; explicitly stating that $min(a, n-a)$ and $min(a-1, n-a+1)$ have opposite parity when $n$ is even would improve readability.","section":null},{"comment":"Figure 2: The projection of $X_G$ for $G = K_5 setminus {e}$ is difficult to parse. The caption mentions violet squares and grey 3-cubes, but the distinction is not immediately clear in the figure. Consider enlarging or adding a schematic.","section":null},{"comment":"Section 4.2, proof of Lemma 4.7: The notation $T^{v rightsquigarrow u}$ is defined in Definition 4.6, but the operation $tilde{T}^{v_1 rightsquigarrow i}$ used in the proof involves sliding to a vertex $i$ rather than to a vertex $u$ adjacent to $p_T(v)$. Clarify that $i$ plays the role of $u$ here, or adjust notation.","section":null},{"comment":"Corollary 2.47: The formula for $f(n)$ involves a sum with a $k!$ factor inside. It would be helpful to verify this formula for small $n$ (e.g., $n=5,6$) and state the values explicitly, to assist the reader in checking the enumeration.","section":null},{"comment":"The paper states that computations suggest the upper bound in Theorem 3.3 is sharp for $6 leq n leq 9$. It would strengthen the paper to include a table of these computed diameters alongside the bounds.","section":null}],"recommendation":"major_revision","confidential_remarks":"The skeptic's concern about Proposition 2.20 case (b) is, in my assessment, a genuine gap that needs to be addressed. The monotonicity argument is the linchpin of the Morse matching acyclicity, and the claim that a vertex specified away from the spine can never re-enter $Act_Y$ is not adequately justified given that cospecifications modify the tree structure. I recommend major revision primarily to give the authors the opportunity to either close this gap or replace the argument with a more robust one. The rest of the paper is strong and the other proofs appear sound."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for a careful and constructive report. The referee identifies a genuine gap in the acyclicity argument for Proposition 2.20, case (b), which we acknowledge and will repair. No other major comments were raised.","responses":[{"response":"The referee is correct that the monotonicity argument in case (b) of Proposition 2.20 is not adequately justified as written. The claim that a vertex v not in Act_Y(N_i) 'can never be cospecified later' does not follow from v not being active at a single step, because the tree modifications induced by cospecifications via u_Y can change which vertices are leaves of T and which spine leaves are unoccupied. We have carefully re-examined the argument and confirmed that the gap is real: the quantity |B setminus Act_Y| is not, by itself, obviously monotone along a putative cycle, for precisely the reason the referee identifies. We will revise the proof to use a more robust monotone quantity. Specifically, we observe that along any step N_i > tilde{N}_{i+1} in the putative cycle, a vertex v in B setminus Act_Y(N_i) is specified to an interior vertex of the spine (since specifying to a leaf of the spine would keep v in Act_Y). Once specified to an interior spine vertex, v enters A and becomes part of the spine Sp(N) for all subsequent cells in the cycle (since all cells in the cycle share the same spine by Lemma 2.18). A vertex that lies in the interior of the spine cannot become a leaf of T whose parent is an unoccupied leaf of Sp(N), because interior spine vertices are, by definition, not leaves of the spine. The key observation is that the spine is invariant along the entire cycle (Lemma 2.18), so the set of interior spine vertices is fixed. A vertex specified to an interior spine vertex remains in the interior of the spine for all subsequent steps, and hence can never enter Act_Y^- (which requires being a leaf of T whose parent is an unoccupied leaf of Sp(N)). This gives a genuine monotone quantity: the number of vertices in B that are not active strictly decreases at each","revision_made":"no","referee_comment":"Proposition 2.20, case (b): The acyclicity argument claims that a vertex v not in Act_Y(N_i) 'can never be cospecified later,' and hence |B setminus Act_Y| decreases monotonically along any putative cycle. The referee argues this claim requires more careful justification, because cospecifications of other vertices modify the tree T by removing vertices in Act_Y^-(N_j), which can alter which vertices are leaves of T and which spine leaves are unoccupied. A vertex specified to an interior vertex of the spine could potentially become a leaf of T after such removals, and if its parent then becomes an unoccupied spine leaf, it would enter Act_Y^-."},{"response":"We agree with the referee's observation that the argument in Proposition 2.29 is cleaner and does not suffer from the same issue. The monotonicity in Proposition 2.29 relies on equation (2.4), which gives an explicit description of the non-active vertices as the neighbourhood of the occupied vertex u_N, and the inclusion N_{T_i}(u_{N_i}) subseteq N_{tilde{T}_{i+1}}(u_{tilde{N}_{i+1}}) provides a clean, strictly monotone quantity. We will revise the proof of Proposition 2.20, case (b), to provide a similarly rigorous argument. As described in our response to the first comment, the spine invariance along the cycle (Lemma 2.18) provides the needed monotonicity: once a non-active vertex in B is specified to an interior spine vertex, it remains in the interior of the invariant spine and can never re-enter Act_Y. This makes |B setminus Act_Y| genuinely strictly decreasing along the cycle, yielding the desired contradiction. We will rewrite the proof to make this argument explicit and self-contained, rather than relying on the brief and insufficient justification currently in the manuscript.","revision_made":"no","referee_comment":"Proposition 2.20, case (b) (continued): The monotonicity claim on |B setminus Act_Y| is load-bearing for the acyclicity of the Morse matching, which in turn is the foundation of Theorem 2.1. The referee notes that the analogous argument in Proposition 2.29 uses a different, cleaner monotonicity argument based on Act_M and equation (2.4), which does not suffer from the same issue."}],"tokens_in":41815,"tokens_out":970,"duration_ms":421797,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"This paper generalizes Kozlov's network realignment complexes from K_n to arbitrary connected graphs G. The main results: (1) X_G admits an Aut(G)-equivariant deformation retraction onto K_{S_G} ⊔ D_G, where S_G is the set of universal vertices and D_G is discrete; (2) explicit diameter bounds for G_n answering a question of Kozlov; (3) Aut(X_n) ≅ S_n for n ≥ 5. All three are new and non-trivial. The cubical flag complex proof (Lemma 4.3) is clean — the argument that the slid leaf depends only on the coordinate direction, via adjacent transpositions and 4-cycle uniqueness, is the right approach and well executed. The diameter bounds via Φ_c, Ψ, and the matching distance δ are parameter-free and give tight results for small n (verified computationally for 6 ≤ n ≤ 9). The automorphism group argument via 4-cycle completion (Proposition 4.11) is the most intricate piece and is carried out carefully, with the two-case analysis (centroid structure) handling the obstruction that Ψ alone cannot always find the needed 4-cycle. The equivariant Morse theory appendix is a legitimate adaptation of Freij's work to cubical complexes with the subcomplex condition, and the proof is self-contained. The examples in Section 2.5 (K_n minus a path) give concrete orbit counts and show the machinery produces real output. Now the soft spot. The stress-test flags Proposition 2.20 case (b), the acyclicity proof for the generalised Morse matching. The concern is specific: the proof claims that a vertex v ∉ Act_Y(Ñ_i) can never be cospecified later, and that |B ∖ Act_Y| decreases monotonically. On careful reading, I think this concern partially lands but does not sink the argument. The claim that v 'can never be cospecified later' is too terse — the tree structure does change under cospecifications of other active vertices, and a vertex that is interior to the spine at one step could in principle become a leaf later. However, the key observation is that specifying v to an interior vertex of the spine means v is now in A and attached to the spine; for v to re-enter Act_Y^-, it would need to become a leaf of T whose parent is an unoccupied leaf of the spine. The matching is defined so that all active vertices are simultaneously (co-)specified within an interval, and Lemma 2.14 shows the spine and active set are invariant within an interval. The monotonicity of |B ∖ Act_Y| across distinct intervals needs a more explicit argument than the paper gives, but the structural constraints (spine preservation, Lemma 2.19's inclusion) make it plausible that the claim holds. This is a gap in exposition, not clearly a gap in mathematics — but it is the load-bearing step for Theorem 2.1, and a referee should ask for it to be written out in full. This paper is for combinatorial topologists and reconfiguration theorists. It deserves a serious referee. The diameter bounds and automorphism result are solid and self-contained. The equivariant Morse theory argument needs one proof step expanded.","headline":"Solid extension of Kozlov's network realignment complexes to general graphs, with one proof gap worth checking","tokens_in":43113,"tokens_out":739,"would_cite":true,"duration_ms":343286,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05E45","57Q05","05C05","55U10"],"pacs":[],"model":"glm-5.2","headline":"Network realignment complexes retract onto star trees","keywords":["network realignment complex","leaf slide","spanning tree reconfiguration","equivariant discrete Morse theory","cubical complex","automorphism group","graph diameter","flag complex"],"falsifier":"Construct a connected graph G where the claimed Aut(G)-equivariant deformation retraction of X_G onto K_{S_G} ⊔ D_G fails because the Morse matching is cyclic (a cycle exists in the matching relation) or because the critical cells do not form a subcomplex.","tokens_in":42100,"feed_emoji":"🌳","tokens_out":1601,"duration_ms":247040,"temperature":0.7,"pith_summary":"This paper generalizes Kozlov's network realignment complexes from complete graphs to arbitrary connected base graphs G. The central objects are the network realignment complex X_G (a cubical complex encoding simultaneous independent leaf-slide reconfigurations of spanning trees of G) and, for the complete graph K_n, the network realignment graph G_n (its 1-skeleton, encoding single leaf slides). The paper's three main contributions are: (1) For any connected G, X_G admits an Aut(G)-equivariant strong deformation retraction onto the disjoint union of a complete graph K_{S_G} (whose vertices are the star trees of G) and a discrete Aut(G)-space D_G. This means the equivariant homotopy type is completely determined: the only possibly non-trivial component is a complete graph on the vertices of G that support star trees. (2) For K_n, explicit upper and lower bounds on the diameter of G_n are established, partially answering an open question of Kozlov. The upper bound is n^2/2 - n (even n) or (n^2-1)/2 - n (odd n); the lower bound is floor((3n^2-4n)/8) (even) or floor((3n^2-6n)/8) (odd). The key mechanism is the invariant Ψ(T), which counts edge-by-edge imbalance in the tree and changes by at most one per leaf slide, providing a tight lower bound on distance to the nearest star tree when the target center is a centroid. (3) For n ≥ 5, every automorphism of X_n is induced by a vertex relabeling, so Aut(X_n) ≅ S_n. This is proved by first showing X_n is a cubical flag complex (determined by its 1-skeleton), then identifying a rigid subcomplex H whose automorphism group is S_n, and showing H is closed under 4-cycle completion in G_n, forcing any automorphism of G_n to be determined by its restriction to H.","feed_headline":"Spanning-tree reconfiguration complexes collapse to star trees","feed_subtitle":"For any connected graph, the cubical complex of leaf-slide reconfigurations equivariantly retracts onto a complete graph of star trees, and,","key_machinery":"The proofs rest on three mechanisms. (1) An extension of Freij's equivariant generalized discrete Morse theory to cubical complexes (Theorem 2.3, proved in Appendix A), which allows label-free Morse matchings where all active vertices are simultaneously (co-)specified. (2) The tree invariant Ψ(T) = Σ_e (σ_T(e) - 1), where σ_T(e) is the smaller side of the cut induced by edge e; this changes by at most one per leaf slide and equals zero only for star trees, making it a sharp distance lower bound. (3) The 4-cycle completion property: any 4-cycle in G_n is uniquely determined by three of its vertices (Lemma 4.2), which propagates rigidity from a small subcomplex H to the entire graph.","core_discovery":"The central discovery is that the topology, geometry, and symmetry of network realignment complexes are governed by star trees. Topologically, the entire complex X_G equivariantly collapses onto a complete graph whose vertices are star trees plus a discrete space of isolated points. Geometrically, the distance from any spanning tree to its nearest star tree in G_n is exactly the tree invariant Ψ(T), achieved when the star center is a centroid of T. This invariant also controls the diameter bounds. And algebraically, the rigid configuration of star trees and their neighboring cells in the subcomplex H is sufficient to pin down all automorphisms of X_n as relabeling symmetries for n ≥ 5.","pith_inferences":["The condition n ≥ 5 for Aut(X_n) ≅ S_n likely reflects a threshold where the complex has enough local structure to force rigidity; below this, small-n coincidences (like X_4 ≅ Σ_{K_4} with its larger automorphism group) allow extra symmetries. This suggests a general phenomenon where rigidity of reconfiguration complexes stabilizes above a critical size.","The matching distance δ, introduced as a lower-bound tool for the diameter, may be of independent interest as a metric on trees: it compares inter-vertex distances across matchings and could serve as a computationally cheaper proxy for the leaf-slide distance in algorithmic applications.","If the upper diameter bound is sharp (as computations for 6 ≤ n ≤ 9 suggest), then the worst-case leaf-slide distance between two spanning trees of K_n is achieved by pairs of path trees with specific labelings, which would mean path trees are the geometric antipodes of the realignment graph.","The extension of equivariant Morse theory to cubical complexes (Appendix A) is developed in a self-contained way and could be applied to other cubical reconfiguration complexes beyond network realignments, such as state complexes of reconfigurable systems more generally."],"forward_implications":["The equivariant homotopy type X_G ≃ K_{S_G} ⊔ D_G means the Betti numbers and fundamental group of X_G are determined purely by the number of universal vertices (vertices of degree n-1) in G, making the topology computable from local degree data.","The diameter bounds on G_n constrain the computational complexity of shortest-path algorithms for leaf-slide reconfiguration of spanning trees: any algorithm must handle distances that grow quadratically in n.","The result Aut(X_n) ≅ S_n for n ≥ 5 means the complex has no hidden symmetries beyond vertex relabeling, which is a rigidity property useful for distinguishing X_n from other cubical complexes arising in reconfiguration.","The characterization of connected components of X_G via spine and spine assignment (Proposition 2.37) provides a concrete invariant for classifying reconfiguration orbits under Aut(G).","The cubical flag property of X_n means the higher-dimensional structure is fully encoded in the reconfiguration graph, so combinatorial data about single moves suffices to reconstruct the full topology."],"fun_headline_variants":["Star trees govern topology and symmetry of network realignment complexes","Network realignment complexes equivariantly retract onto star-tree graphs","Leaf-slide complexes collapse to star trees plus discrete Aut(G)-space","Diameter of realignment graph bounded by tree invariant measuring distance to star trees","Automorphisms of realignment complex X_n are exactly vertex relabelings for n ≥ 5"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The extension of equivariant generalized discrete Morse theory to cubical complexes requires that the critical cells of the generalized Morse matching form a subcomplex. The acyclicity proof of the matching relies on the claim that the set of non-active specified vertices strictly decreases along any putative cycle, which depends on verifying that no cospecification can reintroduce a vertex into the non-active set.","fun_headline_variants_meta":{"raw":{"variants":["Star trees govern topology and symmetry of network realignment complexes","Network realignment complexes equivariantly retract onto star-tree graphs","Leaf-slide complexes collapse to star trees plus discrete Aut(G)-space","Diameter of realignment graph bounded by tree invariant measuring distance to star trees","Automorphisms of realignment complex X_n are exactly vertex relabelings for n ≥ 5"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":614,"prompt_tokens":534,"completion_tokens":80,"prompt_tokens_details":null},"tokens_in":534,"tokens_out":80,"duration_ms":18281,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T11:44:44.085619+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"Construct a connected graph G where the claimed Aut(G)-equivariant deformation retraction of X_G onto K_{S_G} ⊔ D_G fails because the Morse matching is cyclic (a cycle exists in the matching relation) or because the critical cells do not form a subcomplex.","supporting_citations":[],"review_version":1}