Zur Zerlegbarkeit von Skeletten

U. BETKE, e l l . SCHULZ~, AND J. M. WILLS

Z U R Z E R L E G B A R K E I T V O N S K E L E T T E N

1. EINLEITUNG

In der vorliegenden Arbeit werden kombinatorische Eigenschaften der Randkomplexe konvexer Polytope untersucht. Dabei werden weitgehend die Bezeichnungen von Griinbaum [2] verwendet. Insbesondere sei das k- Skelett skel~ P eines Polytops P der von den h6chstens k-dimensionalen Seiten von P gebildete Komplex. Das k-Skelett des d-Polytops P, 1 ~< k ~< d - 2 heisse zerlegbar, wenn P zwei k-dimensionale Subkomplexe M1, M2 enth~ilt mit

M1 u M2 = skelk P, 3/1 n M2 = skelk_ 1 P,

deren Tr/igermengen set Ms = UF~M, F, i = 1, 2, k-dimensionale Marmig- faltigkeiten sind.

Das Paar (M1, Mz) nennen wir eine Zerlegung von skelk P, M1 und M2 die Komponenten der Zerlegung. Unter einer Mannigfaltigkeit verstehen wir eine zusammenh/ingende topologische Mannigfaltigkeit. Wo keine Mil3- verst/indnisse auftreten k6nnen, unterscheiden wir nicht zwischen einem Zellkomplex M und seiner Tr/igermenge set M.

Der Fall k = 1, der die t3berdeckung von Graphen mit zwei Kreisen bzw. Wegen behandelt, ist u.a. von B. Griinbaum/Malkevitch [3] und von Martin [6] untersueht worden. Wie im n/ichsten Abschnitt gezeigt wird, ist eine Zerlegung des k-Skeletts mit k > 2 zumindest fiir den Fall, dass M~, M2 stiiekweise lineare Mannigfaltigkeiten sind (vgl. [5]), nicht m6glich. Wir besehr/inken uns deshalb aufden Fall k = 2 und nennen ein Polytop zerlegbar, wenn sein 2-Skelett zerlegbar ist. Da d-Polytope mit d >i 6 niemals zerlegbar sind (vgl. Abschnitt 2), und da aus k = 2 und k ~< d - 2, d/> 4 folgt, bleiben Polytope der Dimensionen 4 und 5 zu untersuchen.

Im zweiten Abschnitt werden notwendige Bedingungen ftir Zerlegbarkeit bewiesen und einige Beispiele zerlegbarer Polytope angegeben. Im dritten Abschnitt wird gezeigt, dass die Zerlegbarkeit der einfachen 4-dimensionalen Prismen /iquivalent zur Vierfarbenvermutung ist. Im vierten Abschnitt werden die zerlegbaren simplizialen Polytope vollstfindig charakterisiert, w/ihrend der fiinfte Abschnitt Fragen der Eindeutigkeit von Zerlegungen behandelt. Die Hauptergebnisse der Arbeit stehen in den S/itzen 6, 12, 13, 14 und 16.

2. IN~OTWENDIGE BEDINGUNGEN UND BEISPIELE

Wir leiten zuniichst einige einfache, aber ntitzliche notwendige Bedingungen fiir die Zerlegbarkeit her.

Geometriae Dedicata 5 (1976) 435-451. All Rights Reserved Copyright © 1976 by D. Reidel Publishing Company, Dordrecht-Holland

436 U. BETKE ET AL.

LEMMA 1. Das k-Skelett eines d-Polytops P, 1 <<. k <<. d - 2 sei zerlegbar in die beiden k-Mannigfaltigkeiten M1 und 3"12. Dann gilt M1 n Ma = skelk_ 1 P.

Beweis. Eine ( k - 1)-Seite einer k-Mannigfaltigkeit liegt in h6chstens zwei k-Seiten dieser Mannigfaltigkeit. Eine ( k - 1)-Seite eines d-Polytops mit k ~< d - 2 liegt in mindestens drei k-Seiten.

In [8] wird bewiesen, dass fiir einen Teilkomplex M des Randkomplexes eines konvexen d-Polytops P, der skelk P, k ~< d - 2, enthfilt, und dessen Tr~germenge eine stiickweise lineare n-Mannigfaltigkeit ist (vgl. [5]), die Ung- leichung n >/2k gilt. (Der dort nur fiir geschlossene orientierbare Mannig- faltigkeiten geftihrte Beweis l~isst sich ohne weiteres auf berandete und nicht orientierbare iibertragen.) Zumindest ffir diese Klasse yon Mannigfaltigkeiten ist also nach dem obigen Lemma eine Zerlegung yon k-Skeletten mit k > 2 nicht mfglich. Im folgenden beschrfinken wir uns daher auf den Fall k = 2. Analog zum in der Graphentheorie benutzten Begriff der Valenz einer Ecke definieren wir als Valenz der Kante eines d-Polytops P die Anzahl der 2-Seiten yon P, die diese Kante enthalten.

LEMMA 2. Die Kanten eines zerlegbaren Polytops sind h6chstens 4-valent. Die 3-valenten Kanten bilden ein System kantendisjunkter Kreise, wobei von dreien dieser Kreise stets zwei vollkommen disjunkt sind.

Beweis. Sei M eine Zellzerlegung einer 2-Mannigfaltigkeit. Dann liegen jeweils die Randkanten von M in genau einer 2-Seite von M; sie bilden ein System paarweise disjunkter Kreise. Alle iibrigen Kanten liegen in genau zwei 2-Seiten von M. Mit Lemma 1 ergibt sich hieraus die Behauptung.

Bemerkung. Da eine Kante eines d-Polytops in mindestens d - 1 2-Seiten liegt, folgt aus Lemma 2, dass hfchstens Polytope der Dimensionen 4 und 5 zerlegt werden k6nnen.

LEMMA 3. Sei P ein zerlegbares Polytop und V die Eckenfigur an einer beliebigen Ecke v yon P (vgl. [2]). Dann ist skell V zerlegbar.

Beweis. Seien M1, M2 die beiden Mannigfaltigkeiten, in die skel2 P zerffillt. V habe die Darstellung V = H n P, wobei Heine Hyperebene ist, die v und vertP\(v) echt trennt. Dann bilden /~t = { F n H: F e M1} und M2 = {F n H: F e Mz} eine Zerlegung von skelt V.

Die angefiihrten notwendigen Bedingungen sind keineswegs hinreichend:

BEISPIEL 4. Q sei die Pyramide fiber dem Viereck. Die Basis von Q heiBe Found die iibrigen Facetten F1 . . . . . /74 (Abb. 1.).

P sei die Pyramide fiber Q mit Spitze x. Ist P zerlegbar, so folgt mit Lemma 3 auf x angewandt, dass skell Q zerlegbar ist. Da Q vier 3-valente Ecken hat, miissen die Komponenten dieser Zerlegung zwei Hamilton-Wege W1, W2 auf Q sein, und man sieht leicht, dass dies im wesentlichen auf zwei verschiedene Arten m6glich ist.

d c

F3

ZUR ZERLEGBARKEIT VON SKELETTEN 437

o b Abb. 1.

Zunfichst sei W1 = adebc und W2 = baecd.

Dann geh6ren die vonder Ecke x und den auf W1 gelegenen Ecken und Kanten gebildeten 2-Seiten yon P zur Komponente M~ der Zerlegung yon P, und entsprechendes gilt ffir die Komponente M2 und den Weg W2 (vgl. Beweis yon Lemma 3). Aus Symmetriegriinden k6nnen wit o.E. Foe 3,/1 annehmen. M~ ist eine 2-Mannigfaltigkeit, d.h. jede Kante liegt in h6chstens zwei 2-Seiten yon Mx. Wendet man dies auf die Kanten [a, d] und [b, c] an, so folgt F4, F2 e M2. Eine analoge Argumentation mit M2, [a, e] und [c, e] liefert F1, Fa e M1. Dies fiihrt zum Widerspruch, da st(b, M2) keine Kreis- scheibe, M2 also keine Mannigfaltigkeit ist.

Die zweite M6glichkeit, skelx Q in zwei Hamilton-Wege zu zerlegen, ist Wz = adceb und W2 = cbaed. Sie ergibt in/ihnlicher Weise einen Wider- spruch.

P ist also nicht zerlegbar, obwohl die notwendigen Bedingungen yon Lemma 1-3 erffillt sind:

Im Fall von Lemma 3 hatten wir dies ffir die Ecke x bereits gezeigt. Die Eckenfigur an e ist ebenfalls die Pyramide fiber dem Viereck, und die iibrigen Eckenfiguren sind Tetraeder. Ebenso erfi~llt P die in Lemma 2 geforderten Bedingungen. Welter enth/ilt skel2 P eine 2-Mannigfaltigkeit Mmit skel~P c M (vgl. Lemma 1), n/imlich das M6biusband

M -- skell P u {F0, F1, Fa, conv{a, d, x}, conv{d, e, x}, conv(b, e, x}, conv{b, c, x)}.

Die folgenden Beispiele zeigen, dass trotz der starken Einschrfinkungen sehr unterschiedliche Zerlegungen m6glich sind, z.B. 1/isst sich das 4-Simplex T 4 in zwei M6biusb~inder zerlegen. Bezeichnen wir die Ecken von T 4 mit a, b, c, d, e, so bilden die 2-Seiten conv(a, b, c), cony(b, c, d), conv(c, d, e), conv{a, d, e) und cony(a, b, e) zusammen mit skel~ T 4 ein M6biusband M~,

438 u . BETKE ET AL.

und die iibrigen 2-Seiten yon T 4 bilden zusammen mit skel~ T 4 ebenfalls ein M6biusband M2. Die R/inder yon M1 und M2 bilden eine Zerlegung yon skell T 4. Deswegen bilden diejenigen 2-Seiten des 5-Simplex T ~ (aufgefasst als Pyramide fiber T4), die nicht in M1 u M2 liegen, zweiKreisscheiben, dieM~ und M2 zu projektiven Ebenen schliel3en. T 5 ist also ebenfaUs zerlegbar. Analog iJberlegt man sich, dab das Prisma fiber T 4 zerlegbar ist. Sein 2- Skelett zerfhllt in zwei Kleinsche Flaschen.

Die bisherigen Beispiele brachten Zerlegungen in berandete und geschlossene nichtorientierbare 2-Mannigfaltigkeiten; die beiden folgenden bringen Zerlegungen in berandete bzw. geschlossene orientierbare 2-Mannigfaltig- keiten:

Die Pyramide fiber dem Oktaeder l~sst sich in zwei gelochte Tori zerlegen. Da sp/iter weitere Zerlegungen in berandete orientierbare 2-Mannigfaltig- keiten folgen, verzichten wir auf den Beweis. Die Doppelpyramide fiber dem Oktaeder l~13t sich in zwei Tori zerlegen:

C

• e / / \ I x \ / i I F3 X.\\x

F4

a b Abb. 2.

Die Spitzen der Doppelpyramide seien x und y. 3,/1 bestehe aus Fx . . . . . #'4, den 2-Seiten, die von den Kanten des gestrichelten Hamilton-Kreises und x aufgespannt werden, den 2-Seiten, die von den Kanten des strichpunktierten Hamilton-Kreises und y aufgespannt werden und aus skel~ P. Der Komplex M2, bestehend aus den iibrigen 2-Seiten von P und skell P, ist ein zu M1 isomorpher Komplex. set Mo i = 1, 2 ist homeomorph zum Torus.

Entfernt man aus dem Schlegeldiagramm der soeben untersuchten Doppel- pyramide fiber dem Oktaeder die 2-Seite conv(a, d, x}, so hat man eine Zerlegung in einen Torus und einen gelochten Torus, und mit einfachen


Oberlegungen erh~ilt man, dass das neue Diagramm das Schlegel-Diagramm der konvexen Hfille aus dem 3-dimensionalen Doppelsimplex D und einem zur Basis von D parallelen, aber gedrehten Dreieek ist.

Diese Beispiele zeigen, dass verschiedene 4- und 5-Polytope zerlegbar sind, und der folgende Abschnitt enth/ilt eine grosse Klasse weiterer Beispiele. Auch der topologische Typ der hierbei auftretenden 2-Mannigfaltigkeiten kann offenbar recht unterschiedlich sein (berandet, geschlossen, orientierbar und nieht-orientierbar). Aus Lemma 1 folgt allerdings, dass keine dieser Mannig- faltigkeiten homeomorph zur 2-Sph/ire oder zu Teilen der 2-Sph/ire ist, da sieh der Graph eines d-Polytops, d >t 4 nicht in die 2-Sph/ire einbetten l~sst (vgl. [2], Satz 11.1.2 und [10], Satz 14.7).

3. Z E R L E G U N G VON PRISMEN UND DAS VIERFARBENPROBLEM

Unter dem Prisma fiber einem (d - 1)-Polytop Q versteht man das d-Polytop P = conv{Q, x + Q}, wobei x E Ea/{0) ein nicht zu aft Q paralleler Vektor ist.

Es ist vert P = vert Q u vert(x + Q). Die k-Seiten von P mit 1 ~< k ~< d - 1 sind einerseits die k-Seiten von Q und x + Q, andererseits Seiten des Typs cony(F, x + F), wobei Feine (k - 1)-Seite von Q ist (vgl. [2], Abschnitt 4.4). Die Seiten dieses Typs nennen wir Verbindungsseiten von P. Q heisst Basis yon P.

Wir zeigen in diesem Abschnitt, dass die Frage der Zerlegbarkeit der einfaehen 4-dimensionalen Prismen fiquivalent zum Vierfarbenproblem ist. Daher untersuchen wir jetzt Prismen, deren Basis Q ein einfaches 3-Polytop ist, also nur 3-valente Ecken hat.

LEMMA 5. Sei Q ein einfaches 3-Polytop und P = conv{Q, x + Q} das Prisma i~ber Q. P ist genau dann zerlegbar, wenn es eine Klasseneinteilung sowohl der Facetten yon Q in zwei Klassen A und B als auch der Kanten yon Q in zwei Klassen a und b so gibt, dass J'ar v E vert Q stets gilt:

Von den drei Facetten F1, F2, 1:3 yon Q, die in v anstoflen, sind F1 und F2 A-Facetten, und F3 ist eine B-Facette. (Fine in der Klasse A gelegene Facette nennen wir A-Facette usw.) 171 c3 Fz ist eine b-Kante. Von den i~brigen beiden Kanten, die in x anstoflen, ist die eine a-Kante und die andere b-Kante. Oder es gilt die entsprechende Eigenschaft, wenn man A mit B und a mit b vertauscht.

Beweis. Angenommen, P ist zerlegbar und M1 und M2 seien die beiden Komponenten der Zerlegung. Die in M1 gelegenen Facetten von Q seien die A-Facetten und die in Mz gelegenen die B-Facetten. Eine Kante von Q sei genau dann eine a-Kante, wenn die von ihr aufgespannte Verbindungsseite von P in M1 liegt. Analog seien die b-Kanten definiert. Wir mfissen nun zeigen, dass diese Klasseneinteilungen der Facetten und Kanten von Q an jeder Ecke das Verlangte liefert.

Sei also v ~ vert Q beliebig und F1, F2, Fa die drei in v anstoBenden Facetten

440 U. BETKE ET AL.

von Q. Sei F1, F2, Fa ~ A. Da eine Kante in h6chstens zwei 2-Seiten von Mx liegt, folgt hieraus, dass alle drei in v anstoBenden Kanten von Q b-Kanten sind. Dies fiihrt zum Widerspruch, da dann die von v aufgespannte Ver- bindungskante conv{v, x + v} in drei 2-Seiten von M2 liegt. Wir k6nnen also o.B.d.A. F1, F2 ~ A und Fa e B annehmen. F~ r~ F2 ist eine b-Kante, da sie sonst in drei 2-Seiten von M1 l/ige. Von den iibrigen beiden in v anstol3enden Kanten ist mindestens eine aus a. Sind F~ c~ Fa und F2 c~ Fa a-Kanten, dann enth~lt st(v, M2) nur zwei 2-Seiten, n~imlich Fa und die vonder b-Kante F1 n F2 aufgespannte Verbindungsseite von P. Also ist st(v, M2) keine Kreisseheibe und damit M2 keine Mannigfaltigkeit. Also geh6rt genau eine dieser beiden Kanten zu a und eine zu b, womit alles gezeigt ist.

Seien nun umgekehrt Klasseneinteilungen der Facetten und Kanten von Q gegeben, die an jeder Ecke die obige Eigenschaft haben. Wir definieren:

M~ = skell P w {F: Fist A-Faeette} w (x + F: Fist A-Facette} u (conv(K, x + K}: K ist a-Kante}

und analog M2 mit den B-Facetten und b-Kanten. Wir miissen nun noch M1 und M2 als Mannigfaltigkeiten nachweisen, und tun dies fiir M~. Nach Voraussetzung ist fiir v ~ vert Q st(v, M~) eine Kreisscheibe, und das gleiche gilt fiJr v e vert(x + Q). Es bleibt zu zeigen, dass M~ zusammenh~ingend ist. Hierzu reicht es aus, den Zusammenhang der aus den A-Seiten und a-Kanten gebildeten Menge M zu zeigen. Ist M nicht zusammenh/ingend, dann gibt es zwei Ecken v~ und v2, die durch eine Kante verbunden sind, so dass gilt: v~ ~ F,, i = 1, 2, und F~ und F2 sind A-Facetten aus verschiedenen Zusam- menhangskomponenten von M (Abbildung 3).

1=3

1 F4

Abb. 3.

Daraus folgt, dass F3, F~ B-Facetten sind. Dies f'tihrt zum Widerspruch, da dann nach Voraussetzung [vl, v2] eine a-Kante ist, so dass F1, F2 in der gleichen Zusammenhangskomponente von M liegen. M1 und M2 bilden also eine Zerlegung von skel2 P und Lemma 5 ist bewiesen.

Bemerkung. MI ist genau dann orientierbar, wenn es eine Orientierung der a-Kanten und eine Orientierung der A-Facetten gibt, so dass gilt:

Z U R Z E R L E G B A R K E I T VON SKELETTEN 441

(a) Die Kanten eines aus a-Kanten gebildeten Weges sind koh[irent orientiert.

(b) Die Orientierung einer a-Kante K, die an einer A-Facette F liegt, ist umgekehrt zu der von der Orientierung von F auf K induzierten.

Entsprechendes gilt fiir 3/2 (siehe hierzu Abbildung 4).

SATZ 6. Sei P = conv{Q, x + Q) das Prisma i~ber einem einfachen 3- Polytop Q. Dann gilt: P ist genau dann zerlegbar, wenn Q vierfiirbbar ist, d.h. wenn es eine Einteilung der Facetten yon Q in vier Klassen so gibt, dass zwei Facetten aus der gleichen Klasse keine Kante gemeinsam haben.

Beweis. Wenn P zerlegbar ist, dann konstruieren wir mit den Klassen- einteilungen aus Lemma 5 eine Einteilung der Kanten von Q in drei Klassen:

I = {K: K ist a-Kante und liegt in zwei B-Facetten} u {K: K ist b-Kante und liegt in zwei A-Facetten}

II = {K: K ist a-Kante und liegt in einer A- und einer B-Facette} III = {K: K ist b-Kante und liegt in einer A- und einer B-Facette).

Nach Konstruktion dieser Klasseneinteilung st613t in jeder Ecke yon Q genau eine Kante aus jeder der drei Klassen an.

Eine solche 'Dreif/irbung der Kanten' ist aber /iquivalent zur Vierf/irb- barkeit von Q (Satz von Tait, vgl. [10], Satz 15.13).

Sei umgekehrt eine F~rbung der Facetten von Q mit den vier Farben 1, 2, 3, 4 gegeben. Wir definieren eine Klasseneinteilung der Kanten von Q:

I = {K: K liegt in einer 1- und einer 2-Facette oder in einer 3- und einer 4-Facette}

II = {K: K liegt in einer 1- und einer 3-Facette oder in einer 2- und einer 4-Faeette}

III = {K: K liegt in einer 2- und einer 3-Facette oder in einer 1- und einer 4-Facette}.

Diese Einteilung ist eine Dreiffirbung der Kanten yon Q, d.h. in jeder Ecke st6Bt genau eine Kante aus jeder der drei Klassen an (vgl. [10], S. 144). Hieraus konstruieren wir eine Einteilung der Facetten und Kanten yon Q, die die Voraussetzungen von Lemma 5 erfiillt. Die A-Facetten seien die Facetten der Farben 1 und 2. Die B-Facetten seien die Facetten der Farben 3 und 4. Die Kanten von Q, die in einer 1- und einer 2-Facette liegen, seien b-Kanten. Die Kanten, die in einer 3- and einer 4-Facette liegen, seien a-Kanten. SchlieBlich seien noch alle Kanten aus der Klasse II a-Kanten und die Kanten der Klasse III b-Kanten. Nach Lemma 5 erhalten wir hieraus die Zerleg- barkeit von P.

Aus diesem Satz ergibt sich (vgl. [2], S. 364):

KOROLLAR 7. Die Vermutung, dass alle einfachen 4-Prismen zerlegbar sind, ist iiquivalent zur Vierfarbenvermutung.

Aus einer 4-F/irbung der Facetten eines einfachen 3-Polytops Q lassen sich

442 U. BETKE ET AL.

nach der im Beweis von Satz 6 dargestellten Methode Zerlegungen des Prismas fiber Q konstruieren. So gibt es eine Zerlegung des 2-Skeletts des 4-dimensionalen Wiirfels in zwei jeweils 4-fach gelochte Tori und eine weitere Zerlegung in einen 4-fach gelochten Torus und eine 2-fach gelochte Brezel- fl/iche. Die Zerlegung eines Polytops ist also hinsichtlieh des topologischen Typs der beiden Komponenten keineswegs eindeutig bestimmt. Ein allgemeineres Beispiel hierzu findet sich im fiinften Abschnitt. In den bisherigen Beispielen von Zerlegungen waren M1 und M2 entweder beide orientierbar oder beide nicht-orientierbar. Dies mul~ jedoch nicht der Fall sein.

/I/1111~ i / i \

/I I xF'X // Abb. 4.

Ein Beispiel hierfiir ist das Dreiecksprisma Q, dessen Schlegel-Diagramm Abbildung 4 zeigt. Die A-Facetten yon Q seien Fund F'. Die a-Kanten sind in Abbildung 4 gestrichelt eingezeiehnet. Die fibrigen Facetten und Kanten von Q sind die B-Facetten und b-Kanten. Hieraus ergibt sich nach Lemma 5 eine Zerlegung des Prismas fiber Q in eine l-faeh gelochte nieht-orientierbare Fl/iche vom Geschlecht 4 und einen 2-fach gelochten Toms.

Bei den Zerlegungen einfaeher 4-Polytope sind die Komponenten stets berandete Mannigfaltigkeiten, da alle Kanten 3-valent sind. Aus jedem solchen 4-Polytop l~13t sich jedoch ein 5-Polytop konstruieren, dessen 2-Skelett sich in zwei geschlossene Mannigfaltigkeiten zerlegen 15sst:

LEMMA 8. 1st das einfache 4-Polytop Q zerlegbar, so ist das Prisma P = eonv{Q, x + Q} i2ber Q ebenfalls zerlegbar.

Beweis. Seien M1 und M2 die Komponenten der Zerlegung von Q. Da alle Kanten von Q 3-valent sind, sind M1 und M2 berandete Mannigfaltigkeiten, und die Vereinigung der R/inder von M1 und M2 ist eine 1Stberdeckung der


Kanten yon Q mit kantendisjunkten Kreisen (vgl. Lemma 2). Wir definieren:

M: = M~ U {x + F : F e Mt} u {eonv{F, x + F} : F liegt im Rand von M~}

ffir i = 1, 2. Die M~ sind geschlossene 2-Mannigfaltigkeiten (vgl. [8], S. 37 ft. und [9] S. 129/144), die eine Zerlegung von skel2 P bilden.

4. Z E R L E G U N G SIMPLIZIALER POLYTOPE

Ziel dieses Absehnitts ist es, die zerlegbaren simplizialen Polytope zu eharak- terisieren.

LEMMA 9. Ein zerlegbares simpliziales 4-Polytop P hat h6chstens 10 Ecken. Ist eine der Komponenten der Zerlegung berandet, so hat P sogar nur h6ehstens 8 Eeken.

Beweis. P ist simplizial, also folgt aus den Dehn-Sommerville-Gleiehungen:

A = 2 f l - 2fo (vgl. [7], S. 112). Aus Lemma 2 folgt, da alle 2-Seiten Dreieeke sind:

(+ ) 4fl /> 3f2.

Damit ist

(+ +)f~ ~< 3fo.

Naeh [1], Formel (1) gilt:

A ~ 4 fo - 10.

Zusammen mit (+ +) folgt darausfo ~< 10. Ist eine der beiden Komponenten der Zerlegung berandet, so sind die im Rand dieser Komponenten gelegenen Kanten 3-valent. P hat also mindestens drei 3-valente Kanten, so dass statt (+ ) die sehfirfere Ungleiehung

4 A - 3 ~ 3f2

gilt. Setzt man dies start (+) in die obige Argumentation ein, so folgtfo ~< 8. Damit bleiben die simplizialen 4-Polytope mit h6ehstens 10 Eeken auf ihre

Zerlegbarkeit zu untersuehen. Wir betraehten zunfiehst Zerlegungen, bei denen beide Komponenten gesehlossene Mannigfaltigkeiten sind.

LEMMA 10. Ist ein simpliziales 4-Polytop P in zwei geschlossene Kom- ponenten zerlegbar, so ist das zu P duale Polytop P* einfach und kubisch.

Beweis. P ist simplizial, also ist P* einfach. Alle Kanten von P sind 4-valent (vgl. Lemma 2), also sind alle 2-Seiten von P* 4-Ecke. Die Facetten von P* sind demnach kubische 3-Polytope. Ein kubisches 3-Polytop hat mindestens

444 U. BETKE ET AL.

6 Facetten, und das einzige kubische 3-Polytop mit 6 Facetten ist der Wiirfeh Daraus folgt:

6f3(V*) ~< 2f2(P*)

wobei Gleichheit genau dann gilt, wenn P* ein kubisches 4-Polytop ist. Da alle Kanten von P genau 4-valent sind, gilt in (+ +) im Beweis des vorigen Lemmas die Gleichheit, woraus ffir P* folgt:

f2(V*) = 3fa(P*)

das heisst, P* ist kubisch.

LEMMA 11. Das einzige einfache kubische 4-Polytop mit hiichstens 10 Facetten ist der 4-Wi~rfeL

Beweis. Sei P ein einfaches kubisches 4-Polytop mitfa(P) <~ 10. Sei ferner Qo eine beliebige Facette von P und seien Q1,. . . , Q~ die Facetten von P, die mit Q0 eine 2-Seite gemeinsam haben. Da P ein einfaches Polytop ist, hat der aus Q0 . . . . . Q6 und deren Seiten gebildete Komplex h6chstens sechs 2-Seiten, die nur in einem der Q~ liegen. Istfa(P) = 8, so ist deshalb P der 4-Wiirfel. Istfa(P) = 9, so hat P noch zwei weitere Facetten Q7 und Qa. Der aus den 3-Wfirfeln Q7 und Qa und deren Seiten gebildete Komplex enthfilt mindestens zehn 2-Seiten, die nur in einem der Q~, i = 7, 8, liegen. P hat also mindestens vier 2-Seiten, die jeweils nur in einer Facette liegen- Widerspruch. Ein analoger Widerspruch ergibt sich ffir fa(P) = 10, wo der aus den von Q0,. . . , Q6 verschiedenen Facetten QT, Qa, Qa und deren Seiten gebildete Komplex mindestens zw61f 2-Seiten enth/ilt, die jeweils nur in einem der Q~, i = 7, 8, 9 liegen.

SATZ 12. Es gibt genau vier zerlegbare simpliziale 4-Polytope und ein zerlegbares simpliziales 5-Polytop: Das 4-Simplex, das zyklische 4-Polytop mit 6 Ecken, die Doppelpyramiden i~ber dem Tetraeder und dem Oktaeder und das 5-Simplex.

Beweis. Aus Lemma 9-11 folgt ffir ein zerlegbares simpliziales 4-Polytop V fo(P) <<. 8.

Die kombinatorische Struktur der simplizialen 4-Polytope mit 8 Ecken ist in Form von Tabellen in [4] dargestellt. Aus diesen Tabellen folgt leicht, dass diese 37 verschiedenen Polytope, mit einer Ausnahme, stets eine mindestens 5-valente Kante enthalten, so dass sie nach Lemma 2 nicht zerlegbar sind. Das dort mit Paa~ bezeichnete Polytop, ffir das dies nicht der Fall ist, ist die Doppelpyramide fiber dem Oktaeder, deren Zerlegbarkeit wir bereits im zweiten Abschnitt gezeigt haben.

Die 5 verschiedenen simplizialen 4-Polytope mit 7 Ecken sind ebenfalls in [4] aufgelistet. Bis auf eine Ausnahme - das dort mit Pa 7 bezeichnete Polytop- enthalten sie eine mindestens 5-valente Kante. 4 Kanten von P] sind 3-valent, die fibrigen 4-valent. Angenommen Pa 7 ist zerlegbar. Dann ist eine der


beiden Komponenten dieser Zerlegung, etwa M~, eine geschlossene 2- Mannigfaltigkeit. Wegen Lemma 1 ist set M1 nicht homeomorph zur 2- Sph/ire. Als in die 3-Sphere eingebettete geschlossene 2-Mannigfaltigkeit muss M~ orientierbar sein. Die Euler-Charakteristik von M~ ist somit ~< 0:

A(MO - fx(M~) + fo(M~) <~ O.

Alle 2-Seiten von M~ sind Dreiecke, also ist 3f2(M~) = 2f~(M~) und damit:

fo (g l ) - ½f~(M~) ~< 0.

Wegen Lemma 1 istf0(M0 = f0(Pa 7) = 7, also

A(P~) >>. 21

im Widerspruch dazu, dass P~ nut 19 Kanten hat. Es gibt genau zwei simpliziale 4-Polytope mit 6 Ecken ([7], Theorem 3.3.9),

das zyklische Polytop C(6, 4) und die Doppelpyramide P tiber dem Tetraeder:

// / // F

\t . \ Abb. 5.

Seien a und b die Spitzen von P. Der Komplex 3/1 bestehe aus F, F', den von den in Abbildung 5 gestrichelten Kanten und a aufgespannten Dreiecken, den von den strichpunktierten Kanten und b aufgespannten Dreiecken und aus skell P. M1 ist ein M6biusband, und die iibrigen 2-Seiten von P bilden zusammen mit skell P ebenfalls ein M6biusband. Im zweiten Abschnitt batten wir gezeigt, dass skel2 T 5 in zwei projektive Ebenen zerf/illt, skel2 C(6, 4) entsteht aus skel2 T 5 durch Entfernen von zwei disjunkten 2-Seiten ([7], Proposition 2.3.18).

Also l~isst sich auch skel2 C(6, 4) in zwei M6biusb/inder zerlegen. Die Zerlegbarkeit des 4-Simplex haben wir bereits im 2. Abschnitt gezeigt.

446 U. BETKE ET AL.

Absehliessend der Nachweis, dass das 5-Simplex das einzige zerlegbare simpliziale 5-Polytop ist: Ffir ein simpliziales 5-Polytop gilt wegen der Dehn-SommerviUe-Gleichungen (s. [7], S. 112)

f2 = 4fl - lOfo + 20.

Da alle 2-Seiten Dreieeke sind und alle Kanten 4-valent, gilt 3f2 = 4fl. Aus beiden Gleichungen folgt: 4fl = 15f0 - 30. Naeh dem schon vorher zitierten Satz yon Barnette ist

0,--

Damit folgtfo ~< 6, d.h. h6chstens das 5-Simplex ist zerlegbar. Daandererseits sehon bei den Beispielen gezeigt wurde, dass das 5-Simplex in zwei projektive Ebenen zerlegbar ist, ist aUes bewiesen.

5. E I N D E U T I G K E I T VON Z E R L E G U N G E N

Wie schon im dritten Abschnitt erwihnt, gibt es Polytope, die sich auf mehr als eine Weise zerlegen lassen. Es gilt sogar:

SATZ 13. Zu jeder nati~rlichen Zahl n gibt es ein 4-Polytop P,, dessen 2-Skelett n verschiedene Zerlegungen zuliisst, so dassJ~r die n Paare (Mf , M~), 1 <<. k <~ n, yon Zerlegungskomponenten gilt: Die M~ sind paarweise nicht-homeomorph. Die M~ sind zueinander homeomorph.

Beweis. Sei o.E. n i> 2 und Qn das dreidimensionale Prisma fiber dem 2n-Eck. E und G seien die beiden 2n-eckigen Facetten von Qn und F1 . . . . . F, die Verbindungsfacetten von Qn in zyklischer Reihenfolge. Wir zeigen, dass das 4-Prisma Pn fiber Q, die gewiJnschten Eigenschaften hat, indem wir n verschiedene Klasseneinteilungen der Facetten und Kanten von Q, konstruieren, die den Bedingungen von Lemma 5 genfigen. Bei allen n Einteilungen seien die A-Facetten die F~ mit ungeradem i; und alle fibrigen Facetten von Qn seien B-Facetten. Ferner seien die Kanten von Qn, die in keiner A-Facette liegen, a-Kanten. Die n Klasseneinteilungen unterscheiden sich durch die Einteilung der iibrigen Kanten yon Qn, d.h. der Kanten der F~ mit ungeradem i. Ein solches F~ heil3e vom Typ 1, wenn F~ n G und F~ n E a-Kanten sind und die fibrigen beiden Kanten yon F~ b-Kanten. Sind F~ n G, F~ n E b-Kanten und die anderen Kanten a-Kanten, so heisse F~ vom Typ 2. Die k-te Einteilung 1 ~< k ~< n d e r Facetten und Kanten von Q, ist dadurch definiert, dass F1+2~, 0 ~< i ~ k - 1, vom Typ 1 sind und F~+'a~, k ~< i ~< n - 1 vom Typ 2.

Abb. 6 zeigt die drei Einteilungen im Fall n = 3; die a-Kanten sind

Z U R Z E R L E G B A R K E I T V O N S K E L E T T E N 447

E E

//" F2 .,'~"---'~x F6 \" <

k=1 k=2

E

/ / /~x, F l ? \ x . / / F2 ) - ' - - - - ( \ F 6 \ \

( < (3 > > \ \ F \ z 3 /~----<x F 5 / /

,,Z_ k=3

Abb . 6.

gestrichelt. Zur k-ten Einteilung geh6rt nach Lemma 5 eine Zerlegung von P, in die Komponenten M~, geh6rig zu den A-Facetten und a-Kanten, und M#, geh6rig zu den B-Facetten und b-Kanten. Aus der Bemerkung zu Lemma 5 folgt, dass alle M~ orientierbar sind. Es gilt:

A(M~') = 6n, 1 ~< k ~< n.

Naeh Lemma 1 haben deshalb alle M~ die gleiehe Euler-Charakteristik; M~ und M~" sind demnach genau dann homeomorph, wenn ihre R/inder aus der gleichen Anzahl von Kreisen bestehen.

Die Anzahl dieser Kreise betr/igt bei M~ 2k, so dass die M~ paarweise nicht- homeomorph sind. In Abbildung 7 sind die Kanten von Qa, die im Rand von M~ liegen, gestrichelt gezeichnet. Die M~ haben ebenfalls s/imtlich die gleiche Euler-Charakteristik. Die Anzahl ihrer Randkreise ist jedoch unabh/ingig von k. Sie betr~tgt 2n. Die M~ sind deshalb alle vom gleichen topologischen Typ. In Abbildung 7 sind die Kanten von Q3, die im Rand von M~ liegen, als durchgezogene Linien eingezeichnet.

Wir wollen nun eine Aussage beweisen, die man erh/ilt, wenn man in Satz 13 die Rollen von Mannigfaltigkeit und Polytop vertauscht, d.h., wir geben ein Paar von Mannigfaltigkeiten M1, M2 vor und fragen nach der Existenz verschiedener Polytope, die eine Zerlegung mit zu M1 und M2 homeomorphen Komponenten zulassen.

SATZ. 14. Zu jeder natiirlichen Zahl n gibt es ein Paar M~, M"2 yon 2-Mannig- faltigkeiten und n paarweise nicht isomorphe 4-Polytope P1 . . . . . P,, die eine Zerlegung zulassen, deren Komponenten zu M~ und ME homeomorph sind.

Beweis. Wir konstruieren mit Hilfe von Lemma 5 Prismen, die das Gewiinschte leisten. Fiir k, I e [~ sei Gk.~ der in Abbildung 8 dargestellte Graph.

448 U. BETKE ET AL.

E

,,' \x F1 /'x,,, / / N / / F2 /%"--"-<x, F6 X\

\\ F 3 ~- - - -~ F 5 / / \ \ L / / F4 ~ / /

k=l

E

/~\ F1 /'x,,. / x (/ \ / F 2 ) F6 \ / \

- - - . q G ,~, ~, F 3 ~-- ' -~ F 5 / /

/ F 4 % / /

k=2

E A ¢N

/ / \ \ F1 I I \ \ / / F2 /~ - - " (x F6 \ \

k=3

Abb. 7.

Ol 02 Q3 Ok ak*l Ce÷l Ce C3 C2 C1

bl b2 b3 bk bk.l de+l de d3 62 dl

Abb. 8.

G~,~ erg~mzen wir zu einem 3-zusammenh/ingenden Graphen, wie in Abbildung 9 gezeigt, der nach dem Satz von Steinitz Kantengraph eines einfachen 3-Polytops Q~.t ist. Die A-Facetten von Q~,t seien D1, D2, E1 . . . . . E~+I, F1, . . . ,Ft+t , die B-Faeetten seien D3, D4, Ds. Die a-Kanten seien [x~, x2], [Yl, Ya], [a~, Ys], [Ya, Y4], [d~, Y4], die Kanten der Form [a~, a~+l] und [dt, d~+~] mit geradem i und die Kanten der Form [b~, b~+~], [c~, c~+z] mit ungeradem i, sowie ffir gerades k [xl, b~+l] bzw. ffir ungerades k [xl, a~+~] und ffir gerades l [x2, c,+ 1] bzw. ffir ungerades l [Xa, d,+ 1]. Alle fibrigen Kanten von Qk.z seien b-Kanten. Nach Lemma 5 wird hierdurch eine Zerlegung des Prismas Pk,, fiber Q~.~ in die Komponenten M~ '~ und M~ 'z definiert. Fiir zwei Paare (k, l) und (k', l ') natfirlicher Zahlen mit k + I = k' + l' sind M~ "~ und M~ "'r zueinander homeomorph, und das gleiehe gilt fiir M~ ,~ und ME'"'. Wir zeigen dies ffir M~ 'l = Mi und M~ "'r = M'i, M1 und M~ haben naeh Konstruktion die gleiehe Anzahl von 2-Seiten und damit nach Lemma 1 die gleiehe Euler-Charakteristik. An Hand der Bemerkung zu Lemma 5

Z U R Z E R L E G B A R K E I T V O N S K E L E T T E N 4 4 9

Yl

[33

Y3 Y4 05

Abb. 9.

priift man leicht nach, dass M1 und M~ nicht-orientierbar sind. Diejenigen Kanten von Qk.z, die im Rand von M1 liegen, sind: [Ya, Y4], [xl, Xz], [Yl, Y4], [bl, Ya] und [cx, Y2], die Kanten der Form [ao a~+ ~], [a~, d~+l] mit ungeradem i und die Kanten der Form [b~, b~÷~], [co C~+l] mit geradem i. Diese Kanten bilden k + l + 3 paarweise disjunkte Wege auf Q~,z. Der Rand von M1 besteht deshalb aus k + 1 + 3 paarweise disjunkten Kreisen. Entsprechend besteht der Rand von M~ aus k' + 1' + 3, also nach Voraussetzung aus der gleichen Anzahl von Kreisen. M~ und M~ sind demnach homeomorph. Analog beweist man die Homeomorphie von M~ a und M w'r 2 •

Fiir ein festes m e ~, m /> 2, besteht die Menge {Qk.~: k + l = m, k~< 1} aus [m/2] paarweise nicht-isomorphen Polytopen. ([~] bezeiehnet die gr6sste ganze Zahl ~ c~.) Fiir m t> 2n haben demnach die Prismen Pk,t, k + l = m, k ~< l mit den oben konstruierten Zerlegungen die im Satz behauptete Eigenschaft.

In Satz 13 haben wir eine Folge P,, n e N von Polytopen konstruiert, so dass die Anzahl verschiedener Zerlegungen der P, gegen unendlich strebt. Da der Randkomplex eines Polytops endlich ist, ist klar, dass ein festes Polytop nur h6chstens endlich viele Zerlegungen zul~isst. Im Anschluss an Satz 14 stellt sich damit die Frage, ob es zu einem fest gegebenen Paar M~, Ma von 2-Mannigfaltigkeiten auch stets nur endlich viele Polytope gibt, die sich in zu M1 und M2 homeomorphe Komponenten zerlegen lassen. Die Antwort darauf geben wir in Satz 16.

450 u. BETKE ET AL.

L E M M A 15. Sei P ein d-Polytop mit 2fa-a(P) - dfa-l(P) = k. Dann gibt es eine nut yon i, k, d abhiingige Funktion g(i, k, d) und ein simpliziales Polytop ff mit fo(P) = fo(P) und

0 <~ f~(P) - f~(P) <, g(i, k, d).

Beweis. Seien F j die Facetten yon P. Es gilt

card{F j lfa_2(F j) > d} = r <<. k

da Y4 (fa-2(Fj) - d) = k ist. Aus dem gleichen Grund ~lt fa_a(F j) <~ d+ k, so dass es eine Funktion g~(k, d) gibt mit

fo(F j) <. gx(k, d).

Insgesamt liegen also hSchstens kgl(k, d) Ecken von P in Facetten von P, die nicht Simplices sind. Dutch die Methode des Eckenziehens ([7], Kapitel 2) k6nnen wir P in ein simpliziales Polytop iiberfiihren. Da beim Ziehen an einer Ecke, deren Stern simplizial ist, sich der kombinatorische Typ des Polytops nicht/indert, geniigt es zu zeigen, dass bei jedem Ziehen die Zahl der hinzuge- kommenen Seiten durch eine nut von k, d und i abh~ngige Konstante besehr/inkt ist. Die feste Ecke x liegt in einer Anzahl yon nicht-simplizialen Facetten, die durch eine Funktion g2(k, d) beschr~inkt ist, da diese Faeetten insgesamt h5chstens kgl(k, d) Ecken haben. Aus dem gleichen Grund hat jede dieser Seiten h6chstens ga(k, d, i) i-Seiten. Beim Ziehen kommen also h6chstens g2(k, d).ga(k, d, i - 1) i-Seiten hinzu.

SATZ 16. Zu je zwei 2-Mannigfaltigkeiten M1 und 312 gibt es h~chstens endlich viele Polytope, deren 2-Skelett in zu M1 und Mz homeomorphe Mannigfaltigkeiten zerlegbar ist.

Beweis. Sei P in M1 und Ma zerlegbar. Wegen 3/1 u Mz = skel2 P und M1 n/14"2 = skell P gilt fiir die Euler-Charakteristiken ml, m2 von Mx,/1"/2:

2 f o - 2 f l + f 2 = m l + m 2 = - k , k~{0} w N.

Weiter gilt, da jede Kante von P h6chstens 4-valent ist und jede 2-Seite von P mindestens 3 Kanten entMdt: 4ft >/ 3f2 und damit

k 2fo - fx >1 - ~ .

Nach [1] Formel (1) und Lemma 15 gilt fiir d = 4:

(f2 °) -- ~r(fo - 4)(fo -- 5 ) - g(2, k, 4).

Eingesetzt in (*) ergibt sich

2fo - 4fo ~> k 10 - g(2, k, 4).

Z U R Z E R L E G B A R K E I T VON SKELETTEN 451

Also ist fo beschrfinkt. Ana log folgt fiir d = 5:

f~ I> 5fo - 15 - g(2, k, 5).

Eingesetzt in (*) folgt:

k 2fo - 5fo I> - ~ - 15 - g(2, k, 5).

Also ist auch fiir d = 5 fo beschrfinkt. D a h6chstens 4- und 5-Polytope zerlegbar sind, ist alles bewiesen.

B I B L I O G R A P H I E

1. Barnette, D.W.: 'A Proof of the Lower Bound Conjecture for Convex Polytopes', Pac. J. Math. 46 (1973), 349-354.

2. GriJnbanm, B.: Convex Polytopes, Interscienc¢, New York, 1967. 3. Grfinbaum, B. and Malkevitch, J.: 'Pairs of Edge-disjoint Hamiltonian Circuits',

erscheint demniichst in Aequationes Mathematicae. 4. Griinbaum, B. and Sreedharan, V.P.: An Enumeration of Simplicial 4-Polytopes

with 8 Vertices', J. Comb. Theory 2 (1967), 437-465. 5. Hudson, J. F. P.: Piecewise Linear Topology, Amsterdam/New York, 1969. 6. Martin, P.: ' Cycles Hamiltoniens dans les graphes 4-reguliers 4-connexes', erscheint

denm~ichst in Aequationes Mathematieae. 7. McMullen, P. and Shephard, G.C.: Convex Polytopes and the Upper Bound Con-

jecture, Cambridge University Press, Cambridge, 1971. 8. Schulz, Ch.: ' Mannigfaltigkeiten mit Zellzerlegung im Randkomplex eines konvexen

Polytops trod veralIgemeinerte Hamilton-Kreise', Dissertation, Bochum 1975. 9. Seifert, H. and ThrelfaU, W.: Lehrbuch der Topologie, Chelsey/New York, 1947.

10. Wagner, K.: Graphentheorie, BI 248/248a, Mannheim, 1970.

(Eingegangen am 18. Juli 1975)

Anschrift der Verfasser :

U. Betke, Ch. Schulz, and J. M. Wills, Lehrstuhl ftir Ma thema t ik II , G H Siegen, 59 Siegen 21 HSlderlinstr. 3 Bundesrepublik, Deutschland

Documents

Zur Zerlegbarkeit von Skeletten