REVIEW 2 major objections 4 minor 40 references
Any static decomposition theory lifts, under categorical hypotheses, to a temporal theory that recovers natural time-varying analogues of tree-width.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-14 11:41 UTC pith:EHPA3MP2
load-bearing objection Clean categorical lift of static decompositions to persistent narratives; theorems hold under explicit axioms, recovered widths are max-over-snapshots, main external hypothesis is sheafification. the 2 major comments →
Decomposing time-varying data into simple pieces: structured decompositions of narratives
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Under four categorical hypotheses (spine inclusions preserve and reflect pullbacks, the base is finitely cocomplete, a sheafification left adjoint that is a retraction exists, and pushouts along monomorphisms are also pullbacks with monomorphisms stable), the category of persistent narratives valued in a spined sd-category is itself a spined sd-category. Consequently every static width measure induced by a spine lifts to a temporal width measure on time-varying data.
What carries the argument
Temporalization of a spined sd-category: the subcategories pΩ_n of those persistent narratives that land in the n-th spine layer on a chosen sub-semilattice of time intervals; Theorems 3.2 and 3.4 prove that these form a spine once the four hypotheses hold.
Load-bearing premise
The sheafification left adjoint that turns ordinary diagrams into persistent narratives must exist and be a retraction, so that colimits of decompositions remain inside the subcategory of narratives rather than merely in the larger presheaf category.
What would settle it
Exhibit a concrete spined sd-category that satisfies the other three hypotheses but admits no sheafification left adjoint that is a retraction, and check whether structured decompositions of its persistent narratives still possess colimits inside the narrative subcategory.
If this is right
- Any static width measure already captured by a spined sd-category (tree-width, path-width, independence number, …) automatically yields a family of temporal width measures indexed by sub-semilattices of the time category.
- Varying the sub-semilattice S of time intervals gives a tunable parameter: longer intervals force the temporal width to ignore short-lived fluctuations.
- The same lifting recipe applies verbatim to other adhesive or quasitopos bases once their sheafification functors are known.
- The recovered temporal tree-width, complemented tree-width and tree-independence number become well-defined invariants of persistent narratives of graphs.
Where Pith is reading between the lines
- The dual cumulative-narrative construction sketched in the conclusion is likely to succeed under the dual hypotheses, producing a second, co-presheaf-based family of temporal widths.
- If the conjectured embedding of structured decompositions of narratives into narratives of structured decompositions holds, one obtains a single 2-categorical setting in which static and temporal decompositions can be compared directly.
- The framework supplies a candidate language for transferring algorithmic meta-theorems (Courcelle-type results) from static graphs to temporal graphs once the temporal width is bounded.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a categorical procedure that lifts any static spined structured-decomposition category (C,G,Ω) to a temporal counterpart on the category Pe(T,C) of C-valued persistent narratives over a finite discrete time category T. Under hypotheses (T1)–(T4)—pullback-preserving full spine inclusions, finite cocompleteness of C, existence of a sheafification left adjoint that is a retraction of the inclusion Pe(T,C)↪[T^op,C], and pushouts along monomorphisms that remain pullbacks with monomorphisms stable—the pair (Pe(T,C),G) is shown to be an sd-category (Theorem 3.2) and the image subcategories pΩ_n form a spine (Theorem 3.4). Three case studies instantiate the construction for ordinary tree-width (via reflexive graphs), complemented tree-width, and the tree-independence number, recovering the expected “maximum over snapshots in S” formulae for the resulting temporal widths.
Significance. The work supplies a uniform, axiomatic route from static width theories to temporal ones, rather than ad-hoc combinatorial definitions. The proofs of the two main theorems are written out in full detail (pointwise colimits followed by sheafification; explicit pushout/pullback constructions and pasting for the spine axioms), and the case studies correctly recover the natural max-snapshot analogues once the ambient category is adjusted. This is a genuine contribution to the programmatic question of “the right way” to decompose objects of an arbitrary category, and it places several recent temporal-graph parameters inside a single categorical framework. The external character of (T3) for general C is a limitation, but it is already flagged by the authors and is verified for the graph examples they treat.
major comments (2)
- Axiom (T3) is load-bearing for Theorem 3.2: without a sheafification left adjoint that is a retraction, the pointwise colimits constructed in the presheaf category need not land back inside Pe(T,C). The paper verifies the axiom for Grph_refl via ordinary set-valued sheafification, but leaves it as an external hypothesis for general C. A short additional paragraph (or appendix remark) listing further classes of C for which (T3) is known, or stating a sufficient condition, would strengthen the claim that the lift is “systematic” beyond graphs.
- In Case Study 4.1 the ambient category is changed from ordinary simple graphs to reflexive graphs in order to obtain finite cocompleteness and to make the identity-on-vertices maps into morphisms. The resulting pΓ-width is therefore a temporal width for reflexive graphs, not for ordinary simple graphs. The manuscript should state explicitly whether (and how) the ordinary simple-graph tree-width is recovered by restriction or by a forgetful functor, so that the claim “natural temporal analogues of ordinary tree-width” is fully justified.
minor comments (4)
- Several typographical slips appear: “althoughthetheory” (p. 2), “time-respectingnotion” (p. 12), “spinedsd-categories” (p. 22), and missing spaces after periods in the abstract and introduction.
- Figure 2.1 and the schematic diagrams in §3 would benefit from larger fonts and consistent arrow styles; the current rendering makes the pullback squares hard to parse at a glance.
- The notation pΩ_n is introduced as the image of π_n, yet later used interchangeably with the full subcategory of narratives whose values on S land in Ω_n (Lemma 3.1). A single clarifying sentence after the definition would avoid momentary confusion.
- References [9] and [10] are cited heavily; a brief parenthetical reminder of the precise statements being lifted would help readers who have not memorised those preprints.
Circularity Check
No significant circularity: lift theorems proved from explicit axioms (T1)–(T4); self-citations supply input frameworks only.
specific steps
-
self citation load bearing
[Section 2 (Defs 2.3, 2.10–2.16) and Section 4 (case studies citing [10, Props 3.1.1, 3.3.4, 3.4.5])]
"We apply structured decompositions to categories of persistent narratives. ... the static spined sd-categories of [10] that recover the time-independent notions of ordinary tree-width, complemented tree-width and the tree-independence number and to apply our theorem to those contexts."
The input notions of structured decomposition, spine, and the three static width parameters are taken from prior work by overlapping authors. This is ordinary framework citation rather than a load-bearing circular step: the lift theorems and the explicit max-over-S formulae are proved independently from the axioms and do not reduce to the cited results by construction.
full rationale
The central claims (Theorems 3.2 and 3.4) construct a temporal spined sd-category (Pe(T,C),G,pΩ) by verifying the sd-category and spine axioms (S1)–(S5) under hypotheses (T1)–(T4). Proofs proceed by pointwise colimits in the presheaf category (via (T2)), preservation under the sheafification left adjoint S that is a retraction ((T3)), monomorphism stability and pasting of pullbacks/pushouts ((T4)), and fullness of the Ω_n layers (Lemma 3.1). Case studies then compute the induced sizes/widths explicitly (Propositions 4.3, 4.6, 4.7), obtaining max_s s_Γ(X(s)) and max_s w_Γ(d_s); these equalities follow by direct unwinding of the general definitions, not by fitting or tautological redefinition. Self-citations to [9] (persistent narratives) and [10] (structured decompositions/spined sd-categories) introduce the static ingredients being lifted; they are not used to justify the lift itself or to import uniqueness/ansatz that forces the temporal widths. No parameter is fitted and then re-presented as a prediction; no known empirical pattern is merely renamed. The derivation is therefore self-contained given the stated categorical hypotheses.
Axiom & Free-Parameter Ledger
axioms (5)
- domain assumption (T1) C and each Ω_n admit all pullbacks; inclusions ι_n preserve (and, being full, reflect) pullbacks.
- domain assumption (T2) C is finitely cocomplete.
- domain assumption (T3) The inclusion Pe(T,C) ↪ [T^op,C] admits a left-adjoint sheafification S that is a retraction.
- domain assumption (T4) C admits pushouts along monomorphisms; those squares are also pullbacks; monomorphisms are stable under pushouts.
- domain assumption T is a finite discrete time category (finite join-semilattice of discrete intervals).
invented entities (2)
-
pΩ_n (image of the pullback category Pn under projection to Pe(T,C))
no independent evidence
-
Temporalized spined sd-category (Pe(T,C),G,pΩ)
no independent evidence
read the original abstract
Graphs that change over time arise throughout applications, but there is no single standard way to decompose them into smaller pieces. In this paper, we propose a systematic categorical method for doing so. The main idea is to combine structured decompositions, which generalize graph decompositions, such as tree-decompositions, with persistent narratives, which model time-varying data as diagrams. We prove that, under suitable categorical hypotheses, any static theory of decompositions can be lifted to a corresponding temporal theory. As case studies, we apply this construction to time-varying graphs and recover natural temporal analogues of ordinary tree-width, complemented tree-width, and the tree-independence number.
Figures
Reference graph
Works this paper leans on
-
[1]
Time-Varying Graphs and Dynamic Networks
A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. “Time-Varying Graphs and Dynamic Networks”. In:Ad-hoc, Mobile, and Wireless Networks. Ed. by H. Frey, X. Li, and S. Ruehrup. Vol. 6811. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2011, pp. 346–359
2011
-
[2]
Compo- sitional Modeling with Stock and Flow Diagrams
John Baez, Xiaoyan Li, Sophie Libkind, Nathaniel D. Osgood, and Evan Patterson. “Compo- sitional Modeling with Stock and Flow Diagrams”. In:Electronic Proceedings in Theoretical Computer Science380 (2023).url:http://dx.doi.org/10.4204/EPTCS.380.5
-
[3]
url:https://arxiv.org/abs/1911.04630v3
JohnC.BaezandKennyCourser.Structured Cospans.2020.arXiv:1911.04630v3 [math.CT]. url:https://arxiv.org/abs/1911.04630v3
Pith/arXiv arXiv 2020
-
[4]
Structured versus Deco- rated Cospans
John C. Baez, Kenny Courser, and Christina Vasilakopoulou. “Structured versus Deco- rated Cospans”. In:Compositionality4 (2022).url:http : / / dx . doi . org / 10 . 32408 / compositionality-4-3
2022
-
[5]
John C. Baez and Jade Master. “Open Petri nets”. In:Mathematical Structures in Computer Science30 (2020), pp. 314–341.url:https://doi.org/10.1017/S0960129520000043
-
[6]
A compositional framework for reaction networks
John C. Baez and Blake S. Pollard. “A compositional framework for reaction networks”. In:Reviews in Mathematical Physics29.09 (2017).url:https : / / doi . org / 10 . 1142 / S0129055X17500283
2017
-
[7]
Basic Category Theory
Francis Borceux.Handbook of Categorical Algebra 1. Basic Category Theory. Cambridge Uni- versity Press, 1994
1994
-
[8]
Binh-Minh Bui-Xuan, Florent Krasnopol, Bruno Monasson, and Nathalie Sznajder.Model checking with temporal graphs and their derivative. 2026. arXiv:2602.12446v3 [cs.DS].url: https://arxiv.org/abs/2602.12446v3. 32
Pith/arXiv arXiv 2026
-
[9]
Benjamin Merlin Bumpus, James Fairbanks, Martti Karvonen, Wilmer Leal, and Frédéric Simard.Towards a Unified Theory of Time-Varying Data. 2025. arXiv:2402 . 00206v3 [math.CT].url:https://arxiv.org/abs/2402.00206v3
Pith/arXiv arXiv 2025
-
[10]
Kocsis, Jade Edenstar Master, and Emilio Minichiello
Benjamin Merlin Bumpus, Zoltan A. Kocsis, Jade Edenstar Master, and Emilio Minichiello. Structured Decompositions: Structural and Algorithmic Compositionality. 2025. arXiv:2207. 06091v7 [math.CT].url:https://arxiv.org/abs/2207.06091v7
Pith/arXiv arXiv 2025
-
[11]
Edge Exploration of Temporal Graphs
Benjamin Merlin Bumpus and Kitty Meeks. “Edge Exploration of Temporal Graphs”. In: 85 (2023), pp. 688–716.url:https://link.springer.com/article/10.1007/s00453-022- 01018-7#citeas
-
[12]
Jacobs, Paul Knappe, and Jan Kurkofka.Canonical graph decompositions and local separations: From infinite coverings to a finite combinatorial theory
Johannes Carmesin, Raphael W. Jacobs, Paul Knappe, and Jan Kurkofka.Canonical graph decompositions and local separations: From infinite coverings to a finite combinatorial theory
-
[13]
arXiv:2501.16170v1 [math.CO].url:https://arxiv.org/abs/2501.16170v1
-
[14]
Rewriting Structured Cospans: A Syntax for Open Systems
Daniel Cicala. “Rewriting Structured Cospans: A Syntax for Open Systems”. PhD Thesis. University of California, Riverside, 2019.url:https : / / www . proquest . com / docview / 2308216336?pq-origsite=gscholar&fromopenview=true
2019
-
[15]
The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
Bruno Courcelle. “The monadic second-order logic of graphs. I. Recognizable sets of finite graphs”. In:Information and Computation85.1 (1990), pp. 12–75.url:https : / / www . sciencedirect.com/science/article/pii/089054019090043H
arXiv 1990
-
[16]
Open Systems: A Double Categorical Perspective
Kenny Allen Courser. “Open Systems: A Double Categorical Perspective”. PhD Thesis. University of California, Riverside, 2020.url:https : / / www . proquest . com / docview / 2404393265?pq-origsite=gscholar&fromopenview=true
2020
-
[17]
Jacobs, Paul Knappe, and Jan Kurkofka.Canonical graph decompositions via coverings
Reinhard Diestel, Raphael W. Jacobs, Paul Knappe, and Jan Kurkofka.Canonical graph decompositions via coverings. 2025. arXiv:2207.04855v8 [math.CO].url:https://arxiv. org/abs/2207.04855v8
Pith/arXiv arXiv 2025
-
[18]
Michelle Döring, Jessica Enright, Laura Larios-Jones, and George Skretas.FO and MSO Model Checking on Temporal Graphs. 2026. arXiv:2602 . 14592v1 [cs.DM].url:https : //arxiv.org/abs/2602.14592v1
arXiv 2026
-
[19]
Jessica Enright, Samuel D. Hand, Laura Larios-Jones, and Kitty Meeks.Families of tractable problems with respect to vertex-interval-membership width and its generalisations. 2026. arXiv: 2505.15699v5 [cs.DM].url:https://arxiv.org/abs/2505.15699v5
Pith/arXiv arXiv 2026
-
[20]
Structural Parame- ters for Dense Temporal Graphs
Jessica Enright, Samuel D. Hand, Laura Larios-Jones, and Kitty Meeks. “Structural Parame- ters for Dense Temporal Graphs”. In: vol. 306. Schloss Dagstuhl – Leibniz-Zentrum für Infor- matik, 2024, 52:1–52:15.url:https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.MFCS.2024.52
2024
-
[21]
Dynamic graph models
F. Harary and G. Gupta. “Dynamic graph models”. In:Mathematical and Computer Modelling 25.7 (1997), pp. 79–87. 33
1997
-
[22]
As Time Goes By: Reflections on Treewidth for Temporal Graphs
Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. “As Time Goes By: Reflections on Treewidth for Temporal Graphs”. In:Treewidth, Kernels, and Algorithms. Springer International Publishing, 2020, pp. 49–77.url:http://dx.doi.org/ 10.1007/978-3-030-42071-0_6
-
[23]
Brendan Fong.The Algebra of Open and Interconnected Systems. 2016. arXiv:1609.05382 [math.CT].url:https://arxiv.org/abs/1609.05382
Pith/arXiv arXiv 2016
-
[24]
S-functions for graphs
Rudolf Halin. “S-functions for graphs”. In:Journal of Geometry8 (1976), pp. 171–186.url: https://api.semanticscholar.org/CorpusID:120256194
1976
-
[25]
Modern temporal network theory: a colloquium
Petter Holme. “Modern temporal network theory: a colloquium”. In:The European Physical Journal B88.234 (2015)
2015
-
[26]
Temporal networks
Petter Holme and Jari Saramäki. “Temporal networks”. In:Physics Reports519.3 (2012), pp. 97–125
2012
-
[27]
Compositionality
Theo MV Janssen and Barbara H. Partee. “Compositionality”. In:Handbook of logic and language. Elsevier, 1997, pp. 417–473
1997
-
[28]
A note on discrete Conduché fibrations
Peter Johstone. “A note on discrete Conduché fibrations”. In:Theory and Applications of Categories5.1 (1999), pp. 1–11
1999
-
[29]
Connectivity and Inference Problems for Temporal Networks
David Kempe, Jon Kleinberg, and Amit Kumar. “Connectivity and Inference Problems for Temporal Networks”. In:Journal of Computer and System Sciences64.4 (2002), pp. 820–842
2002
-
[30]
Adhesive Categories
Stephen Lack and Paweł Sobociński. “Adhesive Categories”. In:Foundations of Software Sci- ence and Computation Structures. Ed. by Igor Walukiewicz. Springer Berlin Heidelberg, 2004, pp. 273–288
2004
-
[31]
An algebraic framework for structured epidemic modelling
Sophie Libkind, Andrew Baas, Micah Halter, Evan Patterson, and James P. Fairbanks. “An algebraic framework for structured epidemic modelling”. In:Philosophical Transac- tions of the Royal Society A: Mathematical, Physical and Engineering Sciences380.2233 (2022), p. 20210309. eprint:https : / / royalsocietypublishing . org / rsta / article - pdf / doi / 10...
-
[32]
Composing Behaviors of Networks
Jade E. Master. “Composing Behaviors of Networks”. PhD Thesis. University of California, Riverside, 2021.url:https://www.proquest.com/docview/2565195807?pq- origsite= gscholar&fromopenview=true
arXiv 2021
-
[33]
An Introduction to Temporal Graphs: An Algorithmic Perspective
Othon Michail. “An Introduction to Temporal Graphs: An Algorithmic Perspective”. In:In- ternet Mathematics12 (2015)
2015
-
[34]
Structured and Decorated Cospans from the Viewpoint of Double Category Theory
Evan Patterson. “Structured and Decorated Cospans from the Viewpoint of Double Category Theory”. In:Electronic Proceedings in Theoretical Computer Science397 (2023).url:http: //dx.doi.org/10.4204/EPTCS.397.13. 34
-
[35]
Open Markov Processes and Reaction Networks
Blake Stephen Swistock Pollard. “Open Markov Processes and Reaction Networks”. PhD Thesis. University of California, Riverside, 2017.url:https://www.proquest.com/docview/ 1972046592?pq-origsite=gscholar&fromopenview=true
2017
-
[36]
Graph minors. XVII. Taming a Vortex
Neil Robertson and P.D. Seymour. “Graph minors. XVII. Taming a Vortex”. In:Journal of Combinatorial Theory, Series B77.1 (1999), pp. 162–210
1999
-
[37]
Graph minors. III. Planar Tree-Width
Neil Robertson and P.D Seymour. “Graph minors. III. Planar Tree-Width”. In:Journal of Combinatorial Theory, Series B36.1 (1984), pp. 49–64.url:https://www.sciencedirect. com/science/article/pii/0095895684900133
arXiv 1984
-
[38]
Spivak, and Christina Vasilakopoulou.Dynamical Systems and Sheaves
Patrick Schultz, David I. Spivak, and Christina Vasilakopoulou.Dynamical Systems and Sheaves. 2019. arXiv:1609 . 08086v4 [math.CT].url:https : / / arxiv . org / abs / 1609 . 08086v4
2019
-
[39]
Compositionality
Zoltán Gendler Szabó and Richmond H. Thomason. “Compositionality”. In:Philosophy of Language. Cambridge Textbooks in Linguistics. Cambridge University Press, 2018, pp. 41–63
2018
-
[40]
Oxford University Press, 2012
Markus Werning, Wolfram Hinzen, and Edouard Machery, eds.The Oxford handbook of com- positionality. Oxford University Press, 2012. 35
2012
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.