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.
58
questions
2
votes
0
answers
91
views
Hochschild cohomology of path algebra as a cohomology of simplicial complex
M. Gerstenhaber and S. D. Schack have shown that a cohomology of simplicial complex can be expressed as a Hochschild cohomology of path algebra constructed from this complex (link).
Is the opposite ...
- 61
2
votes
0
answers
71
views
Description of a point cloud being "undersampled" wrt persistent homology, confidence level?
I am completely new to topological data analysis, so I apologise if this is a well-known area of persistent homology, as well as for any imprecise language.
Suppose we know completely the topological ...
- 19
4
votes
0
answers
69
views
KLO for operations over braids
KLO is a program that permits you to the do twistings, band operations over knots or Kirby diagram. However, I couldn't find a function on KLO that permits me to do the same thing over braids.
Is ...
- 141
0
votes
0
answers
42
views
Persistent diagrams for images : existing implementations or packages?
I am interest to compute the persistent diagram associated to the image of a persistent module as in ''Persistent Homology for Kernels, Images, and Cokernels'' : https://epubs.siam.org/doi/epdf/10....
- 71
3
votes
1
answer
150
views
Homeomorphic extension of a discrete function
Let $f : \{ 0,1 \} ^ {n} \rightarrow \{ 0,1 \} ^ {n}$ be a bijective map. Then is there a known computable way to extend it to a homeomorphism $g:[ 0,1 ] ^ {n} \rightarrow [ 0,1 ] ^ {n}?$
- 31
8
votes
2
answers
360
views
Knot Diffie–Hellman
Here's an idea for a knot-based Diffie–Hellman exchange:
Public: random (oriented) knot $P$.
Private: random (oriented) knots $A$ and $B$.
Exchange: Alice sends (randomized or canonical ...
- 435
-2
votes
1
answer
197
views
Are there any non-elementary functions that are computable?
Does a function $\mathit{f}:\mathbb{R}→\mathbb{R}$ being non-elementary (not expressible as a combination of finitely many elementary operations), imply that it is not computable?
The particular case ...
- 11
2
votes
0
answers
53
views
If a set is covered by simplices then can it be covered by "almost disjoint" simplices?
Let $x_1,\dots,x_N$ be points in Euclidean space $\mathbb{R}^d$ (positive $d$), $r>0$, and consider set $X\subset\mathbb{R}^d$ defined as the collection of all $x\in \mathbb{R}^d$ of the form
$$
x =...
- 4,961
14
votes
4
answers
2k
views
Is there an algorithm for the genus of a knot?
A Seifert surface of a knot is a surface whose boundary is the knot. The genus of a knot is the minimal genus among all the Seifert surfaces of the knot. My question is, is any algorithm known to ...
- 4,471
14
votes
1
answer
336
views
Are hyperbolic $n$-manifolds recursively enumerable?
Fixing a dimension $n \ge 4$, is the class of closed hyperbolic $n$-manifolds recursively enumerable?
Since hyperbolic manifolds are triangulable I can reformulate this in the following more explicit ...
- 3,319
10
votes
3
answers
1k
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 ...
- 231
6
votes
1
answer
437
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 ...
- 961
9
votes
6
answers
951
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
0
answers
219
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 ...
- 149
4
votes
0
answers
113
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 $...
- 41
1
vote
0
answers
104
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 ...
- 1,405
8
votes
2
answers
422
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 ...
- 585
27
votes
2
answers
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 ...
- 674
1
vote
0
answers
92
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 ...
- 261
2
votes
1
answer
53
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 ...
- 9,492
3
votes
2
answers
163
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 ...
- 5,299
9
votes
1
answer
255
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 \...
- 899
3
votes
0
answers
117
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 ...
- 2,431
5
votes
2
answers
307
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 ...
- 1,169
3
votes
0
answers
168
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 ...
- 4,365
7
votes
0
answers
172
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 ...
- 877
0
votes
2
answers
237
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 ...
- 127
2
votes
0
answers
163
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 ...
- 602
4
votes
3
answers
459
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 ...
- 95k
7
votes
1
answer
939
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 ...
- 127
11
votes
0
answers
151
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 ...
- 38.7k
40
votes
5
answers
3k
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 ...
- 3,071
2
votes
1
answer
174
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 ...
- 417
18
votes
3
answers
601
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 ...
- 375
3
votes
1
answer
136
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 ...
- 5,299
35
votes
1
answer
3k
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).
...
- 1,169
4
votes
1
answer
553
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 ...
- 1,405
10
votes
0
answers
258
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$, ...
- 75.7k
0
votes
1
answer
288
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
1
answer
359
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 ...
- 35
7
votes
1
answer
219
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 ...
- 543
29
votes
3
answers
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,...
- 393
7
votes
0
answers
335
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 ...
- 5,201
6
votes
3
answers
959
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 ...
- 415
11
votes
2
answers
668
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 ...
- 858
17
votes
3
answers
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, ...
- 21.8k
36
votes
5
answers
7k
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 ...
- 699
5
votes
1
answer
514
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 ...
- 153
5
votes
1
answer
405
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-...
- 455
4
votes
1
answer
227
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 ...
- 183