Questions tagged [computational-topology]

Computational topology is the study of decidability problems in topology and the algorithms that determine decidability. Examples of area of study include Normal Surface theory and the subproblems of unknot and $S^3$ recognition.

Filter by
Sorted by
Tagged with
8
votes
3answers
668 views

Deep learning for knot theory. Classification

As far as I know, there is a classification of all prime knots with less than 16 crossings. It seems that there is already a fast enough algorithm to distinguish a knot from an unknot. So in principle ...
5
votes
1answer
306 views

Properties a triangulation must have in order to describe a manifold

I am mainly interested in the $3$-dimensional case. It is a well-known fact, following from the work of E. E. Moise and R. H. Bing in the 1950s, that every $3$-dimensional topological manifold (with ...
6
votes
5answers
491 views

Homology software

What software is there to efficiently compute homology? Specifically: What software can take a simplicial complex (provided by a file listing maximal simplices, for example) and quickly compute its ...
4
votes
0answers
211 views

What field of mathematics is this? Necessary and sufficient corridors for topological routing

I am a computer scientist working on a problem in electronics design. The overall problem is about how to route traces on a circuit board, and I am looking for help on one of the subproblems. We ...
4
votes
0answers
108 views

Is finding boundary-reducing discs for PL 3-manifolds with boundary pattern computationally efficient?

I am working with manifolds with boundary pattern, as defined by Matveev in his book Algorithmic Topology and Classification of 3-Manifolds. A manifold with boundary pattern is a pair $(M, P)$ where $...
0
votes
0answers
36 views

Are there structural properties of minimal torsion parts in simplicial complexes?

Are there any structural criteria to find torsions in a simplicial complex? Are there some sufficient and/or necessary properties of torsion-free simplicial complexes? Would it becomes easier to ...
1
vote
0answers
93 views

(Best) ways to reduce knot complexity?

Lets say I have a diagram of a knot in some notation. What's the fastest algorithm to simplify it? Or asked differently: what algorithms do software usually use? I do not need to put it into the very ...
8
votes
2answers
387 views

Quantitative word problem for 3-manifold groups

The word problem for 3-manifold groups is solvable: given a based loop $\gamma$ in $M^3$ there is an algorithm to decide whether $\gamma$ bounds a disk. What kinds of quantitative results are known ...
27
votes
2answers
1k views

Is being simply connected very rare?

Essentially, my question is how strong a restriction it is to be simply connected. Here is a way of making this precise: Let's say we want to count simplicial complexes (of dimension 2, though that ...
1
vote
0answers
64 views

Direct representation of simplical complexes in a HoTT implementation

Persistent homology can be used to transform a point-cloud into a simplical complex. Do such simplical complexes have a first-class representation: Conceptually, within HoTT? Concretely, within some ...
2
votes
1answer
48 views

Uniform closure of a neighbourhood complex in the tritetragonal tiling

Consider a neighbourhood complex of eight vertices (red) with vertex configuration $(3.4)^3$ which gives rise to the tritetragonal tiling of the hyperbolic plane: Not knowing if this complex can be ...
3
votes
2answers
153 views

Looking through a bunch of links for unlinks?

I am looking for a bit of orientation with regards to computational topology resources, as I am personally totally ignorant on the subject. I have lots of different links in $S^3$ (hundreds of ...
9
votes
1answer
217 views

Smooth Morse function from Forman's discrete Morse function

Let $M$ be a smooth manifold and $K$ a triangulation of $M$, so $K$ is a regular CW-complex and in particular a simplicial complex. Assume that $M$ is compact so $K$ is finite. Let $f\colon K \to \...
3
votes
0answers
99 views

Motivation for persistent homology with respect to eigenfunctions of distance kernel operator in a recent preprint

I have a question about a recent preprint https://arxiv.org/pdf/1912.02225.pdf by Maria, Oudot, and Solomon. As far as I understand, in Section 8 they prove that persistent homology (persistence ...
4
votes
2answers
230 views

Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?

I am interested in the topic of persistent homology (topological data analysis). According to what I read, there is some roadblock in the analysis of "big data" using persistent homology as it is ...
3
votes
0answers
159 views

The complexity of cutting hackers in a computer network

Let $l_1,l_2,\dots,l_m$ be parallel lines in the plane, say $l_k=\mathbb R\times\{k\}$. On the $k$th line fix a set $V_k$ consisting of $n_k$ points. Let $(V,E)$ be a directed graph whose set of ...
6
votes
0answers
160 views

Coarsifying persistence modules

The context Let $I=[0,∞)$ and consider the category of persistence modules $(V,π)$ indexed over $I$ satisfying: For all $t$ in $I$ but a closed discrete set of points $T$, there exists a ...
0
votes
2answers
208 views

Representations of modular lattices, extension to cellular sheaves

There are various "representation theorems" for lattices such as Birkhoff's Representation Theorem that states that every finite distributive lattice is isomorphic to a quasi-sublattice of the lattice ...
2
votes
0answers
133 views

Discrete Morse theory, choice of Morse function, and removing noise

If I have a simplicial complex, and a discrete Morse function defined on the simplices, I can use persistent homology to produce a barcode which helps me distinguish "persistent" shape from noise. To ...
4
votes
3answers
345 views

Triangulations of 3-manifolds in Regina and SnapPy

I have been doing some statistical studies on small 3-manifolds, and I note that one can produce larg-ish censuses of triangulations in Regina. Now, the Regina documentation tells us how to convert a ...
7
votes
1answer
614 views

Products, coproducts and equalizers in category of lattices

Background: Let $\mathbf{Lat}$ be the 2-category of lattices which can be viewed as a subcategory of the 2-cateogry of posets $\mathbf{Pos}$, that is, objects in $\mathbf{Pos}$ that have all finite ...
11
votes
0answers
138 views

Known obstruction for efficient computation of Stable homotopy groups?

Computation of stable homotopy groups (for example of sphere) is hard, but still, not as hard as unstable ones. For unstable homotopy groups there are some results showing that there cannot be ...
39
votes
5answers
2k views

Reference on Persistent Homology

I will be teaching a course on algebraic topology for MSc students and this semester, unlike previous ones where I used to begin with the fundamental group, I would like to start with ideas of ...
2
votes
1answer
129 views

On the entries of a matrix representation for a boundary operator of a persistence module

In equation 6 of Computing Persistent Homology (page 8), the authors put forward the following identity: $$\deg \hat{e_i}+\deg M_k (i,j)=\deg e_j$$ Where $\hat{e_i}$ and $e_j$ are elements of ...
18
votes
3answers
501 views

Vietoris-Rips complex homology of a higher degree than the ambient dimension

Assuming we have a set of points $X=\{x_1,..,x_n\}$, all in $\mathbb{R}^d$, and construct the Vietoris-Rips-Complex $V_\epsilon (X)$ for some distance parameter $\epsilon > 0$. Is it possible to ...
3
votes
1answer
97 views

An algorithm to tell if two cut systems are handle slide equivalent?

Let $\Sigma$ be a genus $g$ closed orientable surface and let $\alpha = \{ \alpha_1,...,\alpha_g\}$ and $\beta = \{ \beta_1 ,..., \beta_g \}$ be two cut systems (i.e. nonintersecting homologically ...
34
votes
1answer
2k views

Why is persistent cohomology so much faster than persistent homology

I refer to this paper: de Silva, Vin; Morozov, Dmitriy; Vejdemo-Johansson, Mikael. Dualities in persistent (co)homology. Inverse Problems 27 (2011), no. 12, 124003, 17 pp. (Journal link, arXiv link). ...
4
votes
1answer
334 views

Complexity of computing the Vietoris-Rips complex

For me it looks like computing the Vietoris-Rips complex from a data cloud is very similar to the clique problem in graph theory, which it NP-hard. How do the two differ and what is the computational ...
10
votes
0answers
244 views

Computing the equivariant cohomology class of a Białynicki-Birula cell

One of my current research interests is Hessenberg varieties. Briefly, if $m_1\le m_2\le \cdots \le m_{n-1}$ is a weakly increasing sequence of positive integers such that $i\le m_i\le n$ for all $i$, ...
0
votes
1answer
214 views

QUBO formulation of a discrete-variable Genetic Algorithm optimization problem

I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic real-valued function $f$ depending on a set of parameters $ \theta\...
0
votes
1answer
336 views

Clarification of "death event" in persistent homology

Before I ask my question let me clarify some notation: $f^{i,j}_r$, where $i < j$, refers to the inclusion map $f: H_r(X_i) \hookrightarrow H_r(X_j)$. $X_i$ and $X_j$ are subcomplexes of a filtered ...
7
votes
1answer
207 views

Computing homology of subvarieties of Euclidean spaces by persistent homology

Let $M$ be a submanifold of the Euclidean space $\mathbb{R}^n$. Let $G$ be a finite group acting on $M$ freely. I want to compute the homology (or even the cohomology ring) of $M/G$. Suppose the ...
30
votes
3answers
3k views

What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka)

Kronheimer and Mrowka showed that the Khovanov homology detects the unknot. Bar-Natan showed a program to compute the Khovanov homology fast: there was no rigorous complexity analysis of the algorithm,...
7
votes
0answers
281 views

Translation of Haken's paper "Theorie der Normalflächen"

Haken's paper "Theorie der Normalflächen" is one of the formative papers in the development of normal surface theory and provides an algorithm for detecting the unknot. While there are now a variety ...
6
votes
3answers
780 views

Algorithm for computing the Arf invariant of a knot

According to "The knot book", by Colin Adams, two knots are pass equivalent if they are related by a finite sequence of pass-moves. Moreover every knot is pass-equivalent to either the unknot or the ...
11
votes
2answers
632 views

Software for computing Thurston's unit ball

Is there any software which can be used for computing Thurston's unit ball (for second homology of 3-manifolds) of link complements? In particular can I do that with SnapPy? PS: even a table for ...
17
votes
3answers
1k views

What is the state of the art for algorithmic knot simplification?

Question: Given a `hard' diagram of a knot, with over a hundred crossings, what is the best algorithm and software tool to simplify it? Will it also simplify virtual knot diagrams, tangle diagrams, ...
36
votes
5answers
6k views

Inference using Topological Data Analysis: Is it worth it for a regular statistician to learn TDA?

After having read Gunnar Carlsson's Topology and Data I feel enthusiastic to use some topological data analysis (TDA) methods in my current research, mostly in social sciences. We often handle huge ...
5
votes
1answer
452 views

Biggest ball included in an intersection of balls

I would like to prove that for any family of balls $\{B(c_i,r_i)\}_i \subset \mathbb{R}^d$ such that $\{c_1, \dots, c_n\} \subset \bigcap_i B(c_i,r_i) $ and $\forall i, r_i \geq 1$, there exists a ...
4
votes
1answer
389 views

Are there "geometrically nice" sets from which to construct coverings that admit "Vietoris-Rips like" approximations to the nerve?

It is well known that the nerve (or Čech complex) of a covering consisting of metric balls with a common fixed radius is nicely approximated by the Vietoris-Rips complex. Being a flag complex on its 1-...
4
votes
1answer
223 views

Triangulation of the surface determined by sampling two of its cross-sections

I have a data set that essentially looks like the picture below, i.e., it's given by sets of points in $\mathbb{R}^3$ that sample the cross-sections of a certain surface that in principle I do not ...
23
votes
3answers
2k views

Persistent homology of Gaussian fields in Euclidean space

If you generate points in $\mathbb R^n$ via a process that respects a Gaussian normal distribution, then compute the persistent homology / barcodes, to my eye something fairly regular seems to be ...
16
votes
3answers
1k views

Computer-aided homology computations

Background I am currently working on the homology of some moduli space and there exists a much simpler chain complex with the same homology. It is a quotient of a bisimplicial complex by a subcomplex....
10
votes
1answer
239 views

Algorithmic Borel finiteness for hyperbolic manifolds

It is a theorem of Borel that there is a finite number of arithmetic hyperbolic manifolds of volume bounded above by $V.$ Is there any algorithm (or hope of an algorithm) to actually construct all of ...
3
votes
0answers
439 views

Connected Sum Decomposition of a Knot

Given a composite knot, is it possible to decompose it in prime knots by an algorithm that runs in polynomial time?
2
votes
2answers
911 views

Computational Topology Paper

I am delving into the field of Computational Topology. I am aware of the books in this field, but could anybody tell me a nice relevant paper in this field which tackles a "typical" Computational ...
8
votes
2answers
952 views

Homological computations

Suppose I have a group acting on some Hadamard manifold, and I want to understand as much as possible about the (co)homology of the quotient. In my case I can find a fundamental domain for the action ...
10
votes
4answers
3k views

Reference request for manifold learning

I am interested in learning about manifold learning (no pun intended) and would like to know of some references that discuss the subject from a more geometric perspective. By manifold learning I mean ...
30
votes
4answers
7k views

Computational software in Algebraic Topology?

I was wondering if there is any good software out there that allows you to do specific computations in algebraic topology. For example: Create a simplicial complex/set and ask questions about its ...