Combinatorial manifolds and Kleene’s theorem, homotopically
Yorgo Chamoun · 2026
Read Combinatorial manifolds and Kleene’s theorem, homotopically by Yorgo Chamoun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21142.txt.
Introduction
Yorgo Chamoun builds a general way to form categories of combinatorial manifolds. These are objects that meet a local rule at each point. He places them inside larger categories of relational presheaves, using unique factorization systems. The result is a model category whose cofibrant objects are exactly the manifolds. He tests the method on grid-like precubical sets and on a new abstract proof of Kleene's theorem.
Catalog record
| CREATOR | Yorgo Chamoun |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60456 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21142
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Combinatorial manifolds and Kleene’s theorem, homotopically Yorgo Chamoun Abstract We give a general method to build categories of combinatorial manifolds, i.e. categories of combinatorial objects satisfying some local property at every “point”, as coreflective subcategories of categories of relational presheaves. To do this, we crucially rely on unique factorization systems, and we can interpet our technique as a way of building a model category whose cofibrant objects are exactly the combinatorial manifolds. We then illustrate the usefulness of this point of view by two applications. First we build a category of euclidean precubical sets, i.e. precubical sets that locally look like a grid (of some fixed dimension), and show that it is coreflective in the category of relational precubical sets. This is the combinatorial analog of eulidean locally ordered spaces and the blowup construction from directed topology. Secondly, we show how to give an abstract proof of Kleene’s theorem from automata theory by defining “manifold automata” that behave well with respect to concatenation. 1 Introduction Relational presheaves [ Ros91 ] over some category \mathcal{C} are lax functors \mathcal{C}^{op}\to{\mathbf{Rel}} with {\mathbf{Rel}} the category of sets and relations. We can interpret these objects as “open” combinatorial structures. For example, if \mathcal{C} is the simplex category \Delta , for every n\in\Delta , there is a relational simplicial set S_{n} such that S_{n}(n)=\{*\} and S_{n}(m)=\varnothing for m\neq n , which can be interpreted as the open n -simplex. This topological interpretation has been confirmed by recent work on their realization [ CM26 ] . Thus, using relational presheaves, we are able to define “combinatorial manifolds”, i.e. combinatorial objects which are defined by a local property, where local means “on some open neighborhood of every point”. Since we are in the combinatorial world, and moreover in a very well-behaved category (the category of relational presheaves over any category is locally finitely presentable), we can expect this definition to be given by an elegant categorical formalism. This is indeed the case, and the goal of this paper is to show that this can be done via unique factorization systems. In some cases, we can even define a model structure where the “manifolds” are exactly the cofibrant objects, even though this point of view does not seem to be fundamentally richer, since the other factorization system of the model structure is trivial. This is developped in § 2 , after a quick overview of relational presheaves. We then give two applications of this methodology. Euclidean precubical sets. A precubical set is a presheaf on the cube category \square , and can be thought of as a collection of n -cubes for every dimension n glued together on their faces. Allowing a precubical set to be relational just means that we allow a cube to have any number of faces (including zero) in every direction. Precubical sets are prototypical higher directed combinatorial objects, and can be used to model parallel programs in computer science for example, where an n -cube represents n operations executed in parallel [ FGH+16 ] . In this context, the subclass of euclidean precubical sets, i.e. precubical sets which are locally isomorphic to a (filled) n -grid for some fixed dimension n , is particularly interesting. From the computer scientist perspective, the programs represented by euclidean precubical sets are locally just n independent parallel processes, and are thus easy to optimize with respect to their execution time, e.g. using tools from differential geometry [ Hau25 ] . A relational euclidean precubical set of dimension 2. A euclidean precubical set of dimension 1. A relational precubical set of dimension 1 which is not euclidean. In § 3 , motivated by this fact, we define a model structure on the category of relational precubical sets, and we show that its cofibrant replacement corresponds to a combinatorial blowup in the vein of [ Hau25 , CM26 ] but with a better universal property. In other words, we give an abstract definition of euclidean precubical sets, which comes with a canonical way of approximating a precubical set by a euclidean one. This example is a good illustration of our techniques, since the manifold interpretation is explicit. Relational automata. An automaton over some alphabet \Sigma is a (possibly infinite) \Sigma -labelled graph with distinguished initial and accepting vertices. Vertices are called states and edges are called transitions . A word w=w_{1}w_{2}\dots w_{n} , i.e. a finite list of letters, is recognized by an automaton A if there is a w -labelled path in A from an initial to an accepting state, i.e. if there is a morphism \odot\hskip-3.44444pt\xrightarrow{w_{1}}\hskip-3.87495pt\circ\hskip-3.87495pt\xrightarrow{w_{2}}\cdots\xrightarrow{w_{n}}\hskip-3.87495pt\otimes\;\to\;A \odot \otimes a b (A) \odot \otimes a b \varepsilon (B) (where the dotted state is initial and the crossed state is accepting). The language recognized by an automaton A is the set of words recognized by A . Kleene’s theorem [ Sak09 , Sip96 ] states that the languages recognized by finite automata are exactly the regular languages , i.e. the languages generated by the empty language and the singleton languages \{a\} for every a\in\Sigma under union, concatenation ( L_{1}*L_{2}:=\{w_{1}*w_{2}\,|\,w_{1}\in L_{1},w_{2}\in L_{2}\} , where concatenation of words is the ususal concatenation of finite lists) and Kleene star ( L^{*}:=\bigcup_{n\in\mathbb{N}}L^{n} ). To prove that every regular language is recognized by some finite automaton, one procedes by induction on the constructors of these languages. In particular, one should prove that given two automata recognizing languages L_{1} and L_{2} respectively, they can be concatenated into an automaton recognizing L_{1}*L_{2} . This is not obvious, and the standard proof uses automata with silent transitions , i.e. transitions labelled by the empty word \varepsilon , and shows that these are equivalent to ordinary automata. For example, consider the languages \{a\}^{*} and \{b\}^{*} recognized by the automata with a unique initial and accepting state and a loop labelled by a (respectively b ). If we naively concatenate the automata by glueing the accepting state v of the first and the initial state v^{\prime} of the second, we get the automaton (A) recognizing \{a,b\}^{*}\neq\{a\}^{*}*\{b\}^{*} . What we should do instead is adding an \varepsilon -transition between v and v^{\prime} (B) , and then “eliminate” the \varepsilon . So automata with \varepsilon -transition can be seen as a technical tool to handle concatenation of automata. We suggest in this paper that relational automata are a (categorically) better such technical tool. Indeed, in § 4 , looking at the category of relational automata, we abstractly define the automata which behave well with respect to composition. This is a local property, since we only need to look at the neighborhood of initial and accepting states. As an application, we give a simple abstract proof of the corresponding direction of Kleene’s theorem. 2 Theoretical preliminaries 2.1 Relational presheaves Definition 1 . A relational presheaf P over some category \mathcal{C} is a lax functor \mathcal{C}^{op}\to{\mathbf{Rel}} . A morphism \alpha:P\Rightarrow Q of relational presheaves over \mathcal{C} is an oplax natural transformation. Relational presheaves over \mathcal{C} form a category noted \mathbf{RelPsh}(\mathcal{C}) . In concrete terms, a relational presheaf P amounts to the data of a family of sets P(c) indexed by objects c\in\mathcal{C} and a family of relations P(f) indexed by morphisms f , with P(f)\subseteq P(c)\times P(d) for f:d\to c , subject to