Algorithmische Topologie

Lektion 7. Die Lösung des Homöomorphieproblems für Mannigfaltigkeiten und Quasi-Mannigfaltigkeiten von Stallings.

7.1. Ein Resultat von G. Hemion.

Seien $F$ eine orientierbare Fläche und $f\colon F\to F$ ein Homöomorphismus. Betrachten wir das Produkt $F\times [0,1]$ und identifizieren $F\times \{ 0\}$ und $F\times \{ 1\}$ durch $f$. Die resultierende 3-Mannigfaltigkeit $M_f=F\times [0,1]/\{ (x,0)\approx (f(x), 1)\}$ heißt Stallingssche 3-Mannigfaltigkeit. Es gibt eine natürliche Faserung $M_f \to S^1$, so daß alle Fasern zu $F$ homöomorph sind. Sei $g\colon F\to F$ ein anderer Homöomorphismus.

Satz 7.1. Stallingssche 3-Mannigfaltigkeiten $M_f$ und $M_g$ sind dann und nur dann fasertreu homöomorph, wenn $f$ und $g$ konjugiert sind (modulo Isotopie).

Beweis. Offensichtlich, da zwei Homöomorphismen $h,h'\colon F\to F$ dann und nur dann isotop sind, wenn es einen fasertreuen Homöomorphismus $H\colon F\times [0,1]\to F\times [0,1]$ gibt, so daß  $H(x,0)=(h(x), 0)$ und $H(x,1)=(h'(x), 1)$.

Da die Gleichungen $g=hfh^{-1}$ und $g=(hf^n)f(hf^n)^{-1}$ äquivalent sind, erzeugt jeder Homöomorphismus $h\colon F\to F$, der $f$ zu $g$ konjugiert, die unendliche Menge $hf^n$ von konjugierenden Homöomorphismen. Alle solchen Homöomorphismen heißen äquivalent.

Satz 7.2. (G. Hemion) Für jedes $f,g$ ist die Menge von Äquivalenzklassen endlich. Die Klassen lassen sich durch algorithmisch konstruierte Homöomorphismen repräsentieren.

Daraus folgt, daß das Homöomorphieproblem für Stallingssche Mannigfaltigkeiten algorithmisch lösbar ist.

7.2. Vertikale Gerüste.

Definition. Ein abstraktes 2-dimensionales Polyeder $P$ heißt vertikal, wenn das folgende gilt:

1. $P$ enthält eine Menge $\{F_0,\ldots, F_{n-1}\}$ von disjunkten Flächen, die zu einer fixierten Fläche $F$ homöomorph sind.
2. Die abgeschlossene Hülle jeder Komponente von $P\setminus \cup_iF_i$ ist das Produkt $G_i\times [0,1]$, wobei $G_i$ ein Graph ist.
3. Die Graphen $G_i\times \{ 0\}$ und $G_{i-1}\times \{ 1\}$ liegen auf $F_i$, sind dort transversal und jeder Graph enthält $\partial F_i$ und zerlegt $F_i$ in Scheiben (Indizes werden modulo $n$ genommen).
4. Die durch die Identität definierte Abbildung $G_i\times \{ 0\} \to G_i\times \{ 0\}$ läßt sich zu einem Homöomorphismus $F_i\to F_{i+1}$ erweitern.

Figure: Vertikale Gerüste sind Gerüste von Stallingsschen 3-Mannigfaltigkeiten.

Satz 7.3.

1. Jedes vertikale Gerüst $P$ läßt sich in eine Stallingssche 3-Mannigfaltigkeit $M$ eingebettet, so daß  $M\setminus P$ aus offenen Bällen besteht.
2. $M$ ist durch $P$ eindeutig bestimmt.
3. Jede Stallingssche 3-Mannigfaltigkeit besitzt ein vertikales Gerüst.

Beweis. Offensichtlich, da für jedes $i$ die Vereinigung $F_i\cup (G_i\times [0,1])\cup F_{i+1}$ läßt sich als ein Gerüst von $F\times [0,1]$ betrachten.

Wir werden die Kompliziertheit von Gerüsten durch die Anzahl von echten Eckpunkten messen.

Satz 7.4. Jede Stallingssche 3-Mannigfaltigkeit $M$ enthält nur endlich viele minimale vertikale Gerüste. Die Gerüste kann man algorithmisch konstruieren.

Beweis. Erstens konstruieren wir ein vertikales Gerüst $P_M$. Sei $k=c(P_M)$ die Zahl seiner echten Eckpunkte. Dann zählen wir alle abstrakten vertikalen Gerüste $P$ mit $c(P)\leq k$ auf (es gibt nur eine endliche Menge von denen). Für jedes $P$ vergleichen wir die entsprechende Stallingssche 3-Mannigfaltigkeit mit $M$. So bekommen wir eine vollständige Liste des vertikalen Gerüste von $M$ mit $\leq k$ Eckpunkten. Es bleibt nur unter denen die minimale Gerüste auszuwählen.

7.3. Der Aufbau der Scheidewände geht weiter.

Jetzt machen wir den nächsten Schritt zu der Klassifikation von Haken 3-Mannigfaltigkeiten: wir füllen die Stallingsche Löcher mit minimalen vertikalen Gerüsten. Um die Auswahl endlich zu erhalten, muß  man zeigen, daß das Einstellen jedes minimalen Gerüstes durch nur endlich viele Weisen erfüllt werden kann. Es stellt sich heraus, daß es für dies nur eine Möglichkeit gibt.

Lemma 7.1. Sei $H\colon M_f\to M_f$ ein Homöomorphismus, der jede Randkomponente auf sich selbst abbildet. Dann ist $H_{\vert\partial M_f}$ isotop zur Identität.

Beweis. Wir wissen schon, daß sich die Menge von Homöomorphismen $M_f\to M_g$ durch Homöomorphisme $h\colon F\to F$, die $f$ zu $g$ konjugieren, parametrisieren läßt (Satz 7.1). Im Fall $f=g$, der uns interessiert, bilden solche Homöomorphisme eine Gruppe, in der nach dem Satz 7.2 die Untergruppe $\{f^n, n\in Z\}$ einen endlichen Index hat. Da die Homöomorphismen $S^1\times S^1\to S^1\times S^1$, die einen Kreis fix halten, die unendliche zyklische Gruppe bilden, bestimmt die Beschränkung von $H\colon M_f\to M_f$ auf jeden Randtorus von $M_f$ ein triviales Element aus dieser Gruppe. Daraus folgt, daß  $H_{\vert\partial M_f}$ isotop zur Identität ist.

7.4. Das Stopfen der Quasi-Stallingsschen Löcher.

Seien $F$ eine orientierbare Fläche und $\alpha, \beta \colon F\to F$ zwei orientierungsumkehrende fixpunktfreie Involutionen. Betrachten wir das Produkt $F\times [0,1]$ und identifizieren die Punkte von $F\times \{ 0\}$ und $F\times \{ 1\}$ durch $\alpha$ bzw $\beta$. Die resultierende 3-Mannigfaltigkeit $M_{\alpha, \beta}=F\times [0,1]/\{ (x,0)\approx (\alpha(x),0), (x,1)\approx (\beta (x),1), \}$ heißt Quasi-Stallingssche 3-Mannigfaltigkeit. Es gibt eine naturliche Faserung $M_{\alpha, \beta} \to I$, so daß alle Fasern, außer zwei singulären Fasern, zu $F$ homöomorph sind. Die singulären Fasern sind zu der Fläche $F/\alpha$ homöomorph.

Satz 7.5. Quasi-Stallingssche 3-Mannigfaltigkeiten $M_{\alpha, \beta}$ und $M_{\alpha' ,\beta'}$ sind fasertreu homöomorph $\Longleftrightarrow$ es existiert ein Homöomorphismus $\psi \colon F\to F$, so daß  $\psi \alpha \beta \psi^{-1}=\alpha'\beta'$ und $\psi \alpha \psi^{-1}=\alpha'$ (modulo Isotopie).

Beweis. Die Gleichungen oben sind zu den Gleichungen $\psi \beta \psi^{-1}=\beta'$, $\psi \alpha \psi^{-1}=\alpha'$ äquivalent, die einen Homöomorphismus $M_{\alpha, \beta} \to M_{\alpha' ,\beta'}$ bestimmen.

Die erste Gleichung hat einen klaren geometrischen Sinn. Es gibt kanonische zweiblättrige Überlagerungen $M_{\alpha\beta}\to M_{\alpha, \beta}$ und $M_{\alpha'\beta'}\to M_{\alpha' ,\beta'}$, wobei $M_{\alpha\beta}$ und $M_{\alpha'\beta'}$ die Stallingsschen 3-Mannigfaltigkeiten sind, und die Gleichung sagt uns, daß $\psi$ einen Homöomorphismmus $M_{\alpha\beta}\to M_{\alpha'\beta'}$ bestimmt. Die zweite Gleichung gewährleistet, daß dieser Homöomorphismus äquivariant ist.

Wie kann man diese Gleichungen lösen? Nach dem Satz 7.2 gibt es nur endlich viele Kandidate für $\psi$, freilich modulo Multiplizieren mit $(\alpha\beta)^n$. So können wir annehmen, daß  $\psi =\psi_0(\alpha\beta)^n$, wobei $\psi_0$ bekannt ist.

Dann läßt sich die zweite Gleichung so transformieren:

$\psi_0(\alpha\beta)^n \alpha (\alpha\beta)^{-n} \psi_0^{-1} =\alpha'$ $\Longrightarrow$ $\psi_0(\alpha\beta)^n \alpha (\beta\alpha)^{n}\psi_0^{-1} =\alpha'$ $\Longrightarrow$

$\psi_0 (\alpha\beta)^{2n} \alpha \psi_0^{-1} =\alpha'$ $\Longrightarrow$ $(\alpha\beta)^{2n}=\psi_0^{-1}\alpha'\psi_0\alpha$.

Wir sind zu dem folgenden Problem gekommen:

Existiert ein Algorithmus zur Erkennung, ob einer von zwei gegebenen Flächenhomöomorphismen eine ganze Potenz des anderen ist?

Die positive Antwort auf diese Frage würde uns die Lösung des Homöomorphieproblems von Quasi-Stallingsschen 3-Mannigfaltigkeiten geben. Man kann sie mit Hilfe von Thurston Theorie der Flächenhomöomorphismen bekommen. Jeder Homöomorphismus $f\colon F\to F$, der keine periodischen Kurven hat (und das ist unser Fall, da periodische Kurven den inkompressiblen Tori und Kreisringen entsprechen), hat einen so-genannten Dehnfaktor $\lambda (f)$. Der Dehnfaktor besitzt folgende Eigenschaften:

1. $\lambda (f)$ ist immer größer als 1.
2. $\lambda(f^n) = \lambda(f)^n.$
3. Die ausdehnenden Faktore von isotopen Homöomorphismen sind gleich.
4. Den Dehnfaktor jedes Homöomorphismus kann man algorithmisch ausrechnen.

Diese Eigenschaften erlauben uns, eine obere Grenze $N$ für die Potenzen $n$ zu finden: man muß  nur ein solches $N$ kalkulieren, daß  $\lambda^{2N}(\alpha\beta)$ größer als $\lambda(\psi_0^{-1}\alpha'\psi_0\alpha)$ ist. Dann bleibt nur, alle $n<N$ prüfen, ob $(\alpha\beta)^n$ und $\psi_0^{-1}\alpha'\psi_0\alpha$ isotop sind. Das letzte kann man leicht algorithmish feststellen.