Mathematical Sciences Research Institute

Home » Workshop » Schedules » Computing simplicial representatives of homotopy group elements

Computing simplicial representatives of homotopy group elements

Geometric and topological combinatorics: Modern techniques and methods October 09, 2017 - October 13, 2017

October 11, 2017 (11:30 AM PDT - 12:30 PM PDT)
Speaker(s): Uli Wagner (Institute of Science and Technology Austria)
Location: MSRI: Simons Auditorium
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
No Video Uploaded

A central problem of algebraic topology is to understand the homotopy groups πd(X) of a topological space X. 
For the computational version of the problem, it is well known that there is no algorithm to decide whether the 
fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several 
algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute 
the higher homotopy group πd(X) for any given d ≥ 2.

However, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2, as an abstract 

finitely generated abelian group given by generators and relations, but they work with very implicit representations 

of the elements of πd(X). 

We present an algorithm that, given a simply connected simplicial complex X, computes πd(X) and represents its elements 

as simplicial maps from a suitable triangulation of the d-sphere to X. For fixed d, the algorithm runs in time singly exponential 

in size(X), the number of simplices of X. 


Moreover, we prove that this is optimal: For every fixed d ≥ 2, we construct a family of simply connected simplicial complexes X 

such that for any simplicial map representing a generator of πd(X), the size of the triangulation of Sd on which the map is defined is 

exponential in size(X). 


Apart from the intrinsic importance of homotopy groups, we view this as a first step 

towards the more general goal of computing explicit maps with specific topological properties, 

e.g., computing explicit embeddings of simplicial complexes or counterexamples to Tverberg-type

problems, and towards quantitative bounds on the complexity of such maps.


Joint work with Marek Filakovský, Peter Franek, and Stephan Zhechev


29711?type=thumb Wagner Notes 2.67 MB application/pdf Download
Video/Audio Files
No Video Files Uploaded