Simplicial Constructions in Applied Topology

Abstract

I topologisk dataanalyse (TDA) analyserer man data ved å først konstruere et rom som fanger opp interessante egenskaper i dataen, og så studerer man topologien til dette rommet. Det er praktisk å jobbe med rom som har en simplisiell struktur, som gjør det mulig å utføre beregninger. I denne oppgaven ser vi på ulike simplisielle konstruksjoner som beskriver data av ulike former.

Hvis man har data som er gitt som en relasjon, kan man studere Dowker-komplekset til relasjonen. Dowkers teorem sier at Dowker-komplekset til en relasjon er homotopi ekvivalent med Dowker-komplekset til den transponerte relasjonen. Vi viser at de to Dowker-kompleksene begge er homotopi ekvivalent med et tredje simplisielt kompleks, som vi kaller rektangelkomplekset. Dette gir et nytt bevis for den funktorielle versjonen av Dowkers teorem, som blir brukt i TDA.

I utgangspunktet er Dowkers teorem for relasjoner av mengder, men vi viser at man også kan utvide Dowker- og rektangelkompleksene til mer generelle relasjoner, nemlig relasjoner av kategorier. Med et ekstra krav om sammentrekkbarhet, får vi en kategoriteoretisk versjon av Dowkers teorem. Denne kategorifiseringen gir oss muligheten til å finne nye anvendelser som ikke dekkes av den klassiske teorien.

Den kanskje vanligste dataformen er punktskyer i metriske rom. Et sentralt problem i anvendt topologi er å gjenkjenne formen til et rom ved å kun se på en sky av utvalgte punkter. For euklidske rom gir vi tilstrekkelige betingelser for rommet og de utvalgte punktene, slik at man kan lese av homologien til rommet fra persistensdiagrammet til punktskyens Čech-kompleks. Betingelsene er at rommet må ha positiv rekkevidde og punktskyen må være tilstrekkelig tett.

For punktskyer med støy må vi utvikle robuste metoder som kan fange opp signalet til den underliggende formen gjennom støyen. Vi ser på dette problemet fra et flerparameterperspektiv, og presenterer kjerne- og alfakjerne-biltrasjonene som alternativer til flerdekke-bifiltrasjonen. Disse tre bifiltrasjonene er alle sammenflettet, og de har lignende Prohorov-stabilitetsegenskaper. For punktskyer i euklidsk rom er kjerne- og alfakjerne-biltrasjonene enkle å beregne.

Ikke all data er best representert som punktskyer med en metrikk, eller som relasjoner. Vi introduserer den monoidale Rips-filtrasjonen for å analysere data gitt som en vektet rettet graf. Den monoidale Rips-filtrasjonen er en filtrert simplisiell mengde som generaliserer Vietoris-Rips-komplekset. Vi viser at den er stabil med hensyn til Gromov-graf-avstanden, en Gromov-Hausdorff-inspirert avstand mellom grafer.

Vi tar også for oss spørsmål om kompleksitet. Vi ser på problemet med å finne den minste kjeden i et simplisielt kompleks med en gitt rand. Dette problemet er NP-hardt, så vi ser etter ulike parametere som kan isolere den eksponentielle kompleksiteten av problemet. Vi viser at problemet kan løses effektivt (det er FPT-vanskelig) om vi enten parameteriserer med en kombinasjon av løsningsstørrelse og kofasett-grad, eller med trebredden til en Hasse-graf som avhenger av komplekset.

In topological data analysis (TDA) we analyse data by constructing a space that captures features of interest in the data, and then study this space. It is convenient to work with spaces that have some simplicial structure, as this extra structure allows us to do computations. In this thesis we consider different simplicial constructions describing data of different forms.

To data given as a relation, there is an associated simplicial complex, namely the Dowker complex. Dowker’s theorem states that the Dowker complex of a relation is homotopy equivalent to the Dowker complex of the transpose relation. We give a short proof of this, by noting that these two simplicial complexes are both homotopy equivalent to a third simplicial complex, which we call the rectangle complex. All constructions involved are functorial, directly giving the functorial version of Dowker’s theorem used in TDA.

Dowker’s theorem concerns relations of sets, but we also show that the notion of Dowker- and rectangle complexes can be extended to include more general relations, namely relations of categories. Under a contractibility hypothesis, we get a categorical version of the functorial Dowker theorem. This categorification allows us to find broader applications outside the scope of the classical theory.

Often, data are given as point clouds in some metric space. A central problem in applied topology is to determine the shape of a space using only a sampled point cloud. For the case of Euclidean subspaces, we give sufficient conditions on the space and the sample, to be able to determine the homology of the space looking only at the persistent homology of the intrinsic Čech complex of the sample. In particular, we consider spaces with positive reach where the sample is sufficiently dense.

For noisy samples, we need to develop robust methods that can capture the signal of the underlying shape through the noise. Taking a multiparameter approach, we present the core- and alpha-core bifiltrations as alternatives to the multicover bifiltration. These three bifiltrations are all interleaved, and they have similar Prohorov stability properties. For point clouds in Euclidean space, the core- and alpha-core bifiltrations are simple to compute.

Not all data are best represented by point clouds or relations. We introduce the monoidal Rips filtration to analyse data given in the form of a weighted directed graph. The monoidal Rips filtration is a filtered simplicial set generalizing the Vietoris-Rips complex. We show that it is stable with respect to the Gromov graph distance, a Gromov-Hausdorff inspired distance between graphs.

Lastly, we consider the computational complexity of finding the smallest chain in a simplicial complex with a given boundary. This problem is known to be NP-hard, so we explore different parameters that isolates the exponential complexity. We find that the problem can be efficiently solved (it is fixed parameter tractable) if we either parameterize by a combination of coface degree and solution size, or by the treewidth of a certain Hasse graph constructed from the simplicial complex.