Paperlane

no. 4 · Wednesday 28 October 2026

Limit Computation Over Posets via Minimal Initial Functors

Tamal K. Dey and Michael Lesnick

math.AT · v3 · 53 pp

Abstract

It is well known that limits can be computed by restricting along an initial functor, and that this often simplifies limit computation. We systematically study the algorithmic implications of this idea for diagrams indexed by a poset. We say an initial functor $F\colon C\to D$ with $C$ small is minimal if the sets of objects and morphisms of $C$ each have minimum cardinality, among the sources of all initial functors with target $D$. For $Q$ a finite poset or $Q\subseteq \mathbb N^d$ an interval (i.e., a convex, connected subposet), we describe all minimal initial functors $F\colon P\to Q$. In particular, we show that such $F$ is always a subposet inclusion, up to isomorphism. We give efficient algorithms to compute a choice of minimal initial functor. In the case that $Q\subseteq \mathbb N^d$ is an interval, we give asymptotically optimal bounds on $|\hom P|$, the number of relations in $P$ (including identities), in terms of the number $n$ of minima of $Q$: We show that $|\hom P|=Θ(n)$ for $d\leq 3$, and $|\hom P|=Θ(n^2)$ for $d>3$. We apply these results to give new bounds on the cost of computing $\lim G$ for a functor $G \colon Q\to \mathbf{Vec}$ valued in vector spaces. For $Q$ connected, we also give new bounds on the cost of computing the generalized rank of $G$ (i.e., the rank of the induced map $\lim G\to \operatorname{colim} G$), which is of interest in topological data analysis.

comments
Many expository improvements and minor fixes. 53 pages
fields
Algebraic Topology, Category Theory
pdf ↗ page arXiv:2601.00209 ↗