Scale-Isometric Polytopal Graphs in Hypercubes and Cubic Lattices: Polytopes in Hypercubes & Zn

Scale-Isometric Polytopal Graphs in Hypercubes and Cubic Lattices

Polytopes in Hypercubes and

This page intentionally left blank

Scale-Isometric Polyt Graphs in Hypercubes and Cubic Lattices

Polytopes in Hypercubes and

Michel Deza Ecole Normale Superieure & CNRS, Paris, France

Viatcheslav Crishukhin Central Institute of Mathematical Economics, Moscow, Russia

Mikhail Shtogrin Stekloo Mathematrcal hstitute, Moscow, Russia

Imperial College Press

Published by

Imperial College Press 57 Shelton Street Covent Garden London WC2H 9HE Distributed by

World Scientific Publishing Co. Re. Ltd. 5 Toh Tuck Link, Singapore 596224 USA ofice: Suite 202, 1060 Main Street, River Edge, NJ 07661 UK ofice: 57 Shelton Street, Covent Garden, London WC2H 9HE

British Library Cataloguing-in-PublicationData A catalogue record for this book is available from the British Library.

SCALE-ISOMETRIC POLYTOPAL GRAPHS IN HYPERCUBES AND CUBIC LATTICES Polytopes in Hypercubes and Z. Copyright 0 2004 by Imperial College Press All rights reserved. This book, or parts thereoj may not be reproduced in any form or by any means, electronic or mechanical, includingphotocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher.

For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher.

ISBN 1-86094-421-3

Printed in Singapore by World Scientific Printers ( S ) Pte Ltd

Preface

This research monograph is a follow-up to the book Geometry of Cuts and Metrics by M.Deza and M.Laurent, published in 1997 by Springer-Verlag, Berlin (Russian translation was published in 2001 by MCNMO, Moscow). The main object of that book was the el-metrics, i.e. those isometrically embeddable, up to a scale, into some hypercube H , or, if infinite, into some cubic lattice 2,. During the last six years a lot of work was done on a special case of el-metric: the graph distance of the skeleton of (finite or infinite) polytope. This monograph consists mainly of identifying such polytopes combinatorially C1-embeddable, within interesting lists of polytopal graphs, i.e. such that corresponding polytopes are either prominent mathematically (regular partitions, root lattices, uniform polytopes and so on), or applicable in Chemistry (fullerenes, polycycles etc.) The embeddability, if any, provides applications to chemical graphs and, in the first case, it gives new combinatorial perspective to &-prominent affine polytopal objects. The lists of polytopal graphs in the book, come from broad areas of Geometry, Crystallography and Graph Theory; so, just to introduce them we need many definitions. The book concentrates on such concise and, as much as possible, independent definitions. The scale-isometric embeddability - the main unifying question, to which those lists will be subjected - will be presented with the minimum of technicalities. The main families of the considered graphs come from: various generalization of regular polytopes (or tilings), from (point) lattices and from applications in Chemistry. Some samples of results are: (i) All embeddable regular tilings and honeycombs of dimension d > 2, are, besides the hyper-simplices and hyper-octahedra, exactly those with

V

vi

Scale Isometric Polytopal Graphs

bipartite skeleton: the hyper-cubes, cubic lattices and 11 special tilings of hyperbolic space. (ii) If P is an Archimedean polyhedron or a plane partition, other than 3-gonal prism, then exactly one of P and its dual P is embeddable. (iii) For the regular 4-polytope 24-cell, its usual and golden truncation (Gosset’s semi-regular 4-polytope) are embedded into Hlz and half-Hl2 , respectively. (iv) The skeletons of Voronoi tiling for the lattice A, and its dual lattice A: are embedded into Z,+l and Z n.tl , respectively. ( 2 ) The book is organized as follows. Relatively long introduction (chapter 1) gives main notions, as well as methods of embedding. After reading it, any of the other chapters can be read independently. Chapters 14 and 15 consider, respectively, specifications and generalizations of the notion of embeddability. Each of chapters 2-13 is centered around embeddability for a particular list of graphs. We tried to give concise and, as much as possible, independent presentation of those lists; so that the readers of different backgrounds will be able to isolate “ready to use” chapters, which are of interest for them. Chapters 2, 4, 5, 6, 12, 13 treat various lists of 3-polytopes. Chapters 9, 10 and 11 consider infinite graphs coming from the tilings of R2, R3 and from lattices. Chapters 3, 7, 11 consider graphs in En.Finally, chapters 2, 8 and 11 can be of interest for workers in Mathematical Chemistry and Crystallography. The authors are grateful to Marie Grindel, Jacques Beigbeder and, especially, to Mathieu Dutour for various help: in drawings, redaction and inspiration. 1991 Mathematics Subject Classification: primary 05C12; secondary 52C99

Contents

Preface

V

1. Introduction: Graphs and their Scale-isometric Embedding

1

1.1

1.2 1.3 1.4 1.5 1.6

1.7

Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Embeddings of graphs . . . . . . . . . . . . . . . . . . . . Embedding of plane graphs . . . . . . . . . . . . . . . . . Types of regularity of polytopes and tilings . . . . . . . . Operations on polytopes . . . . . . . . . . . . . . . . . . . Voronoi and Delaunay partitions . . . . . . . . . . . . . . Infinite graphs . . . . . . . . . . . . . . . . . . . . . . . . .

2 . An Example: Embedding of Fullerenes 2.1 2.2 2.3

Embeddability of fullerenes and their duals . . . . . . . . Infinite families of non-ll fullerenes . . . . . . . . . . . . . Katsura model for vesicles cells versus embeddable dual fullerenes . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 . Regular Tilings and Honeycombs 3.1 3.2 3.3 3.4

25 26 30 30 35

Regular tilings and honeycombs . . . . . . . . . . . . . . . 35 The planar case . . . . . . . . . . . . . . . . . . . . . . . . 36 Star-honeycombs . . . . . . . . . . . . . . . . . . . . . . . 40 The case of dimension d 2 3 . . . . . . . . . . . . . . . . 40

4 . Semi-regular Polyhedra and Relatives of Prisms and Antiprisms 4.1 4.2

1 3 10 14 17 18 19

Semi-regular polyhedra . . . . . . . . . . . . . . . . . . . . MOSCOW, Globe and Web graphs . . . . . . . . . . . . . . . vii

43 43 45

Scale Isometric Polytopal Graphs

viii

4.3 4.4

Stellated k.gons, cupolas and antiwebs . . . . . . . . . Capped antiprisms and columns of antiprisms . . . . .

5. Truncation. Capping and Chamfering 5.1 5.2 5.3

48 50 53

Truncations of regular partitions . . . . . . . . . . . . . . Partial truncations and cappings of Platonic solids . . . . Chamfering of Platonic solids . . . . . . . . . . . . . . . .

53 54 59

6 . 92 Regular-faced (not Semi-regular) Polyhedra

63

7. Semi-regular and Regular-faced n.polytopes. n 2 4

71

7.1 7.2 7.3 7.4

Semi-regular (not regular) n-polytopes . . . . . . . . . . . Regular-faced (not semi-regular) n-polytopes . . . . . . . Archimedean 4-polytopes . . . . . . . . . . . . . . . . . . The embedding of the snub 24-cell . . . . . . . . . . . . .

8. Polycycles and Other Chemically Relevant Graphs 8.1 8.2 8.3

(r.q)-polycycles . . . . . . . . . . . . . . . . . . . . . . . . Quasi-(r, 3)-polycycles . . . . . . . . . . . . . . . . . . . . Coordination polyhedra and metallopolyhedra . . . . . . .

9. Plane Tilings 9.1 9.2 9.3

71 72 72 73 75 75 77 80 83

58 embeddable mosaics . . . . . . . . . . . . . . . . . . . . Other special plane tilings . . . . . . . . . . . . . . . . . . Face-regular bifaced plane tilings . . . . . . . . . . . . . .

10. Uniform Partitions of 3-space and Relatives

83 87 89 99

10.1 28 uniform partitions . . . . . . . . . . . . . . . . . . . . . 100 10.2 Other special partitions . . . . . . . . . . . . . . . . . . . 103 11. Lattices. Bi-lattices and Tiles 11.1 11.2 11.3 11.4

107

Irreducible root lattices . . . . . . . . . . . . . . . . . . The case of dimension 3 . . . . . . . . . . . . . . . . . . Dicings . . . . . . . . . . . . . . . . . . . . . . . . . . . . Polytopal tiles of lattice partitions . . . . . . . . . . . .

12. Small Polyhedra

12.1 Polyhedra with at most seven faces

107 108 110 111 115

............

115

Contents

ix

12.2 Simple polyhedra with at most eight faces

.........

13. Bifaced Polyhedra 13.1 13.2 13.3 13.4 13.5 13.6

Goldberg’s medial polyhedra . . . . . . Face-regular bifaced polyhedra . . . . Constructions of bifaced polyhedra . . Polyhedra 3, and 4, . . . . . . . . . . . Polyhedra 5, (fullerenes) revisited . . Polyhedra oc, (octahedrites) . . . . .

119

. . . . . . . . . . . 120

. . . . . . . . . . . 123 . . . . . . . . . . . 125

.......... 126 . . . . . . . . . . . 129 . . . . . . . . . . . 129

14. Special el-graphs 14.1 Equicut el-graphs . . . . . . . . . . . . . . . . . . . . . . . 14.2 Scale one embedding . . . . . . . . . . . . . . . . . . . . . 15. Some Generalization of el-errhedding 15.1 15.2 15.3 15.4

116

Quasi-embedding . . . . . . . . . . . . . . . . . . . . . . . Lipschitz embedding . . . . . . . . . . . . . . . . . . . . . Polytopal hypermetrics . . . . . . . . . . . . . . . . . . . . Simplicia1 n-manifolds . . . . . . . . . . . . . . . . . . . .

137 137 145 153 153 157 157 160

Bibliography

163

Index

171

This page intentionally left blank

Chapter 1

Introduction: Graphs and their Scale-isometric Embedding

In this chapter we introduce some basic definitions about graphs, embedding and polytopes. We present here only basic notions, further definitions will be introduced later. The reader can consult the following books for more detailed information: [Grun67], [Coxe73], [CoS188], [DeLa97], [Crom97].

1.1

Graphs

A sample graph G = (V,E) consists of a set V of vertices and a set E of edges. Every edge e E E consists of two end-vertices u and u;we set e = (u, v), Those two vertices are called adjacent and each of these vertices u and v is incident to the edge e. The degree of a vertex v E V is the number of edges, to which the vertex v is incident. If every two vertices of G are adjacent, then G is called complete. A complete graph on n vertices is denoted as K,. If a graph has no edges, it is called empty. For U 2 V, let Ev be the set of edges having both its end-vertices in U and the graph GU := ( U ,E u ) is called induced subgruph (by U ) of G. A graph G is called bipartite graph if its vertices can be partitioned into two non-void parts, V = Vl U Vz, in such a way that the graphs induced by Vl and Vz are both empty. If G is bipartite with bipartition (Vi, Vz) and if every vertex of Vl is adjacent to every vertex of &, then G is called a complete bipartite graph. Let Kn,,, denote the complete bipartite graph with IVll = n and lVz1 = m. The complete bipartite graph K I , ( ~ m 2 1) is called a star. A set E' of edges is called a matching if no two edges of E' have a common end-vertex. A matching is called perfect if every vertex is an end1

2

Scale Isometric Polytopal Graphs

vertex of the matching. (Only graphs with even number of vertices can have a perfect matching.) The following graphs will be frequently used in the book: The multipartite graph Knl,n2,...,nkwith k parts of sizes nl ,722, . . . ,n k is the graph, whose edges are all having end-vertices in different parts. An example is the complete bipartite graph Kn,m ( I c = 2). The p a t h Pn=P~,,,uz,...,u n ) with vertex-set V = { q , v 2 , .. . ,v,}, whose edges are (vi,vi+l) for 1 5 i 5 n - 1. The circuit C,=C{,,,,,,,,,,,,} (or n-gon) is obtained from the path P{uIruZ, ...,v n } by adding the edge (vl,vn)* The hypercube gruph H, is the graph with vertex-set V = (0,l}", whose edges are the pairs of vectors ( 2 1 , . . . , z n ) and ( y l , . . . ,y,) in (0, 1)" such that I{i : xi # yi}l = 1. The half-cube graph $Hn is the graph with vertex-set V = { (21,. . . ,z,) E { 0 , I}, : CZl zi is even} (in e v e n representation, and C:=l xi is odd in odd representation), whose edges are pairs 2,y E (0,l}, such that I{i : z i # yi}l = 2 . The cubic lattice graph 2, is an infinite graph with vertexset Z" = { ( z I , x 2 , .. . , z n ) : xi E Z},whose edges are ( ( X I , . . . , zn)?( ~ 1 ,. .. Y n ) ) such that C1
In Coxeter's notation, a,, P,, -yn and $7" denote, respectively, following n-dimensional convex polytopes: regular n-simplex, n-cross-polytope, ncube and half-n-cube; their respective 1-skeleton graphs (see chapter 1.4 below) are K,+1, Knx2, H , and +Hn. A graph G is said to be connected if, for every two vertices u , v in G, there is a path in G joining u and v;a graph, which is not connected is said

fntroduction

3

to be disconnected. Let G1 = (V1,El) and G2 = (V2,Ez) be two graphs. Their Cartesian product GI x G2 is the graph G := (V1 x V2,E) with vertex-set

VI x

V2

= { ( w I , ~ :) W I E VI and wz E

v2},

whose edges are the pairs ((u1,ua),( u I , w ~ ) )where , u l, w l E V1 and ~ 2 , 7 1 2 E h,such that either (u1,vl) E E1 and u2 = U Z , or (u2,~ 2 E) E2 and u1 = 0 1 . For a graph G, its suspension V G is the graph obtained from G by adding a new vertex (called the apez of V G ) and making it adjacent to all vertices of G. The graphs VC, and C, x K2 are called n-wheel and n-prism, respectively. The line graph L(G) of G is the graph, whose vertices are the edges of G with two vertices of L ( G ) adjacent in L(G)if the corresponding edges of G share a common vertex. We denote L(Kn) by T(n). This graph is the special case k = 2 of the Johnson graph J(n, k). The Johnson graph J ( n ,k ) has the family of all k-subsets of an n-set as its vertex-set. Two vertices of J ( n ,k) are adjacent if and only if the cardinality of the intersection of the corresponding Ic-sets equals to k - 1. In particular, J ( n , 1) = Kn.

1.2

Embeddings of graphs

Before recalling some graph-related metric notions, we briefly discuss the relevance of such embedding. A graph G can be isometrically embedded into a half-cube :Hm if we can label or encode the vertices of G by a binary string of length m with an even number of ones such that the square of the Euclidean distance between the labels is twice the path distance of the vertices in the graph G. If, moreover, the embedding is el-rigid, then we have an essentially unique encoding. Such labeling of vertices can be useful, for example, in Chemistry, for a nomenclature of fullerenes (see chapter 2) and for the calculation of molecular parameters depending only on the graphical distances such as the Wiener, J and other indices (see, for example, (BLKBSSR951).

A semimetric on a set V is a real symmetric function d ( z ,y) defined on all pairs of points z,y E V satisfying d(z, z)= 0 and for each ordered triple (z, y, z ) of points of V , the following triangle inequality:

4

Scale Isometric Polytopal Graphs

Summing two inequalities for the triples (z,y,z) and (z,z,y), we obtain the inequality 2 d ( y , z ) L 0. Hence any semimetric d is non-negative, i.e. takes only non-negative values. A metric is a positive semimetric, i.e. such that d ( z , y) = 0 if and only if z = y. Let G = (V, E ) be a connected graph (finite or not), where V and E are the sets of its vertices and edges, respectively. The path-metric d G , associated with the graph G, is the integer valued metric on the vertices of G, which is defined by setting d G ( w , u ) equal to the length of the shortest path in G joining v and u. The sum of all @%$ distances between the vertices of an n-vertex graph G is denoted by W ( G ) .Chemists call it the Wiener number. A connected subgraph G1 of G is called an isometnc subgraph of G if dG = dG1 on the vertices of G I , i.e. if the distances of G are preserved in GI. In this case we write GI < G. A geodeszc is a (possibly, infinite in one or two directions) simple path P with the property that d p ( x ,y) = d G ( x , y) for any z, y E P . The metric dG allows us to introduce convex subsets on V . A subset S V is called convex subset if for any vertices u,'u E S all vertices of every shortest (u, w)-path (i.e. geodesic), belong to S . The set Z" is naturally endowed with an el-metnc. Namely, for x = (zl,. . . , z n ) and y = ( P I , . . . , y), in Z", the el-distance between z and y is d ( z , y) = Cy=l12% -yl.l. 2, is the graph of Z", whose path-metric coincides with the el-metric d . Similarly, the hypercube graph H, is the subgraph of 2, induced by (0, l},. (The path-metric dH, is also the square of the Euclidean 12-metric.) An [,-graph is a graph G, whose path-metric dG is, up to a scale A, isometrically embeddable into a hypercube Hm or, if G is infinite, into 2,. That is, for some A, m E N , there is a mapping 4 : V --t Hm or Z,, such that: m

A ' dG(wz,Wj) = Il4(vz) - @ ( ' u j ) / l t i =

I+k(Vz)

- 4k(Uj)1

k=l

with wz E V and +(vz) = (41(wz), . . . , +,(vz)) E Hm or in 2,. The least integer X is called the minamal scale of the embedding. For example, the half-cube graph $ H , and the half-cubic lattice graph $2,are naturally embedded into H , and Z,, respectively, with the scale X = 2. Hence $H, and $2,are I1-graphs. Recall that the 2 , vertices of the rn-cube H , can be labeled by all 2m subsets of the set { 1 , 2 , . . . , rn}, such that two vertices with labels A and

Introduction

5

B are adjacent if and only if JAABI = 1, where A A B is the symmetric difference of the sets A and B . Hence the scale X embedding $ : V -+ H , is equivalent to a labeling of each vertex w E V ( G )by a set $(w), such that vertices v and u are adjacent if and only if I$(v)A$(u)I = A. On the other hand, this labeling implies a labeling of edges ( v , u )by the sets qh(u)A$(u). For i E { 1 , 2 , . . . , m } ,call the set of edges, labels of which contain i, a i-zone or, simply, a zone. Both these labeling of vertices and edges of G are used in Figures of the chapter 2, for example. If G is embedded into a hypercube H,, then any partition of H , into two opposite facets induces a partition S U = V of the set of vertices of G. Any partition S U 3 = V is called the cut { S, 3).The edge set E ( S ,3) of - the cut { S , S }is the set of edges with one end in S and another one in S . Evidently, removing E ( S , S ) from G we obtain a graph with at least two connected components, i.e. E ( S , S ) is a cutset of edges. The edges of the set E ( S ,3) are cut by the cut { S ,3). The cut { S , s } defines the cut semimetric 6 ( S ) on the set V :

s

Let us project the hypercube H , with an embedded graph G along the edges connecting two opposite facets. Then we obtain an embedding of G into H,-I, such that some distances of G are diminished by one. In other words, we embed G endowed with the new semimetric dG - 6 ( S ) . In such a way we obtain a decomposition of the path-metric dG of an 11embeddable graph G (actually, of any 11-metric) into a non-negative linear combination of cut semimetrics. All 11-semimetrics on n vertices (that is, all 11-semimetric spaces (Vn,d ) with IVnl = n ) , considered as points of an (;)-dimensional space, form a (;)-dimensional pointed cone called the cut cone. This cone is generated by the 2"-l - 1 extreme rays. Each extreme ray is a non-zero cut semimetric 6 ( S )for some proper subset S of Vn = { 1 , 2 , . . . ,n } . In other words, a graph G (or any metric) is 11-embeddable graph if and only if the path-metric dG is a linear combination, with non-negative coefficients, of cut semimetrics:

dG

as6(S) with as 2 0 for all

=

s.

scv, If G is embeddable into H , with a scale A, then the above decomposition

Scale Isometric Polytopal Graphs

6

can be rewritten as follows

XdG =

asd(S) with integer as

2 0 for all s.

(1.1)

scvn

An advantage of using (1.1) is that it allows to classify Cl-embedding of G up to equivalence: different solutions t o (1.1)with non-negative integers as such that g.c.d.(X,as) = 1 correspond to different embeddings. If such a solution is unique, the graph G is called Cl-rigid graph (see [DeLa94]). Rigidity of any Cl-metric is defined similarly. Restated in terms of the cut cone, a metric is Cl-rigid if and only if it belongs to a face of the cut cone, which is a simplex subcone. If G is an C1-graph, then for every cut { S , s } occurring in the eldecomposition of dG (i.e. with as > 0), both sets S and 3 are convex; we call such a cut convex cut. The following fact was established in [DeTu96].

Proposition 1.1 [DeT2196]A graph G is scale X embeddable into a hypercube if and only i f there exists a complete collection C(G) of (not necessary distinct) convex cuts of G , such that every edge of G is cut by exactly X cuts from C(G). For X = 1 this is the well-known Djokovic characterization ([Djok73]) of graphs, which are isometrically embeddable into hypercubes.

Lemma 1.1 rigid.

[CDG97] A n y P1-graph, which does not contain

K4,

is

C1-

We say that a polyhedron P is C1-embeddable if its skeleton G ( P )(that is, the graph formed by its vertices and edges) is an C1-graph. A graph G is called polytopal graph if there is a polytope P (possibly, infinite) with

G ( P )= G. For an embedding of a metric d into rn-cube with scale A, the ratio s ( d ) = is called size of the embedding. For a graph G on n vertices there are the following lower and upper bounds on size S(dG) (see [DeLa97], page

45) :

where, recall,

7

Introduction

When the equality holds in the left-hand side of the inequality (1.2), we say that G is an equicut graph. This means that for such a graph, every S in the formula (1.1)satisfies as # 0 if and only if S partitions V into parts of size and [FJ, where n = IVI. On the other hand, the equality on the other side of (1.2) only happens in a very special case.

Lemma 1.2

S(dG)

=

9if and only if G is the star K I , , - ~ .

As an example, consider embedding of an n-simplex a, having G(a,) = Kn+l. Any a n , n 2 3, is not [I-rigid, i.e. it admits at least two different embeddings. We give now three embeddings of a, into m-cubes H,,, with scale A, realizing, respectively, maximum, minimum and a middle (for n > 4) of size y . For the simplex an the bounds (1.2) take the form

For the left hand side, we have sn = 2 -

m,1.e. sn = 2 for odd n, '

nf1

and s, = for even n. The upper bound is realized by the embedding a, + ;H,+1, where the zi = 1 (in vertices of a, are mapped into vertices 5 of ;H,+1 with odd representation of i H n + l ) . A middle (for n > 4) size is realized as follows. Take the set of all n n+l edges (ij), 1 5 i < j 5 n 1, of Kn+l as the set of indices V of H,, i.e. m = Map the vertex i of a, (i.e. of Kn+l) into the subset V , = {ij : 1 5 j 5 n f 1 , j # i} c V . Then IV,A&I = 2(n - 1) is the scale A. In this case s(a,) = For n = 4, this gives 4 ~ x 4 )= s4 = i.e. the lower bound for n = 4. Define A, be the minimal even positive number t such that ts, is an integer. Then there is an embedding of a, into Ans,-cube with scale A, realizing the lower bound S n . This is an equicut embedding (cf. the item (i) of Theorem 1.1 below). Any ,On, n 2 4,is also not el-rigid. All embedding of ?/, are into 2A-cube with a such even scale A that an-l is embeddable into m-cube, m 5 2A, with scale A. For minimal such scale, denote it p,, the following is known: n > pn 2 2 r Z l with equality in the lower bound for any n 5 80 and, in the case of n divisible by four, if and only if there exists an Hadamard matrix of order n. In particular, ,O3 and /?4 are embeddable into iH4 (in

xyL;

9.

w.

+

i,

Scale Isometric Polytopal Graphs

8

fact, G(P4) = i H 4 , but there are two embeddings of /34 into a H 4 ) , ,& is embeddable only with scale four (into Hs). The size S(dG) has the following properties formulated in terms of n =

IVI. Theorem 1.1 [DePaOl] Let G be a n Il-graph. if and only if G = K,; (i) s ( d G ) = S n - 1 = 2 (ii) s ( d G ) = 2 if and only if G as a non-complete subgraph of a cocktailparty graph K n x 2 ; (iii) s ( d G ) = n - 1 if and only if G is a tree; (zu) 2 < s ( d c ) < n - 1, otherwise. Clearly, the scale X embeddability into H , implies the scale 2X embeddability into +Hzm. Moreover, for any graph G, which is scale X embeddable into a hypercube, we have: (i) X = 1 G is an isometric subgraph of a hypercube; we write: G 4 Hm . (ii) X = 1 or 2 @ G is an isometric subgraph of a half-m-cube; we write:

G + +Hm. Similarly, for an infinite graph G we have: (i) X = 1 H G is an isometric subgraph of a cubic lattice; we write:

G -+ 2,.

*

(ii) X = 1 or 2 G is an isometric subgraph of a half-cubic lattice graph; we write: G ---t i Z m .

Lemma 1.3 two.

[CDG97] T h e scale X of a planar el-graph is either one or

Finally, we recall that a graph G is called hypermetric graph (see [DeGr93] for details) if its path-metric dG satisfies any hypermetric inequality defined by:

bzbj d G ( v , , v j ) 5 01

(1.3)

lsz<j
where b = { b l , b z , . . . ,bn} E Z", C:xl b, = 1 and u,, 1 5 i 5 n, are arbitrary distinct vertices of G. Note that the above definition of a hypermetric is local, since it uses only finite sets of vertices. Hence an infinite graph is called h y p e m e t r i c graph if each its finite subgraph is a hypermetric graph.

Introduction

+

9

+

If C:=, jbil = 2k 1, this inequality is called a (2k 1)-gonal inequality ( [DezasO]) and a graph satisfying all ( 2 q 1)-gonal inequalities for q 5 k is called (2k 1)-gonal. Clearly, the case k = 1 corresponds to the usual triangle inequality. Below we present the case k = 2, i.e. the 5-gonal inequality, which is an important necessary and in many cases sufficient (see below) condition for embedding of graphs. Namely, for b, = bb = b, = 1, b, = b, = -1, (1.3) takes the form :

+

+

+ (4%b) + d(a, c) + d(b, c ) ) I ( d ( T a ) + 4x3 b ) + d(z, c ) ) + (d(Y,a ) + d(Y, b) + d(Y, c ) ) d(z, Y)

(1.4)

for distances between any five vertices a, b, c, z, y. Using the given above definition of the cut semimetric S ( S ) , it is not difficult to verify that

ciEs

bi is an integer. According to the decomposition (1.1))this since implies that every el-semimetric is a hypermetric. For the path-metric of a graph G, the links between those metric properties are given by the following inclusions:

G is an isometric subgraph of a hypercube =+ dG is el-rigid =. G is an isometric subgraph of a half-cube + G is an [,-graph dG as hypermetric

+ dG is ( 2 k + 1)-gonal

3

dG as ( 2 k - 1)-gonal

dG is 3-gonal (= metric).

We also recall that the DjokoviC’ characterization of el-graphs with scale X = 1 can be reformulated (see Avis [Avis80]) in the following way: a graph is an isometric subgraph of a hypercube if and only if it is bipartite and 5-gonal. In general, a graph G is an el-graph if and only if G is an isometric subgraph of a Cartesian product of cocktail-party graphs (i.e. the skeletons of the polytopes dual to hypercubes) and half-cube graphs, see [Shpe93] (or [DeGr93] for another proof). As for complexity results: while recognizing of a metric as elembeddable (that is isometrically embeddable into an l?) is NP-complete (see [Karz85]), recognizing of a graph as el-embeddable is polynomial (see [DeSh96]). See also [DeLa97] for a general study of el-metrics.

10

1.3

Scale Isometric Polytopal Graphs

Embedding of plane graphs

In spite of the fact that recognizing if a graph is .!I-embeddable, is polynomial, a more simple algorithm is suggested in [CDG97] for any planar graphs. This algorithm is very useful, since polytopal graphs of 3dimensional polytopes and 2-dimensional tilings are planar. A proof of all assertions of chapter 1.3 can be find in [CDG97]. Recall that, according to Lemma 1.3, a planar .!I-graph G has scale X equal to 1 or 2, and it is 1 if and only if G is bipartite. According to Proposition 1.1,in order to find an el-embedding of a planar non-bipartite graph, it is sufficient to find a collection of convex cuts, such that every edge of G is cutted by exactly 2 cuts of this collection. The algorithm, which is mentioned above, finds explicitly this collection. Let G be a planar locally finite graph (i.e. all vertices have finite degree) and assume a plane drawing of G is given, i.e. G is a plane graph. An interior face of G is a cycle of G, which bounds a simply connected region. Denote by G* the plane graph dual to G; suppose that a plane drawing of G* is given, such that the vertices and the edges of G* belong to the corresponding faces of G. Let Z ( S , 3 ) be the family of interior faces of G, which are crossed by the cut {S,3);we say that Z ( S ,3)is the belt of the cut {S,3). Let C ( S ,3) be a partial subgraph of G" defined in the following way: the vertices of C ( S ,3)are the faces of Z ( S ,3)and two such faces are adjacent in C ( S ,3) if and only if they share a common edge from E ( S , S ) .

Lemma 1.4 If {S,T} i s a convex cut and F is a face of a plane graph G , then IE(S,S)n E(F)I = 0 or 2. In particular, C ( S ,3) is either a path, o r a cycle.

s),

Geometrically, Lemma 1.4 asserts that if we cut the plane along C ( S , then, once entering a face of Z ( S , s ) ,we must exit this face through some other edge and we will never visit this face again. In particular, the line, along which we cut, has no self-intersections. F'urthermore, the sets S n Z ( S , s ) and 3 n Z ( S , 3 ) are either paths, or cycles. Let us denote them by b d ( S ) and b d ( 3 ) , and call them the border lines of the cut { S , S } . Now, we assume that a planar graph G embedded in the Euclidean plane with the following property: (a) A n y interior face is a n isometric cycle of G .

(Although this property is natural, one can construct planar el-graphs,

Introduction

11

which do not admit a planar embedding obeying the condition (a): for example, take a book, i.e. a collection of at least three 4-cycles sharing a common edge.) Two edges e = ( u ,v ) and e’ = (u’, w’) on a common interior face F are called opposite if &(u, u’) = d ~ ( vv’), and these distances are equal to the diameter of the cycle F . If F is an even face (i.e. if it is bounded by a circuit of even length), then any of its edges has a unique opposite. Otherwise, if F has an odd length, then every edge e E E ( F ) has two opposite edges e+ and e-. In the latter case, if F is clockwise oriented, we distinguish (for e) the left opposite edge e+ and the right opposite edge e-. If every face of Z(S,3)is crossed by the cut { S, 3)in two opposite edges, then we say that { S ,3)is an opposite cut of G. If a convex cut { S,3)of G enters an interior face F through an edge e, then convexity of S and 3,and isometricity of F yield that {S,z} exits F through an edge opposite to e. We say that { S , s } is straight on an even face F and this cut makes a turn on an odd face F . The turn is left or right, depending on which of the opposite edges e+ or e- we cross.

Lemma 1.5 opposite.

I n a plane graph with isometric faces all convex cuts are

If G is a plane graph with isometric faces of even length only (i.e. if G is bipartite), then G is an el-graph if and only if every opposite cut is convex. This presents a useful way to verify if G is 41-embeddable or not. An opposite cut of a plane graph G is alternating cut if the turns on it alternate. For many important plane el-graphs the convex cuts, participating in an el-decomposition, turn out to be alternating. Consequently, if G is bipartite, then the alternating cuts are exactly the opposite cuts of G. By Lemma 1.5 every convex cut of a bipartite graph G is alternating. Another class of plane graphs with this property is given in the next lemma (we say that two interior faces are adjacent if they share an edge).

Lemma 1.6 Let G be a plane graph, in which all interior faces are isometric cycles of odd length. If the union of each pair of adjacent faces is an isometric subgraph of G , then any convex cut of G is alternating. The most known class of plane graphs verifying the conditions of Lemma 1.6 is that of triangulations (i.e. plane graphs, in which all interior faces are triangles) without 4-cliques. It has been established in [BaChOO] that any finite triangulation with the property that all vertices, which do not belong to the exterior face, have degree larger than five is

12

Scale Isometric Polytopal Graphs

C1-embeddable. Moreover, all such graphs are Cl-rigid. For a triangulation, Lemma 1.6 implies the following property:

If a triangulation G does not contain K4 as an induced subgraph ( i e . i f all interior vertices have degree at least 4), then any convex cut of G is alternating.

A circuit C of a plane graph G is said to be alternating (or left-right circuit, or Petri walk, or zigzag) if every face of G is either disjoint with C, or shares with it exactly two consecutive edges. Clearly, any edge of G is covered by exactly two circuits from the family of alternating circuits of G; in other words, G has a double cover by its alternating circuits. The graph G*, which is the dual to a cubic plane graph G, is a plane triangulation, Every alternating simple circuit of G corresponds to an alternating cut of G* and, conversely, any convex alternating cut of G* defines a simple alternating circuit of G. Therefore, we obtain the following necessary condition of embedding of G*: If the dual of a finite plane cubic graph G is C1-embeddable1 then all its alternating circuits are simple. Above condition is not sufficient; for example, fullerenes C2Oa2( I h ) (see chapter 2) have exactly 6a alternating circuits, all of which have length 10a and simple, but their dual polyhedra embed only for a = 1 (the icosahedron). A circuit C of a plane Eulerian (i.e. with every vertex having even valence) graph G is said to be central (or straight-ahead) circuit if entering in each its vertex, it leave it by opposite edge. Clearly, any edge of G is covered by exactly one circuit from the family of central circuits of G; in other words, the edge-set of G is partitioned by its central circuits, i.e. G has a cover by its central circuits. The graph G*, which is dual to an Eulerian plane graph G, is a plane bipartite one. Every central simple circuit of G corresponds to an opposite cut of G* and, conversely, any convex opposite cut of G* defines a simple central circuit of G. Therefore, we obtain the following necessary condition of embedding of G*:

If the dual of a finite plane Eulerian graph G is C1-embeddable, then all its central circuits are simple, Now we present an algorithmic procedure to find the alternating cuts

Introductaon

13

(if they exist) crossing given edge e = ( u ,w) of a plane graph G. In order to do this we extend the cuts from the edge e , crossing face after face. We go away from e straight through even faces until we arrive to an odd face, say, F . Then in one cut we make a left turn on F and in the other cut we make a right turn on F . After that we have only to alternate the directions when passing through odd faces of G. Namely, if, say, our last turn in a cut was to left, then coming to the next odd face this cut turns to right and conversely. Let E ( e ) and E’(e) be two subsets of edges, which we cross in this movement. Then any alternating cut { S , s } ,which cuts the edge e , satisfies either to E ( S , g ) = E ( e ) ,or to E ( S , S ) = E’(e). Indeed, { S , s } cuts the edges from the common part of E ( e ) and E’(e) until the face F . At this moment, we have only two possibilities to continue the movement along E ( S , S ) ;namely, { S , S } cuts the face F in the same fashion as E ( e ) or E’(e), say as E ( e ) . In this case necessarily E ( S , s ) and E ( e ) coincide everywhere. We call a set of edges of the form E ( e )or E’(e),for some e , an alternating zone (of edges). If we label each alternating zone by a number, then each edge obtains a label consisting of two numbers. If G is an (1-graph, then the alternating zone with a label i is the i-zone defined above. So, we have the following result.

Lemma 1.7 Every edge e of a plane 11-graphG is crossed by at most two alternating cuts, each of them being defined by the alternating zones E ( e ) or E’(e). Denote by d ( G ) the collection of all alternating cuts of G, where every cut, which never has to turn is counted twice. In general, there are plane graphs without alternating cuts. This is due to the fact that E ( e ) and E’(e) do not necessarily define cutsets of G. However, if E ( e ) and E’(e) are cutsets for all e E E(G), then Lemma 1.7 infers that the family of alternating cuts d ( G ) is rather complete: every edge of G is crossed by exactly two cuts from d(G). Unfortunately, only this property together with the property (a) do not imply (1-embeddability of a plane graph G , because alternating cuts can be non-convex. Neither it can exclude (1-embeddability: there exist plane (1-graphs with non-convex alternating cuts and so, such that the complete family of convex cuts (which, by Proposition 1.1, gives the embedding) contains non-alternating convex cuts. Let us call such embeddings nonstandard. Examples of 3-polytopes having non-standard embedding are: as, (Prisrn3)* i H 4 , dual RhDo-ws -+ (three amongst six convex --f

Scale Isometric Polytopal Graphs

14

cuts are non-alternating), Durer’s octahedron i H 8 (five amongst eight convex cuts are not alternating; see Figure 1.3), FzS -+ (see Figure 2.2 below) and (considered in chapter 5) B-extensions, realizing P P r i s m s , and elongations along circuit of graphs with non-standard embedding. To ensure the el-embeddability of G we have to impose the following metric condition on the border lines of alternating cuts constructed by our procedure (fortunately, these natural requirements are easily verified in many important particular cases): --f

+

(b) A n y border line b d ( S ) and b d ( 3 ) of any alternating cut {S,z}i s a n isometric cycle o r a geodesic. Evidently, (b) implies the condition (a). Proposition 1.2 If G i s a plane graph, satisfying condition (b), t h e n a cut {S,??} of G i s alternating if and only i f it i s convex. Hence G i s a rigid el -graph.

In fact, from Lemma 1.6 and condition (b) we obtain that every edge of G is crossed by exactly two alternating cuts. By Proposition 1.2 we conclude that G is scale two embeddable into a hypercube. Since every convex cut of G is alternating, we deduce that this el-embedding of G is unique. Recall that a finite planar graph G is outerplanar graph if there is an embedding of G in the Euclidean plane, such that all vertices of G belong to the exterior face. Applying the above facts to outerplanar graphs, we obtain P r o p o s i t i o n 1.3

A n y outerplanar graph i s a rigid [,-graph.

Easy to see, that any embeddable finite plane graph embeds into H S + ~ , if it is bipartite, and into ;Hp+z, otherwise; here p is the length of the perimeter and .z is the number of closed (i.e. having only non-boundary edges) alternating zones.

1.4 Types of regularity of polytopes and tilings In this book, we shall consider el-embedding of graphs G ( P )of 1-skeletons (i.e. edge-skeletons) of (convex) n-polytopes P . We consider also such generalizations of n-polytopes as non-convex n-polytopes, tilings, honeycombs

Introduction

156

15

157

14578

456

45678 -

Fig. 1.1 Examples of embedding: a) Durer’s octahedron -t $ H s , b) elongated dodecahedron ElDo -+ H5

etc. We call such P -ernbeddable if its graph G ( P ) is el-embeddable. A convex n-polytope is an n-dimensional compact convex subset of Euclidean n-space formed by intersections of finitely many half-spaces, see [Grun67]. The k-dimensional intersection, 0 5 k 5 n- 1,of n-polytope with supporting hyperplanes are called their k-faces. In particular, for k = 0 , l and n - 1, we have vertices, edges and facets, respectively. An n-polytope is called simple n-polytope if each its vertex has exactly n neighboring vertices. For n = 3, we sometimes call a 3-polytope by a polyhedron. The graph of the edge-skeleton of a polyhedron is planar. We call a polyhedron a k-hedron if it has k facets, For example, the tetrahedron is a 4-hedron, the cube is a 6-hedron, the octahedron is an 8-hedron, the dodecahedron is a 1Zhedron and the icosahedron is a 20-hedron. A polyhedron, such that all of its facets are regular triangles, is called deltahedron. There are exactly eight (convex) deltahedra with regular ones tetrahedron, octahedron and icosahedron amongst them. A dual polytope of a convex n-polytope P is an n-polytope P* such that the k-faces of P*, 0 5 k 5 n - 1, are in one-to-one correspondence with the (n - k - 1)-faces of P and corresponding faces are orthogonal. The planar graphs of the skeletons of dual polyhedra are also dual. We shall also consider non-convex n-polytopes, which are compact sets with interior points and piecewise linear boundary structure. They are

16

Scale Isometric Polytopal Graphs

honiothetic to the n-ball. An n-dimensional honeycomb is an infinite set of n-polytopes fitting together to fill all n-space, such that every facet of each polytope belongs to exactly one other polytope; it is called tiling if all above polytopes are convex. For a definition of regularity a notion of a vertex figure is important. A vertex figure of an n-polytope or, more generally, of a tiling or of a honeycomb, is the convex hull of the midpoints of all edges incident to a given vertex. A vertex figure of an n-polytope is a convex ( n - 1)-polytope. But a vertex figure of an n-tiling or of an n-honeycomb can be infinite and/or non-convex. The regularity of an n-polytope is defined by induction over its dimension supposing that a point is a convex regular 0-polytope. A convex n-polytope is regular n-polytope if all its facets and vertex figures are regular ( n - 1)-polytopes. A regular-!aced n-polytope is one, whose facets are regular ( n - 1)polytopes. All regular-faced n-polytopes are known. An isogonal n-polytope is one, whose group of symmetries is transitive on vertices. A semi-regular n-polytope is a regular-faced isogonal n-polytope. A semi-regular 3-polytope is the same as uniform polyhedron. With the semi-regular 3-polytopes as a starting point, for n 2 4, an isogonal n-polytope is called uniform if all its facets are uniform (that is, for n = 4, the facets are semi-regular polyhedra). A quasi-regular n-polytope is a semi-regular polytope, whose symmetry group is transitive on edges. Five regular polyhedra (Platonic solids) and semi-regular polyhedra (13 Archimedean solids, prisms, antiprisms) have been known since antiquity. Archimedean polyhedra and their dual (Catalan polyhedra) were rediscovered during the Renaissance, and Kepler ([Kep11619])gave them their modern names. We give the usual notations of the five Platonic polyhedra:

0

a

simplex a3 = tetrahedron; it is self-dual, G(a3)= Kq; cube 73, G(73)= H3 and its dual: octahedron ,&, G(P3) = K3x2; icosahedron ICO and its dual: dodecahedron Do.

We denote by $yn the convex hull of a half of vertices of the n-cube T ~ , such that its skeleton form the graph +ITn. The Johnson n-polytope P J ( n ) is the convex hull of vertices of yn+1 lying in the hyperplane Z;'' z i = 2. Its skeleton G ( P j ( n ) )is J ( n 1 , 2 ) = T ( n 1) = L(Kn+l). Similarly as

+

+

Introduction

17

for graphs, we have

See below for definition of the n-bipyramid B P y r ( P ) . Apropos, for m = 3,4, ( ;ym)* = a3,7 4 , respectively; for m 2 5, (;ym)* contains isometric subgraph K5 - K3 and so, not 5-gonal. All regular and regular-faced polytopes are known. For each n > 4, all regular n-polytopes are: n-simplex an with G(a,) = & + I , n-crosspolytope Pn with G(&) = K n x 2 and n-cube -yn with G(yn) = H,. All 92 regular-faced polyhedra were found by the work of many people, especially, of Johnson and Zalgaller (see, for example, [John661, [Zalg69], [Berm711, [KoSu92]). Finally, in [BlB191],the complete list of regular-faced n-polytopes is given. Semi-regular n-polytopes were found in 1897 by Gosset. It is proved for n = 4 in [Maka88) and for any n in [BlB191]that the Gosset’s list is complete (see [Coxe73] and [Grun67] for an historical account). In what follows, we use frequently the names and numbers of 112 regular, Archimedian and regular-faced polyhedra from the list of [Berm7l]. For example, Nr.1-5 are regular polyhedra. In [Berm711 and [Zalg69], the regular-faced polyhedra are given as appropriate joints of 28 basic polyhedra M I - M28.

1.5

Operations on polytopes

We use some operations transforming a polytope into another polytope.

Direct product. The direct product of n-polytope P and m-polytope P’ is an (n m)-polytope P x P’ with G ( P x P‘) = G ( P ) x G(P’). Sometimes, it is called the Cartesian product. Prisms. The prism with the base P is the polytope P r i s m P := a1 x P . P r i s m n denotes the prism with an n-gon as the base, i.e. P r i s m n = Prism(C,). Elongation. Let C be a simple circuit in a 3-polytope (or, in general, in any plane graph) P. An elongation of P along C consists of replacing C by the ring of 4-gons. The elongation of P along the circuit C , bounding a face, means putting the prism on this face. Truncation. A truncation (at vertex v) of a polytope P cuts the vertex v. In other words, the vertex v of P is substituted by a facet, which is the vertex figure of P. A polytope P is called truncated and denoted

+

Scale Isometric Polytopal Graphs

18

as t r ( P ) if all vertices of P are truncated. In most cases, we can do truncation at of edge distances. Capping. In a sense, this operation is an inverse of truncation. A capping of a polytope P at its facet F consists of addition of a new vertex 'u to P, such that 'u is adjacent to all vertices of F . A t-capped polytope P is obtained by cappings a t t distinct facets of P. P y r a m i d s . The convex hull of an n-polytope P and a vertex 'u, not lying in the space spanned by P, is called pyramid over P (with the apex v) and denoted by P y r ( P ) . We set Pyr, = Pyr(C,). We denote by P y r t ( P ) the result o f t consecutive applications of taking pyramid. One has G(Pyrt(P)) = V t G ( P ) . B P y r ( P ) denotes an ( n + 1)-bipyramid with n-polytope P as the base. It has two apexes, which are opposite with respect to the hyperplane spanned by P . G ( B P y r ( P ) ) is V2G(P)-e,where e is the edge connecting two apexes of V 2 G ( P ) . We set BPyr, = BPyr(C,). Chamfering. This operation is applied only to 3-polytopes. The chamfering of a polyhedron P is the polyhedron, denoted by Cham(P), which is obtained by putting prisms on all facets of P and deleting original edges. t-iterated chamfering is denoted by Chamt(P) (see also the end of chapter 5). A m b o . The convex hull of the midpoints of all edges of a polytope P is called its ambo-polytope and denoted by Ambo(P). We restrict ourself only to the cases when the mid-points of edges, which are incident to any given vertex, lie on the same plane. If P is a polyhedron, then each vertex of the polyhedron Ambo(P) has degree four. This is so, since each edge of P is incident to two faces, and, in each face, an edge is adjacent to two edges. The skeleton of Ambo(P) is called also the medial graph of the skeleton of P . The skeleton of Ambo(P) is the line graph of the skeleton of P, if P is a simple polyhedron. We have Ambo(a3) = /33, Ambo(/34)=24-cell.

4

0

0

0

0

1.6

Voronoi and D e l a u n a y p a r t i t i o n s

A finite or infinite set X of points of Rn is called discrete if there is a positive number r , such that the ball of radius r with the center in a point of X does not contain another points of X. A special case of an infinite discrete set in Rn is an n-dimensional point lattice. It is the set of end-points of vectors C Z , aibi, where the vectors bi

Introduction

19

are linearly independent, and zi E Z for all i. Any discrete set of points X defines two partitions (tilings) of R" by Voronoi and Delaunay polytopes. Voronoi, who introduced this theory (for lattices) in his last two papers, call them M- and L-polytopes, respectively. Any lattice has exactly one afine type of Voronoi polytope and a finite number of types of Delaunay polytopes. Each Voronoi polytope P ( x ) of the Voronoi partition relates to a point x E X such that P ( x ) is the set of all points of R", which are not more far from 2, than from any other point of X . Denote by V o ( X ) the skeleton graph of the Voronoi partition. In particular, for a lattice L , V o ( L )is the skeleton of the Voronoi partition defined by L. The Delaunay partition is dual of the Voronoi partition (dual, in both, combinatorial and metric sense). .It can be obtained by the empty sphere method of Delaunay. Take a point y # X as center of a sphere S, not containing points of X. Then increase radius of S, until a point x E X touches S,. After that move the center y such that one can again increase radius of S, remaining x on S, until another point x' E X touches S,. Continuing, one obtains a (locally maximal) empty (i.e. not having points of L in its interior) sphere S, with n 1 affinely independent points from X on S,. The convex hull of all points of X , lying on S, is a Delaunay polytope Po of the Delaunay partition. The case when radius of S, is infinite is not excluded. Denote by D e ( X ) the skeleton graph of the Delaunay partition. In particular, for a lattice L , D e ( L ) is the skeleton of the Delaunay partition of L. Edges of D e ( L ) are minimal vectors of the simple cosets of L/2L. Recall that if L is the root lattice D,, then the graphs De(D,) and i2, have the same vertex-set, but the graphs themselves are distinct.

+

1.7 Infinite graphs First, we give an example of a sequence of polytopal graphs, which are embeddable with increasing scale, but the graph in the limit is not embeddable. Consider i points u 3 , 1 5 J < 2 , with the positive integer coordinate J on the axe. Let any neighboring points u3-1,a3 be a pair of antipodal vertices of the cross-polytope pm, of dimension m3 := 2 3 , such that ,Om, has a common vertex only with ,Om,_, (namely, a3--1) and ,Bm,+, (namely, a 3 ) . Denote by W, the graph obtained by such attaching of z cross-polytopes. Clearly, Pm, and W, are embeddable into Zmt with scale A, = 7 = 2,-'.

20

Scale Isometric Polytopal Graphs

Denote by W, the limit of Wi for i -+ co. We have X i -+ co for i -+ co; so, W, cannot be embedded, with finite scale, even into 2,. Now (following [DeSt02a]) we consider cubical complexes and, especially, introduce the infinite dimensional cube. Novikov proposed in [Novi86] to study cubical complexes, i.e. those consisting (instead of simplexes) of cubes of all dimensions. The simplest example of a cubical complex is an Euclidean cube of an arbitrary dimension (with faces of all dimensions). Another example of a cubical complex is usual cubical lattice giving a partition of Euclidean n-space into n-cubes adjacent by facets. This complex consists of a countable number of cubes of finite dimension. Each point of the complex belongs only to one cube, if it is an inner point, and to a finite number of cubes, if it is a boundary point. Now, we construct a third example of a cubical complex. Let E, = (0,e l , e 2 , . . . , ek, . . . ) be limit for n + 03 of the orthonormal frame &n = (0,e l , e2,. . . , e n ) . We take k arbitrary integers il < 22 < - . . < ik from N , k E N , and construct on the corresponding k vectors ei,, ei,, . . . , eik from I, a closed cube I k ( O ,e,, , e z z , . . , ei,) with origin 0 as a vertex. Take union of all such cubes U i l < i z < . . . , i k E N , k E N l k ( O , e z l , e i z ,* ..

,eik).

The family of cubes of this union, including faces of all dimensions, composes an infinite-dimensional cubical complex. In fact, at first, each cube of the family is either a cube of the form I k ( ( o , e i l , e i z , .. . , e i L ) , or its face. Hence each face of the cube I k is a cube of the family. Secondly, any two cubes of the family are obviously faces of a cube of the form I k ( O ,ei, , ei,, . . . , eik). Therefore their intersection is again a cube of the family. Since each cube of the form I k ( O ,ei, , ei,, . . . , eik)is a k-dimensional face of the n-dimensional cube I " ( 0 , e l , e2,. . . , e n ) , where n is not less than the maximal index ik, then our family has a more simple description U n E ~ I n Here . I n is a short denotation of I n ( O ,el,e 2 , . . . ,en). Since I' c I 2 c . . . C I n C . . . , our cubical complex can be considered as a family of faces of all dimensions of an infinitely expanding cube I" when n goes to infinity. Dimensions of the cubes composing the complex are finite, but there is no upper bound for all these dimensions. Hence this complex is not finite-dimensional. This cubical complex determines a polytope of infinite dimension, let us denote this polytope by W . The body of the polytope W is union of

Introduction

21

all open cubes of the complex. Hence it is not closed, In fact, the infinite sequence of points Mi = ($, . . . , 0,0,. . . ), each of which belongs t o t h e p o l y t o p e W h a s a l i m i t p o i n t M , = ( $ , i , . . . ,9 1 ,v 1 , . . .) i f i - + m .

i, &, A,

The point Mm does not belong to W since it does not belong to any finite dimensional cube I" of above union. (The polytope W is a proper subset of the Tikhonov cube IT,i.e. of the topological product of r copies of the unit interval of the real line, with cardinal number T = No. This special Tikhonov cube is homeomorphic to the Hilbert cube, i.e. to the subspace of the Hilbert space C2 consisting of all the points z = ( q , 2 2 , . . .), for which 0 5 Z n 5 1, n 2 1. As a graph, the edge skeleton of the polytope W is a maximal connected component of the edge skeleton of the cube P of countable dimension.) We consider a set of points such that their coordinates in the basis ,& are 0 and 1, and the number of ones is finite. These points are not all points with coordinates 0 and 1. The points of this set are just the points, which can be reached from origin 0 (or from any point of the set) by a finite shortest path, whose edges are unit vectors of the basis Em. These (and only these) points are vertices of the polytope W . The distance between points y = (yl, yz, . . . , y k , . . . ) and z = (21, z z , . . . , zk,.. . ) of W (in particular, between vertices of W )is given by the formula p(y, z ) = Iyk - z k \ . For any pair of points (y, z ) of W , this sum contains infinitely many members, but only finite number from them are distinct from zero (and are equal to 1 in the case of vertices). Hence, in fact, the distance is computed by a finite formula. We denote by 'Ho3 the graph induced by the set of vertices of the polytope W . (The metric space of 'H" is a special limit of an infinite sequence of metric spaces 'Hn for n -+ 03. It contains all IFI", n E N. It turns out that 7-P is a universal carrier of graphic metrics of all graphs embeddable in hypercubes and cubic lattices.) Since any finite set of vertices of an infinite dimensional cube H a has finitely many coordinates equal to 1 (and infinitely many zero coordinates), it belongs to a finite dimensional cube. Hence this finite set of vertices satisfies every hypermetric inequality. Therefore we have

cr=l

Proposition 1.4

T h e metric space H m i s hypermetric.

Now we want to prove that the metric space 2" is also hypermetric. A simple path P, of length n - 1 is obviously embedded isometrically into the skeleton of an n-dimensional cube. Any embedding of the path Pn into a cube of dimension less than n, cannot be isometric. In fact, if P, is embedded into Hk with k < n, then there are two parallel edges in the

Scale Isometric Polytopal Graphs

22

embedded P,. The sub-path consisting of any two nearest parallel edges and all edges between them composes a path of the form e l + e z + . . . + e k - e l . Only the border vectors of the sum are colinear. The colinear vectors should be apposite directed, since otherwise the path cannot belong to the cube. The shortest path in the cube between the end-points of above path is e2 + .. e k . It is shorter by 2 of the original path. Hence the embedding is not isometric. But if an edge path of length n can be embedded isometrically into the finite cube Hn, an edge ray (as an edge path of infinitely many edges) cannot be embedded isometrically in any cube of finite dimension. The edge ray is embedded isometrically into the infinite dimensional cube H,. We use above considerations for a study of an n-dimensional cubic lattice. Let the orthonormal frame ( O , e l , e 2 , .. . , e,) in R" be a basis of an n-dimensional cubic lattice. We enlarge the frame up to a countable orthonormal frame ( 0 ,e l , e ~ ,. .. , e,, e , + l , . . . ), which we consider as a basis of an infinite dimensional cube. There are 2n rays in an n-dimensional lattice such that they goes from 0 in 2n directions along the unit vectors e l , e 2 , .. . ,en and - e l , -e2,. . . ,-en. Each of these rays can be mapped into the edge skeleton of the polytope W (which is a proper subset of a cube of countable dimension). Namely, we map, edge by edge, the rectilinear ray of the skeleton of an n-dimensional lattice, which is directed along ei, that is, which goes in the positive direction of the i-th axis, 1 5 i 5 n , into the broken path

+

of the skeleton of the polytope W . Here the first edge begins in the point 0, and the edge e i + j . 2 , begins in the end of the edge e i + ( j - l ) . z n ,j = 1 , 2 , 3 , .. . . In a similar way, we map the rectilinear edge ray in an n-dimensional cubic lattice directed along -ez, that is, going in the negative direction of the i-th axis, 1 5 i 5 n, into the edge path

of the edge skeleton of W , where the edge ei+, begins in the origin 0, and the edge e i + n + j . ~ nbegins in the end of the edge e i + n + ( j - 1 ) . 2 n , j = 1 , 2 , 3, . . . . We take an edge of the skeleton of a standard cubic lattice. We consider the hyperplane, which is orthogonal to this edge and bisects it. This hyperplane gives a middle cut of the partition (that is, of the n-dimensional cubic

Introduction

23

lattice). All edges of the partition, which are intersected by this hyperplane form an equivalence class. All edges of the same class are mutually parallel and have the same direction. This equivalence class contains always an edge of the rectilinear ray going from 0 along the corresponding coordinate axis (into positive or negative direction). This edge is mapped by above map into a vector of the basis €". Let this vector be a label of all edges of the equivalence class containing this edge. Then edges of distinct equivalence classes obtain distinct labels. Different equivalence classes correspond to different middle cuts, even if the hyperplanes of middle cuts are parallel. When we label all edges of the one-dimensional skeleton of a standard cubic lattice by vectors of the basis &", we construct a map of the skeleton of a primitive cubic lattice into the skeleton of the polytope W (and in the skeleton of an infinitedimensional cube). Above construction shows that this map transforms each shortest edge path (of a finite length) into a shortest path. Hence the constructed map is an embedding, moreover an isometric embedding. (This map can be extended up to a continuous locally isometric cellular map of a normal partition into cubes of n-dimensional Euclidean space into the n-dimensional skeleton of the polytope W . )

Proposition 1.5

The following embedding 2"

-+

'H" holds.

Since the embedding 2" -+'H" is isometric, and any metric subspace of a hypermetric space is itself hypermetric, the following is true

Corollary 1.1 The metric space 2" is hypermetric. It is clear that the metric space 'H" is not embedded into the metric space 2" for any finite n. In the space with the basis , ,€ we consider a set of all points, which can be reached from origin 0 by edge paths, whose links are vectors of the frame &". The coordinates of any point of this set in the basis ,& are integer, and there are only finitely many non-zero coordinates. Denote this set of points (with the natural el-metric) by 2". Clearly, any finite set of points of 2" is contained in 2" c 2" for some n E N. Since 2" is a hypermetric space, the metric space 2" is a hypermetric space, too.

Proposition 1.6

The following embeddings are true

2"

-+

'H"

c 2".

The fact that the embedding 2" -+ 'H" holds can be proved by the same way as in previous Proposition. The only difference is that now there

24

Scale Isometric Polytopal Graphs

are countably many rays in both directions. However in this case, we can label edges of each ray by distinct labels. This is true, since a union of countably many countable sets is itself countable.

Chapter 2

An Example: Embedding of Fullerenes In order to illustrate above notions of el-embedding and its applicability, we start with fullerenes, a variety of polyhedra important in Chemistry. In this chapter, after introducing fullerenes and giving a general lemma, we report the ll-status of more than 4000 small fullerenes and their duals. Some infinite families of non-embeddable fullerenes are also considered. The tl-status was computer-checked by D.Pasechnik and M.Dutour. A fullerene is a carbon molecule, which can be seen as a simple polyhedron. We denote it by F,. The n vertices - the carbons atoms - are arranged in 12 pentagons and - 10) hexagons, and the edges correspond to carbon-carbon bonds. Fullerenes F, can be constructed for all even n 2 20 except n = 22 (see [Grun67],page 271). For a given n, different arrangements of facets are possible; such fullerenes are called isomers. For example, there are 1, 1, 1, 2, 3, 40, 271 and 1812 fullerenes F, for n = 20, 24, 26, 28, 30, 40, 50 and 60, respectively. Any fullerene without pair of pentagons sharing a common edge, is denoted by C, and called preferable fullerene (or also IP-fullerenes, for Isolated Pentagons). For example, the unique preferable fullerene made of 60 carbon atoms C60 is the truncated icosahedron, also called buckminsterfullerene. A usual way to somehow distinguish between isomers is t o give their symmetry group. For example, C l ~ o ( l his) the unique preferable fullerene with 180 vertices and symmetry group Ih (extended icosahedral group of order 120). While Cso(Ih)is a soccer ball, F 3 2 ( 0 3 ) ,Cm(D5h) and Cw(D2d) resemble t o a tennis, rugby and baseball ball, respectively. The general reference for fullerenes is [FoMa95]. In this chapter we focus on the following metric question:

in

(2

Can we embed into a hypercube the graph formed by the vertices and the 25

Scale Isometric Polytopal Graphs

26

edges of a fullerene while preserving, up to a scale, the path distances? 2.1

Embeddability of fullerenes and their duals

Lemma 2.1 A fullerene F, (and its dual F,*) (i) is either an el-rigid isometric subgraph of a half-cube, (ii) or violates a (2k 1)-gonal inequality for some integer k 2 2.

+

Proof. In fact, ( i ) is a direct application of Lemma 1.6. A fullerene F, being a simple polyhedron and its dual F,* having no vertex of valence three, both do not contain K4 and therefore are el-rigid (and are isometric subgraphs of a half-cube by the implications given in chapter 1.2) when C1-embeddable. If F, or F,* is not embeddable, then, as remarked in [DeGr93], a hypermetric but not el-embeddable graph has diameter two or three. Then, since F& is known to be an e1-polyhedron and since any fullerene (and its dual, except of F,o) has diameter a t least four, it is not hypermetric, and (22) follows. 0 Table 2.1 Embeddability of small fullerenes: out of all 7916 Fn and F,* with n < 60, only seven a r e (1-embeddable Fullerene

F20(Ih) F26(D3h) F28 (Td) F36 (D6h) F40(Td) F44 ( T )

(1-embeddability of Fn +

;Hi0

+

$Hi2

not 5-gonal not 5-gonal +HI5

--+

+

iHl6

el-embeddability of F; -+

not 5-gonal

iH,

-+ -i

not 5-gonal not 5-gonal

Amongst fullerenes F, and their duals with n < 60, and all preferable fullerenes C, and their duals with n < 86, only five fullerenes, Fzo(Ih), F26 (&), F40 (Td), F 4 4 ( T ) , and C ~( IO h ), and only four dual fullerenes, Table 2.2 Embeddability of small preferable fullerenes: out of all 102 Cn and C*n with n < 86, only two are -embeddable

.

Fullerene

(1-embeddability of Fn

c60 ( I h

not 5-gonal

CSO(Ih)

--t

iff22

(1-embeddability of F,* +

iHio

not 5-gonal

An example: embedding o f jullerenes

27

F&(Ih), F&(Td), Fi6(D6h) and c & ( I h ) ,turn out to be el-embeddable (see Tables 2.1 and 2.2). The embedding is given in detail in Figures 2.1, 2.2, 2.3 and 2.5, where a vertex of i H m is labeled by the set S c V, of its non-zero coordinates. The vertices of V are labeled by numbers 0,1,2,. . . ,9 and O', l', 2', . . . and by letters a, b, c, . . .. In Figures 2.3 and 2.4, the edges are labeled by the symmetric difference between sets of nonzero coordinates of corresponding vertices of :HI6 and f Hzz, respectively. While there exist 5-gonal but not 7-gonal polyhedra (for example, the snub square antiprism; see Figure 6.4 c) below), we could not find any such fullerene or its dual. Probably, any non-l1-embeddable fullerene F, (or F,*) is, moreover, not 5-gonal. On the other hand, we believe that five F, and four F,*, given in Tables 2.1 and 2.2, are only 11-embeddable ones.

Fig. 2.1

Embedding of Fzo(1h) into i f f l o

28

Scale Isometric Polytopal Graphs

125791'

346191'

Fig. 2.2

Fig. 2.3

Embedding of

F26(D3h)

Embedding of

F44(T)

into

into

$Hlz

$H16

A n example: embedding of fullerenes

Fig. 2.4 Embedding of Cso(Zh) into $ H z z

29

Scale Isometric Polytopal Graphs

30

2.2

Infinite families of non-ll fullerenes

Now we present two families of interesting non-l1 fullerenes. Starting from a fullerene F, that we can separate into two hemispheres by cutting five edges (respectively, six), we insert between those hemispheres a layer of five hexagons (respectively, six) as follows. After the cutting of F, we obtain two hemispheres each with five (or six) tails. Similarly, we can represent a ring of k hexagons as a ring of k rectangles with the outer and inner borders having each k tails. Taking k = 5 (or k = 6) we can glue the outer tails with the tails of one hemisphere and the inner tails with the tails of the other hemisphere for to obtain a fullerene with more hexagons. The obtained fullerene has n 10 vertices (respectively, n 12) and is called a 1-layered F,. By inserting i layers, we get the i-layered F,. For example, cutting anywhere F20 and inserting a layers, we get the i-layered dodecahedron defined as Fio(i+z)(D5h)for odd i and FIo(i+z)(D5d)for even i (see Figure 2.6). (It is most strained, antiaromatic, least stable fullerene, since, as opposite to preferable fullerenes, it has maximal number of abutting pairs of pentagonal faces.) Starting with F24(&d) and inserting i-layers of 6 hexagons between two hemispheres made of five pentagons surrounding a hexagon, we get the i-layered F24(D6d): F12(it2)(D6h) for odd i and F I ~ ( ~ + Z ) (for D Seven ~ ) i, see Figure 2.6.

+

+

Proposition 2.1 For a n y integer i 2 1: (a) T h e i-layered fullerene (and i t s dual) F1qit2)(D5h o r D5d) is n o t l 1 -embeddable, and (ia) the i-layered fullerene (and i t s dual except f o r i = 1 ) F l ~ ( i + ~ ) ( Do6r hD6d) is n o t !I-embeddable.

Proof. To prove that the above fullerenes are not !I-embeddable, we simply exhibit a not 5-gonal configuration contained in their skeletons. The coefficients bi of the violated 5-gonal inequality (see ( 1 . 4 ) in chapter 1.2) are, respectively, 0 for a black vertex, -1 for a square one, and 1 for a white circle. 0

2.3

Katsura model for vesicles cells versus embeddable dual fullerenes

It turns out, that all known fullerenes, for which their duals are

!I-

embeddable - including the plane partition by regular hexagons ( t h e

An example: embedding of fullerenes

31

Voronoi partition of the hexagonal lattice Az), which can be seen as an infinite fullerene C, - fit the following Katsura’s model for coated vesicles cells (see [Kats83]). More precisely, the n vertices of a fullerene F, are partitioned into four types Ta,baccording to the number a of pentagons and b of hexagons they are incident to, that is, T 3 , 0 , T0,3,T1,z and T ~ JKatsura . then considers the average strain energy of its n vertices assuming Hookean elasticity and only short range interactions. The stable fullerenes, that is, with minimal energy under his model (depending on which type of vertices have minimal energy) are the following: 0

The dodecahedron (minimal energy on T3,o vertices); its dual F.o(Ih)-+

0

The hexagonal sheet C, (minimal energy on TO,^ vertices); its dual (the Delaunay partition of A2) -+ iZ3. The buckminsterfullerene (minimal energy on T 1 , 2 vertices); its dual

$6.

C6*0(Ih) 0

0

--t

i&o.

The elongated hexagonal barrel F36(&h) (minimal energy on T2,l vertices); its dual F3*6(&) --+ 4Hs. The Fzs(Td) (minimal energy on Tz,l vertices); its dual is the hexakis truncated tetrahedron and F&(Td) + iH 7 .

The remaining two stable fullerenes have also minimal energy on T2,1 vertices; they are the tennis ball F32(D3) and F36(&), whose duals are not embeddable.

Scale Isometric Polytopal Graphs

32

A5

45

Embedding of F&(lh) into

Embedding of F&(Td) into i f f 7

Embedding of F*(D6h) into 1/2H8

Embedding of C&(Ih) into i f f l o Fig. 2.5 Dual Embeddings

An example: embedding of fullerenes

Fig. 2.6

F36(&h)

= 1-layered &(&d)

and F40(&d)

33

= 2-layered dodecahedron

Fig. 2.7 Not 5-gonal configurations in i-layered F,o(i+z) for i = 1 and for i

22

Fig. 2.8 Not 5-gonal configurations in i-layered F ~ ~ (for i i+=~1 ~and for i

22

34

Scale Isometric Polytopal Graphs

Fig. 2.9 Not 5-gonal configurations in dual i-layered FT2(i+,) and F,,(,+l)

Chapter 3

Regular Tilings and Honeycombs

3.1

Regular t ilings and honeycombs

Fullerenes from chapter 2 can be considered as partitions of a 2-dimensional sphere. In this chapter, we consider regular partitions of an Euclidean n-space, n-sphere or hyperbolic n-space; the results are mainly from [DeStOOc]. We will use the following notations from [Coxe37]: 0 0

0

denote {p} the polygon with p vertices; denote { P } the star polygon with p vertices and an edge between two vertices a t distance r; a 2-dimensional tiling is said to be regular of type { p , q } , or simply, of type p q , if there are p vertices for each face and q faces at each vertex (for each tiling of type pq there is a dual tiling of type q p ) . As an example, we give below denotations of the five Platonic polyhedra:

0

0 0

simplex a3 of type 33, it is self-dual; cube 7 3 of type 43 and its dual, octahedron ,& of type 34; icosahedron ICO of type 35 and its dual, dodecahedron Do of type 53.

All, except hyper-simplexes an and hyper-octahedra ,& (see Remark 3.3) embeddable tilings in this chapter, turn out to be C1-rigid and so, (by a result from [Shpe93])with scale 1 or 2 (the last only for non-bipartite planar tilings). Those embeddings were obtained by constructing a complete system of alternated zones (see chapter 1.3.) Actually, a tiling is a special case of a honeycomb, but we will use the last term especially for the case when the cell or the vertex figure is a star-polytope and so, the honeycomb covers the space several times; the 35

36

Scale Isometric Polytopal Graphs

multiplicity of the covering is called its density. Embedding of Platonic solids was noted in [Ke1175]and precised, for the dodecahedron, in [AsDe80]. Then [Ass0811 showed that tilings 36, 63, and mlc (for even m 2 8 and m = 00) are embeddable. The remaining case of odd m and limit cases of m = 2,oo was decided in [DeSt96]; all those results are put together in Theorem 3.1. All four Keller-Poinsot star-polyhedra are embeddable. The great icosahedron 3%of Poinsot and the great stellated dodecahedron %3of Kepler have the skeleton (and, moreover, the surface) of, respectively, icosahedron and dodecahedron; each of them has density 7. All ten star-4-polytopes are not embeddable. Embeddable tilings among all regular ones of all dimensions, having compact facets and vertex figures, were identified in [DeSt96], [DeSt97]. Coxeter (see [Coxe54]) extended the concept of regular tiling, permitting infinite cells and vertex figures, but with the fundamental region of the symmetry group of a finite content. His second extension was to permit honeycombs. For the 2-dimensional case, above extensions produced only following new honeycombs g m and m y for any odd m 2 7, which are hyperbolic analogue of spherical star-polyhedra :5 (the small stellated dodecahedron of Kepler) and 5% (the great dodecahedron of Poinsot). Both 55 and 55 have the skeleton of the icosahedron. For any odd m above honeycombs cover the space (2-sphere for m = 5) 3 times. The skeleton of m y is, evidently, the same as of 3m, because it can be seen as 3m with the same vertices and edges forming m-gons instead of triangles. The faces of yrn are stellated faces of m3 and y m itself has the same vertices as 3m.

3.2 The planar case All sub-cases are presented in Table 3.1; notation there are as follows: (1) The row indicates the facet (cell) of the tiling (or honeycomb), the column indicates its vertex figure. For convenience, in Tables 3.1, 3.2, 3.3,3.4, the tilings and honeycombs are denoted by their shortened (i.e. without parentheses and commas) Schlafli notation. (2) By a3, p 3 , 7 3 , Ico, Do and 62 we denote regular tetrahedron, octahedron, cube, icosahedron, dodecahedron and the square lattice 2 2 . In Table 3.1, the numbers are: any m 2 7 in 8th column, row and any odd m 2 7 in 10th column, row.

Regular tilings and honeycombs

37

Table 3.1 2-dimensional regular tilings and honeycombs

(3) We consider that: 2m is a multigraph with two vertices and m edges. Its dual m2 can be seen as a m-gon; all vertices of mm are on the absolute conic a t infinity (it has an infinite degree); the faces 00 of o3m are inscribed in horocycles.

Theorem 3.1 A l l 2-dimensional tilings mk are embeddable, namely: (a) i f f > $ (2-sphere), t h e n 2m -i H I for a n y m, m2 + $ H m for odd m and m2 -+ H y f o r e v e n m; 33 = 03 + iH3, 4H4; 43 = 7 3 -i H3; 34 = p3 -+ i H 4 ; 35 = Ico(- 35 55 $5) $Hc and 53 = Do(- 53) $Hm; = $ (Euclidean plane), t h e n (aa) if 200 -i Hi,002 -+ 21; 44 = 62 -+ Z2, 36 -+ iZ3, 63 + 2 3 ; < $ (hyperbolic plane), t h e n (iii) if $ m k 3 $2.. af m i s odd, k 5 00 and m k 2, is m as e v e n or 00, k 5 00.

+a

-

N

-

--f

+

--f

In following two Remarks we give some relevant observations on embedding of regular maps and non-convex relatives of regular polyhedra. Remark 3.1 (notation and terms here are from [Coxe37], [Crom97]): (i) The embedding of the icosahedron 35 into $Hs was mentioned in [Coxe35]on pages 450-451, as regular skew icosahedron. There are 5 proper regular-faced fragments of 35: 5-pyramid, 5-antiprism, parabidiminished 35, metabidiminished 35, and tridiminished 35; 5-pyramid is embeddable into $H5, all others into $H6. (ii) The antipodal quotients of (embeddable, see Theorem 3.1 (i) ) cube, icosahedron, dodecahedron are regular maps {4,3}3, {3,5}5, {5,3}5 on the

Scale Isometric Polytopal Graphs

38

projective plane, which are K4, K6, the Petersen graph and are embeddable, respectively, into i H m for m = 4,6,6. (iii) Besides 44, 36, 63 (embeddable, see Theorem 3.1 (ii)), there are exactly three other infinite regular polyhedra, which are regular skew polyhedra {4,614}, {6,4(4},(6,613). They are labyrinths in 3-space, obtained by deleting half of all cells from the tilings of 3-space by cubes (&), by truncated octahedra (the Voronoi tiling for the lattice A:), by regular tetrahedra and truncated tetrahedra (Foppl uniform tiling, coming as Nr.6 in Tables 10.1, 10.2 below). They are, respectively: embeddable into 2 3 , embeddable into 2 6 , not 5-gonal. All finite regular skew 4-polytopes are: the family (4,417~1)of self-dual quadrangulations of the torus (it is the product of two m-cycles and so, is embeddable into !jH2, for odd m or into H , for even m ) ,three not 5-gonal ones {6,413}, {4,613}, (8,413) and undecided (4,813) (dual of the last one). (iv) Examples of other interesting regular maps are the Dyck map {3,8}6 (8-valent map with 12 vertices and 32 triangular faces), the Klein map {3,7}8 (7-valent map with 24 vertices and 56 triangular faces) and {4,5}5 (5-valent map with 16 vertices and 20 quadrangular faces). Those maps (all of oriented genus 3) come from the hyperbolic tilings 38, 37,54, respectively (which are embeddable; see Theorem 3.1 (iii)) by identification of some vertices of the unit cell. Those three maps and their duals are all not 5-gonal. But, for example, the 3-valent partition of the torus into four hexagons is embeddable: it is the cube on the torus.

3

10 3

3

1

Fig. 3.1 Examples of not 5-gonal regular maps: Klein map {3,7}8 and Dyck map { 3 , 8 ) 6

Regular tilings and honeycombs

39

Remark 3.2

(notation and terms here are from [Coxe73], [Wenn71] and [ C r o m ~ ]: ) (i) All facetings of Platonic solids, which are not Platonic solids (see [Coxe73],page 100) are: four star-polyhedra :5,5:, :3,3: and four regular compounds 2a3 (Kepler’s stella octangula), 573, 5a3, 10a3. The remaining regular compound is 5/33, which is dual to 573. In this Remark only, contrary to Theorem 3.1 (i), we consider all visible “vertices” of polyhedra, not only those of their shells, i.e. (asit was put on pages 78,80 of [GrSh98]) “we interpret the diagrams naively, as solids with triangular faces, and forget about stellations and self-intersections” Then it turns out, that $5, 54, $3, 3$, 2a3, 5/33 have the same skeletons as dual truncated, respectively: 35, 53, 53, truncated 35, 73, icosidodecahedron. 5a3 has the same skeleton as dual snub dodecahedron. Amongst all four star-polyhedra, five regular compounds and their nine duals, all embeddable ones are: $5 + $Hlo, 5g(- t 3 ) + iH26, 35 -+ $ H ~ o 2a3 , iH12, dual 5 P 3 ( 573) ~ ---$ H I S ,dual 5a3 -+ $ H I S . (ii) Amongst eight stellations A - H of 35 (the main sequence, see [Crom97], page 272), all embeddable ones are A = 35, B 5; and G H 3%. Also the dual of the stellation Deaf2 of 35 has the same skeleton as the rhombicosidodecahedron and it is embeddable into iH16. The stellations Del Fg2 C = 5a3 and F g l , Dez fz are not embeddable. (iii) Amongst the compounds of two dual Platonic solids and dual compounds, all embeddable ones are 2a3 and, into ~ H z sthe , dual of 35 53. Amongst all 53 non-convex non-regular uniform polyhedra (Nr.67-119 in [Wenn7l]), two are quasi-regular: the dodecadodecahedron and the great icosododecahedron (see [Coxe73], page 101 and Nr.73, 94 in [Wenn71]). Again we consider all visible “vertices” and see a pentagram $ as a pentacle (i.e. a 10-sided non-convex polygon). Then both above polyhedra and their duals are not embeddable. But, for example, the ditrigonal dodecahedron (Nr.80 in [Wenn71], a relative of Nr.73 there) is embeddable into H2o . ---f

- -

-

- -

+

3

Returning to regular 2-dimensional case, we conclude it by the following Theorem. Theorem 3.2 For any odd rn (i) Yrn is not embeddable; (22) mF(w 3m) ---t $zoo.

2 7 we have

Above and next theorems are proved in [DeStOOc]; those proofs are messy, but mainly because of difficulty to visualize star-honeycombs.

Scale Isometric Polytopal Graphs

40

3.3

Star-honeycombs

Besides star-polygons, four regular star-polyhedra on 2-sphere, which are all embeddable (last four are isomorphic to ICOor Do) and those, considered in Theorem 3.2 above, there are ([Coxe54]) only the following regular star-honeycombs: ten regular star-polytopes on 3-sphere and four starhoneycombs in hyperbolic 4-space; see Tables 3.1, 3.2, 3.3, 3.4. Here we show that none of last 14 is embeddable. Consider first the case of 3-sphere. There are six regular 4-polytopes (the two self-dual ones: 4-simplex a 4 and 24-cell and the two pairs of mutually dual: 4-cross-polytope p4 with 4cube y 4 and 600-cell with 120-cell), as well as ten star-4-polytopes; see the chapter 14 in [Coxe73]. Assouad [Ass0811 showed non-embeddability of 24and 600-cell; in [DeGr97b] it was done for 120-cell. Clearly, 7 4 and p4 are H4 and !jH4 themselves. a4 is embeddable into H5 and it is embeddable also, for example, with scale 6 into 10-cube (see chapter 1.2). The isomorphisms amongst ten star-4-polytopes, see pages 266-267 of [Coxe73], preserve all incidences and imply, of course, isomorphisms of the skeletons of those polytopes. Using Schlafli notation, those isomorphisms of graphs are: (i) $53 523; (ii) z33 ~120- cell(remind the isomorphism of $3 and 53); (iii) all remaining seven skeletons are isomorphic with the skeleton of 600-cell (moreover, 35; has same faces; remind the isomorphism of 3%and 35). So eight star-polytopes from (ii) and (iii) above are not embeddable. Remaining case (i) is decided by the Theorem 3.3, using 5-gonal inequality. N

Theorem 3.3

N o n e of the t e n star-4-polytopes is embeddable.

Corollary 3.1 embeddable.

N o n e of the f o u r star-honeycombs in hyperbolic 4-space is

3.4 The case of dimension d

2

3

Tables 3.2, 3.3, 3.4 present all sub-cases in the dimensions 3, 4, 5; for higher dimensions d, d-simplices a d , d-cross-polytopes p d , d-cubes 'yd and cubic lattices b d are only regular ones. In those Tables, 24-, 600-, 120- are regular spherical 4-polytopes 343, 335, 533 with indicated number of cells and De(D4), Vo(D4) are

41

Regular tilings and honeycombs

Table 3.2 3-dimensional regular tilings and honeycombs

Table 3.3 4-dimensional regular tilings and honeycombs

63

9 53 355 5q5

4343* q533

35g5 5253

Table 3.4 5-dimensional regular tilings and honeycombs

regular partitions 3343, 3433 of Euclidean $-space, which are also Delaunay (Voronoi, respectively) partitions associated with the (point) lattice D4. The Euclidean cases (three in dimension 2, 4 and one in dimension 3, 5) are denoted by bold symbols. All cases of embeddability are marked by the asterisk * in these Tables. Theorems 3.1, 3.2 show that all regular 2-dimensional tilings and starhoneycombs are embeddable except y m for all odd m > 7. The following

42

Scale Isometric Polytopal Graphs

Theorem 3.4 decides all remaining regular sub-cases.

Theorem 3.4 All embeddable regular tilings and honeycombs of dimension d 2 3 are the following tilings: (a) either (Ud+l, or ,&+I, or (ii) all with bipartite skeleton: (ia.1) all with cell T d : T d + l , 6 d and 3 hyperbolic ones: 435, 4335, non-compact 436; (ii.2) all 4 with cell b d - 1 : hyperbolic non-compact 443, 444, 4343, 43343; (ii.3) all 4 with cell 63: hyperbolic non-compact 633, 634, 635, 636. All el-rigid regular tilings are the bipartite ones. All, except yd+l and 6 d themselves, bipartite tilings are embeddable into Z,.

Remark 3.3 All infinite families of regular tilings are embeddable. In fact, n-gons n, 6, = Z,, 7, = H,, a,, pn are embeddable and, moreover, first three are C1-rigid. But embedding of skeletons of a, and, for n 2 4, of pn, is more complicate. It is considered in detail (in terms of the corresponding graphs K,+1 and Knxa) in chapter 23 and chapter 7.4 of [DeLa97], respectively; see also chapter 1.2 above.)

Remark 3.4 All non-embeddable regular tilings are not 5-gonal. For two most difficult cases, 120-cell and 600-cell, it was shown in [DeGr97b] and [Duto02], respectively. For 120-cell, an isometric not 5-gonal70-vertex subgraph of its skeleton was found. For 600-cell, a computer check exhibited, amongst all 190578024 5-uples of vertices, all 93 orbits of 986400 5-uples (i.e. about one of 193), which violate the 5-gonal inequality. All, but three, of 93 orbits correspond to a not 5-gonal isometric subgraph of the skeleton, having diameter 4 or 5. But the smallest such subgraph is the 7-vertex planar graph of diameter 3, which comes from Kq by adding the mid-points of three edges of its subgraph P3.

Chapter 4

Semi-regular Polyhedra and Relatives of Prisms and Antiprisms

4.1

Semi-regular polyhedra

The results on l1-embedding of semi-regular polyhedra and their duals are presented in Tables 4.1, 4.2 below. We obtained them by direct check; let us illustrate this check on embeddability of antiprisms. Remind that an antiprism APrism, is a polyhedron, whose 2n vertices lie on two parallel facets F and F’. Let &it, 1 5 i,i‘ 5 n,be vertices lying on F and F’, respectively. Then edges of APrism, are the pairs (i, i + I), (i, i’), (i 1,i’), (i’,i’ 1) (here and below the addition is modulo n). Let us give, for example, the embedding APrism, i H n + l . We give the embedding APrism, + ;H,+l by addressing the vertex v as the following subset a(v)of { 1 , 2 , . . . ,n,n I}) for all three possible cases (below we suppose 1 5 i 5 n).

+

+

---f

+

(1) n = 2 k + 1 :

+

a(i) = {i,i 1,.. . , i a(i’) = { i , i+ 1 , .. , , i

+k}, + k - 1) u { n + I},

(2) n = 4 k + 2 :

a(i) = {i, i + I , . . . , i + k}, { n 1) U (a(i)- { i } ) if i is odd, a(i’) = { n 1) U a(i)u { i + k + I} if i is even;

+ +

43

44

Scale Isometric Polytopal Graphs

(3) n = 4k:

+ if either 1 5 i 5 2k and i is odd, + or 2k < i I 4 k and i is even, {n + 1) U a ( i ) U {i + k + 1) otherwise.

a ( i ) = {i,i 1 , . . * , i f 2k - l ) , { n 1) U ( a ( i ) )- (2)) a(2’) =

Remark 4.1 (i) “14th Archimedean solid” (twisted Rcbt) on Figure 4.1, unique new polyhedron if we weaken the vertex-transitivity to the uniqueness of the vertex figure) and its dual are not 5-gonal. (ii) [PSCSO] gives P 4 H , for any 3-polytope without triangular faces and without vertices of degree three. The truncated icosahedron provides an example of a 3-polytope without triangular faces (but with all vertices of degree three), which is not 5-gonal.

3

In Tables 4.1, 4.2 d = d ( Q ) and w = w(Q) denote, respectively, the diameter and the number of vertices of polyhedron Q, where Q is P*or P, the later being a Platonic or a semi-regular polyhedron. All l1-polyhedra in those Tables are ll-rigid, except the tetrahedron and dual Prism3 having two embeddings each. While for both embeddings of dual P r is ms all items of Tables 4.1, 4.2 coincide, they are different for two embeddings of the tetrahedron. For convenience, Tables 4.1,4.2 present those two embeddings of this self-dual polyhedron as, respectively, embedding of the tetrahedron and of its dual. Two possible properties of embeddings (see also chapter 14) are addressed in columns “ J ( m ,k)?” and (‘cuts” of Tables 4.1, 4.2, using computer check in [Duto02]. Columns “ J ( m ,k)?” treat isometric embeddability into the Johnson graph J ( m , k), i.e. whether considered embedding into a half-m-cube has, moreover, the same size k of subsets, which address the vertices. It turns out, that for every 11-polyhedron Q in those Tables, which embeds isometrically into some J(m,k), we have m = 2k, except m = 2 k + l for all odd-sided prisms and m = 4 for the second embedding (a3 -+ i H 4 ) of the tetrahedron. Moreover, k = d ( Q ) in all cases, except dual truncated cube. Columns ‘kuts” list all values of w(S) := min(lSl,v - IS\),where S is any subset (of v-set V of vertices), such that the coefficient as is positive in the equality ( l . l ) , i.e. the cut d(S) appears in the embedding under correspond to a singleton cut and an consideration. The values w = 1, equicut b ( S ) ,respectively (see chapter 14 for details).

Semi-regular polyhedra and relatives

45

Table 4.1 Embedding of semi-regular polyhedra

polyhedron P face-vector tetrahedron (3.3.3) cube (4.4.4) dodecahedron(5.5.5)

tr(icosidodecah.) (4.6.10) snub cube (3.3.3.3.4) snub dodecah. (3.3.3.3.5) Prism3 (4.3.4) Prismn>s9,dd (4.n.4) P ~ i ~ m n > c i , e v e(4.n.4) n APriSmn>5,0dd(3.3.n.3) A P r i ~ m , > r ,(3.3.n.3) ~~~~

4.2

el-emb. P -+ i H 3 -+

H3

$Hie

+

+ Hl5

$Hg

-+

+ --t

-+

$H5

iHn+2

- + H e -+

-+

$Hn+1 $Hn+1

J ( m ,k)?

cuts 2

-2 -2 V V

no

V 2 V -

J(30,15) no no

J(5,2) J(n+2,y) J(n+2,?) J(n 4- I,?) no

d 1 3 5

V -

no J(673)

2

-2 V

v-2 -

2

2

' 2

y, $

V 2

15 4 7 2 n+l 2 n+ 1 2 -n2

Moscow, Globe and Web graphs

Call Prismr:=Pm+l x C, ( m 2. 1 , n 2 3) Moscow graph, since its pathmetric is called, in Computational Geometry, Moscow distance (or Karlsruhe distance). Moscow graph is sometimes called annular city street graph, and this metric also appears under the name radar-discrimination distance. Prism, is the case m = 1 of Moscow graph. Clearly, Prism," -+ iHn+am,since Pm+l 4 H, (so, Pm+l 4 +H2,) and + iHn. Also, Prism; + H k + m l since C 2 k -+ H k . The Moscow graph is polyhedral, since it is planar and 3-connected. This polyhedron can be seen as a column of m copies of Prism, put consecutively one on the top of other by identifying two n-gonal faces. Call (Prism,")" the Globe graph and denote it by 2-Prism,""-l (since it can be seen as the Moscow graph Prismz-', capped on both n-gonal faces) and by B P y r p (since it can be seen as (m-1)-elongated bipyramid. For m = 1, it is the usual BPyr, and, for m = 2 , it is the usual elongated

c,

Scale Isometric Polytopal Graph

46

Table 4.2 Embedding of dual semi-regular polyhedra

polyhedron P face-vector tetrahedron (3.3.3) c7Jbe

(4.4.4)

dodecnhedron(5.5.5)

tr(cuboctahed.) (4.6.8) tr(icosidodecah.) (4.6.10) snub cube (3.3.3.3.4) snub dodecah. (3.3.3.3.5)

el-emb. P* -+ i H 4

J(4,2)

-+ +

J ( m , k)? J(4,l)

no

:He

cuts 1 21 -

2

-2 V

d 1 2

3

not 5-gonai

4

not 5-gonal not 5-gonal not 5-gonal

6 7

15

bipyramid. In what follows, we will refer to the list of 112 regular faced polyhedra given in [Berm71]. The numbers Nr.34, 35, 36 of the list are the cases n=3, 4, 5 of BPyr;. Also, the case n = 2m 2 is considered on pages 106-107 of [Crom97]; in particular, the Campanus sphere, famous during the Renaissance, corresponds to (n,m) = (12,5) of B P y r r .

+

Proposition 4.1

Consider now the Web graph Pyrp, defined as B P y r r with one of capping vertices being deleted, i.e. l-capped Moscow graph. It is the usual pyramid for m = 1. Clearly, it is the skeleton of a self-dual polyhedron: (m-1)-elongated pyramid.

Semi-regular polyhedra and relatives

47

4

-2 Rhombicuboctahedron embedded into $Hlo

Snub cube embedded into f Hg

Twisted rhombicuboctahedron is not 5-gonal Fig. 4.1 Embeddability of rhombicuboctahedron, of its twist, and of snub cube

Corollary 4.1 $H2m+n-2 if n = 3 , 4 , 5 is not 5-gonal if m 2 2 , n 2 6 4

Another (than Moscow graph) generalization of Prism, = P2 x Cn is the Lee graph its path-metric is the Lee distance (a discrete analog of elliptic distance)

& en,’;

Scale Isometric Polytopal Graphs

48

used in Coding Theory. Remind that H 4 = C4 x Cq, since C 4 = H z ; any C, x C, with m , n 2 3 is a 4-polytopal graph. Clearly, Cn, -+ (and, moreover, 4 Hq if all n, are even), t where n = CZz1 n,. We have also embeddings P,, --+ H,-t; it is a grid graph with usual t grid distance, i.e. I1-distance Ct=,)xa- yzl. Finally, we have Knz -+ i H n - t ; it is the Hamming graph with Hamming distance 1{1 5 i 5 t : x, # g a } l . For example, (2m - 1)-dimensional simplex admits, besides of embedding ~ 2 , - 1 -+ i H z m (and of others, isometric up to a scale, embeddings into hypercubes), the embeddings ~ 2 m - 1 i ( P T ) i Z m 3 lr (take all 2m vertices of the grid PF, which are adjacent to its central point) and the isometric embedding 012,-1 --+ Kam into a Hamming graph.

nb,

iff,

n:=,

n,=,

--+

--+

Fig. 4.2 Lee graph Cs x Cu and Moscow graph Prism! = Ps x

4.3

Cg

Stellated k-gons, cupolas and antiwebs

Call stelluted k-gon (and denote it by S t e l k ) the 2k-cycle C { l , l , , ~ , 2 t , . . . , k , k / } with the additional edges of the k-cycle C { l , 2 , , , , , k } . so, S t e l k is a circuit

ck

Semi-regular polyhedra and relatives

49

with a triangle on each edge; also Stelk is APrismk without the edges of the k-cycle C{1/,2t ,...,k/). For n = 5 , 6 , 7 , 8 it is used as a well known symbol (Red Star, Star of David, US sheriff star, Muslim Star, respectively). Denote by Sunzk the isometric subgraph of Stelzk obtained by deleting vertices (22 - 1)’,1 5 i 5 k . Proposition 4.2 We have embeddings: (i) Stelk -+ + H z k , (ii) S U n 2 k 4 4 H 3 k .

A cupola Cup, is the graph with vertices i, i’, i“ (1 5 i 5 n) and edges on the inner cycle C{I,..., ,I, on the outer cycle C{l,,lt,,...,n ! , n ~ ~and ) , on the paths P{;t,i,i~} for all 1 5 i 5 n. So, Cup, is the skeleton of a polyhedron; for n = 3 , 4 , 5 they are triangular] square and pentagonal cupolas: the polyhedra Nr.23, 24, 25 in the list of 112 regular-faced polyhedra (see chapter 6). We have: (i) Cup, -+ $H2n7 if n 2 4 , (ii) Cups and Cup;, n _> 3, are not 5-gonal.

Proposition 4.3

We give the following explicit embedding Cup, -+ $ H2,. Take an embedding of the inner cycle C,rl,,,,,,)-+ $23,. Let the vertex i is mapped, in this embedding, into a subset a ( i ) of an n-set V . Let a(1) = 0, and V n {1,2,. . . , n ) = 0. Then we map the vertices i’ and i” into the sets a ( i )u {i, i 1) and a ( i )u {i 1,i 21, respectively (the addition is modulo n). Note that the shortest path between non-adjacent vertices of the outer cycle goes through the inner cycle. Hence, it is not difficult to verify that the obtained embedding is isometric for n 2 4. On the other hand, Cup; contains K2,3 as an isometric subgraph for n 2 3; so, it is not 5-gonal.

+

+ +

An antiweb AW;, for 1 5 k 5 l$j, is the graph with the vertices 0 , 1 , . . . , n - 1 and i i + 1,i + 2 , . . . , i + k (mod n). (Here i j denotes that the vertex i is adjacent to the vertex j . ) It is a common generalization of the following embeddable polytopal graphs: N

N

0

AWJ = C, -+ $Hn (and -+ H q if n is even), AW; = G(APrismq)---t $Hn+z if n is even,

0

AWP’2J

0

0

= K , = G(a,-1)

-+

$Ifn,

= Kqx2 = G(P2) -+ $H4m (for some m ) if n is even.

Scale Isometric Polytopal Graphs

50

The next Proposition (see proof in [DeGr97a])states that all other antiwebs are not 11-graphs. It is easy to check that AW; has diameter 2 if and only if 5 k 5 L2J - 1.

Except of four above cases, any AW: is not embeddable. Moreover, (i) at is not 5-gonal an sub-cases: (i.1) k = 2 , n = 7 or n 2 13 and is odd, (i.2) n = 4k 3 , k 2 3 or n = 4k 4, k 2 4, (i.3) pp15 IC < 5 - 1; (ii) AW?', AW?3 and AW& are not 7-gonal; (aii) AW;, AW;2 and AW:4 are hypermetrics non-11.

Proposition 4.4

+

4.4

+

Capped antiprisms and columns of antiprisms

Denote by 1-APrism, (or, respectively, by 2-APrism,) the APrism, with pyramid Pyr,, being put on one of two (or, respectively, on both) m-gonal faces of the APrism,.

Amongst all i-APrism, (with n 2 3 and i = 1 , 2 ) and their duals, we have: (i) i-APrism3 -+ iH~+4, (i-APrisms)* -+ !jHi+6, a-APrisms --+ i H 6 , but i-APrism4 is hypermetric non-ll; (ii) l-APrism6 + iH7, 1-APrismT ;Ha; (1 - APrism4)* -+ ;Ha, Do = (2-APrisms)* -+ !jHlo; (iii) (2-APrism4)* = Barrel4 is not 7-gonal; (iv) all others are not 5 - g o d .

Proposition 4.5

--+

Define by induction on k the following 4-valent polyhedron AP ris mk . is obtained from APrasm: by APrism& := APrism, and APrisrn:+' inscribing a new m-gon in the lower one of its two opposite (upper and lower, say) m-gonal faces, such that the vertices of new m-gon are the midpoints of the edges of the m-gonal faces. Dual APrismK-2 is the polar zonotope P z ( m) H,, considered in chapter 14. One can check that APrism: --+ iH6 and that APrismk is not 5-gonal for any m 2 4. Define by induction on k the following (4,6)-valent polyhedron Tower:. Tower& := APrism, and Tower&+' is obtained from T o w e r i by putting face-to-face a new APrism, on one of its two opposite m-gonal faces. One can check that Tower& is not 5-gonal for any m 2 3. -+

Semi-regular polyhedra and relatives

51

Denote by Barrel; the 3-valent polyhedron, consisting of two opposite m-gonal faces, each surrounded by a ring of m pentagons, and separated by k - 1 consecutive rings of m hexagons. Barrel; is the Barrel,, considered in chapter 13; clearly, Barrel, = (2-APrismm)*. Barrel; is the k-layered dodecahedron from chapter 2. It is easy t o see that (Barrel:)* is 2-Towerk, i.e. it is Tower: with pyramids Pyr,, being put one both of its opposite m-gonal faces. See on Figure 4.3 below examples of graphs from this chapter. We mention finally two interesting not 5-gonal graphs, APrismg and Koester's graph, depicted as items f ) and g) on Figure 6.4. The first one is a projection of a borromean 5-link, i.e. any two of its five components form a trivial link. The second one has the chromatic number four, while every of its proper subgraph have a 3-coloring; this graph can be reduced to the icosidodecahedron by deletion of the large central circle.

Scale Isometric Polytopal Graphs

52

b) 1-APrisms

2a

c ) (l-APrismd)*+ $ H s

g) Tower: = P 3

+

P3

d) (1-APrisms)'

h) dual Tower:

Fig. 4.3 Prisms and their relatives

Chapter 5

Truncation, Capping and Chamfering

5.1

Truncations of regular partitions

For a regular partition P notation ( F ,V ) means that its faces are F and its vertex figures are V . Now t r ( P ) , gtr(P) and Ambo(P) denote usual truncation (i.e. $truncation), golden (coherently) and mid-point (i.e. truncation) of P, i.e. each edge of P is truncated in proportion a:b=2, r and 1, respectively. Consider first embedding of t r ( P ) , of its dual (omnicapped P*)and of Ambo(P) for regular tilings of dimension two, see Table 3.1. For the five Platonic solids all embeddings are listed in Tables 4.1, 4.2. Remind that p3 is Ambo(a3), the cuboctahedron is Ambo(P~)=Ambo(y3) and that the icosidodecahedron is Ambo(P) for both, the icosahedron and the dodecahedron. For three regular partitions P = (rq) of the Euclidean plane all such embeddings are listed in Table 9.1, see Nr.1-6 there. In fact, tr(44)=(4.82), tr(36) = (63), tr(63) = (3.122) and A m b 0 ( 4 ~ )= (44), Arnb0(3~)=Ambo(6~)=(3.6.3.6). The remaining case of all regular partitions P = ( r q ) of the hyperbolic plane is treated by the proposition below.

fr-

Proposition 5.1 (i) tr(rq)=(q.2r2); it is not 5-gonal if q = 3, it is embeddable into ;Zoo i f q 2 5 is odd and it is embeddable into Z, if q 2 4 is even; (ii) tr(rq)* is not 5-gonal i f q = 4 and is embeddable into ;Zoo, otherwise; (iii) Ambo(rq)=(r.q.r.q); it is not 5-gonal if r = 3, q is even or q = 3, r is even, but it is embeddable into Z , i f r , q are even and into Z,, otherwise.

3

Examples of embedding results in higher dimension are: Ambo(ad)= T ( d 1) + ;Hd+l for d 2 2 (the convex hull of all binary sequences of

+

53

Scale Isometric Polytopal Graphs

54

+

length d 1, having exactly two ones), but Ambo(Pd), Ambo(yd) for d 2 3 and (Ambo(P))*, for each of six regular 4-polytopes P , are not 5-gonal. In Table 5.1, we use Coxeter’s notation s(3,4,3) and s(3,4,3,3) for the snub 24-cell (which comes as the golden truncation of the 24-cell; see also chapter 7) and for the honeycomb, coming as the golden truncation of the Voronoi partition Vo(D4) (see [Coxe35]). Remarks to Table 5.1: (i) in dimension d = 2,3,4, we have t r ( P ) -+ Hn, gtr(P) + $ H n , where n = 3 x 2d-2 and polyhedra t r ( P ) , g t r ( P ) have n x 22d-2, n x 22d-2-1 vertices, respectively; (ii) Ambo(P) are not 5-gonal for P = P 3 , 24-ce11, Vo(D4); (iii) t r ( P ) are zonotops for P = a z , P 3 , 24-cell,Vo(D4), but for any other regular d-dimensional tiling with d 2 3, they are not 5-gonal; (iv) compare Table 5.1, concerning regular P = ( F ,V = yn), with Table 5.2, concerning regular P = ( F = ynrV).

5.2

P a r t i a l t r u n c a t i o n s and cappings of Platonic solids

Call i-truncation and i-capping the (usual short) truncation on i vertices of a polytope P and, respectively, adding a pyramid on i its faces. A triakis (tetralcis, pentalcis, hexalcis) i-capping is an i-capping only on %faces (4-, 5-, 6-faces, respectively). The capping on all faces is called also omnicapping or stellation. P r o p o s i t i o n 5.2 (i) i-truncated a3 $H4+i, 0 5 i 5 3; 4-truncated a3 is n o t 5-gonal; dual i-truncated a3 = i-capped a3 -+ $H3+i, 0 5 a 5 4. (ii) i-truncated p 3 + i H 4 , i H 6 , H4, HS for i = 0 , 1 , 2 (on opposite vertices), 6 (i.e. all)) not 7-gonal i f only two vertices of a n edge are not truncated; otherwise, not 5-gonal; dual i-truncated ,83 = a-capped y3 + iH6 if i I 2 o r i = 3 and a n y two capped faces of y3 are not opposite; otherwise, not 5-gonal. (iii) i-truncated y3 + ;Hs+i if i = 0 , 1 , 2 (truncated vertices are at distance one or three), 3 (they form P3), 4 (they form (74); otherwise, not 5-gonal; dual a-truncated 7 3 = i-capped ,& -+ iH4+i f o r 0 5 i 5 8. (iv) a-capped icosahedron + Hs+%f o r 0 5 i 5 20; a-capped dodecahedron + $ H l o f o r 0 5 i 5 12. -+

i

Table 5.1 GoIden and usual truncation

cn

Scale Isometric Polytopal Graphs

56

Table 5.2

All embeddable regular P = ( = n, V)

V dimension TI embeddable into

(Yn

Pn

Ck>5

2 2

2 2

2

Hn+l

2,

Z,

ICO 3 2,

600-cell

4 2,

Remark 5.1 (i) Amongst above el-graphs only non 11-rigid one is a3 -+ iH3, iH4. (ii) 73, 4-truncated on four non-adjacent vertices, or on four vertices forming two opposite edges, are Cham(a3) or twisted Cham(a3), respectively; see them on Figure 5.2. Remaining four ways to 4-truncate 73 are when these four vertices induce one of the graphs C4, P 4 , P3 K1 and K1,3. All three ways to 3-truncate 7 3 are on P3, PZ K1 and 3K1.

+

+

Fig. 5.1 Three embeddable 3,, n = 16,28,16

+

Embedding of P Pyr3. Let G be a plane graph, embeddable into i H m , and let F = ( a ,b,c) be its fixed triangular face. We fix an embedding E of the graph G into i H m ; let t,, t b , t , be the cuts (from the complete family of convex cuts, corresponding to fixed embedding), such that t, goes through sides ( a ,b) and ( a ,c ) , t b goes through sides ( b , a ) and ( b , c), t, goes through sides (c, u ) and (c,b) of the triangular face F = ( a ,b,c). We will say, that the embedding E is A-extendible (or B-extendible) to the embedding of G, capped on the triangular face F , if we get embedding just by augmenting cuts of embedding E , going through F (or, respectively, by above augmenting of cuts and addition of the new cut). A- and B-extension correspond, respectively, to embeddings a3 --+ iH3 and a3 -+ iH4 for the pyramid on the triangular face F . Clearly, A-extension gives embedding of capped G into the same i H m , while B-extension gives embedding into $Hm+l.Call a-, b- or c-secondary every edge of G, which is adjacent to the corresponding

"!runcation, capping and chamfering

57

vertex a , b or c of the face F , but different from the sides of F , adjacent to this vertex. Proposition 5.3 (a) A fixed embedding E of the graph G is both A - and B-extendable to an embedding of its capping on the triangular face F if and only if no one of cuts t,, tb, t, goes through any of a-, b- or c-secondary edges. (ii) The embedding E is A-extendible if and only if no cut ti (i = a, b, c) goes through j-secondary edge ( j = a, b, c, but j # i). (iii) The embedding E is B-extendible if and only if no cut ti (i = a, b, c) goes through a-secondary edge. (iv) Otherwise, the embedding E is not extendible to any embedding of the capping of G on the face F .

For example, unique embedding Prisms -+ iH5 is both A- and Bextendable to embeddings Prism3 Pyr3 -+ i H 5 , iH6. The embeddings a3 $ H3, -+ H4 are, actually, A- and B-extensions of unique embedding C3 -+ iH3. The first of them admits only B-extension, the second one only A-extension; both ways give an embedding of 1-capped a3 (i.e dual Prisms) into H4. Finally, unique embedding of plane triangulation -+

+

i

i

K{1,2,3,4,5,6} - p3142

-+

1 -H5 2

does not admit neither A-, nor B-extension, if we put P y r 3 on its face (1,5,6) or face (4,5,6); it fact, we will get not 5-gonal graph. Capping of some almost regular C1-polyhedra on triangular and quadrangular faces (1) Clearly, any triakis i-capping of an C1-polyhedron P is decided by the

proposition above. iH4+i if the 4-gonal face is capped, H3+i otherwise; 1-truncated Pyr4 (=dual 1-capped Pyr4)= 7 3 if the apex is truncated, or Nr.43*, otherwise (so, not 5-gonal). (3) i-augmented Prism, is Prism, capped on i 4-gonal faces, which are not two base m-gonal faces; i-augmented Prism,(m = 3,4) iHm+2 for i = 0,1,2, not C1 for i 2 3. (4) Snub cube -+ $ H g , but any tetrakis i-capping of it is not 5-gonal. $ H ~ OOnly . 5-gonal tetrakis i-capping of it (5) Rhombicuboctahedron (which, moreover, is embedded into iHlo) is capping on at most two or

(2) i-capped P y r 4 -+

-+

-+

58

Scale Isometric Polytopal Graphs

on three non-opposite 4-gonal faces, chosen between six 4-gonal faces adjacent only to 4-gonal faces. Remark similarity with capping of 7 3 (Proposition 5.2 (ii)). (6) Tetrakis omni-capping of truncated p3 --+ iH12. (7) Omni-capping of a3 (the 3T2(Td))and of of truncated a3 (the 3&(Td)) are embedded into $H7 and i H 1 1 , respectively, but omni-capping of 3 3 6 ( T d ) (the 3T0,(Td)) and of truncated cube are not C1. (Here we use notation 3,, 4,, 5,, introduced in chapter 12.2.)

Embedding of elongations along simple circuits. See definition of such an elongation in chapter 1.5. Call an non-isometric simple circuit C in a plane graph G almost isometric if for any two vertices a and b on it, such that d c ( a , b) > dG(a, b ) , we have d c ( a , b) = 1 dG(a, b) and there are two geodesic paths from a to b (i.e. of the length dG(a, b ) ) , lying one entirely inside and other entirely outside of the (simple) circuit C. See on Figure 5.2 above an example of plane graph, which is embeddable into $ H s and such that the marked simple 8-circuit is almost isometric (see two opposite marked vertices on this 8-circuit).

+

Fig. 5.2 A plane graph, which is embeddable into an such that the marked simple 8-circuit is not isometric, but almost isometric

iHml

Proposition 5.4 Let G be a plane graph, embeddable into a let C be its fixed simple circuit. T h e n for the elongation of G along C the following is true: (i) it is embeddable i f and only i f C is isometric or almost isometric, (ii) it is embeddable into $Hm+2, if it is embeddable; the complete family of convex cuts consists of all those of G (augmented by one i f traversing C , but remaining alternating or not, as in G ) plus two opposite cuts through the ring of 4-gons, replacing the simple circuit C ,

Truncation, capping and chamfering

59

(iii) both simple circuits, on which splits C by this elongation along C , are isometric in the elongation if C is isometric in G; they are neither isometric, nor almost isometric if C is almost isometric. 5.3

Chamfering of Platonic solids

Remind, that Cham(P) denotes the chamfering of the polyhedron P and Chamt(P) denotes its iteration t times. Cham & ()' is obtained by putting prisms on all faces of P and deleting original edges; see Figures 5.3, 5.4.

Fig. 5.3 Chamfering

Proposition 5.5 Let P be one of five Platonic solids and t 2 1. Then Chamt(P) or its dual is .!?,-graphonly in the following cases: (i) (Cham(as))* --t iH8, (ii) Cham(y3) H7 (zonohedron, generated by el, e2, e3, el f e2, e l f e3; it is dual tetrakis cuboctahedron), (iii) Cham(Do) --+ $ H22 (dual pentakis icosidodecahedron; see Figure 2.4). ---f

Remark 5.2 (i) Cham(P) is a partially truncated zonohedron in the following cases: Cham(as), i.e. cube, truncated on 4 non-adjacent vertices, Cham(,&) , Cham(y3) are rhombic dodecahedra truncated on all 3-valent and, respectively, all 4-valent vertices, Cham(lco), Cham(Do) are triacontahedra truncated on all 3-valent and, respectively, all 5-valent vertices. (ii) Moreover, we have that Chamt(a3) (t = 1 , 2 ) , Chamt(P3) (t = 1,2), Chamt(y3) ( t 2 2), Chamz(Ico), (Chamt(Ps))* ( t 2 11, (Cham(y3))*1 (Cham(lco))*, (Cham(Do))* are not 5-gonal. (Example of proving it:

60

Scale Isometric Polytopal Graphs

Fig. 5.4 Chamfering GC2,o(Go)for Go being Tetrahedron, Cube and Dodecahedron

Cham(P) is not 5-gonal if the polyhedron P contains induced K4 - e, because then Cham(P) contains isometric not 5-gonal 11-vertex graph consisting of the cycle Clo with a new point adjacent only to the points 1, 5, 6 of the cycle C ~ O . ) (iii) Cham(Prisms), Cham (rhombic dodecahedron) are not 5-gonal. Iterated chamfering and their duals are used in the image compressing; for example, (Chamt(y3))* appears there as (t 1)-th approximation of some fractal distribution on p3. The dual t-chamfered tetrahedron, cube and dodecahedron (see examples on Figure 5.5) are used for triangulation, seen as a decomposition (of the geometric domain into polyhedral elements) technique, in computeraided geometric design, graphical rendering, solid modeling and finite element analysis. In particular, they are used for spherical wavelets, leading to efficient algorithms in computer graphics. The notion of chamfering can be extended on non-polyhedral graphs. For example, Prism, can be seen as the chamfering of the cycle C,. On the other hand, this notion can be extended naturally onto a simple npolytope P . Denote by C h a m ( P ) the dual of the convex hull of all vertices of P*and of the mid-points of all edges of P* . As a generalization of Propo-

+

Truncation, capping a n d c h a m f e r i n g

Fig. 5.5 Dual 4-chamfered cube 43,,,(Oh) dron 5&0(Id

61

and dual 4-chamfered dodecahe-

sition above, we get (Charn(a,))* ;Hzn+2. Remark that an + i H n + l , Ambo(a,) 4 iH,+1 and (Charn(cu,))* = conv(V(a,) U V(Ambo(a,))). (Recall, V(P) is the set of vertices of P ) . Cham(P) is (2,O)-leapfrog in terms of [Sah94]. The dual of (3,O)-leapfrog corresponds to putting capped anti-prisms on all faces of P and replacing each original edge (seen as a diagonal of a quadrilateral) by the second diagonal. --f

This page intentionally left blank

Chapter 6

92 Regular-faced (not Semi-regular)

Polyhedra Now we will show that exactly 36 of 92 regular-faced polyhedra are embeddable. Those polyhedra were founded in [John661 and [Zalg69]. We use names and numbers of regular-faced (but not semi-regular) polyhedra from [Berm7l],where they are given as Nr.21-112 of the list of all 112 regularfaced polyhedra; in [Zalg69]they are numbered by 1-92. In both references they are given as appropriate joints of 28 basic polyhedra M1 - M ~ s See . also [KoSu92] with coordinates and nice pictures of those polyhedra. The 28 basic regular-faced polyhedra include: regular ones M I , M15; pyramids M2, M3; cupolas M4 - M6; The nine Archimedean polyhedra Mi for i E (10 - 12,16 - 19,26,27} (these are all Archimedean polyhedra without two quasi-regular ones and truncations of these two quasi-regular polyhedra); M I S ,M14 (which are tridiminished, parabidiminished RIDo, where we use notation rhombicosidodecahedron RIDo); M7 (which is tridiminished 1.0); pentagonal rotunda Mg; and eight others, whose complicate names reflect their high individuality. (M25 is called either snub disphenoid, or Siamese dodecahedron). The remaining four Archimedean polyhedra of Tables 4.1, 4.2 in this terms of join are: cuboctahedron Cbt=CupS G, icosidodecahedron=Mg RI Do = M14 + 2 C u p ~rhombicuboctahedron , Rcbt=Cup4+P'rismg +Cup4. (The sum P + p denotes a join of two copies of P by its face with odd number of vertices; this join is such that one of the copies is turned with respect to the other copy.)

+ z,

+

Lemma 6.1

We have: 63

Scale Isometric Polytopal Graphs

64

(i) M , is not 5-gonal for n = 4,8,10 - 13,19 - 21,23 - 25, (ii) M2g (=Nr. 105, snub APrism4) is not 7-gonal, (iii) M22 (=Nr. 106, sphenocorona) is hypermetric not 11, (iv) remaining 14 polyhedra M,, have 41 -skeletons (see Figure 6. l ) , (v) M; has l1-skeleton for n=1-3, 10-12, 15, 16, 19, 23, 25 and it i s not 5-gonal for other 17 polyhedra M,. Lemma 6.2 Skeletons of the following five polyhedra are hypermetrics not ll(see three of them on Figure 15.4): Nr.SO=APrism4 Pyr4 (gyro-elongated Pyr4 = l-APrismd), Nr.37=Pyr4 APrism4 Pyr4 (gyroelongated BPyr4 =2-APrism4), Nr. 71=Prisms 3Pyr4 (triaugmented Prisms), Nr. 1O6=M22 (sphenocorona), Nr. 1O'i'=M22 Pyr4 (augmented sphenocorona).

+

+

+

+

+

Proposition 6.1 Besides of the not 7-gonal Nr.105 and above five non 11 -embeddable hypermetrics (Nr.30, 37, 71, 106, 107)) remaining 86 regularfaced polyhedra consist of 50 not 5-gonal ones and 36 with Cl-embeddable skeletons: Nr.21, 22, 24-29, 31, 32, 34, 39-41, 44, 48, 69, 70, 72-76, 78-84, 92-95, 100. Corollary 6.1 el-status of eight convex deltahedra is as follows: i H 4 , icosahedron ;He, (i) a3 3 i H 3 , Nr.32=BPyr3 -+ i H 5 , P3 (ii) Nr.33=BPyr5 and Nr. 104=M25 (snub disphenoid) are not 5-gonal, (iii) Nr.37, 71 are hypermetric and not e l . -+

-+

Remark that all five dual truncated P , where P is a Platonic solid, are simplicial and have !I-skeletons. They embed into H, with n = 7,6,12,10,16 for P being a3, P 3 , 7 3 , Ico, Do, respectively. Amongst of other simplicia1 Catalan polyhedra, namely Prism: and dual truncated Q (Q being cuboctahedron or icosidodecahedron), only Prism: ( n = 3,4) are 5-gonal; amongst remaining nine Catalan polyhedra (including A P r i s m i , n 2 4) only dual Q are 5-gonal.

i

Remark 6.1 Duals of regular-faced polyhedra. Examples of not 5-gonal ones are duals of Nr.23-25 (the cupolas M4M e ) , Nr.46 (the gyrobifastigium); Nr.26, 83, 100, 103, 105, 109-112, which are Mi, respectively, for i = 9, 7, 14, 13, 28, 21, 24, 8, 20. Examples of el-graphs amongst of duals of el-graphs, are duals of Nr.2122, 27-29, 32-35 and of not 5-gonal Nr.36, 104 (=M25), 108 (=M23). Namely, Mi3 --+ i H l o , Mi5 i H 8 ; apropos, ([Well84], page 75) --+

92 regular-faced polyhedra

65

together with a 17-hedron fills the 3-space. Duals of Nr.34-36 are Prism: for n = 3,4,5. Also, the duals of the non el-embeddable hypermetrics Nr.30, 37 are embeddable into and not 7-gonal, respectively, while duals of Nr.71, 106 (=M22), 107 are not 5-gonal. Apropos, examples of pairs ( P , P * )of dual polytopes having both elskeletons] are:

0

0 0

(%,%)r (pn,'Yn)?(PYr,", PY.,") for n E (3,415)~(ICO,DO), (2-capped cy3, its dual) for i # 4, (2-capped /33, its dual) for i 5 2, (Prism,"l BPyr?) for n E {3,4}.

66

Scale Isometric Polytopal Graphs

M26

M

Fig. 6.1 All embeddable ones amongst basic regular-faced polyhedra M i , 1 5 i 5 28

92 regular-faced polyhedra

67

Fig. 6.2 All not hypermetric ones amongst basic regular-faced polyhedra M,, 15a528

68

Scale Isometric Polytopal Graphs

Square ortho-bicupola Nr.48=Cups + Cup4 -+ +He

Square gyro-bicupola Nr.49=Cup4 + G,not 5-gonal

Fig. 6.3 Two bicupolas

92 regular-faced polyhedra

69

a) Tkiangular hebesphenorotunda Mzo,

b) Bilunabirotunda Ma,

C) M z ~snub , APrisme,

d) Barrel4,

e) Dual triaugmented Prisms,

f ) Dual rhombicicosahedron Pz(5)' = APrismg,

g ) Koester's graph,

h) 4-polytope Pyr(icosahedron)

Fig. 6.4

Examples of non-hypermetric polytopes

70

Scale hometra'c Polytopal Graphs

a) M ; , dual tridiminished icosahedron

b0 M*, dual hebesphenocorona

c) Mzz, dual sphenocorona

d) M&, dual snub APrism4

127

78

126

e) Dual snub disphenoid M& + ~ H s

f) Dual sphenomegacorona Mi'3 -+ ~ H I O

Fig. 6.5 Some dual basic polyhedra Mi

Chapter 7

Semi-regular and Regular-faced n-polytopes, n >4

Remind, that a regular n-polytope is one having only regular facets and regular vertex figures (the convex hull of all midpoints of edges through a given vertex). A regular-faced n-polytope is one having only regular facets. A semiregular n-polytope is a regular-faced n-polytope with equivalent vertices (i.e. the group of symmetries of the polytope is transitive on vertices). It is quasi-regular if, moreover, this group is transitive on edges. All regularfaced polytopes are known. 7.1

Semi-regular (not regular) n-polytopes

They belong to the following list, discovered by Gosset in 1897 (see, for example, [BlB191];we use notations of [Coxe73]). In dimension 4: 021=Ambo(a4) with the skeleton G(021) = T ( 5 ) -+ i H 5 , snub 24-cell s(3,4,3) + and octicosahedric polytope (not 5gonal). In dimension 5: 1 2 1 with the skeleton G(lz1) = i H 5 . In dimension 6: 221 with hypermetric, but not I! skeleton. In dimension 7: 321 with hypermetric, but not I! skeleton. In dimension 8: 421, skeleton of which is the root graph of all 240 roots of the root system Es. (It is not C1-graph, since it contains the skeleton of 221 as an induced subgraph of diameter two, and therefore, as an isometric subgraph.) So, besides the series n21 of (n+4)-dimensional polytopes for n = 0, 1, 2, 3 , 4 , there are two exceptional ones, both 4-dimensional: s(3,4,3) and nonembeddable one having 120 icosahedral and 600 octahedral facets (octicosahedric polytope). G(Oz1) is the Johnson graph J ( 5 , 2 ) and G(121) = +H5; 71

72

Scale Isometric Polytopal Graphs

remaining three are non-embeddable. 221 and 321 are Delaunay polytopes of lattices E6 and E7; they are hypermetric. s(3,4,3) comes as the convex hull of 96 points, dividing all 96 edges of 24-cell in the same ratio r : 1, where r = denotes the golden number. The icosahedron comes by the same procedure from the octahedron. All permutations of (fr,*r, 0,O) gives all vertices of the 24-cell; all even permutations of ( k ~ k1, ,k : , 0) give those of s(3,4,3). The s(3,4,3) has 120 tetrahedral and 24 icosahedral facets. By capping (i.e. putting the pyramid on) each icosahedral cell, one get the regular 600-cell, which is non-embeddable, because G(Pyr(1co)) is a not 7-gonal isometric subgraph of the graph G(600-cell) (in fact, G(600-cell) is also not 5-gonal).

7.2

Regular-faced (not semi-regular) n-polytopes

Going through the list of those polytopes given in [BlB191],we obtain: G(Pyr(Pn-l)) = K1,2,...,2is an isometric subgraph of Knxz and G(BPyr(Q,-l)) = Kn+2 - e = K2,1,,,,,1is an isometric subgraph of K(n+l)x 2. So, both these graphs are el-graphs. Besides, for the following two 4-polytopes we have: Pyr(1co) is not 7-gonal, BPyr(1co) is not 5-gonal (its skeleton contains K5 - p 2 - P3); the union of 021 and Pyr(p3) (where p3 is a facet of 021) -+ i H 5 ; finally, any 4-polytope arising from the 600-cell by special cuts of vertices, except of the snub 24-cell, is not embeddable.

7.3

Archimedean 4-polytopes

Finite relatives of uniform partitions of 3-space are Archimedean 4polytopes, i.e. those having vertex-transitive group of symmetry and whose cells are Platonic or Archimedean polyhedra and prisms or antiprisms with regular faces. So, it is a large generalization of semi-regular 4-polytopes. [Conw67] enumerated all of them: (1) 44 polytopes (others than prism on 73) obtained by Wythoff’s kaleidoscope construction from 4-dimensional irreducible reflection (point) groups; (2) 17 prisms on Platonic (other than 73) and Archimedean solids;

Semi-regular n-polytopes, n

24

73

(3) prisms on APrism, for any n > 3; (4) a doubly infinite set of polytopes, which are direct products of two regular polygons (if one of polygons is a square, then we get prisms on 3-dimensional prisms); (5) the snub 24-cell; (6) a new polytope, called Grand A n t i p r i s m , having 100 vertices (all from 600-cell), 300 cells a3 and 20 cells APrism:, (those antiprisms form two interlocking tubes). Using the fact, that the direct product of two graphs is !I-embeddable if and only if each of them is, and the characterization of embeddable Archimedean polyhedra in [DeSt96] (see Tables 4.1, 4.2 above), we can decide about embeddability in cases 2)-4). Now, the snub 24-cell is embedded into i f f l a (see below) and the Grand Antiprism (as well as 600-cell itself) violates 7-gonal inequality, which is necessary for embedding. It implies the following Corollary. Corollary 7.1 Besides n o t 7-gonal Grand Antiprism, six n o t 5-gonal p r i s m s ( o n truncated ag, truncated 7 3 , cuboctahedron, truncated icosahedron, truncated dodecahedron and icosidodecahedron) and undecided case I), all Archimedean 4-polytopes are embeddable.

7.4 The embedding of the snub 24-cell The snub 24-cell was introduced by Gosset in 1897. It has 96 vertices, 288+144 edges in two orbits, 96+96+288 triangular faces in three orbits and three orbits of cells: 24+96 tetrahedra and 24 icosahedra. One orbit of edges is surrounded by one tetrahedron and two icosahedra, the other one by three tetrahedra and one icosahedron. The vertex figure (and the local graph of the skeleton) of the snub 24-cell is the tridiminished icosahedron (the regular-faced solid MT = Nr.83 of the list [Berm71]); it is embeddable into i H 6 . We give an embedding of the snub 24-cell into as 48 columnvectors representing some 48 vertices amongst the 96 vertices. The remaining 48 columns are obtained by adding the all-ones vector modulo 2 to each of these 48 columns.

I HI^

74

Scale Isometric Polytopal Graphs

000000000000000000000000000000000000000000000000

000000000000000000000000111111111111111111111111 000000000000111111111111000000000000000000001111 000011111111000000001111000000001111111111110000 000000001111000011111111000011110000000011111111 000000000000000100110001001101110000000100111111 001100000011001111110011111111110000111111111111 000100111111000001010111010l111l0111111111110111 011101010111111111111111011010110000001001011111 000000001001000000000101000001010011010111110011 010111111111011011111111000010010101011011110101 000001101101010010011111000000000001000010010001

Chapter 8

Polycycles and Other Chemically Relevant Graphs

8.1

(r,q)-polycycles

Recall that a graph G is k-(vertex)-connected if a deletion of any k - 1 vertices from G does not disconnect it. A girth of graph G is the length of a maximal isometric circuit of G. A polycycle or, more precisely, (r,q)-polycycle is a simple planar 2(vertex)-connected finite or countable locally-finite graph G of girth r and maximal vertex-degree q , which admits a realization on the plane, such that: (i) all interior vertices are of degree q, (ii) all interior faces are (combinatorial) r-gons, It is shown in [DeSt02d], that (i) and (ii) imply (iii) all vertices, edges and interior faces form a cell-complex (i.e. the intersection of any two faces is edge, vertex or 0), while neither (i), (iii) imply (ii), nor (ii), (iii) imply (i). Clearly, a polycycle is the skeleton of a 3-polytope if and only if its plane realization is 3-connected, i.e. the degree of each boundary vertex is at least three and each interior face has a t most one boundary edge. The main example of (r,q)-polycycle is the skeleton of ( r q ) , i.e. of the q-valent partition of the sphere S2,Euclidean plane R2 or hyperbolic plane H 2 by regular r-gons. For ( T , q ) = (3,3),(4,3), (3,4), (5,3), (3,5)it is, respectively, Platonic tetrahedron, cube, octahedron, dodecahedron, icosahedron on S 2 , but with excluded exterior face; for ( r ,q ) = (6,3), (3,6), (4,4) it is the regular tiling (63), (36), (44) of R2; all others (rq) are regular partitions of H 2 . Call a polycycle proper if it is a partial subgraph of (the skeleton of) 75

76

Scale Isometric Polytopal Graphs

the regular partition ( r q ) . Call a proper ( r ,q)-polycycle induced (moreover, isometric) if it is induced (moreover, isometric) subgraph of ( r q ) . (rq) is embeddable into i H 3 , H3, i H 4 , ~ H I o~, H s 23, ; i 2 3 , 22 and $ 2 (or1 ~ moreover, 2,) for (r,q)=(3,3)1 (413), (3,4), (5,311 (375); (613), (3,6), (4,4) and rnax(r,q) 2 7 (or, moreover, r is even), respectively. So, any isometric polycycle is embeddable. Call a vertex-split (34), a (3,4)-polycycle, coming from (34) as follows. Let V C I ~ , ~ be , ~ (induced ,~) in (34)) 4-wheel with an apex 2 ; replace the edges (x,a ) , (x,b ) of (34) by the edges ( ~ ’ , a )(x’, , b), where x’ is a new vertex. See it on the right hand side of Figure 13.3. The vertex-split (35) is defined similarly. Examples of non-embeddable polycycles are: (43) - e , (34) - el ( 5 3 ) - el (35) - e , vertex-split (34), vertex-split (35) and four polycycles, given on Figures 8.1 and 8.2. Amongst above ten polycycles only vertex-split (34) and vertex-split ( 3 5 ) are not proper ones and amongst eight proper ones, only those on the right-hand side of Figures 8.1 and 8.2 are induced ones. Theorem 8.1 ([DeStOl], [DeSt02b], [DeSt02c]) (i) For ( r , q ) # ( 5 , 3 ) ,( 3 , 5 ) , there are exactly three non-embeddable polycycles: (43) - e, (34) - e and the vertex-split (34)) (ii) except of (53) itself, any (5,3)-polycycle is embeddable if and only i f it does not contain, as an induced subgraph, neither of two proper polycycles with p5 = 6, given on Figure 8.1.

Fig. 8.1 The forbidden induced subgraphs of embeddable (5,3)-polycycles

(iii) except of (35) and (35) - v , any (3,5)-polycycle is embeddable if and only if it does not contain, as an induced subgraph, neither of two proper 10-vertex polycycles, given on Figure 8.2. Amongst all 39 proper (5,3)-polycycles, the embeddable ones are: (53), three with p5 = 7 (see Figure 8.3), nine with p5 = 6 (all but two from Figure 8.1) and all 14 with p5 1. 5. Any outer-planar polycycle is embeddable, as well as any connected outer-planar graph.

Polycycles and other chemically relevant graphs

Fig. 8.2

77

The forbidden induced subgraphs of embeddable (3,5)-polycycles

Fig. 8.3 The embeddable (5,3)-polycycleswith p5 = 7

Embeddable (r,q)-polycycles have the scale X = 1 if T is even and 2, otherwise. Consider any finite embeddable polycycle with perimeter p and .z closed zones of opposite (alternating left and right opposite, if T is odd) non-boundary edges. Then (see Introduction) it is embedded into if T is even (it implies that p is also even), and it is embedded, with scale two, into H p f z , if r is odd. There is a continuum of (6,3)-polycycles, which are embedded only into 2,. Let us label the six edges of a hexagon consecutively by the numbers 1, 2,. . . , 6. Then opposite edges have distinct parity. Call edges with odd labels odd. Now, consider a polycycle, which is an odd tree 7 of hexagons. Hexagons of the odd tree are adjacent only by odd edges and there is no cycle of hexagons. For example, an infinite chain is an odd tree ‘&, where every hexagon of hi, -m < i < CQ, is adjacent to exactly two other hexagons hi-1 and hi+l. Let ( p i , q i ) be the labels of edges, such that hi is adjacent to hi-1 and hi+1. We obtain an infinite sequence { ( p i , q i ) : --oo < i < m}, p i , q i E {1,3,5}, corresponding to lo. Obviously, this family of sequences contains the continuum of aperiodic sequences. Note that every hexagon of contains a free odd edge. Hence we can join lo by the free odd edge to a finite or infinite branch. So, we have a continuum of infinite odd trees with finite and infinite branches.

8.2

Quasi-(r, 3)-polycycles

In [DeStOOb] the embedding of quasi-(r,3)-polycycles, i.e. ( T , 3)-polycycles without condition (ii), was considered: a few interior r’-gonal faces with r’ # r are permitted. Let P be such plane realization of a graph and

Scale Isometric Polytopal Graphs

78

let pint denote the sequence (p3,p4,. . .), where pi is the number of igons amongst interior faces of P. Such graphs, especially those with pint = ( P 6 ) i (p4 = l , p s ) , ( ~ = 5 1 , ~ s( ) ~~= 4 2 , ~ s(p5 ) ~= 2 P S ) are of interest in Organic Chemistry (namely, as polycyclic aromatic hydrocarbons); such compounds as benzene, biphenyl, Auorentene, terphenyl, indacene correspond to p6 = 2 , 2 , 3 , 1 , 1 , respectively, in the five above cases. Figure 8.4 represents (in terms of the atoms of carbon C and hydrogen H , corresponding, respectively, to all and to all 2-valent vertices): benzene C S H S , naphtalene (710 Hg , azulene CloHg, indacene c12H8, terpheniloide Cg H5 , fluorentene C16H10, pentalene C s H 6 , biphenilene c12Hg, respectively. ?

,

benzene

naphtalene

azulene

indacene

c 6 H6,

CioHs,

ClOHS,

C12H8,

terpheniloide

fluorentene

pentalene

biphenilene

C9H5,

c16Hl0,

c8H6,

C12Hs

Fig. 8.4

Some small quasi-(r,3)-polycycles

Ernbeddability of such graphs is useful for the calculation of some their distance-related indices and for the purpose of nomenclature. Theorem 8.2 below describes the embeddability of many quasi-(r, 3)-polycycles in terms of forbidden isometric subgraphs; in cases (iv) and (v) of this Theorem, the set of such forbidden subgraphs is infinite. An example of graphs from Theorem 8.2 (i) is coranulene C2oHl0, consisting of a pentagon, surrounded by five hexagons; it embeds into iH15.

Theorem 8.2 ([DeStOOb]) A quasi-(r,3)-polycycle P is embeddable (i) f o r p3 = p4 = 0,p5 L: 1: always, (ii) for pint = (p3 5 2 , ~ s ) if: and only if each triangle has a vertex of degree 2 (ie. P has n o Figure 8.5 a) above as an isometric subgraph), (iii) for pint = (p4 = 1,p6): if and only if P has n o Figure 8.5 b) above as a n isometric subgraph,

Polycycles and other chemically relevant graphs

a

79

b

Fig. 8.5 The forbidden isometric subgraphs for pint = = (P4 = L P 6 )

5

(p3

2 , ~ s )and for

Pint

(iv) for pint = ( p q = 2 , p ~ ) only : if P has no graphs G,,t (illustrated by Figure 8.6 a), b) for ( s , t ) = (3,2), (1,l)), or G, (illustrated by Figure 8.6 c) for u = 4, l), or Figure 8.6 d) 8.2 d) as an isometric subgraph, (v) for pint = (p5 = 2 , ~ s ) only : if P has no graphs F,?t (illustrated b y Figure 8.7 a), b) for ( s , t ) = ( 3 , 2 ) , ( 1 , 1 ) ) or F, (illustrated by Figure 8.7 c) for u = 3) as an isometric subgraph.

a

b

d

C

Fig. 8.6 Some forbidden isometric subgraphs for pint = (p4 = 2 , p ~ )

e b

a

C

Fig. 8.7 Some for idden isometric sL-graphs for pint = ( p 5 = 2 , ~ s )

Remark that embeddable graph on Figure 2.2 (see chapter 2 ) contains the forbidden graph F1,1, given on Figure 8.2 b), but it is not an isometric subgraph.

80

8.3

Scale Isometric Polytopal Graphs

Coordination polyhedra and metallopolyhedra

According to Wells [Well84], the chemical crystal structure is usually described by the coordination polyhedra (i.e. the convex hulls of anions forming the group of nearest neighbors of each metal ion) or by the domains of atom (i.e. Voronoi polyhedra). Coordination polyhedra are arrangements of nearest neighbors in crystals, molecules and ions. More precisely, as defined by Frank and Kasper in Chemistry, a coordination polyhedron is the convex hull of the mirror images of the center of a Voronoi-Dirichlet domain in each of its faces. Remark that the coordination polyhedron is, in general, not dual to the Voronoi domain, and different from the contact polytope of sphere packing. For example, while the Voronoi polyhedron of a point of the bcc (i.e. the body-centered cubic lattice A:) is the truncated octahedron, its coordination polyhedron is the rhombic dodecahedron. In addition to some frequent coordination polyhedra, the el-status of some metallopolyhedra (convex hull of atoms of metallic cluster) or metal and oxygen polyhedra (see, for example, [Kinggl; Well841) are given in Table 8.1. The names and the numbers (as regular-faced polyhedra) are taken from the list of such 112 polyhedra given in [Berm7l; Zalg691. For example, see Figure 4.1, where the embedding of the rhombicuboctahedron (Nr.13) and the not 5-gonality of its twist (Nr.57) are given. The cuboctahedron and its twist (triangular orthobicupola Nr.47) are the coordination polyhedra of, respectively, the fcc and the hcp; their duals are space-fillers with the dual of the second one being not 5-gonal. The regular-faced polyhedra from Table 8.1 with Nr. 1, 2, 4, 32, 33, 37, 71 and 104 are the eight convex deltahedra with regular (triangular) faces and with n vertices, where 4 5 n I 12, n # 11. Those deltahedra are dual of the first eight medial polyhedra F, given in Figure 13.1 with n = 4, 8, 20, 6, 10, 16, 14 and 12. The last three el-embeddable polyhedra of Table 8.1 are capped or 2capped Platonic solids. Remind that, i-capped tetrahedron ;H3+% for 1I i I 4, i-capped octahedron + $H4+%for 1 5 i I 8, i-capped cube + $H6 for 1 I i 5 2, or i = 3 without opposite capping, and i-capped cube is not 5-gonal for 4 I iI 6 or i = 3 with opposite capping. The cuboctahedron and its twist (triangular orthobicupola Nr.47) are the coordination polyhedra of, respectively, the f cc and the hcp; their duals are space-fillers with the dual of the second one being not 5-gonal. --f

Polycycles and other chemically relevant graphs

Fig. 8.8 The edge-coalesced icosahedron

81

82

Scale Isometric Polytopal Graphs

Table 8.1 dra

Embeddability of some of the most frequent chemical polyhe-

Polyhedron (its Nr. as regular-faced) Tetrahedron ( 1 ) Octahedron ( 2 ) Cube ( 3 ) Zcosahedr on (4) Cuboctahedron (6) Thncated tetrahedron ( 8 ) Rhombicuboctahedron (13) Triangular prism (19) Square antiprism (20) Square pyramid (21) %angular cupola (23) Gyro- elongated

gyrobicupola (56) Twisted rhombicuboctahedron (57) Elongated pentagonal Augmented triangular prism (69) Biaugmented triangular prism (70) Waugmented triangular prism (71) Snub disphenoid (104) Octahedron f Pyr3 Octahedron f 2 Pyr3 Tetrahedron 2 Pyr3 Edge-coalesced icosahedron (Fig. 8.8)

+

el-embeddability

Chemical example

$H3 aH4 H3 -+ $He not 5-gonal not 5-gonal

Rh(C0)iz

+.

[o% (COlS)]’-

+.

CSCl [Molz030(Ce01~)1~[M012036(Si04)]4[M01z(HOAs03)4034]~[VIS 0 4 2 (504 118[RhsC ( c 0 )151 [C08C(CO)1812FesC(C0)15 [w903o(P04)1’[Cog (CO)2 1 12-

+

+.

’-

$H5 +H5 -+ 4H4 not 5-gonal ext. hypermetric +.

-+

si

I

not s-gonal

I

I

not 5-gonaI

I

I

+

+

’-

[H4 VIS0 4 2 ( B r ) ] IW30P50110

$H5

Na5 Z r z Fi3

$H5

Nz H6 (ZrF6)

ext. hypermetric

Eu(OH)3

not 5-gonal ---t $H5

[ R U 7 (cO16l3-

14-

K4 Zr Fs

-+ $H6

[oss(co2212-

iH5 ext. hypermetric

[oS6(co18]2-

-+

[BllH11I2-

Chapter 9

Plane Tilings

9.1

58 embeddable mosaics

We review here mosaics T (i.e. edge-to-edge tilings of Euclidean plane by regular polygons) with respect of possible embedding, isometric up to a scale A, of their skeletons or skeletons of their duals T * , into the cubic lattice 2, for some n. Main result of this chapter is the classification, given in Table 9.1, of all 58 such mosaics amongst all 165 mosaics of the catalog, given in [Chav89] and including all main classifications of mosaics. It turns out that all non-embeddable mosaics T and their duals T* considered here are, moreover, not 5-gonal. In Table 9.1, non-embeddability of T or T* indicated by the sign - in the columns 4 or 5, respectively. All embeddings were found by the same method of complete system of alternating zones, as in [DeSt96], [DeSt97], [CDG97]. A mosaic is denoted here by its standard face-vector ([GrSh87]), giving all stars (i.e. the list of all tiles, surrounding a vertex) for vertices of each type. Denote by w,t , e the number of types (i.e. orbits under action of the symmetry group Aut T of a mosaic 7') of vertices, tiles and edges, respectively. Call a mosaic vertex-homogeneous, if any two vertices with congruent stars belong to the same orbit of vertices. Call a mosaic tilehomogeneous, if any two congruent tiles belong to the same orbit of tiles. Call a mosaic edge-homogeneous (or strongly edge-homogeneous), if their edge figures (weak edge figures) belong to the same orbit of edges. An edge figure is an edge together with all edges, which meet it, and a weak edge figure is an edge with its two incident tiles. The 165 mosaics from [Chav89] include following classifications of mosaics: 0

135 vertex-homogeneous (and 20 with 83

Y

= 2), found in [Krot69],

84

0

0 0 0

Scale Isometric Polytopal Graphs

[Krot7Oa], [Krot70b]; 22 tile-homogeneous (and 13 with t = 2), found in [DbLa81]; 22 strongly edge-homogeneous, found in [Chav84]; all 11, 20, 61 mosaics with 21 = 1,2,3; all 3, 13, 26 mosaics with t = 1,2,3; and all 4, 4, 10 mosaics with e = 1 ,2 ,3 .

(Apropos, in Tables 1, 2 of [Chav89] should be 26, 27, (instead of 25, 26, respectively) for the number of mosaics with t = 3.) All 58 mosaics amongst above 165, such that T or T* is embeddable, are given in Table 9.1 in the lexicographic order with respect to their vector (21, t , e). The pictures of those 58 mosaics are given, in the same order, in this chapter. Representatives of the orbits of vertices are indicated there by larger black circles. On the right hand side of Table 9.1 the vertex-, tile-, For edge-, strongly edge-homogeneity (if any) of T is given by signs each mosaic, its symmetry group Aut T is also given, using the standard crystallographic notation. Remind that the mirror image of the tiling T cannot be superimposed on the original (i.e. we have two enantiomorphic forms of T ) if and only if neither “m”, nor “g” is contained in above notation of Aut T . Remark that for any mosaic T , the embeddability of T or T* into 2, or $Znimplies that n is divisible by 3 (or by 2) if Aut T contains a 3-axis (or a 4-axis) of rotation, i.e. if Aut T is one of the groups p6m, p6,p31m, p3m1, p3 (or p4m, p4g,p4, respectively). It is interesting that for the mosaics of Table 9.1 we have:

+.

(1) Nr.4,17,31,37,41 (all mosaics T with avertex (3.6.3.6)) have T* -+ 2, and vice versa; (2) Nr.7, 15, 21, 23, 30, 32, 44, 47, 49, 54, 55, 57, 58 (all T with a vertex (32.4.3.4)) have T + iZ4 or T -+$ 2 6 (except Nr.58, containing also a vertex (34.6)) and all 6 mosaics T , embeddable into $24, are amongst them; (3) Nr.11, 13, 22, 25, 28, 48, 52, 53, 56, 58 (all T with a vertex (34.6))have T + $25 or T 4 $26,and all 7 mosaics, embeddable into $25,are amongst them.

The following groups of mosaics in Table 9.1 have the same face-vector: 14,18; 21,23; 27,33,34,40; 29,38; 31,41; 35,43; 36,42; 50,51; in each of eight cases, except of the 2-nd and the 8-th, the embeddability is the same. Table 9.1 contains 41 (from 135) vertex-homogeneous, 18 (from 22) tile-

Plane tilings

85

homogeneous and 15 (from 22) strongly edge-homogeneous mosaics. Also it contains: 0

0

all 11 mosaics with v = 1, 12 (from 20) mosaics with v = 2 and 26 (from 61) mosaics with w = 3; all 3 mosaics with t = 1, 11 (from 13) mosaics with t = 2 and 15 (from 26) mosaics with t = 3; all 4 mosaics with e = 1, all 4 mosaics with e = 2 and 6 (from 10) mosaics with e = 3.

Table 9.1 does not contain only the following 3 mosaics with homogeneity (3’.6’;3.6.3.6), (3.4.3.12;3.12’), (3.4.6.4;4.6.12) with (v, t , e) = (2,2,3), (2,3,3),(2,4,4), respectively. It does not contain also the 2 mosaics with t = 2: the one (3’.6’;3.6.3.6) above and the second (3’.6’; 3.6.3.6; 63)1 with (v,t , e) = (3,2,4) and homogeneity +, +, +, -. The embeddings given in Table 9.1 are taken from [DeSt96], [DeSt97] and [DeSt99].

+,+,+,+:

86

Scale Isometric Polytopal Graphs Table 9.1 58 mosaics T with embeddable skeleton of T or T*

The pictures of 58 mosaics of Table 9.1 are given below in the same order.

Plane tilings

56 57 58

9.2

(34.6;32.62;63;63;63) (3’.4.3.4; 32.62; 3.42.6;3.4.6.4;S3) (34.6;33.42;32.4.3.4; 32.62:3.42.6:3.4.6.4)

87

pmg p3ml

$25

-

$26

-

5,3,7 5,6,8

-,-,-,+,-,+,-

cmm

$25

-

6,9,13

+,-,+,-

Other special plane tilings

Embedding of other interesting plane partitions (by any polygons) was considered in [DeSt97]. For instance, a zonotopal Penrose tiling of the plane by two golden rhombi (or its analogue in the 3-space, by two golden rhombohedra) is embedded into Z5 (respectively, into 26). An embeddability of the Penrose tiling into Z5 (a part of it is drawn on Figure 9.7 b)) is seen on Figure 9.7 a), where its five zone are shown. The Robinson subdivision of above Penrose zototopal tiling and a 10gonal Tubingen triangulation (see both on Figure 9.8 a) and b) ) are not 5-gonal: the five vertices violating a 5-gonal inequality are marked on a separated graph on seven vertices. This graph is an isometric subgraph of both these triangulations (see Figure 9.8 c). The three vertices marked by small circles are taken with sign and the two vertices marked by small squares are taken with sign -. It is interesting that the Voronoi partition for the system of vertices of above Penrose tiling is not 5-gonal, but all found by us 5-vertex sets,

+,

88

Scale Isometric Polytopal Graphs

Fig. 9.1 Examples of mosaics, embeddable into i 2 3 : (36), (3.4.6.4)and (33.42)

violating a 5-gonal inequality, have diameter greater than 17. This Voronoi tiling is dual to the Delaunay triangulation, coming from Penrose tiling by addition of short diagonals on all rhombi, such that all obtained triangles are acute. (Recall that there are two mutually dual partitions of an n-space corresponding t o any discrete system of points in this space; they are called Delaunay and Voronoi partitions, respectively. We consider these partitions for the system of vertices of above Penrose tiling.) The Voronoi partition consists of 5-, 6-, 7-gons of 3, 2, 2 types, respectively. An existence of 5 points violating a 5-gonal inequality comes from the presence of pentagons] since the skeleton of any normal partition of the plane without 3-, 4-and 5-gons, is embeddable (see [DeStOOb],Theorem 3 ) . The following tilings are not 5-gonal (see [Wellgl], pages 104, 89, and also Figure 9.9 a) and b) below): a Durer tiling (by regular pentagons and rhombi) and a tiling by Greek crosses (combinatorially equivalent to

Plane tilings

89

(44) with two new vertices on each edge). In fact, the fragment of Durer tiling, depicted on Figure 9.9 a), admits unique extension t o a tiling of the plane by congruent pentagons and rhombi. In this fragment we added 32nd pentagon, with respect of the fragment given in [WellSl], page 104, since that original fragment is embeddable into f H45 (45 being the perimeter of this fragment). Also not 5-gonal the pinwheel tiling by the right triangles with edge lengths 1, 2 and & (see [Radi94]; this tiling is not edge-to-edge, but we consider it as edge-to-edge tiling by 3- and 4-gons). Let Cham(T) denote the chamfered T, i.e. the plane tiling obtained from mosaic T by putting prisms on all its faces, followed by the removal of all original edges. Then Cham(63) = (63), Cham(36) is not 5-gonal and the zonotopal tiling Cham(44) is embedded into 2 4 ; see three stylized ancient tilings, which are combinatorially equivalent to Cham(44) on Figure 9.10 below. The tiling Cham(44) is dual t o (44), considered as an infinite chess board, with pyramids on all black squares. (44) provides unique (combinatorial type of) normal partition of Euclidean plane by even-gons, having only even degrees of vertices. There are none such partitions of 3-sphere and an infinity of them of the hyperbolic plane, all embeddable into 2,. Finally, the graph of a part of some embeddable T or T * ,bounded by a simple circuit of length n. and containing Ic closed zones of interior edges, is an isometric subgraph of H k + $ , if all faces are even-sided, and of i H k + , , otherwise.

9.3

Face-regular bifaced plane tilings

All face-regular bifaced plane tiling of Euclidean plane were found in [Deza02]. Vertices of these tilings have the same degree Ic, and there are only two combinatorial types of faces (say, a- and b-gons); moreover, any a-gon (respectively, any b-gon) have the same number t , (respectively, t b ) of adjacent a-gons (respectively, b-gons). This implies that each a-gon is adjacent to a - t, b-gons and each b-gon is adjacent to b - t b a-gons. All embeddable ones amongst them are the three Archimedean tilings (4.8’), (3’.4.3.4), (33.42) (i.e. Nr.6-8 in Table 9.1, embeddable into 2 4 , $ 2 4 , $ 2 3 , respectively) and the following tilings A, B and continuums D, C of tilings (Nr.3’, 1 3 and ~ continuums Nr.33 and Nr.29 in notation of [Deza02]), which are embedded into i23, iZ8, iZ4, i25, respectively.

90

Scale Isometric Polytopal Graphs

The tiling A is the regular tiling (63) truncated on a “half” of its vertices, such that exactly one end of any edge is truncated. The tiling B is the Archimedean tiling (4.8’), in which a “half” of 8-gons is cut in two hexagons by a new vertical edge, while any other 8-gon is cut in two hexagons by a new horizontal edge; any two adjacent 8-gons are cut differently. The tiling C is the continuum of all tilings, obtained from the Archimedean tiling (33,4’) by taking, instead of fixed horizontal row of squares, any other (infinite in both directions) sequence of adjacent squares, going %p” and/or “right” arbitrary; all tiling then shifted accordingly. The continuum D comes by all the following decorations of the Archimedean tiling (4.82), considered combinatorially as the tiling of the plane by parallel horizontal zones (infinite in both left and right direction). Each zone consists of (alternated) 4- and 8-gons, such that their edges of adjacency are parallel and opposite in each 4- or 8-gon. Now decorate each zone by diagonals, cutting each 4-gOn in two 3-gons or each 8-gon in two 5-gons, such that all diagonals have the same direction: either South-West to North-East, or North-West to South-East. So, we get a continuum of such decorations of the (4.S2). The parameters (k;a, b; ta,t b ) of the seven above mentioned embeddable types of face-regular tilings are as follows: (3;4,8;0,4), (5;3,4;1,0), (5;3,4;2,2), (3;3,9;0,6), (3;4,7;0,5), (5;3,4;2,2), (4;3,5;1,3), respectively. The first three of them (the Archimedean ones) occur also in real crystal structures: they are depicted on Figures 7.20, 6.51 and 6.50 of [OkHy96] as nets, representing the paracelsian BaAlzSizOs, u3si2 and FezAlB’, respectively.

Plane tilings

91

(3. 6 . 3. 6)

(3.4.6.4)

132.4. 3. 4)

II

(4.6.12)

Fig. 9.2

(3'.6)

Mosaics 1-11 of Table 9.1

Scale Isometric Polytopal Graphs

92

(3'. 6:32.62)

(36:

32.4.3.4)

(33. 4 ' : 4"),

(36; 33.49,

(3. 42.6:3.6.3.61,

(3'. 42; 3.4.6.4)

(33.4 ' ; 3'.4.3.412

(33.42;3?4.3,4),

Fig. 9 . 3 Mosaics 12-23 of Table 9.1

Plane tilings

(3', 6: 32.62;63)

93

13.Q2. 6 : 3. 4. 6. 4; a4)

136; 33.42; 4",

(36;3486;3'. 6'12

(33, 42; 44: 4",

(36;33.42; P . 4 . 3 , 4)

(3.4'. 6;3.6.3,6: 4'&

(33, 41; 3"& 3.4: 4')

(36:33.4'; 4 0 2

(36;33.42; 4'i3

Fig. 9.4 Mosaics 24-35 of Table 9.1

(36;33.42; 33. 421,

Scale Isometric Polytopal Graphs

94

(3.4’6; 3.63.6;3.6.3.6),

8

3

1

4

w

(3 :3 .4 ;4 1,

(3.4’.6;3.6.3.6;44),

I Z 3 t i l

13 . 4 ; 3 .4 ;4

(33.42;33. 4*; 2.4.3.4)

)2

(36; 9;3t42r,

1

2

2

(3 .4 ;3 .4.3.4; 3’.4.3.4)

Fig. 9.5 Mosaics 36-47of Table 9.1

Plane tilings

95

(36;32.62;63;67,

(36;3*.6';6'; 63)2

(3.6; 3*.6';63;63)

(3@; 3742;3=*4.3.4; 4')

f3'; 3'.4.3.4; 3.4'.6; 3.4.6.4)

d.4.3.4; 3'6': 3.42.6;3.4.6.4;6')

(3'~;3~.4'; 3l.4.3.4;3'.6'; 3.4l.6;3.4.6.4)

Fig. 9.6 Mosaics 48-58 of Table 9.1

96

Scale Isometric Polytopal Graphs

Fig. 9.7 Penrose rhombic tiling: a) 5 zones, b) a fragment

Fig. 9.8 a) Robinson subdivision of Penrose rhombic tiling, b) Tiibingen triangulation, c) their not 5-gonal isometric subgraph

Plane tilings

Fig. 9.9 Fragments of: a) a Durer tiiling, b) a tiling by Greek croses

Fig. 9.10 Three ancient tilings, depicting Cham(4*)

97

This page intentionally left blank

Chapter 10

Uniform Partitions of 3-space and Relatives

Recall that a uniform polyhedron is the same as a semi-regular polyhedron. A normal partition of 3-space is called uniform partition if all its facets (cells) are uniform polyhedra and group of symmetry is vertex-transitive. There are exactly 28 uniform partitions of 3-space. A short history of this result follows. In 1905 Andreini in [Andr05] proposed, as a complete list, 25 such partitions. But one of them (13’, in his notation) turns out to be not uniform; it seems, that Coxeter [Coxe54], page 334, was the first who realized it. Also Andreini missed partitions 25-28 (in our numeration given below). Till recent years, mathematical literature was abundant with incomplete lists of those partitions. See, for example, [Crit70], [Will721 and [Pear781 (all of them do not contain partitions 24-28). The first, who published the complete list, was Grunbaum in [Grun94]. But he wrote there that, after obtaining the list, he realized that the manuscript [John911 already contained all 28 partitions. We also obtained all the 28 partitions independently, but only in 1996. The results presented in this chapter are from [DeStOOa]. All embeddable partitions in this chapter turn out to be 11-rigid and SO, having scale one or two. Those embeddings were obtained by constructing a complete system of alternated zones; see chapter 1 and [CDG97], [DeSt96], [DeSt97], [DeSt98]. It turns out also that all non-embeddable partitions, considered in this chapter, are, moreover, not 5-gonal. Remind that De(T) and V o ( T )are the Delaunay and the Voronoi partitions of 3-space associated with given set of points T . By an abuse of language, we will use the same notation for the graph, i.e. the skeleton of a partition. Remind also that P* is the partition dual to the partition P ; it should not be confounded with the same notation for dual lattice.

99

Scale Isometric Polytopal Graphs

100

10.1

28 uniform partitions

In Tables 10.1, 10.2 of the 28 partitions, the meaning of the columns is as follows: 1: the number, which we give to the partition; 2 and 3: its numbers in [AndrO5] (if any) and in [Griin94]; 4: a characterization (if any) of the partition; 5: tiles of the partition and the corresponding number of them in the Delaunay star; 5*: tiles of its dual; 6 and 6*: embeddability (if any) of the partition and of its dual. The special notations for the tiles given in the Tables 10.1, 10.2 are as follows: Cbt and Rcbt for Archimedean cuboctahedron and rhombicuboctahedron; RhDo, twisted RhDo and RhDo-v3 for Catalan rhombic dodecahedron, for its twist and for RhDo with deleted vertex of degree three; B D S * for dual snub disphenoid. Remarks to Tables 10.1, 10.2:

(1) The partition 15* is only one embeddable into 2, (in fact, with scale two). (2) All partitions, embeddable with scale one, are, except of 25*, zonohedral. The Voronoi tile of 25* is not centrally-symmetric. It will be interesting to find a normal tiling of 3-space, embeddable with scale 1, such that each tile is centrally-symmetric; such a non-normal tiling is given in [Sht080]: see item 35 in Table 10.3 below. (3) An embedding of tiles is necessary, but not sufficient, for embedding of whole tiling; for example, 26* and 27* are non-embeddable, while their tiles are embeddable into H4 and ~ H s respectively. , In fact, all dual uniform partitions P* in Tables 10.1, 10.2, except of 24*, have no non-embeddable tiles. Amongst all eleven non-embeddable uniform partitions only items 11, 15, 24 and 26 have only embeddable tiles. The same is true for tilings 30, 33 and 32*, 33*, 34*, 46* of Table 10.3. (4) Amongst all 28 partitions only items 1, 2, 5, 6, 8 have the same surrounding of edges: polygons (4.4.4.4), (4.6.6), (3.3.3.3), (3.3.6.6), (3.3.4). (5) Each of partitions 8 and 24 is the Delaunay partition of a lattice complex (i.e. bi-lattice, in which the environments of all points are identical,

Table 10.1 Embedding of uniform partitions and their duals: partitions 1-14 - - 5" 6' 1 2 3 4 5 of dual dual tiles Nr . - - "13 8 73 22 De(Z3), Po 1 1 z3

2

3

28

3

4

11

4

5

26

5 6 7 8

2 13 14 15

1 6 8 7

9 10

11 12 13

22 6 8 12 11

27 24 18 17 13

14

11'

14

-- -

V o ( A ; = bcc), sodalite De(A2 x Z ) high-pressure Si Vo(A2 x Z ) B in AlBz De(A3 = fcc), Cu Laves ph. MgCuz boride CaB6 De( J-complex) perovskite ( A B X 3 ) zeolite rho De(4.8' x Z ) De(3.6.3.6 x Z ) De(34.6 x Z ) ~ e (.4' 3 x~ boride FezAZBZ De(3'.4.3.4 x Z ) , silicide U3Siz

z),

a3

Prism3

12

Prisms

z4

Prism6

6

Prism3

f24

---

RhDo 73

z4 z4

Pyr4

Prisms,tr(Cbt) Prisms, y3 Prisms, Prisms Prisms, Prism6 Prisms, 7 3

2,2 42 4,4 8,2 6,4

Prism3 ,73

6,4

P3

P 3

R

a3

kR

Prism3 73

z4

s. rn

Prisms Prisms Prisms

-

Table 10.2 Embedding of uniform partitions and their duals: partitions 15-28

-1 2 Nr. -

3 -

4

19

De(3.122 x Z)

5' of dual N Prism3

18 20

25 21

zeolit Linde A

N

18 19 20 21

17 16 21 9

9 5 10 16

oxifloride Ag708F boride UBl2 De(3.4.6.4 x Z)

22

10

23

De(4.6.12 x Z)

23

19

20

selenide Pd17Se15

-

2 3

De( hcp), Zn De(elong.As), MoS2 De(elong.hcp), TiP silicide ThSi2 De(e1ongated 27)

twRhDo RhDo-t~a RhDo-t~s BDS' Prism5

15

7

16 17

2' 24 25 26 27 28 -

4 12 15 -

-N

-

-

a3

- 6 6' emb. - dual

pz

29

3

a3

fl

BPyrs BPyr3 Pyr4

f 27

73

f z4

Prisms

z 7

PYT4

f z4 ZS

& f

z 4

Uniform partitions of 3-space and relatives

103

except, possibly, for an orientation): J-complex and the hcp; the tile of Vo(J-complex) has form of jackstone (it explains the term ”J-complex”) and it is combinatorially equivalent to /33. (6) Partitions 1, 3, 5 are the Delaunay partitions of lattices Z3, A2 x 2 , A3 = fcc. The partitions 2 and 4 are the Voronoi partitions of lattices A: = bcc and A2 x 2. Items 10, 11, 12, 13, 14, 15, 21, 22 are the Delaunay prismatic partitions over eight Archimedean partitions of the plane; the embeddability of them and of their duals is the same as in Tables 4.1, 4.2, but the dimension increases by one. (7) In Chemistry, partitions 1, 5, 24 occur, for example, as metals polonium Po, copper Cu, zinc Zn; partitions 4, 7, 13, 20 as borides AlB2, CaBs, FezAlBz, UB12; partitions 9 and 16 as zeolites rho and Linde A; partitions 3 and 14, 27 as high-pressure Si and silicides U3Si2, ThSi2. Finally, partitions 2, 6 (known also as Foppl partition), 8, 19, 23, 25, 26 occur as sodalite Na4A13Si3012Cl , Laves phase MgCu2, perovskit (ABXs), AgTOgF, Pd17Se15, MoS2, T i p . Nice pictures of all those structures and chemical details can be found in chapters 6 and 7 of [OkHy96]. (8) The ratios of tiles in the partition are as follows: 1:l for 6,7,8, 10 8:l for 12

3:2:1for 21, 22, 25,26

10.2

2:l for 5, 11, 13, 14,24, 28 2:l:lfor 17, 19,20 3:3:1:1 for 23.

3:l for 9 3:l:l for 16, 18

Other special partitions

In Table 10.3 we group some other relevant partitions. Here L5 denotes a 3-dimensional lattice of the 5-th Fedorov’s type (i.e. by the Voronoi polyhedron) and El Do denotes its Voronoi polyhedron, called elongated dodecahedron. Remaining four lattices appear in Tables 10.1, 10.2 as Nr.l=De(&) = Vo(Z3), Nr.5=De(As), Nr.2=Vo(A;), Nr.S=De(Az x ZI), Nr.4=Vo(Az x 21). Remark that De(L5) and De(A2 x 21) coincide as graphs, but differ as partitions. By the notation De(Ke1vin) below we denote any Kelvin packing by a3 and ,& (in proportion 2:1), which is proper, i.e. different from the lattice A3 = fcc and the bi-lattice hcp. Each proper Kelvin partition, as well as the partition 13’ in [Andr05] (given as 46 in Table 10.3, which Andreini wrongly gave as a uniform one), have exactly two vertex figures. The Voronoi tiles of the tiling 46 are two rhombohedra: a rhombohedron (i.e.

Scale Isometric Polytopal Graphs

104

29 30 31 32 33 34

35 36 37 38 39 40

41 42 43 44 45 46 -

Table 10.3 Embedding of some other partitions De(L5) De(D-complex) De (Kelvin) De(Griinbaum) De(e1ong. Kelvin) De(e1ong. Griinbaum) P(S1) P(S2) P(S3) A-19 A-20, n even A-20, n odd A-22 A-23 II --type I-type chess-type A-13’

a3,

PY7-4

a3,

P3

a3, 0 3

Prisms a 3 , P 3 , Prisms Prisms, 7 3

ElDo triakis t r a3 RhDo, tw RhDo Prisms, B D S RhD0-v~ Prisms N

R, twisted R

the cube contracted along a diagonal), say, R, and twisted R; both are equivalent to 7 3 . The same is true for each Griinbaum partition; see items 32-34 of Table 10.3. In fact, call a normal partition of the 3-space into Platonic and Archimedean polyhedra, almost-uniform if the group of symmetry is not vertex-transitive but all vertex figures are congruent. Griinbaum [Griin94] gave two infinite classes of such partitions and indicated that he do not know other examples. In our terms, they called elongated proper Kelvin and elongated proper Griinbaum partitions. Kelvin and Griinbaum partitions are defined uniquely by an infinite binary sequence characterizing the way how layers follow each other. In Kelvin partition, the layers of a3 and p3 follow each other in two different ways (say, a and b) while in Grunbaum partition the layers of Prism3 follow each other in parallel or perpendicular mutual disposition of heights. Unproper Kelvin partitions give uniform partitions 5 and 24 for sequences ...aaa ... (or ...bbb...) and ...ababab..., respectively. Proper Kelvin and Grunbaum partitions are not almost-uniform; there are even oo-uniform ones (take a non-periodic sequence). Consider now elongations of those partitions, i.e. we add alternatively

Uniform partitions of 3-space and relatives

105

the layers of Prisms for Kelvin and of cubes for Griinbaum partitions. Remark that RoDo - v (the Voronoi tile of partitions 25, 26, 33) can be seen as a half of RoDo cut in two, and that twRoDo is obtained from RoDo by a twist (a turn by 90') of two halves.The Voronoi tiles for proper Kelvin partition 31 are both RoDo and twRoDo, while only one of them remains for two unproper cases 5, 24. Similarly, the Voronoi tile of 34 (a special 5-prism) can be seen as a half of Prisms cut in two, and B D S * can be seen as twisted Prisms in similar way. The Voronoi tiles for proper Grunbaum partition 32 are both Prisms and BDS*, while only one of them remains for two unproper cases 3, 27. Besides of two unproper cases 25, 26 (elongation of uniform 5, 24) which are uniform, we have a continuum of proper elongated Kelvin partitions (denoted 33 in Table 4), which are almost-uniform. Amongst them there is a countable number of periodic partitions corresponding to periodic ( a ,b)sequences. Remaining continuum consists of aperiodic tilings of 3-space by as, p 3 , Prisms with very simple rule: each has unique Delaunay star consisting of 6 Prisms (put together in order to form a 6-prism), 3 a3 and 3 /33 (put alternatively on 6 triangles subdividing the hexagon) and one a3 filling remaining space in the star. Each b in the ( a ,b)-sequence, defining such tiling, corresponds to the twist interchanging 3 a3 and 3 p 3 above (i.e. to the turn of the configuration of 4 a3, 3 P3 by 60"). Similar situation occurs for elongated Grunbaum partitions. Besides two uniform unproper cases 13, 28 (elongation of uniform 3, 27), we have a continuum of proper elongated Grunbaum partitions (denoted 34 in Table 4) which are almost-uniform. The aperiodic (a, b)-sequences give a continuum of aperiodic tilings by Prisms, 7 3 with similar simple rule: unique Delaunay star consisting of 4 7 3 (put together in order to form a 4-prism), 4 Prism3 put on them and 2 Prism3 filling remaining space in the star. Each b in (a,b)-sequence, defining the tiling, corresponds to a turn of all configuration of 6 Prism3 by 90°.

A D-complex is the diamond bi-lattice; triakis tr(a3) has Pyr3 on each its triangular faces. Partitions 29 and 30 from Table 10.3 are both vertextransitive, but they have some non-Archimedean tiles: Pyr4 for Nr.29 and a non-regular polyhedron, having the same combinatorial type with P 3 , for Nr.30. The partitions 35,36,37 of Table 10.3 are just all three non-normalizable tilings of 3-space by a convex parallelohedron, which were found in [Shto80] (see Theorem 11.3 below). The polyhedra denoted by 5'1, 5'2 and 5'3 are

106

Scale Isometric Polytopal Graphs

centrally symmetric 10-hedra obtained by a decoration of the paralellopiped. S1 is equivalent to /33 truncated on two opposite vertices. P*(Si)for i = 1 , 2 , 3 are different partitions of 3-space by non-convex bodies, but they have the same skeleton, which is not 5-gonal. We will denote here non-compact uniform partitions, introduced in subsections 19,20, 22, 23 of [Andr05], by A-19, A-20, A-22, A-23, respectively, and put them in Table 10.3 as Nr’s 38, 40, 41, 42. Denote by Prism,, APrism, and C, x PZ the m-sided prism, co-sided antiprism and the cylinder on C,, respectively. A-19 is obtained by putting Prism, on S2 and so, its skeleton is 22. We add, as item 39, the partition, which differs from item 38 only by other disposition of some infinite prism under net S2, i.e. perpendicular to those above it. A-20 is obtained by putting the cylinders on 62, A-22 by putting APrism, on (36) and A-23 by putting Prism, and APrism, on (33.42). In subsection 20’ [Andr05] mentions also the partition into two halfspaces separated by some of ten Archimedean (and one degenerated) nets, i.e. uniform plane partitions. We can also take two parallel nets (say, T ) and fill the space between them by usual prisms (so, the skeleton will be direct product of the graph of T and Kz) or, for T = 62 or (33.42), by a combination of usual and infinite prisms. Similar uniform partitions are obtained if we will take an infinity of parallel nets T . The partitions 43, 44, 45 of Table 10.3 differ only by the disposition of cubes and cylinders. In 43 the layers of cylinders stay parallel (/(-type);in 44 they are perpendicular t o the cylinders of each previous layer. In 45 we see 62 as the infinite chess-board; cylinders stay on ”white” squares while piles of cubes stay on the ”black” ones. One can get other non-compact uniform partitions by a decoration of Prism, in 38, 39.

Chapter 11

Lattices, Bi-lattices and Tiles

Remind that V o ( L ) and D e ( L ) denote the skeletons of Voronoi partition and Delaunay partition for a lattice L . So, edges of these graphs are edges of the Voronoi parallelotope and of the Delaunay polytopes of L ; any minimal vector of L is an edge of D e ( L ) but, in general, not vice versa. We are interested whether the infinite graph G, where G = V o ( L ) or D e ( L ) ,either is embedded isometrically (or with doubled distances) into a 2, for some m 2 n, or not. We report here the results obtained in this direction for irreducible root lattices, for two generalizations of the diamond bi-lattice and for a 3-dimensional case. See [Voro1908],[RyBa79] and [CoS188] for notions in Lattice Theory. It turns out again that all cases of non-embedding, given in this chapter, came out by violation of a 5-gonal inequality.

11.1

Irreducible root lattices

Let us consider the irreducible root lattices, i.e. A,, D,, E6, E7,Eg. For small dimension n, one has: De(A2) = (36) 4 !j&, V o ( A 2 ) = (S3) t Z3 ([Asso81]) and, of course, DZ= 2 2 , A; = Aa, 0 3 = A3.

We have: (i) De(E,) is not 5-gonal for n = 6, 7, 8; (ii) for 72 2 3, W A , ) g n + 1 , Vo(A,) GS1, V o ( A i )+ 2, (where m = D e ( A i ) is not 5-gonal; (iii) for n 2 4, De(D,), Vo(D,), D e ( D i ) are not 5-gonal.

Theorem 11.1

-+

("i')),

+

For example, De(D4) is not embeddable (contrary t o Proposition 2 (b) of 107

Scale Isometric Polytopal Graphs

108

[Asso81]): take 5 points such that a = (O,O, 0, O), b = (1,1,0, O), z = (1,0,1,O), y = (1,0, -1, O), z = (0,1,0,1)

forming a not 5-gonal isometric subgraph K5 - K3. In fact, (z, y) is not an edge, since the middle point of the segment [z, y] is the center of the square ( a , z ,c, y), where c = (2,0,0,0), with edges ( a , z ) , (z,c), (c, y), (y, a) from the graph De(D4). Now, De(D4) is a metric subspace of De(D,) for n 2 5. Remark also, that we have isometric embedding of 2, into De(D2,) and of 2, into D e ( A 3 ) . 11.2

The case of dimension 3

Now we consider five types (depending on their Voronoi polyhedron) of 3-dimensional lattices, obtained by Fedorov [Fedo1885]. Besides of 2 3 , A3 = fcc and A: = bcc, there are two other types of lattices having a 6-prism and an elongated dodecahedron as the Voronoi polyhedron. Let us take A2 x 21 and, say, L5 as representatives of the lattices of these two types. Remind that De(A3), De(L5) coincide as graphs, but the partitions of R3 (for which they are skeletons) are different. Theorem 11.2 We have: (2) De(A2 x 21) $ 2 4 , Vo(A2 x 21)--+ 24; ---f

(iz) ~ e ( ~-+5 i )~

4 V,

O ( L ~+) z5.

So, the Delaunay partition of the general lattice A: is unique nonembeddable one amongst D e ( L ) , V o ( L ) for the five Voronoi types of 3dimensional lattices. In R3, the combinatorial type of a parallelohedron P determines the combinatorial type of the corresponding tiling by P ; also the type of a dual partition is determined by the type of its star (i.e. the configuration around a vertex). For normal partitions, we have five types of parallelohedra and five dual types of partitions (whose skeletons are of four types, this was already in [Fedo1885]);their embeddings are described in the theorem above. In [Sht080], all three types of convex parallelohedra for essentially nonnormal (i.e. non-normalizable) partitions of R3 were found (see Table 10.3 above). Denote these parallelohedra by 5’1, 5’2, 5’3; and denote by P(Si), P*(Si)the tiling by Si and the dual partition for i=l, 2, 3. All Si(z=l,2, 3)

Lattices, bi-lattices and tiles

109

are centrally-symmetric 10-hedrons obtained by decoration of a rectangular parallelepiped; their p-vectors are (p4=10), (p4=6, p6=4), (p4=4, p6=4, p ~ = 2 ) ,respectively. SI = 7 3 7 3 is (combinatorially) 0 3 truncated in two opposite vertices; SZ and S3 have 2-valent vertices. All P*(Si) have the same combinatorial type of the skeleton; they are partitions of R3 by non-convex bodies.

+

Theorem 11.3

For i P*(Si)is not 5-gonal.

= 1,

2, 3, we have Si

-+

H3+i,

P(S,) --+ Zz+i and

The two most interesting lattice complexes in 3-space are bi-lattices Jcomplex and D-complex (D-complex is called also diamond or tetrahedral packing and denoted by 0,').

We have: (i) De(D-complex) -+ i Z 5 , but Vo(D-complex), De(J-complex), Vo(Jcomplex) are not 5-gonal; ( t i ) any Kelvin packing K by a 3 and p3 (except A S , but including the bi-lattice hcp) has not 5-gonal D e ( K ) , V o ( K ) .

Theorem 11.4

Amongst the packings of 3-space, considered above, the tilings De(Z3), De(A2 x Zl), V o ( A 2 x Zl), D e ( A 3 ) , V o ( A : ) , De(J-complex), De(hcp) are uniform partitions 1, 3, 4 , 5, 2, 8 , 24 from Tables 10.1, 10.2. Consider now the following two bi-lattices generalizing a D-complex:

D,f := D, U ( d

+ Dn ),

where the new point d is the center of the greatest Delaunay polytope, and

A,f := A, U ( a + An), where the new point a is the center of a regular n-simplex, which is a Delaunay polytope of A,, see [CSSS]. D,f is a lattice if and only if n is even; D: = 2 2 , D4f = 2 4 , DZ = &. A: is always a bi-lattice; it is obtained from A, by the above centering of its smallest Delaunay polytope, the regular n-simplex an. The centering of all Delaunay polytopes of A, will give A;. Remind that D e ( A $ ) = V o ( A 2 ) = ( S 3 ) -+ 2 3 , V O ( A = ~ )(36) -+ fz3, A: = DZ. Theorem 11.5

W e have:

(i) D e ( D $ ) n 2 5;

$25,

-+

V o ( D i ) is not 5-gona1, De(D;) is not 5-gonal for

Scale Isometric Polytopal Graphs

110

(ii) D e ( A $ ) -+ iZn+z for n 2 3 All above results are obtained by techniques given in [CDG97] and [DeSt96]. For example, not 5-gonality of De(AE), n 2 3, is given by 5 points: u = ( O , O , O , O , . . . , O ) , b = (1,1,1,0,.. . , O ) , z = (1,0,0,0,... ,O ) , y = (0,1,0,0,... , 0 ) , 2 = (0,0,1,0,. . . )0)

in the Selling-reduced basis of the lattice; the points a, x, x f y , b are vertices of a face of a Delaunay simplex. 11.3 Dicings

Let us consider a family of equi-spaced parallel hyperplanes that cuts R" into slabs of equal thickness. If we take n such hyperplane families that are independent, we obtain Rn diced into equal parallelepipeds with the vertices forming an n-dimensional lattice. In general, a dicing 2) is an arrangement of hyperplanes formed by families of equi-spaced parallel hyperplanes that satisfies the following properties: (i) amongst the families there are n independent ones, (ii) through each vertex of the dicing there is one hyperplane from each family. The condition (i) ensures that the cells of D are polytopes. The condition (ii) implies that the vertex-set L ( D ) of a dicing D is a lattice and the vertex-set of any sub-dicing (satisfying (i)) coincides with L(D). The lattice L ( D ) is called a dicing lattice. The partition of R", which is cut by hyperplanes of a dicing D , is the Delaunay partition of the dicing lattice L ( D ) . The main property of a dicing lattice is the following (see [Erda98]):

the Voronoi polytope of a lattice i s a zonotope i f and only i f the lattice is a dicing lattice. Since the skeleton of a zonotope Z, of diameter m is embeddable into H m l the skeleton of the Voronoi partition of any dicing lattice is embeddable into 2, for the same m. Our question is: do there exist, amongst non-zonotopal centrally symmetric polytopes with embeddable skeleton, ones, which are parallelohedra (i.e. tile the space by translation) or, more precisely, Voronoi polytopes of

Lattices, bi-lattices and tiles

111

lattices? If answer is yes, then the problem is, whether the corresponding Voronoi partition is embeddable into some 2, (remind that embeddable RhDev3 is the tile of Voronoi partitions Nr.25*, 26* from Tables 10.1, 10.2, amongst which only Nr.25* is embeddable) and gives, perhaps, an infinite analog of a non-realizable oriented matroid (see chapter 14). If answer is no, then we obtain a new characterization of dicing lattices as such lattices, whose Voronoi polytope has the skeleton embeddable into H , for some m. The case of embeddability of Delaunay partition of a dicing lattice is more complicated. At first glance, it seems that the Delaunay partition formed by m families of hyperplanes should be embeddable into 2,. But this is not always so. For example, the graph of Delaunay partition of the dicing lattice A:, n 2 3, is non-embeddable.

11.4 Polytopal tiles of lattice partitions Here the ambient discrete set of points is a point lattice,

Voronoi polytopes Recall that a partition of n-space is called primitive if each vertex of the partition belongs exactly to n 1 polytopes (tiles) of the partition. Otherwise, the partition is non-primitive. A polytope (tile) determining a primitive or non-primitive partition is called primitive or non-primitive, respectively. So, there are primitive and non-primitive Voronoi polytopes. In each dimension n 2 2, amongst all primitive Voronoi n-polytopes, there is only one, namely n-permutahedron, which is a xonotope. This ( n l)!-vertex zonotope is the Voronoi polytope of the lattice An*; it embeds into H n+l ( 2 1' For n = 2, the Voronoi polytopes (the non-primitive rectangles and primitive centrally symmetric hexagons) both are zonotopes and have the skeletons c 4 = H2 and cf3-+ H3. For n = 3, all five Voronoi polytopes are eonotopes (primitive truncated octahedron and four non-primitive ones: cube, Prisms, rhombic dodecahedron, elongated dodecahedron) and so, their skeletons are embeddable with scale one into H , (for m = 6 , 3 , 4 , 4 , 5 ,respectively). For n = 4, there are three primitive Voronoi polytopes. In 1937 Delaunay enumerated 2(primitive)+49=51 Voronoi n-polytopes. They are given in [Delo37]; in 1968 Shtogrin found the last one (this Nr.52 has 24 facets, which are 8-hedra of two types: 18 of one type and 6 of the other one).

+

+

112

Scale Isometric Polytopal Graphs

Amongst above 52 4-polytopes, 17 are zonotopes (Nr.1 and 3-19); they are embedded into H , for m = 10, 9, 8, 8, 7, 7, 7, 7, 6, 6, 6, 5, 5, 6, 5, 4, 9, respectively. We checked that all others are not 5-gonal; moreover, only Nr.33 (unique non-zonotope with bipartite skeleton), Nr.45, Nr.48, Nr.50, Nr.51 (the regular 24-cell) and Nr.52 have only 5-gonal 3-faces. The skeleton of an i-face is not, in general, an isometric subgraph of the skeleton of a convex n-polytope (for example, a hexagon is not isometric face in a &pyramid), but it is so, if the polytope is a parallelohedron. Two lattices are said to be of the same L-type, if their Voronoi (and so, Delaunay) partitions are affinely equivalent. Ryshkov and Baranovskii found in [RyBa76] 221 distinct general (i.e. corresponding, in the cone of positive semi-definite quadratic forms, to domains of maximal dimension) L-types of 5-dimensional lattices. Each general L-type determines a primitive Voronoi polytope. Engel [Enge98], using a computer, found 222 distinct primitive Voronoi 5-polytopes. Using those results, the L-type, which was missed in [RyBa76], was explicitely given in [EnGr02]. Engel [Enge98] found also that there are exactly 179.377 Voronoi 5-polytopes; 80 amongst them are non-primitive ones, which are zonotopes. Note that it is a routine work to enumerate all Voronoi n-polytopes, which are zonotopes: there is a bijection between such Voronoi n-polytopes and non-isomorphic unimodular matroids of rank n. This is similar t o that all n-zonotopes are in one-to-one correspondence with realizable oriented matroids of rank n (see chapter 14).

Delaunay polytopes Now we consider Delaunay polytopes of small dimension and some operations on Delaunay polytopes. For n = 2, the Delaunay polytopes (triangles with acute angles and rectangles) have the skeletons C3 -+ i H 3 and C4 = Hz. For n = 3, skeletons of all five Delaunay polytopes are also el-graphs: 7 3 = H3, a3 = i H 3 , ,B3 3 iH4, Pyr, --t iH4, Prism3 4 i H 5 . All 19 types of Delaunay 4-polytopes are given in [ErRy87]. We get the following proposition, listing all embeddable ones amongst them, by direct check; the Nr.2, 1 5 i 5 16 (only in this chapter) and the letters A, B, C below are notation from [ErRy87]. Kononenko in 1997 computed that there are exactly 138 Delaunay 5polytopes and Dutour in 2002 found all 6241 Delaunay 6-polytopes. Proposition 11.1 (i) N r . 1 6 ~ = 4 a1 x

73

= H4;

Lattices, bi-lattices and tiles

113

(ii) P --+ aH4 for the following polytopes P: Nr.2=Pyr(Pyr4) with G(Nr.2) = K z , ~ , ~B=Pyr(,&) ,J, with G ( B ) = K2,2,2,1,

C=BPyr(P3) = ,& = 3H4; (iii) P -+ for the following polyhedra P: Nr,l=Pyr(a3) = 0 4 , Nr.3=Pyr(Prisms), Nr.5, Nr. 7=01 x 0 3 = Pris m( a s ) , Nr.9, Nr.13 with G(Nr. 13) = T ( 5 )= J ( 6 , 2 ) ; (iv) P -+ ~ H for s the following polyhedra P: Nr.lO= 0 2 x 0 2 , Nr.ll=cul x Pyr4 = Prisrn(Pyr4), Nr.15= a1 x b3 = Prism(P3), A with G ( A ) = Kg (the cyclic 4-polytope); (v) P -+ iH7 for P = Nr.14 = a1 x Prism3 = Prism(Prism3); (va) the following polyhedra P are not 5-gonal: Nr.4, Nr,6=BPyr(Prism3), Nr.8=Pyr(y3), Nr.l2=BPyr(ys). It is well known that the direct product P x P' of Delaunay polytopes P and P' is a Delaunay polytope, and G ( P x P') = G ( P ) x G(P'). Also, for every Delaunay polytope P there is a pyramid Pyr(P) and (if P is centrally symmetric) a bipyramid BPyr(P),which are Delaunay polytopes (see [DeGr93]). The direct product construction preserves el-ness of Delaunay polytopes. For example, G ( P x p ' ) -+ !jH,+,/ if G ( P ) i i H m and G(P') + Hm,. But the pyramid and bipyramid constructions can produce not 5-gonal Delaunay polytopes from those with Cl-skeletons. Consider, for example, the following Delaunay polytopes: a,, ,&, T,, ?yn 1 ( n 2 5), Ambo(a,) ( n 2 4), the Johnson n-polytope PJ with G(PJ) = J ( n f 1 , k ) ( 3 5 k 5 L(n+1)/2]), a,-l x a,-i for n 2 3; Pris ms, Pyrq. All of them have C1-skeletons: Ambo(a,) 3 iH,+1, PJ -+ iHn+i, Pris ms -+ iH5, P y r 4 -+ iH4. The pyramid and bipyramid constructions produce from them ti-polytopes in the following cases: Pyrm(a,), pyrm(P,),B p w m( f i n ) , pyrm( P ~ r 4 ) . Additionally, we have the following el-embeddings: 0

Pyr2(Prismg) i H 5 , Pyr(Ambo(a,)) $&+I, Pyr(an-l x C Y , - ~ ) -+ ?jHzn. -+

-+

0

The inclusions (i), (ii) below show that the skeletons of the mentioned there polytopes are not 5-gonal, and therefore, they are not el-graphs:

114

Scale Isometric Polytopal Graphs

(i) the graph Kg - K3 is an isometric subgraph of the skeletons of the following eight types of polytopes:

0 0

0

0

Pyr(-Yn), BPyr(~n), Pyr2(Ambo(a,)), n 2 6, Pyr(PJ) (since Kl,k is an isometric subgraph of J ( n Pyr( ;&), 2 6, Pyr2(a,-1 x an-l), BPyr(Ambo(a,)), n 2 6, even, BPyr(;H,), n 2 6 even;

+ 1,k)),

(ii) the graph Ks - Pz - P3 is an isometric subgraph of the skeleton of BPyr(Prism3). Finally, the following skeletons are hypermetric non-ll (see Proposition 4.4 of [DeGr93]): 0 0 0 0

0

Pyr($-Ys), Pyr2($-Y5), Pyr2(Ambo(as)), Pyr3(Ambo(a4)), ~ y r ~ ( ~ r i s m~ sy )r ,~ ( ~ r i s m 3 ) .

Chapter 12

Small Polyhedra

12.1

Polyhedra w i t h at most seven faces

In this chapter Nr.i mean only Nr.1-10, 11-44 of Figures 12.1, 12.2. The Cl-status of all ten polyhedra with a t most six faces and their duals is such that they are either el-embeddable, or not 5-gonal. The el-embeddable ones are 4 i H 4 : a3 N a:, Pyr4 N Pyrz, BPyr3 = Prism:, 7; = p3, + i H 5 : PYI-5 N Pyr:, Prism3 N BPyr;, (2-truncated q ) * one , with the skeleton K6 - P5 of the dual (Nr.43 in Proposition 12.1 below and on Figure 12.2); + : 7 3 , 2-truncated a3. Remaining are: self-dual one with the skeleton K6 - Pa, one with the skeleton K3x2 - e of the dual, its dual (Nr.44 in Proposition 12.1 and on Figure 12.2) and one with the skeleton K6 - P5 of the dual. P r o p o s i t i o n 12.1 Amongst all 34 polyhedra (Nr.11-44 on Figure 12.2) with seven faces and their duals, we have -+ i H 5 : 20*, 21*, 29*, 35, 36*, 38*, 39 N 39*, 43; -+ i H 6 : 12*, 14*, 16*, 17*, 18, 19 Y 19*; + i H 7 : 12, 20, 23; hypermetric non-el : 13*; not 7-gonal: 32*, 37*, and not 5-gonal: all others (including 40* = 42 and self-dual ones 34, 41). R e m a r k 12.1 (i) Amongst above C1-polyhedra only 7 3 is bipartite and only three are not el-rigid: a3 = a: -+ i H 3 , i H 4 , BPyr3 -+ i H 4 (two ways) and 39 N 39* -+ i H 5 , i H 6 . All simple ones amongst above 10+34 115

Scale Isometric Polytopal Graphs

116

2

3

7

8

4

9

5

10

Fig. 12.1 All polyhedra with at most s i x faces

polyhedra with a t most seven faces are: a3, Prism3 =1-truncated (213, 2truncated (213, 7 3 and Nr.11, 12 (3-truncated (213), 13, 20 (1-truncated y3), 23=Prisms. (ii) 20, amongst of all 44 polyhedra with at most seven faces, are combinatorially equivalent to a space-filler: all ten, except P y r s , with a t most six faces (including all three not 5-gonal) and Nr.12, 15, 18, 20, 22, 23, 28, 30, 36, 43, 44 (amongst them Nr.12, 18, 20, 23, 43 are el-graphs). 12.2

Simple polyhedra with at most eight faces

Proposition 12.2 Amongst all 27 cubic graphs with up to ten vertices, 19 are not 5-gonal, iH6 while remaining eight are el-graphs: non-polytopal Petersen graph and 7 simple polyhedra: i-truncated a3 4 iHd+i for 0 5 i 5 3, i-truncated 7 3 + iHs+i for i = 0 , l and P r i s m s + i H 7 . --f

Proposition 12.3 Amongst the skeletons of all 1Q simple polyhedra with eight faces (i.e. with 12 vertices) four are el-graphs (all are embedded into ~ H s ) P: r i s m g , dual snub disphenoid BDS*, Diirer’s octahedron and 7 3 , truncated o n two adjacent vertices. Duals of first two are not 5-gonal and of last two + ;Ha. Q-truncated a3 and 7 3 , truncated on two vertices at distance 2, are not 5gonal; their duals -+ i H 7 . The five polyhedra from Figure 12.3 are respectively, not 5-, 5-, 7-, 7-, 9-gonal; the skeletons of their duals are respectively, embeddable into i H 8 , i H 7 , i H 7 , i H 6 , not 5-gonal. Remaining three polyhedra and their duals are not 5-gonal. One of the three above polyhedra (a 3-truncated P r i s m 3 ) is the smallest

Small polyhedra

16

11

117

IS

19

20

21

22

21

24

2s

26

21

28

29

10

31

32

11

34

36

31

IS

19

41

42

43

3s

44

Fig. 12.2 All polyhedra with seven faces

simple polyhedron with p = ( 3 , 1 , l , p 6 , 0 , .. .); such polyhedra exist (see page 271 in [Grun67]) if and only if p6 is odd, other than one. The Diirer’s octahedron above is 73, truncated on two opposite vertices; it is called so, because it appears in Diirer’s painting ”Melancolia”, 1514, staying on a triangular face.

Remark 12.2 (i) The skeletons of all simple l1-polyhedra with f 5 8 faces (there are eleven of them) are embedded into $ H f ; all of them, except of ag, are el-rigid and 7 3 -+ H3, Prisms + H4. (ii) the polyhedron in the center of Figure 12.3 and one of three not 5-gonal simple octahedra, having not 5-gonal duals, are the two smallest 3-regular graphs with trivial group of automorphism. (iii) amongst all eleven simple polyhedra with only k-gons, k 5 5, as faces (duals of all eight convex deltahedra, 1-truncated a3, 1-truncated y3

118

Scale Isometric Polytopul Graphs

Fig. 12.3 Some simple octahedra

and Durer’s octahedron) the skeletons of only two (duals of 3-augmented Prisms and of 2-capped APrism4) are not el-graphs.

Chapter 13

Bifaced Polyhedra

Denote by ( k ;a, b;pa,pb) and call bifaced any k-valent polyhedron, whose faces are only pa a-gons and pb b-gons, where 3 <_ a < b and pa > 0, p b 2 0. Any bifaced polyhedron ( k ; a ,b;p,,pb) with n vertices has k n / 2 = (spa bpb)/2 edges and satisfies Euler relation n - k: (pa pb) = 2 , i.e. n = 2(pa +pb - 2 ) / ( k - 2 ) . Equating above two expressions for n, we obtain

+

+

p a ( 2 k - U(k - 2 ) ) +pb(2k - b ( k - 2 ) ) = 4k.

+

(13.1)

This equality implies a < 2 k / ( k - 2). In fact, the inequality 2 k 5 a(k - 2) implies the inequality 2 k < b ( k - 2). Both these inequalities and 13.1 contradict to k 2 3. Hence only possible ( k ,a) are (3,5), (3,4), (3,3), (4,3), (513). Now, since b > a, we have b = 2 k / ( k - 2 ) only for ( k ,b) = (3,6), (4,4), and b < 2 k / ( k - 2 ) only for six simple (i.e. with k = 3 ) polyhedra with (a,b ) = (3,4),(3,5), (4,5). If pb = 0, then the above five possible values of ( k ,a ) give (combinatorially) Platonic polyhedra Do, 7 3 , a3, ,&, ICO,respectively. If pb = 1, then bifaced polyhedra do not exist. If pb = 2, then there are no bifaced polyhedra with ( k , a ) = ( 3 , 3 ) , and for ( k , a ) = (3,4), (3,5), (4,3), (5,3) polyhedra are as follows: Prismb, Barrel6 (the dual of 2-capped APrismb), APrismb and snub APrismb. The last polyhedron consists of the following three circuits: outer ( ~ 1 .~. ,. ~ b ) middle , (yl, y;, . . , ,Yb, yi), and inner ( ~ 1 ,. . . , Z b ) , where xi N yi, y:, yi+l and zi N yi, y i for all i = 1 , . . . ,b ordered cyclically. This polyhedron is called snub APrismb since for b = 4 it is (combinatorially) the well known regular-faced polyhedron snub APrism4, which is 5-gonal, but not 7-gonal. Note that snub A P r i s m s is sometimes called snub tetrahedron; it has the same skeleton as Ica, but its symmetry is T .

YL-~,

119

Scale Isometric Polytopal Graphs

120

Barrelb := (2 - APrismb)* (see chapter 4) is an analog of Prismb, where the layer of 4-gons is replaced by two layers of 5-gons; it has 46 vertices. Proposition 13.1 We have: (a) Prismb -+ $Hb+2 (moreover, H ( b + 2 ) / 2 for even b), Prism; 3H4, 3H4, not 5-gonal for b = 3,4, and b 2 5, respectively; (ii) APTiSmb * iHb+i, APrismg -+ H3, not 5-gonal for b 2 4; (aii) Barrel3 =Diirer’s octahedron i H 8 , Barrel: -+ 3H6, Barrela = Do iHlo, Barrel; ---$ 4H6, Barrel4 is not 5-gonal (see Figure 6.4 d)), Barrel; is hypemetric non-+

.--)

--f

-+

11,

for b > 5 both, Barrelb and its dual, are not 5-gonal; $=Hlo, (iv) snub APrism3 = Ico 4 i H 6 , its dual snub APrisms is not 7-gonal, its dual is not 5-gonal, for b 1 5 both, snub APrismb and its dual, are not 5-gonal. .--)

From now on we consider mainly bifaced polyhedra with pb 2: 3. Consider first sample bifaced polyhedra, i.e. the case of k = 3. For b < 6 there are only six such polyhedra: the Durer’s octahedron (i.e. 7 3 truncated on two opposite vertices) and five dual deltahedra (Prisms and duals of BPyrs, of snub disphenoid, of 3-augmented Prisms, of 2capped APrism4). Moreover, there are only eleven simple polyhedra with pi = p3 p4 pa: six above polyhedra, remaining three dual deltahedra (as, 7 3 , Dodecahedron) and 1-truncated 7 3 , 2-truncated a3, having ( p 3 , p 4 , p 5 ) = (1,3,3), (2,2,2), respectively. The ti-status of all these polyhedra and their duals is known (see above). Simple bifaced n-vertex polyhedra with b = 6 will be denoted as a,: 3,, 4,, 5, (fullerenes), for a = 3,4,5, respectively. Their parameter p a does not depend on n: p 3 = 4, p4 = 6, p5 = 12. The polyhedra a,, a = 3,4,5, will be considered below as well as the interesting case of (4; 3 , 4 ; p 3 , p 4 ) , having also constant p3 = 8. We denote last polyhedra by oc, and call them octahedrites.

+ +

13.1

Goldberg’s medial polyhedra

In 1935, Goldberg [Gold351introduced the fullerenes (in a slightly more general setting). He mentioned that Kirkman found, in 1882, over 80 (amongst all 89) isomers of F44. For n # 18,22, he defined a medial polyhedron with

Bifaced polyhedra

121

n vertices as a simple polyhedron, for which all faces are 16 - $j-gons or 17 - S j - g o n s . For 20 5 n # 22, medial polyhedra are the fullerenes. Therefore, we extend the notation Fn to any medial polyhedron with n vertices. Figure 13.1 reproduces those medial polyhedra, the last nine being F20(Ih)r F24(D6d)r F26(D3h), F28(Td), F28(D2), F36(D3h)r F36(D6h), C60 ( I h ) and C80 ( I h ) (C80(1h)is called in [Gold351 chamfered dodecahedron). Medial polyhedra was introduced by Goldberg as putative best (isoperimetrically) approximation of a sphere within the class of polyhedra having given number f of faces. A medial polyhedron with f faces is a bifaced polyhedron (3; a = 16 b = a l ; p a , p b = f - p a ) ; it exists for any f 2 4, except for f = 11,13. For f = 4 , . . . , l o , 1 2 they are exactly dual of the eight convex deltahedra: a3, Prisms, Prism4 = ~3~ Prisms, dual snub disphenoid, dual 3-augmented Prisms, Barrel4 and Barrels = Do (see the case k = 3 of Table 13.1 below). The following two polyhedra given in Figure 13.2 are almost medial; we call them quasi-medial polyhedra with 18 and 22 vertices and denote them by F1;18(C2~) and fi22(C2u).F&(CzV)is the edge-coalesced icosahedron (see [Kinggl]) given in Figure 8.8. p22(C2w)is the one-edge truncated dodecahedron mentioned on page 274 in [SaMo97]. This polyhedron has ten pentagonal faces, which is the maximum number of faces among all simple polyhedra with 22 vertices. Both F 1 8 ( c 2 v ) and p ~ 2 ; 2 2 ( c 2and ~ ) their duals are not 5-gonal. Simple bifaced polyhedra with b > 6 were considered in [Malk7O]. Besides Euler’s relation (6 - a)p, = 12 ( b - 6)pb, we have:

y],

+

+

0

0 0

if a = 3, then b E {7,8,9,10}; if a = 4, b 3 0 (mod 8), then pb is even; if a = 5, b = 0 (mod l o ) , then pb is even.

Reference [Malk7O] asserts that above necessary conditions (for existence of such a polyhedron) are sufficient, with only a finite number of exceptions. Polyhedra (3; 3, b;p3,pb) with b < 6 are only Prisms and Durer’s octahedron; both are el-embeddable into $ I T 5 , ;IT*, respectively. The polyhedra (3; 3, b ; p S , p b ) with b = 6,8,10 are not 5-gonal, since they contain (triangles are isolated) isometric not 5-gonal subgraph consisting of a vertex surrounded by a triangle and two even-gons. Examples of el-graphs amongst their duals are three omni-capped Platonic solids ( 1 ~ 3,&, , Ico. Consider now non-simple bifaced polyhedra. There are only two classes of non-simple bifaced polyhedra, namely, (4; 3, b; p 3 , p b ) and (5; 3, b;p3,pb).

Scale Isometric Polytopal Graphs

122

For b 5 6, all possible (k;a,b) are (4;3,6), (4;3,5), (4;3,4), (5;3,6), (5;3,5), (5;3,4). In each of those cases there is an infinity of such polyhedra. Namely, we have: (5; 3,4;p3,p4) exists for any p4 > 1, [Fisc75]; (4;3,4;p3,p4) exists for anyp4 > 1, [Griin67], p.282; an infinity of examples is constructed for each of remaining four cases in [Griin96] (all of them, except tetrakis truncated octahedron (4;3,6;24,8), are not C1-embeddable). Remind, that if P is a polyhedron ( k ; a ,b;p,,pb) with n vertices, then Ambo(P) is a 4-valent polyhedron with pa a-faces, pb b-faces and, in addition, n k-faces. So, Ambo(P) is bifaced if and only if k E {a, b}. All possible cases for Ambo(P) and its parameters are as follows: (i) k = a = 3,4,5, (ii) Ambo(P) = (3,4)2, if P = (3,4),, (iii) Ambo(P) = (4; 3,5; 20 5 ~ 5 ~ 1 25p5) if P = (5; 3,5;p3,p5). (In (iii), we use 13.1 giving p3 = 20 5 ~ 5 . ) If we consider only P with b 5 6, they we have in addition to (ii) and (iii): (i.1) Ambo(P) = (3,4)9 if P = Prism3 = (3; 3,4; 2,3), (i.2) Ambo(P) = (4; 3,5; 14,6) if P is the Diirer’s octahedron, (i.3) Ambo(P) = (4; 3,6; n 4, - 2) if P = 3,. Remark that cases (ii), (iii), (is) of the Ambo(P)-construction produce also an infinity of bifaced polyhedra with k = 4, a = 3 and b = 4,5,6. The dual of a bifaced polyhedron (k, a, b) has vertices of two valences a and b. We denote the numbers of vertices with these valences by 21, and vb. Self-dual polyhedron with p = (pa,pb), 3 5 a < b, exists, according to [Juco~O], if and only if pa = v a , a = a , b, a = 3 and pa = p3 = n - pb, pb = so, it is cy3, P y r b for pb = 0,1. For b = 4, the sub-case n G 1 (mod 4) is realized by k-elongated Py7-4 having p = (p3 = 4,p4 = 4k 1); so, all above polyhedra are embedded into a half-cube. But the polyhedra with b = 4 and n = 6 ,7 ,8 are not 5-gonal (the skeleton is K6 - p6 for n = 6). Also the gyrobifastigum (a regular-faced polyhedron) has p = (p3,p4) = 21 = (213, 214) = (4,4), but it is not self-dual; it and its dual are not 5-gonal. Another nice example of a bifaced polyhedron with two vertex-valences is the following chimera of cube and dodecahedron. It has p = (p4 = 6,p5 = 12) and v = (213 = 20,214 = 6); it is the fundamental polyhedron of the smallest known (by the volume) closed hyperbolic space (see [Week85]). Neither it, nor its dual with the skeleton K6 - K3 - Kz, are 5-gonal.

+

+ +

+

e.

+

Bifacaced polyhedra

123

Table 13.1 All k-valent polyhedra with only a-gonal and b-gonal faces, 3 5 a < b 5 6, p a > 0, pb > 0

Table 13.2 Known bifaced polyhedra with embeddable skeleton

k 3 3 3 3 3

3 3 3 3 3 4 4 4 4 4 4 4 4 5

5 -

13.2

Pa,Pb 2,6 4,4 bl2 68 6,12 6,12 12,3 12,lO 12,12 12,30 2b,2 8,4m 873 8,4 8,lO 8,lO 8,18 24,8 32,6 80.12

polyhedron Diirer’s octahedron dual snub disphenoid Prismb (incl. b = 3) tr(P3) Cham(r3 1 twisted Cham(y3) fullerene 526(03h) fullerene 540(Td) fullerene 544 (2’) Cham( Do) APraSmb 2-capped (C4 x pm+i)

Ambo(Prism3) with symmetry Dz 6-elong. of above 6-elong. of 2-(C4 x Pz) rhombicuboctahedron tetrakis tr(P3) snub 73 snub Do

Face-regular bifaced polyhedra

Examples of el-polyhedra amongst non-simple bifaced polyhedra are: rhombicuboctahedron=(4;3,4;8,18)+ iHlo, tetrakis truncated ,& = (4;3,6;24,8) -+ iH12, snub 7 3 = (5;3,4;32,6) -+ i H g , snub Do = (5;3,5;80,12)-+ and, amongst their duals, both Catalan zonohedra.

iffl5,

124

Scale Isometric Polytopal Graphs Table 13.3 Known bifaced polyhedra with embeddable skeleton of the dual polyhedron 1 ernbedd. into k- a,b Pa,Pb 3 Prisms I fH4 3,4 2,4

3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4

3,5 396 376 3,6 3,6 3,6 3,7 3,7 3,7 33 33 3,8 3,9 3,lO 533 5,6 5,6 3,4 3,4

2,6 4,4 4,6 4,6 4,12 4,16 6,6 8,12 8,12 8,6 12,12 12,12 16,12 20,12 12,4 12,8 12,20 8,6 8,4m

4

3,5 3.5

20,12 16,8

4 -

Durer’s octahedron tr(013 Charn(a3) twisted Cham(a3) 4- tr(Do) tr( omni-capped 013) 6- t4-n) 8- tr(Do) 8- tr(Do) tT(Y3) 12- t r ( D o ) 12- tr(Do) 16- tr(Do) tr(Do) fullerene 528(Td) fullerene 536(&h) 560 = tr(1co) cuboctahedron 2-(c4 X pm+l)= (C4 x Pm+z)* icosidodecahedron

Duals of above six Cl-polyhedra are not 5-gonal. Only three Archimedean polyhedra are not bifaced: rhombicosidodecahedron -+ Hg and two large zonohedra. The lists of known C1-polyhedra amongst bifaced polyhedra and their duals are given in Tables 13.2 and 13.3; they compiled from [DeGr99] and [Deza021. It turns out that all known bifaced C1-polyhedra (or having el-dual) are a- or b-face-regular. A polyhedron, having only a- or b-gonal faces, is called a-face-regular if each a-gonal face is adjacent to the same number ta of a-gonal faces; it called b-face-regular if each b-gonal face is adjacent to the same number t b of b-gonal faces. The classification of such bifaced polyhedra is addressed in [DeGrOl] and [BrDe99]. Remark that the polyhedron 2-capped(C4 x P,+I) is a-face-regular with ta=3 = 2; it is b-face-regular only if m = 1 , 2 (with tb=4 = 2 , 3 for m = 1 , 2 , respectively).

Remark 13.1 (i) Last column in Tables 13.2, 13.3 give, when relevant, above numbers t,, t b All face-regular (i.e. admitting both, ta and t b ) bifaced

Bifaced polyhedra

125

polyhedra of any degree k (see [Deza02])appear amongst polyhedra, given on those Tables. (ii) For all C1-polyhedra of Table 13.2 (except of Prisms, Durer’s octahedron and 2-capped C4 x P,+1) the dual polyhedra are not 5-gonal. (iii) Many of C1-polyhedra P from both Tables 13.2 and 13.3, are embedded into i H 2 d , where d is the diameter of P. But, for example, the diameter of dual truncated a3 is two and of dual truncated dodecahedron is four.

13.3 Constructions of bifaced polyhedra Consider some operations transforming a bifaced polyhedron P into another bifaced polyhedron. Let P have the parameters ( k ; a , b ; p a , p b ) .If b = 2k, then the dual of omnicapped P is called in [FoMa95] leapfrog of P. It has parameters ( 3 ; U , b ; p a , p b IV(P)I)and k l V ( P ) )vertices. If b = 2k = 6, then remind, that the chamfering of P (replace all edges by hexagons) has parameters ( 3 ;a , b;p,,pb ( E ( P ) I )and 4(V(P)Ivertices. All 5,, 4,, 3, with icosahedral, octahedral, tetrahedral symmetry, respectively, are characterized in [Gold37]. They have n = 20(a2 ab b2), 8(a2 ab b2), 4(a2 ab b 2 ) , respectively, for u 2 b 2 0 The cases b = 0 and a = b correspond to the full symmetry Ih, Oh, Td. The leapfrog (and chamfering) of Do, 7 3 , a3 correspond to the case a = b = 1 ( a = 2, b = 0, respectively); above leapfrogs are truncated ICO,p 3 , as, respectively. Clearly, each of classes of all 5,, 4,, 3, is closed under operations of leapfrog and chamfering. Let P , P’ be two Platonic polyhedra having ( k , l , n , f )and (k’ = k , l’, n’,f’),respectively, as size of faces, valence, the number of vertices and the number of faces. Consider the convex polyhedron P fP‘ obtained by adjoining a copy of P’ on each face of P. Then ( P fP’)* is a bifaced polyhedron with parameters (k;l’, l(1‘ - 1); f (n‘ - k),n). The case P’ = a3 corresponds to omnicapping of simplicia1 P. While, clearly, a3 zag, p 3 ia3 are C1-embeddable for 0 5 i 5 f,a3 ip3 for 2 5 i 5 4 and ,& + ip3 for 1 5 i 5 8 are not C1. Given a polyhedron P , let P Pyr, ( P Prismq, P APrism,) be the polyhedron defined by the join of new vertex to all vertices of a q-gonal face (the join of Prism,, APrism, to a q-gonal face, respectively). See Corollary 4.1 in chapter 4 about the cases when Pyr, +Prism, is embeddable. Remark that APrism, -+ $H,+1 but APrism, APrism,

+ +

+ +

+ +

+ +

+ +

+

+

+

+

+

+

+

Scale Isometric Polytopal G r a p h

126

is not 5-gonal. The golden dodecahedron of [HiPe89],i.e. Do with A P r i s m s on each of its 1 2 faces, is not 5-gonal. The embedding of the elongation P P r i s m , of P along an isometric m-gonal face, implies the following embedding. Let P be a polyhedron with a vertex v such that P - v -+ iH,. Then P , truncated on the vertex v, is embedded into fHm+2. For example, this truncation of P on two opposite caps is embedded into: $Hlo if P is ICO (i.e. 2-capped A P r i s m 5 ) ; i H g if P is 2-capped A P r i s m 4 (which is an extreme hypermetric); H4 if P is p 3 = A P r i s m 3 ; $H11 if P is 5& (i.e. if P is 2-capped A P r i s m 6 , which is not 5-gonal). Amongst 92 regular-faced polyhedra, 19 are elongated P (i.e. obtained from P by adjoining or inserting a prism), 27 are i-augmented P i.e. icappings of P. For example, pentakis of A P r i s m s and of Do are embeddable, pentakis of Pyrs and of P r i s m s are not 5-gonal, tetrakis of Prism3 and of A P r i s m 4 are hypermetrics non-Cl.

+

13.4

Polyhedra 3, and 4,

Recall, that we denote an n-vertex simple bifaced polyhedron with b = 6 by a,, a = 3,4,5. The equation 13.1 gives p, = i.e. p3 = 4, p4 = 6, p5 = 12. The embedding for 3n, 4, and their dual is presented below.

e,

Proposition 13.2

(i) Besides of the cube, all known C1-4, are: the Prism6, the truncated octahedron, the chamfered cube and the twisted chamfered cube. (ii) The octahedron is the unique C1-embeddable dual 4,. (iii) The tetrahedron is the unique C1-embeddable 3,. (iv) Besides of the tetrahedron, all known 41-3; are: the triakis tetrahedron 3F2 -+ f H7, the duals of the chamfered tetrahedron and the twisted one, iHlo that is, both 3T6 --t i H 8 , the 4-capped on disjoint facets Ico 318 and the dual of the leapfrog of the triakis tetrahedron 35,(Td) iH11. -+

--$

Proof. To prove that above polyhedra are not C1-embeddable1 we simply exhibit (see Figure 13.3) not 5-gonal configurations contained in their skeletons. The coeficients bi of the violated 5-gonal inequality are again, respectively, 0 f o r a black vertex, -1 f o r a square one, and 1 f o r a white 0 circle.

Bifaced polyhedra

127

Theorem 2 of [GrMo63] gives, that 3, exists for any n _= 0 (mod 4), except of n = 8, and provides complete description of their skeletons. Since 34 = a3 iH3, iH4, then it is not C1-rigid. The "would-be" 38 is 2-, but not 3-connected and it is also not 5-gonal. There are exactly N3(n) polyhedra 3, for 1 5 2 5 30, where N3(n) is given below: -+

2 (1 2 3 4 5 6 7 NJn)ll 0 1 2 1 2 2 2 16 17181920 2 1 2 2 N3(n)8 3 7 4 9 7 6

8 9 101112131415 4 3 3 2 7 3 4 5 232425 26 2728 29 30 4 1 4 6 7 812513

Theorem 3.4 in [Sah94] implies, that Clearly, is unique 3n with abutting triangles. So, any 3 , n > 4, is not 5-gonal, since it contains an not 5-gonal isometric subgraph, given on the left-hand side of Figure 13.3. We know six l-polyhedra 3*; a computation in [Duto02] showed that no others exist for n < 136. Except of 3 and the unique 312 = truncated 3, any 3n is a 4-vertex truncation of a simple polyhedron with 12–2p4 from the Euler equality and n – 8 vertices (so, In particular, 3n is 4-vertex truncation of a fullerene has four vertices of type (5,5,5) at pairwise if and only if this distance at least three; so, any pair of trianlges is separated by more than one hexagon. Such 5n-8 has either four isolated triples of pentagons, or two if and only if isolated clusters of six pentagons. For small values of n we have (see Figure 13.4; marked vertices indicate truncation): (1) exactly seven of 3, come as 4-vertex truncation of dual deltahedra: unique 312 from (13, both 316 (chamfered and twisted chamfered a3) from 73, the unique 320 from dual snub disphenoid, both 324 from dual 2-APrism4 and one (of two) 328 from Do. The second one 328 comes from a simple polyhedron with 12 faces, such that p = (p4,p5,p6) = (4,474). (2) exactly six 3, come as 4-vertex truncation of fullerenes 5,, 20 5 m 5 36: one 328 from 520, a 332 from 524, a 336 from 528(02), another 336 from 528(Td), a 340 from 532(D2), a 344 from 536(D2); each of these six fullerenes has a unique, up to a symmetry, set of four vertices at pairwise distance 2 3.

Scale Isometric Polytopal Graphs

128

Theorem 1 of [GrMo63] gives that 4, exists for any even n 2 8 except n = 10. Clearly, 4, is bipartite, and there is an infinity of centrally symmetric 4,. Hence it either --t H , or is not 5-gonal. For 4 6 6 30, there are N4(n) polyhedra 4,, where N4(n) is given below:

:

p 4 5 6 7 8 9 1011121314151617 N4(n)1 0 1 1 1 1 3 1 3 3 3 2 8 3 18192021222324252627282930 N4(1z) 7 7 7 5 14 6 12 12 13 10 23 12 19 Theorem 3.4 in [Sah94] implies that N4(n) = O(n3). The unique elpolyhedron among 4: is 4; = p 3 + ;H4, since other 4; contain the following not 5-gonal isometric 7-vertex subgraph: Ci1,,,.,6}with chords (1,3), (4,6) plus a new vertex connected with vertices 1,3,4,6. Clearly 48 = 73, 412 = Prism6, truncated p3 is 424 (one of three), two 432 are Cham(y3) and twisted Cham(y3) (see Figure 13.5). Those five polyhedra are all known el-4,. They are embedded into H3, H4, f&3, H7, H7,respectively. The first three are Voronoi polyhedra, Cham(y3) is a non space-filling zonohedron, twisted one is not centrally symmetric (it is only one amongst above five, which, in terms of next chapter, is not an equicut graph). A computation in [Duto02] showed that no others C1-embeddable 4, exist for n 5 96. Chamt(y3) is el only for t = 1. For n = 2 (mod 6), the dual of the column of octahedra p3 gives a 4,; for n > 8, it and its dual are not 5-gonal. Examples of 4, without abutting pairs of 4-gons are Chamt(y3) ( t 2 1) and duals of tetrakis cube, cuboctahedron, twisted cuboctahedron (i.e. the triangular ortobicupola Nr.47), gyro-elongated triangular bicupola and snub cube, having, respectively 8a2 ( a 2 2), 24, 32, 32, 44, 56 vertices. Last two are not 5-gonal. ”Dual tetrakis” above, means a truncation on six 4-valent vertices of the dual polyhedra. On the other hand, any 4, with each pair of 4-gons separated by at least three edges (for example, Chamt(y3), t 2 2) comes as &edge truncation (put 4-gons instead of edges) of a fullerene 5,-12. Hence such a 4, has no abutting pair of 4-gons and, moreover, the corresponding 5n-12 has six pairs of adjacent pentagons. Many 4, come as 6-edge truncation of 5, under weaker conditions: Cham(y3) from 520, tr(p3) from ~ 3 Also . truncated p3 is 6-(disjoint) edges truncation of 412 = P r is ms , Prism6 is 2-(disjoint) edges truncation of 48 = 73, 73 is 2-(disjoint) edges truncation of a3. Suitable 6-(disjoint) edges truncation of 524 (dual 2-APrism6) gives a 436 and so, on (see Figure 13.5).

9

Bifaced polyhedra

13.5

129

Polyhedra 5, (fullerenes) revisited

Theorem 1 of [GrMo63] gives that 5, exists for any even n 2 20 except n = 22. The polyhedra 5,, i.e. the bifaced polyhedra (3; 5,6; l2,p6), are called fdlerenes in Chemistry; see chapter 2. In fact, all 5, are the cases f =2 2 12 of medial polyhedra (cf. chapter 13.1). The number Ns(n) of polyhedra 5, is O(n9) from Theorem 3.4 in [Sah94] (based on a result from [Thur98]). All known el-embeddable 5, are Do = 520 --t 526 * $HI21 540(Td) ---t $H151 544(T) ---t i f f 1 6 and Cham(Do) = 580(Ih) --t $H22. The last one is the dual pentakis icosidodecahedron; its twisted version is not el-embeddable. All known e1-5: are ICO = 5a0 ---t $Her hexakis truncated a3 = 528(Td) $H7, hexakis A P r i s m i = 5&(D6h) -+ $Hs and pentakis Do = 5gO(Ih) * $Hlo. In fact, no other el- embeddable 5,, C1-5: exist for n < 60 and they are not expected for other n. All seven above fullerenes, such that it or its dual is el-embeddable, have the highest symmetry for its number of vertices and all, except the dual of 528(Td) of diameter 3, have the corresponding embedding into iH2,, where m is the diameter of the skeleton. The 528(Td) is also unique not antipodal amongst them. Some interesting classes of 5, were mentioned above in chapter 2:

+5

ifflo,

-+

and those (with four isolated triples of pentagons) coming from collapsing of four triangles in some 3,.

13.6

Polyhedra oc, (octahedrites)

Those are 4-valent bifaced polyhedra on n vertices with parameters (4;3,4;p3,p4). So, by 13.1, p3 = 8 and n = 6 +p4. Besides of 3,, 4,, 5,, it is the only case of bifaced polyhedra, for which pa is fixed for given (k,b). [Grun67], page 282, gives the existence of 0% for any n 2 6, except n = 7. Remark that dual octahedrites ocz are exactly the case d = 3 of almost simple cubical d-polytopes in terms of [BlB198]. Actually, [BlB198] characterizes those d-polytopes for d 1 4. It is not difficult t o enumerate all almost simple cubical 2-dimensional complexes; they are Pz x P,, for any finite n and Pz x Z+,P 2 x 2,i.e. infinite in one or both directions

130

Scale Isometric Polytopal Graphs

(respectively) paths of squares and the cube with deleted vertex or edge. But the variety of such d-polytopes becomes too rich for the exceptional case d = 3. The numbers N,,(n) of polyhedra 0% for 6 5 n 5 30 are given below: 6 7 8 9 1 0 1 1 1 2 1 3 1415 16 17 18 n N o , ( n ) 1 0 1 1 2 1 5 2 8 5 1 2 8 25 19 20 21 22 23 24 25 26 27 28 29 30 n N0,(n)113 30 23 51 33 76 51 109 78 144 106 218 Clearly, Ambo(o%) is a ocZn. Another operation, namely, inserting into some o k , a ring of m 4-gons along a simple straight-ahead circuit (defined in chapter l ) , produces a o%+,; let us call it m-elongation, see iH2t+4 is, m chapter 1. For example, 2-Prismi=BPyr;+' = OC4t+6 times iterated, 4-elongation of 2-Prism4. Iterated 3-elongations of ,&, 4elongations of APrism4 and of 2-Prism4 give 0% for n = 6 3m, 8 4m, 10 4m with any natural m. First examples of octahedrites 0% are: /33 = OC6 + iH4, APrism4 = ocg --+ +H5, Ambo(Prism3)=3-elongated P3 = ocg --+ t H 6 , 2-Prism4 = oclo + i H 6 ; the second oclo is also embedded into i H 6 . All but one of the polyhedra on Figure 13.6 are not 5-gonal: the 0~11,four polyhedra 0~12,(cuboctahedron=Ambo(,&)=4-elongated APrism4, twisted cuboctahedron = Nr.47, another two times 3-elongation of P3 and another 0 ~ 1 2 ) and amboAPrism4 = OC16. Now, rhombicuboctahedron OC24 + iH10 but its twisted version ("14th Archimedean solid") is not 5-gonal. Both these polyhedra are 8-elongations of the twisted Ambo(APrism4), which is a oc16 + iH8, and of Ambo(APrism4), which is not 5-gonal (see both smaller polyhedra on Figure 6.3). Above oc16 is also 6-elongation of 2Prism4; 6-elongation of the second oclo is another oc16, which is embedded into iHg also. Amongst the duals of above o k , all embeddable are zonohedra: (cuboctahedron)* + H4 and (2 - Prismi)*=Prism;+' --+ Ht+3, for any integer t 2 0. Apropos, (Ambo(Prism3)* = (ocg)* is the smallest convex polyhedron with odd number of faces, all of which are quadrilaterals; it is not 5-gonal. ---f

+

+

+

Bafaced polyhedra

131

Nets k r Seueral Medial Pabhedra

Iv

V

VI

VII

*

L I

4

4 - 1.3

5 - 1.3,I

6- 1.4.1

7 - 1.5. I

Vlll

IX

x

XI I

10-1.4 4.1

12- 1.5.5.1

I

t--r 8- 2.2.2.2

b

0- 3.3,3

xv

XVI - 1

XVI- 2

@ s

4

%

L

1

1

14-1.6,6.1

xx-1

'5-3.3.3.3.3

xx-2

2 0 - 1.6.6.6.I

16- 4[1.

4

5-2.2.[2.2.2.21.3.2

XXXll

XLll

2- 1.5.5.J.5,5.5.1 MICHAEL GOLDBERG,

MARCH 1%3

Fig. 13.1 Some GOLDBERG'S medial polyhedra

Scale Isometric Polytopal Graphs

132

Fig. 13.2 Quasi-medial polyhedra @m(Czu)and @ z z ( C z V )

I

Fig. 13.3 Not 5-gonal configurations in 3, and 4;

Bijaced polyhedra

a) would-be

133

38

e) 4-truncations of both

528

f ) 4-truncation of 53z(Oz)

g) 4-truncations of

540

Fig. 13.4 Some graphs 3 ,

134

Scale Isometric Polytopal Graphs

...~ ..........

,

b) Prisms

e) unique

414

f ) unique

i) twisted Cham(y3)

416

........... ,

c) truncated

g) unique

03

d) a 436 (as edge-truncation)

418

j) C h a 4 - d

Fig. 13.5 Some graphs 4,

h) a

420

Bifaced polyhedra

a) cuboctahedron

c) two other

135

b) twisted cuboctahedron

d) Ambo(APrism4)

OCIZ

e) twisted Ambo(APrzsm4) Fig. 13.6 Some ocn

f ) the ocll

This page intentionally left blank

Chapter 14

Special &graphs

14.1 E q u i c u t el-graphs

In the first half of this chapter we follow [DePaOl], where proofs of results below can be found. A graph G is an equicut graph if it admit an 11-embedding, such that the equality holds in the left-hand side of the inequality (1.2) of chapter 1, concerning the size s(dG) of this embedding. Below s(dG) means the size of such equicut embedding. This means that, for such a graph, every S in the equality (1.1) of chapter 1 corresponds to an equicut b ( S ) ,i.e. satisfy a s # 0 if and only if S partitions V into parts of size and [?Il where n = IVI. Remind that a connected graph is called 2-connected (or 2-vertexconnected) if it remains connected after deletion of any vertex. Lemma 14.1 A n equicut graph with at least four vertices is 2-connected. This lemma implies the following Corollary 14.1 For any equicut graph G with n 2 4 vertices, we have

with equality on the left-hand side if and only if G = Kn, and on the righthand side i f and only if G = C,. The condition n 2 4 is necessary in the statements above. Indeed, s(dp3) = 2 > s(dC3)= $. Note, that P 2 and P 3 are the only equicut trees. Also, W(C5)= 15 < W ( p { 1 2 3 4 5 2 } ) and S ( d c S )= < S ( d p { 1 2 3 4 5 2 ) ) , where

4

137

Scale Isometric Polytopal Graphs

138

P{123452)

denotes the circuit on 2,3,4,5 with an extra edge attached to the

vertex 2. Remark 14.1 G is an equicut graph if there is a realization with the If, instead of this or binary matrix F with the column sums condition, we asked that any row of F has exactly k l’s, then we obtain other special I1-graph. Namely, one which is embedded isometrically, up to scale A, into the Johnson graph J ( m , k ) . It was observed by Shpectorov, that such graphs can be recognized in polynomial time using the algorithm in [DeSh96], but we are not aware of any similar characterization of the equicut graphs. It is easy to see, that any graph G , which is embedded isometrically, up to scale A, into hypercube H,, is embedded also isometrically, up to scale A, into Johnson graph J(2m, m). In fact, let any vertex w of G be addressed by corresponding subset A , of a given m-set; then one can address v by the union of A, and the image of its complement in a bijection of the given m-set on some m-set, which is disjoint with given one. The columns “ J ( m , k)?” of Tables 4.1, 4.2 give all embeddings of Q into J ( m , k ) , where Q is anyone amongst Platonic polyhedra, semi-regular polyhedra or their duals.

[TI.

Call an equicut C1-graph an antipodal doubling if its realization in H , (i.e. the above (0,l)-matrix F ) has the form F =

(

AA ?),

where A

is f x m’ (0,l)-matrix, J , J’ are matrices consisting of 1’s only and 0 is n x (m - m’) matrix consisting of 0’s. If, moreover, the matrix A is a realization, with the same scale A, of a graph G’, then it is straightforward t o check, that J’ has A(d(G’) 1) - n columns, where d(G) is diameter of G. Note that Double Odd graph D02s+1 (see, for example, DO5 on Figure 14.1) with s 2 3 is an example of antipodal doubling with the matrix A not corresponding to the realization of a graph G’, for any decomposition of F into the above form.

+

Remark 14.2 An antipodal doubling is exactly an C1-graph, that admits an antipodal isomorphism, i.e. it has a central symmetry (for any vertex, there is exactly one other on the distance equal to the diameter) and the mapping of all vertices into their antipodes is an isomorphism. Antipodal extensions of arbitrary el-metrics was considered in [DeLa97],chapter 7.2.

In order to investigate, when one can construct an el-graph from an el-graph via the antipodal doubling (see Theorem 14.1 below), let us introduce the following definition. For a graph G = (V,E ) , define its diametral

Special e l -graphs

139

34

Fig. 14.1 Double Odd graph D02s+1with s = 2

doubling as the graph U G with the vertex-set V +U V - (where Vf and V are two copies of V) and the adjacency is as follows: ua is adjacent to v b if a = b and (u,z)) E E , or if a # b and dG(U,V) = d ( G ) , where a , b E {+, -}. T h e subgraphs of UG, induced o n Vf and V - , are isometric t o G if and only if

Lemma 14.2

~ G ( u , uI)2 + d G ( w l , w z ) f o r a n y u , v , w l , w z EV, satisfying d G ( u , w I ) = d G ( v , w z ) = d ( G ) . Lemma 14.3

(14.1)

L e t G satisfy the condition of above l e m m a . T h e n d o ~ ( u +V-) , =d(G)

+ 1- d G ( u ,w )

(14.2)

if and only if a n y geodesic in G lies o n a geodesic of length d ( G ) . Certain properties of G are inherited by DG.

Let G be a graph satisfying equations (14.1) and (24.2). T h e n U G satisfies d ( n G ) = d ( G ) 1, equations (14.1) and (14.2).

Lemma 14.4

+

Scale Isometric Polytopal Graphs

140

If d(G) = 2, then G satisfies (14.1). Moreover, G # K, satisfies (14.2), unless it has an edge (u,v) with G, = G,, where G, is the subgraph of G induced by the neighborhood of the vertex u. In particular, the strongly regular graphs, considered below, satisfy (14.1) and (14.2); note, that e l graphs form a rather small sub-family of strongly regular graphs. Not always the graph UG defines uniquely the graph G, from which it was constructed. It can be that UG' = OG for G # GI. See below for many examples of this situation. But the graphs G and G' are related by the following graph operation. The diametral switching of a graph G with respect to S c V is a graph G' that is obtained from G by retaining the edges that lie within ( S x S ) U ((V- S ) x (V - S ) ) and replacing the set of edges from S x (V - S ) with the set { (u, v) E S x (V - S ) : dG(u,v) = d(G)}. Note that Seidel switching is an operation, that coincides with the diametral switching for graphs of diameter two.

Theorem 14.1 Let G be an Cl-graph. Then CIG is an C1-graph if G satisfies (l4.l), (14.2) and S(dG)

+

(14.3)

5 d(G) 1.

Moreover, if UG is an el-graph, then it holds: (i) d(UG) = d(G) 1, OG satisfies equations (l4.l), (14.2) and (14.3) with equality,

+

59)

(ii) all Cl-realizations of OG are equicut of the form ( J A A with X(d(G)+ 1) - m columns, up to permutations of rows and columns, and taking complements of columns, where A is an el-realization of G with scale A.

Remark 14.3 K4 - P3, K4 - Pz,the Dynkin diagram E6 are examples of el-graphs satisfying (14.1), (14.3), but not (14.2). Afine Dynkin diagram fi6 is an example of a graph that does not satisfy (14.1) and (14.3), but does satisfy (14.2). Note that any graph G with diameter D(G) = 2 satisfies (14.1) and (14.2). Certainly, not all of them are C1-graphs, for instance, K2,3. Also not all C1-graphs of diameter two satisfy (14.3), for instance, K1,4. In general, for any el-graph G = (V, E ) with [Vl 2 4 one has

D(G) 5 S ( & ) 5 D ( G )

+ IVI - 3.

(14.4)

The equality a t the right-hand side of (14.4) holds if and only if G is a star, as can be seen by applying Theorem 1.1 of chapter 1.

Special

el -graphs

141

Theorem 14.1 generalizes the situation for the cocktail-party graph Knxa, considered in [DeLa97], chapter 7.4, to arbitrary C1-graphs. It implies, that the minimal scale of an el-embedding of OG equals the minimal A, such that the metric AdG is embedded isometrically into H , with m = A(D(G) 1). In particular case of G = K 4 a , Lemma 7.4.6 of [DeLa97] gives for such a minimal A, the inequality A 2 2a, with the equality if and only if there exists a Hadamard matrix of order 4a.

+

Now we list many examples in no particular order. An equicut elgraph is called a doubling if it is an antipodal doubling. Moreover, if it is obtained from a graph Go as in Theorem 14.1, we give such a representation G = UGo. All equicut graphs with at most six vertices are: Cn (2 5 n 5 6), Kn, (n = 4,5,6), P3, 4-wheel and the octahedron K3x2. Amongst these eleven graphs only Kn is not el-rigid and only C4, CSand K3x2 are doublings. The scale of the direct product G x G’ of two 11-graphs is the least common multiple of the scales of G and GI, and the size will be the sum of their sizes. Moreover, G x G’ is C1-rigid if and only if G and G’ are.

Lemma 14.5 If 11-graphs G, GI have even number of vertices each, then G x G’ is an equicut graph if and only if they are.

A Doob graph (the direct product of a number of copies of Shrikhande graph and a number of copies of K4 (see, for example, [BCN89], page 27) is an example of an equicut graph obtained via Lemma 14.5. It is a (non

!I-rigid and non-doubling) el-graph of scale two.

Embeddable distance-regular graphs. Here we again freely use notation from [BCN89]; also, a significant use is made of [KoSp94]. A graph of diameter d is called distance-transitive graph, if it is connected and admits a group of automorphisms, which is transitive, for any 1 5 i 5 d, on the set of all pairs of its vertices, being on the distance i. More general, a connected graph is called distance-regular graph, if it is regular and, given two vertices z and y, the number of vertices at distance i from z and at distance j from y depends only on the distance d(x,y). Any distance-regular graph of diameter two is called strongly regular graph. All hypermetric polytopal strongly regular graphs are: 0

(TZ

x n)-grids Kn x K,,

Scale Isometric Polytopal Graphs

142

0 0

0 0

triangular graphs T ( n )= J ( n , 2), the skeleton Knx2 of ,&, G(l21) = i H 5 and G(2al)=the Schlafli graph;

only the last one, the Schlafli graph, is not el-embeddable. Reference [KoolSO] proved that all finite distance-regular graphs, embeddable with scale one into an H , are the distance-transitive ones: Yrn, 0 0

CZ, and for odd m, Double Odd graphs DO,.

In [KoSp94] all el-embeddable distance-regular finite graphs are found. Moreover, the Petersen graph and the Shrikhande graph are both equicut graphs of scale two and size 3; both are el-rigid and are not doublings. The Double Odd graph D02,+1 is an equicut graph of scale one and size 2s 1. The halved cube H , is an equicut graph of scale two and size m. It is not L1-rigid only for m = 3,4; it is a doubling if and only if m is even. The Johnson graph J ( 2 s , s) is a non 11-rigid doubling of scale two and size

+

i

S.

Further, the following graphs are distance-regular equicut graphs. (1) Any Taylor el-graph: i H 6 , J ( 6 , 3 ) , C6, H3, icosahedron. They are all doublings of diameter three and size 3; they can be constructed using Theorem 14.1 above. (2) Any strongly regular I1-graph, except J(s,2) ( s 2 5) and any (s x s)grid H ( 2 , s ) with s odd. That is, C5, the Petersen graph, $H5, the Shrikhande graph, H , with m even, Ksx2. (3) Amongst distance-regular graphs G with diameter greater than two and p > 1: i H r n with m > 5, H ( m , d ) , J ( s , t ) with t > 2, icosahedron and Doob graphs. (4) All Coxeter L1-graphs except J ( s , t ) with t < :: J ( 2 s , s), icosahedron, dodecahedron, Ksx2, iH,, H,, C, ( s 2 5). (5) All cubic distance-regular el-graphs: K4, Petersen graph, H3, DO5, dodecahedron.

Also all amply-regular el-graphs with p > 1 are equicut graphs. Yet another example is given by the 12-vertex co-edge regular subgraph of the Clebsh graph i H 5 , (see [BCN89], chapter 3.11, page 104). It is an equicut

Special

graph of size

el -graphs

143

g, scale two, non-doubling.

Reference [Macp82] showed that any infinite distance-transitive graph G of finite degree arises in the following way: the vertices of G are pvalent vertices of T , two of them being adjacent if they lie at distance two in T , where T is an infinite tree, in which the vertices of the bipartite blocks have degrees p , q, respectively. (In other words, G is the halved subgraph of the infinite distance-biregular tree T . ) The graph induced by all neighbors of fixed vertex of G, is the disjoint union of p complete graphs Kq--l. It is easy t o see that, in general, G -+ iZ,. In the special case q = 2, it is just the infinite pregular tree and it is embedded into Z,, except the case p = q = 2, when it is the infinite path PZ -+ 21.

Some equicut graphs, which are doublings of el-graphs (see some in chapter 7.2 of [DeLa97]). (1) cz, = UP,. (2) Ksx2 = O K s . (3) H , = OH,-1. (4) J(2s, s) = 0 4 2 s - 1,s). (5) ;Hzs = 04H2,-1. (6) Prism2, = OC2, (7) APrism2,+1 = UC2s+1. (8) Do is the doubling of C{l,2,,,,,g} with an extra vertex connected to the vertices 3, 6 and 9 of the circle. (9) Ico is the doubling of a 5-wheel; as well, it is the doubling of the graph obtained from hexagon C11,2,,,,,6} by adding edges (2,4), (2,6) and (4,6). (10) 5(6,3) is the doubling of the Petersen graph, in addition to the 4th item above for s = 3. (11) is the doubling of the Shrikhande graph and of (4 x 4)-grid H2x4 (more precisely, of its realization in !jHs), in addition to the 5th item above for s = 3.

In the items 9, 10, 11, we have (diametral) switching-equivalent graphs G, such that DG is a Taylor el-graph; see the definition preceding Theorem 14.1. This situation, in general, is well-known. For instance, the Gosset graph (it is a Taylor graph, which is not an el-graph) can be obtained as the diametral doubling of one of five non-isomorphic, but switching-equivalent, graphs. For definitions and discussion of this situation in more general setting see, for example, [BCN89], pages 103-105.

Scale Isometric Polytopal Graphs

144

E qui c ut polytopes. The skeletons of many ”nice” polytopes are equicut graphs. Below we list several such examples. All five Platonic solids have equicut skeletons; all, except the tetrahedron as, are .!I-rigid. All except the cube 7 3 (of scale one) have scale two. The sizes for as, /Is, 7 3 , ICO and Do are 2, 3, 3 and 5, respectively. The skeleton of any zonotope is a doubling, and it has scale one; so, it is .!I-rigid.

4,

Amongst all el-embeddable semi-regular polyhedra, we have: (1) all zonohedra (i.e. 3-dimensional zonotopes) are as follows: the truncated octahedron, the truncated cuboctahedron, the truncated icosidodecahedron and P r i ~ m 2(s~ > 2) with sizes 6, 9, 15 and s 1, respectively; (2) all other doublings are as follows: the rhombicuboctahedron, the rhombicosidodecahedron and APrismz,+l (s > 1) with scale two and sizes 5, 8 and s 1, respectively; (3) all remaining equicut polytopes are: the snub cube, the snub dodecahedron and APrismz, (s > 1);all have scale two and sizes !, $ and s respectively; (4) the remaining Przsm2,+1 (s > 1) has scale two and size s :; it is not an equicut graph.

+

+

+ 3,

+

Amongst all Catalan (dual Archimedean) el-embeddable polyhedra we have: (1) all zonohedra are as follows: dual cuboctahedron and dual icosidodecahedron of sizes 4 and 6, respectively; (2) the only other doubling is dual truncated ICO of scale two and size 5; (3) all remaining cases (duals of tr(73), tr(Do), tr(a3) and Prisms) are non-equicut el-graphs of scale two and sizes 6, 13, $ and 2, respectively.

All Platonic, semi-regular and dual to semi-regular .!I-polyhedra are C1rigid, except the tetrahedron and the dual Prisms. All not equicut graphs amongst them (see the columns “cuts” in Tables 4.1, 4.2) are: Prism, for odd n and duals of four semi-regular polyhedra (Prisms and truncated ones of tetrahedron, cube, dodecahedron). Examples of regular-faced polyhedra (from the list of 92 polyhedra) with equicut skeletons (all have scale two) are: Nr.75 (biaugmented Prisms) of

Special

el -graphs

145

size 4 (a doubling) and two non-doublings: Nr.74 (augmented Prism6) of size 4 and Nr.83 (tridiminished Ico) of size 3. The regular C1-embeddable polytopes of dimension greater than three, have equicut skeletons. They are as follows: an,yn and ,On. There are just three semi-regular el-embeddable polytopes of dimension greater than three (see [DeSh96]). Two of them have equicut skeletons: aH5 and the snub 24-cell. The latter is a 4-dimensional semi-regular polytope with 96 vertices. The regular 4-polytope 600-cell can be obtained by capping its 24 icosahedral facets. Its skeleton has scale two and size six; it is a doubling. Three of the chamfered Platonic solids have C1-skeletons: Cham(y3) is a zonohedron of size 7, Cham(Do) has an equicut (non-doubling) skeleton of scale two and size 11, Cham(a3) has non-equicut C1-skeleton of scale two and size 4.

14.2

Scale one embedding

Remind first (see chapter 1) that a finite Cl-graph is embeddable with scale one if and only if it is bipartite and 5-gonal.

Small bipartite polyhedral graphs Amongst six bipartite polyhedral graphs with a t most nine faces, there are two embeddable ones, the cube 48 and the 412 = Prisms; both are zonohedra, embeddable in H3 and H4, respectively. Other four are the ocg, oc;, 414 and the not 5-gonal 12-vertex graph on Figure 14.2 a). Amongst five bipartite polyhedral graphs with ten faces and at most 13 vertices, there are two embeddable ones, a ocro and RhDo-v3 (see Figure 14.2 c) and d); they are also Nr.13 (for t=l) and 2 in Table 14.1. Other three are the second ocr0, the APrismg and the not 5-gonal 13-vertex graph on Figure 14.2 b). Both above embeddable graphs are embedded into H4, but only the graph on Figure 14.2 d) is not centrally symmetric. Remind that we allocate to polyhedra, presented only by their combinatorial type, the maximal possible symmetry. For example, the graph on Figure 14.2 c) and, in general, any polyhedron C4 x Pt+z, t 2 1 from Table 14.1 is seen as a centrally-symmetric one, but it is not zonotope, since it should have some trapezoidal faces in order to be realisable as a convex polyhedron. A non-convex realization of C4 x P3 (as two adjacent cubes) tiles the 3-space non-normally; see the partition Nr.35 in Table 10.3) and the graph

Scale Isometric Polytopal Graphs

146

of this tiling is embedded into Z 3 . Nr.15-16 of Table 14.1 are Voronoi t-polytopes for the lattices 2,and A,*;the polyhedra Nr.1, 3 and 4 are Voronoi polyhedra of the lattices A2 x 21, A3 and L5 (see chapter 11). Recall that Nr.2 of Table 14.1 (RhDo-ws, i.e. RhDo with a deleted simple vertex) is the tile of three Voronoi partitions from Tables 10.1, 10.2 and 10.3: Nr.25, which is embeddable into 24, and not 5-gonal ones Nr.26 and 33. Apropos, two 13-vertex graphs on Figure 14.2 b) and d), are exactly two smallest non-Hamiltonian bipartite polyhedral graphs, which can be realized as the Delaunay tesselation of their vertices (see Figure 10 in [DillSS]).

a

C

b

d

Fig. 14.2 Some small bipartite polyhedral graphs

Zonotopes Zonotopes are affine projections (called shadows in [Coxe73]) of hypercubes ?;n. (Apropos, any convex polytope is affine projection of a simplex am and any centrally symmetric convex polytope is affine projection of a cross-polytope ,& .) Remind that a dicing can be seen as a lattice, the Voronoi polytope of which is a zonotope (see [Erda98]). The following result was proved in [BEZSO].

Special e l -graphs

147

Proposition 14.1 The skeleton of a n y zonotope of diameter m i s isometrically embeddable into the skeleton H , of ym, whose a f i n e projection

it is. Remark 14.4

Examples of zonotopes are:

(1) five of Archimedean and their dual (Catalan) polyhedra are zonohedra: Nr.5, 9, 11 and 3, 6 of Table 14.1; (2) All five (combinatorially different) Voronoi polyhedra are zonohedra: cube y3 = H3, rhombic dodecahedron RhDo + H4, Prism6 -+ H4, elongated dodecahedron ElDo ---t H5, truncated p3 +. H6; (3) All five golden isozonohedra of Coxeter (zonohedra with all faces being rhombic with the diagonals in golden proportion) are: 2 types of hexahedra (equivalent to y 3 ) , rhombic dodecahedron, rhombic icosahedron Pz(5) and triacontahedron (i.e. dual icosidodecahedron). (4) Curious family of eight 3-zonotopes, embeddabble into H,, 3 5 m 5 10, and having m(m - 1) faces, is given in [ScYoOO]. (5) Besides Prisrnz, and -ym, some examples of infinite families of zonoH, (73, topes (Nr.12-16 in Table 14.1) are polar zonohedra Pz(m) RhDo, rhombic icosahedron for m = 3,4,5, respectively, see [Coxe73]) and m-dimensional permutahedra (for m = 2 and 3, it is Cs and truncated p3, respectively). The tope graphs of oriented matroids An oriented matroid on E is a pair M = ( E ,F), where E is a finite (melement) set and F is a set sign vectors on E (called faces), which satisfy some special axioms (see, for example, [F’uku95]).A natural order on signed vectors (on E ) defines the rank of a face f as the length of any maximal chain from 0 to f . The maximal faces are called topes; the common rank r of topes is called the rank of the oriented matroid M . The top graph of M is the graph, denoted by T ( M ) , having the topes as vertices, with two of them being adjacent if they have a common face of rank r - 1. The tope graph uniquely defines the oriented matroid. A graph is called antipodal, if for each its vertex a there is an unique vertex a’ such that a’ has larger distance from a than any of neighbors of a’. If the skeleton of a polytope is antipodal, then the maximal symmetry of this polytope contains central symmetry. In those terms, the following results by Fukuda and Handa (see [Fuku95]) connects isometric subgraphs of hypercubes with above tope graphs of an oriented matroids M = ( E ,F)

Scale Isometric Polytopal Graphs

148

Table 14.1 Some isometric polyhedral subgraphs of hypercubes

[

Nr.

I

Nr. vertices

I

deg.

I

polyhedron

I

emb. in

I

Aut

I

zonotope?

I

of rank r 2 3 on m-element set E : (i) T ( M ) is an r-connected antipodal graph and T ( M )-+ H,; (ii) A graph is the top graph of an oriented matroid of rank three on m-element set if and only if it is the skeleton of a centrally symmetric polyhedron, which is isometric subgraph of H,. If T ( M ) is the skeleton of a zonotope, then this zonotope is rdimensional and has diameter m. We are interested now by construction of non-zonotopal centrally-symmetric polyhedra. Every Voronoi polytope is centrally symmetric with centrally symmetric facets. But a zonotope additionally has centrally symmetric faces of all dimensions. The skeleton G ( P ) of a zonotope P is the top graph of an oriented matroid M ( P ) , which is realized by the zonotope P. Hence such oriented matroid is called realizable oriented matroid, or linear one. A face of dimension k of P realizes an oriented matroid of rank k. Consider a 3-dimensional zonotope, i.e. a zonohedron P. Let F and F’ be two opposite faces of P. Let F has 2k edges, k 2 3. These edges are parallel to k vectors. These k vectors are linearly independent and form a circuit C ( F ) of the matroid M ( P ) . Let {(i,i’) : 1 5 i 5 2 k ) be 2k pairs of antipodal vertices of F and F’, respectively. Denote by Q(G) the graph

Specaal

el

-gmphs

149

obtained from G := G ( P ) by adding two new vertices v , v' and new edges ( v , i ) ,(w',z') for i = 2 j 1, 0 5 j 5 Ic - 1. Clearly, Q(G) is antipodal and G is an isometric subgraph of Q(G). If G t H,, then Q(G) -+ H , also. (In fact, let a(1) = 0, 4 2 j + 1) = { l , j l}, 1 5 j 5 Ic - 1; then a(.) = (1) is uniquely determined.) If G is a 3-connected planar graph, then so, is Q(G). Hence Q(G) is the skeleton of a polyhedron, which we denote by Q ( P ) . It is centrally symmetric. Usually, if P is a zonohedron, so is Q ( P ) . But now, the set of vectors, representing F and F', is not a circuit of the oriented matroid

+

+

M ( Q( P )). Consider elongated dodecahedron ElDo and rhombic dodecahedron RhDo. One can check, that Q(Prism6) is RhDo, Q2(E1Do)is the rhombic icosahedron Pz(5), Q4(tr(,&)) is the triacontahedron, i.e. dual icosidodecahedron. (Here Q m ( P ):= &(&"-'(P)).) But there are cases, when the polyhedron Q ( P ) is not a zonohedron and hence, it does not realizes an oriented matroid. An example was given by F'ukuda in [Fuku95] (using a hexagonal faces F and F', on which new vertices were put); see Figure 14.3.

Fig. 14.3 A non-zonotopal centrally symmetric polyhedron, whose skeleton

is embeddable into Hg

This polyhedron contains 56 vertices, 18 hexagonal and 18 square faces. It is an example of a non-zonotopal centrally symmetric polyhedron, whose

150

Scale Isometric PolytopaE Graphs

skeleton is embedded into Hg. This polyhedron is a minimal one in the following sense: any centrally symmetric 3-polytopal isometric subgraph of H,, m 5 8, is (being the tope graph of an rank-three oriented matroid with a t most eight elements) the skeleton of a zonotope. Fukuda constructed it as (non-Pappus) extension of an oriented rankthree matroid on eight points. As a linear extension of the same matroid, he obtain a dual zonohedron of diameter nine, having 54 vertices, 20 hexagonal and 12 square faces: just delete two marked opposite vertices from 56-vertex polyhedron depicted in Figure 14.3 above.

Remark 14.5 See IDeSt96; DeSt971 for similar isometric embeddings of skeletons of infinite polyhedra (plane tilings) into cubic lattices 2,. For example, regular square tiling regular and hexagonal tiling are embeddable into 22 and 2 3 ; they are Voronoi partitions of the lattices .&,A:!. The Archimedean tilings (4.8.8), (4.6.12) and dual Archimedean tiling [3.6.3.6] are embeddable into 24, 26,Z3. Also Penrose aperiodic rhombic tiling is embeddable into 25 and dual mosaic Nr.12 (from Table 9.1 above) is embeddable into 2,. The tiling on Figure 14.4 b embeds also into 2,. Clearly, any lattice plane tiling, such that its Voronoi partition is embeddable into a Z,, is a dicing. In other words, it is zonohedral, i.e. having only centrally symmetric faces. Any zonohedral plane tiling embeds into a Zm , m <_ 00. A zonohedral plane tiling needs not to be periodic (for example, Penrose aperiodic tiling by two golden rhombuses) or to be a projection of Z,, m < 00 (see, for example, the tiling on Figure 14.4 a). The tiling [3.6.3.6]above is non-zonohedral, since its quadrangular faces are not centrally symmetric.

a

b

Fig. 14.4 Two embeddable tilings

Some generalizations of planar scale 1 embeddable graphs

Special

el -graphs

151

Let G be a bipartite plane graph. If it is infinite, we suppose that its vertices have bounded degree and that it is discrete, i.e. any c-neighborhood of any point on the plane contains only finite number of its vertices. Call such a graph G admissible (or strictly admissible) if there exist a mapping f of its vertices into vertices of an hypercube H,, m I 00, such that its edges (z,y ) are mapped into edges ( f ( z )f ,( y ) ) of H , and the images of the circuits, bounding its interior (or, respectively, all) faces are isometric subgraphs of the same Hm. Using a result from [DSSSS], we have that G is admissible (or strictly admissible) if and only if every of its zone (i.e. non-extendible sequence of opposite edges) is simple, i.e. it has no selfintersections. (In strictly admissible case the exterior face is included; so, G is considered as a graph on the sphere and zones can go through the exterior face.) In fact, if a zone self-intersects in a face, then the circuit, bounding this face, will be not isometric in H,. On the other hand, if G is a plane qoadriliage, i.e. all its interior faces are 4-gons, then it was proved in [DSS86] that it is admissible (or strictly admissible) if and only if all its zones are simple. The general case of admissible (or strictly admissible) graph G can be reduced to above one by partition of all interior (or, respectively, all) faces into 4-gons; so that the zones and their simplicity (or not) are preserved. In terms of zones, we have that G is scale one embeddable (i.e. an isometric planar subgraph of a hypercube) if and only if it is admissible and, moreover, every its zone is convex. In fact, zones are belts, corresponding to convex opposite cuts, such that exactly one of them goes through any edge. A partial subgraph of an hypercube is always bipartite; its vertices are mapped injectively into those of the hypercube. Clearly, there are following irreversible implications for possible properties of graphs with respect to the hypercubes: isometric (i.e. scale 1 embeddable) --+ induced -+ partial -+ bipartite, isometric planar + admissible -+ bipartite planar. (We take for each graph its strongest property; for example, the 8-cycle, which is only a partial subgraph of H3, is considered isometric since it is isometric subgraph of H4.) On Figure 14.5 we have seven counterexamples. In the last graph g), two vertices, marked by a black circle, are the points of self-tangency of the zones of eight 4-gons around them; the images of two vertices, marked by a white circles, coincide in He.

152

Scale Isometric Polytopal Graphs

a) the dual of APrism4 is bipartite planar, but non-admissible and non-partial one

c) the cube with deleteL edge is admissible and partial in H3, but non-induced

e) isometric, but not strictly admissible

b)

K2,3

is admissible in H2, but non-partial

d) admissible and induce in but non-isometric

f ) induced in He, but not admissible b

g) strictly admissible in non-partial

H6,

but

Fig. 14.5 Seven counterexamples

4,

Chapter 15

Some Generalization of &-embedding

15.1

Quasi-embedding

Here we consider quasi-embedding or, more exactly, t-embedding of given graph G, i.e. our usual embedding, but for t-truncated distance min(t, d c ) , where t is less than the diameter of the graph G. We say that a metric d is t-embeddable if there is an el-embeddable metric d' such that di,j = min(di,j,t). This notion was introduced in [DeSh96], where it was shown that the polynomial algorithm given there for the recognition of el-graphs can be extended to the recognition of t-embeddable graphs. In what follows, describing a t-embedding of a polyhedron P , we associate to every its vertex v a subset a(.) of a set N . Usually we take as N the set of all faces, which are k-gons for a fixed k. We say that a face F is reachable by an m-path from a vertex v if there is an m-path of length m from the vertex w to a vertex of the face F . We use here notation c 6 0 for the truncated icosahedron 56O(Ih). Even if c 6 0 is not el-embeddable, we still can quasirembed it into iH20 in the following sense. According to [DeSh96], the truncated icosahedron (of diameter 9) has a unique 7-embedding into i H 2 0 : associate each vertex to 2+2+3 hexagons (amongst all 20) reachable by 0-, 1-, 2-paths, respectively. It is also the unique 3-embedding, but not unique 2-embedding: for example, associate every vertex to two its hexagons. The unique 3-embedding of c 6 0 into iH20 is called quasGC60. Moreover, quasi-Cso is an el-rigid (but not graphic) metric. The Figure 15.1 illustrates the 7-embedding of c 6 0 . The construction is as follows: we can associate a coordinate of R20 to each of the 20 hexagons. Then a vertex v (for example the white atom of Figure 15.1) is mapped into the vertex 4(v) of the half-cube iH20 (in odd representation), whose

153

Scale Isometric Polytopal Graphs

154

non-zero coordinates correspond to the seven hexagons of c60 containing a vertex, whose distance to v is less than three (the seven grey hexagons of Figure 15.1). This give us a 7-embedding of c60 into the half-cube 3H20. All distances eight and nine in c60 became seven in quasi-Cs0 (recall that C60 has diameter 9). The automorphism group of quasi-C60 (i.e. all permutations of the 20 coordinates indexed by the 20 hexagons of c60,which preserve quasi-C60) is equal to the one of c60, which is the Coxeter group H3 isomorphic to (1, -1) x As. The Figure 15.2 illustrates one automorphism of quasi-Cso: the reversing of the spiral Hamiltonian path on the 20 hexagons of c 6 0 .

Fig. 15.1 Embedding up do distance 7 of Cso(Ih) into +Hzo

Icosidodecahedron (of diameter 5) has unique ([DeSh96]) 4-embedding in 3H12: associate every vertex to 1+1+2 pentagons (from all 12) reachable by 0-, 1-, 2-paths. It is also a unique 3-embedding, but there is another 2-embedding: associate every vertex to two its triangular faces. Cuboctahedron (of diameter 3) has at least two following 2-embeddings: into 3H6: associate every vertex to its two square faces, into H8: associate every vertex to its two triangular faces; this one, as well as two above ones are t-embeddings into ; H 2 4 ~ ) + 2 where , d ( P ) is the diameter of P. The vertex figure (and the local graph of the skeleton) of the snub 24cell is the tridiminished icosahedron (the regular-faced solid M7 = N r . 83 of diameter 3). It is embedded into 4H6 and has a 2-embedding into i H 7 . Any simple polyhedron has a 2-embedding in the tetrahedral graph

i

Some generalization of el -embedding

Fig. 15.2

155

The spiral Hamiltonian automorphism of quasi-Cso

J ( n ,3) (so in $H,): associate every vertex t o its three faces. If the diameter of a simple polyhedron is a t least 3, then it is 3-embeddable if and only if sizes of its faces are from the set {3,4,5). Examples of this procedure are: (1) dodecahedron (of diameter 5) has a 3-embedding into Johnson graph

J(12,3); also it has a 5-embedding into $Hlo, (not unique), (2) a3 -+ J(4,3) + (3) M;5 J(8,3) $k, (4) a 2-embedding of Prismn, which turns out to be Prismn ( 4H e for even n). -+

+

4

iHn+2

Another procedure: fix a 5-wheel VC5 in the skeleton of an icosahedron and associate every vertex v to the set of all vertices of the 5-wheel a t distances 0 and 1 from v ; we get the (unique) 3-embedding of the icosahedron. The dual of FCO(cs),-, considered on Figure 22 of [DDG98], admits a 4-embedding into i H l o . More precisely, F$o(Cs)r has diameter 5 and all distances are preserved except those between four opposite pentagons: (%,48), (1378,1478), 35) and (2459,2359). Instead of five, those distances became four in $Hlo. See Figure 15.3, where the 4-embedding of F,",(C,), is given by labels of facets of F6O(cs),-. Additionally, a not 5-gonal configuration of FGO(C,),is given, in Figure 15.3. The following Theorem (see [DFSOS])describe completely t-embeddings for fully icosahedral (i.e. with symmetry I h ) fullerenes and their duals.

(a,

Theorem 15.1

Scale Isometric Polytopal Graphs

156

Fig. 15.3 The 4-embedding of F&(C,), into ration of F ~ o ( C ~ ) ~

(a) c 2 o k 2 ( I h ) , k

and a not 5-gonal configu-

1 1 , is ( 2 k + 7)-embeddable into i H 1 2 k - 2 ; its diameter

is 6 k - 1, (2’)

(CZOk2(Ih))*, k

12,

iS

3k’

(ii) c s o k 2 ( I h ) , k is l 0 k - 1 ,

(iiy is 5 k .

2 1, is

(CsOkZ(Ih))*,k

(6k

2k-embeddable into

3H6k;

its diameter is

+ 1)-embeddable into i H 2 0 k ; its diameter

2 1, is (3k+2)-embeddable into i H l o k ; its diameter

In fact, let us indicate for each of four above cases, the complete collection of zones, giving a t-embedding. Each zone will be without selfintersections; so any two of them will be either parallel, i.e. disjoint, or intersect exactly in two faces. We call a zone of faces of a fullerene special or pure, according to if it contains or no some pentagons. The dimension of the half-cube is the number of special zones plus twice the number of pure ones. This dimension turns out to be twice the diameter of the graph in the cases (i), (i’) and (ii’). Remark that this t-embedding is isometric only for k = 1 in the cases (i), (i’), (ii’) and for k = 2 in the case (i). In the case (i’) above there are 6lc alternating zones of length lOk each; they are partitioned

S o m e generalization of

el -embedding

157

into six parallel classes. In the case (ii’) above there are lOk alternating zones of length 18k each; they are partitioned into ten parallel classes. In the case (i) above there are 6 ( k - 1) pure zones of length 5k each; they are partitioned into six parallel classes; there are ten special (alternating) zones of length 6 k each. Each special zone consists of six pentagons, separated by (k - 1)-strings of hexagons. Each zone have equal number (six for pure and three for special one) of pentagons inside and outside of it. In the case (ii) above there are lO(k - 1) pure zones of length 9k each; there are 20 special (alternating) zones of length 9k each. Each special zone is not alternating; it consists of three pentagons, separated by (3k - 1)-strings of hexagons. Each pure zone have six pentagons inside and outside of the ring formed by the zone; each special one has exactly three pentagons inside or outside of it. All 20k zones are partitioned into ten parallel classes and each class consists of k - 1 pure zones, taken in a “sandwich” by two special ones.

15.2 Lipschitz embedding Here we consider another relaxation of our main notion of 11-embedding. The mapping f : X -+ Y of metric spaces X,Yis called Lipschitz, if for any vertices a, b of X ,holds

where C is a constant, called distortion. Bourgain showed in 1985 that any metric on at most n points is Lipschitz-embeddable into @ (for a finite dimension k) with distortion C = O ( b g n ) ;Linial, London and Rabinovitch showed in 1994 that, moreover, k = O ( ( l o g n ) 2 ) . For example, K1,3 has distortion > 1. Aharoni in 1978 showed that any I , with p > 2 is not Lipschitz-embeddable into 11. It looks plausible that the path-metric of any infinite hypermetric graph (moreover, any 5-gonal metric) is Lipschitz-embeddable, up to a scale, into a Z, m 5 00. 15.3

Polytopal hypermetrics

The convex cone of all hypermetrics on m points is denoted by Hyp,. Call a hypermetric d on m points of rank k , if the intersection of all faces of

158

Scale Isometric Polytopal Graphs

Hyp,, to which d belongs, has dimension k ; call a hypermetric extreme hypermetric, if it has rank 1, i.e. it belongs to an extreme ray of Hyp,. A polytope P x P' is hypermetric if and only if both P, P' are hypermetric; it is non-embeddable if and only if at least one of P, P' is nonembeddable. (But, for example, any pyramid P y r ( P ) over polytope P with at least 28 vertices, is embeddable if and only if it is hypermetric.) Any hypermetric, but not el-embeddable graph of rank k has a t most 56k vertices; the skeleton of the direct product of k copies of the 7dimensional Gosset polytope 321 realizes equality in this upper bound. We denote below by Gi, 1 I i 5 26, the graphs from [DeGr93] related (but not as path-metrics) to extreme hypermetric on seven points. Remark that extreme hypermetric graphs G1 and G2 are skeletons of 4-dimensional pyramids with bases Pyrs and 2-capped ag, respectively. All hypermetric but non-ll graphs with at most seven vertices are known (see [DeGr93]); they are 12 graphic metrics amongst of 26 extreme hypermetrics on seven points. Proposition 15.1 Amongst of all hypermetric non-11 graphs with at most seven vertices, the polytopal ones are only: 3-polytopal G4 (see Figure 15.4, d)) and 4-polytopal GI = V2C5 = K7 - C5, G2 = K7 - P4.

Any, except of K2, hypermetric is extreme if and only if it generate 221 or 321. So, the number of vertices of any extreme hypermetric graph is within the interval [7,56] and any polytope, such that its skeleton is extreme hypermetric, has dimension within the interval [6,7]. Call an extreme hypermetric graph of type I (of type 11) if it generates the root lattice E6 (E7,respectively). A graph G of type I has diameter two, since it is an induced subgraph of the Schlafli graph G(221) of diameter two, and in this case VG is an extreme hypermetric of type 11. Clearly, G ( P yr (P)) = VG(P), dim(Pyr(P))=dimP+l. (Remark that Pyrk(C5) --f kH5 for k E (0, l},it is extreme hypermetric for k E {2,3}, and it is 7- but not 9-gonal for k = 4.) Examples of polytopes, whose skeletons are extreme hypermetric but are not represented as VG' for an extreme hypermetric graph G' are: of type I: (1) the polyhedra Nr.30,71,106 = M22 and one with skeleton G4 all having 9, 9, 10 and 7 vertices, respectively (see Figure 15.4); (2) the 4-polytopes with skeletons GI, G2 and both with seven vertices; (3) the 6-polytopes: with skeletons KS - CS = G(Pyr3(Prisms)),

Some generalization of e l -embedding

a) 1 - APrism4,

b) triaugmented Prisms,

c) sphenocorona M22,

d) extreme hypermetric graph G4

159

Fig. 15.4 Examples of hypermetric non-embeddable polyhedra

V'T(5) = G(Pyr2(Ambo(a4))), V $ H 5 and the Shlafli polytope 221 having, respectively, 9, 12, 17 and 27 vertices; of type 11:

+

(1) the polyhedra Nr.37, 107 = A421 Pyr4 (2) and the 7-polytope 321 with 10, 11 and 56 vertices, respectively.

So, we have two following series of inscribed polytopes, such that their skeletons are extreme hypermetrics: GI = V2Cs < V'G(021) < VG(l21) < G(221) (of type I), V3C5 < V3G(021) < V2G(121) < G(321). Some examples of extreme hypermetrics, which are not polytopal, but are close to polytopal in a sense: (1) 7-vertex graph G18 of type I is a planar graph of a skew polyhedron. (2) The skeleton of the stella octangula (the section of 7 3 by ,L?3 with vertices in the centers of faces of y3), which is a non-convex polyhedron; it is

160

Scale Isometric Polytopal Graphs

14-vertex graph Gso. It contains the extreme hypermetric G4 as an induced subgraph. G,, is an isometric subgraph of the Gosset graph G(321) and, since it has diameter 3, it is of type 11. (3) Antiwebs A W , , AWf2, are of type I, and AW,3, is of type 11; AWg” is projectively-planar and it becomes planar, if we delete one edge. Finally, one can enumerate isometric subgraphs (and polytopal ones between them) of a given half-cube +€In,which are not isometric subgraphs of its facet. For example, the following graphs are such isometric polytopal subgraphs of the Clebsh graph i H 5 = G(121): (1) C5, K5 = G(a4) (together with four graphs from 2) below), they are only such subgraphs of i H 5 with at most 6 vertices); (2) Kfj - cfj = G(Prisms), Kf3 - P 5 (polyhedral), K6 - P4 = G(2-capped as),VC5 = G(Pyr5) (amongst of all ten 6-vertex isometric subgraphs of i H 5 ) ; (3) the skeletons of the following polyhedra with a t least 7 vertices: Nr.27 (1-capped Prism3), Nr.60 (augmented Prisms), Nr.70 (biaugmented P r i s ms) , 1-capped p3, APrism4; (4) the skeletons of 4-polytopes: Pyr(Prism3), a1 x a3, G(021) = T(5), T(5) - K1, “(5) 1-capped (on a facet ,&) 021; (5) the skeletons of 5-polytopes: Py r2(Prisms) Pyr(ambo-a4).

z,

15.4

Simplicia1 n-manifolds

An interesting relaxation of our embeddings of polytopes is to consider scale-isometric embedding into hypercubes and cubic lattices of 1-skeletons of simplicial and cubical complexes more general than the boundary complexes of polytopes. For example, the simplicial complex on { 1,2,3,4,5} with the facets {1,2,3}, {1,2,4}, {1,2,5} has the skeleton K5 - K3; the cubical complex on {1,2,3,4,5,6} with the facets {1,2,3,4}, {2,3,5,6}, {1,4,5,6} has the skeleton K3,3. So, both are not 5-gonal. While the general case of simplicial complexes is too vast, we have some partial results in terms of links of (n - 2)-fuces. For any n-simplex S containing fixed ( n - 2)-face S’, there exists unique edge e, such that S is the join of S‘ and e. The link of (n - 2)-face S‘ is the cycle formed by such edges e, for all n-simplexes S , containing S’. Theorem 15.2 Let M be a closed simplicial n-manifold of dimension n 2 3. Then we have:

Some generalization of e l -embedding

161

(i) M is not embeddable, if it has an (n - 2)-face belonging to at least

five n-simplexes and such that its link is an isometric cycle in the skeleton. (ia) M is embeddable, if any of its (n - 2)-faces belongs to at most four (ie. 3 or 4 ) n-simplexes.

If a (n - 2)-face belongs to at least six n-simplexes (so, to at least six (n - 1)-simplexes), then the skeleton of M is not 5-gonal, since it contains the isometric subgraph K5 - K3. For example, De(A;) is not 5-gonal, because it has six tetrahedra on some edges. If a (n - 2)-face belongs to exactly five n-simplexes, then the skeleton of M contains the isometric subgraph K7 - C, (i.e., the skeleton of 4-polytope Pyr(Pyr5)),which is 5-gonal but is not embeddable. For example, the regular 4-polytope 600-cell, which is a closed simplicial 3-manifold, has five tetrahedra on each edge. The condition of isometricity of the link is necessary (it was missed in a result from [DeSt98]). For example, there exists an embeddable 3-manifold having an edge, which belongs to five tetrahedra; its skeleton is K7 - P2. In order to check (ii) for n = 3, for example, consider closed simplicial 3-manifolds, such that any edge belongs to at most four tetrahedra. There are exactly five such manifolds. Their skeletons are K5 = G(a4),K2x4 = G(P4),K6 (a 3-dimensional submanifold of a s ) , K6 - e, K7 - 2e. All those five skeletons are embeddable into $ Hm with m = 5,4,6,8,8, respectively. One can show, that the skeleton of any n-manifold in the case (ii) is the graph Ki - tP2 (i.e. the i-clique with t disjoint edges deleted), such that either (i,t) = ( 2 n + 2 , n + 1 ) , or n 2 t f 1 and n t + 2 I i 5 n t 1 + 1J. In fact, any subgraph of the skeleton of (n+l)-cross-polytope, containing Kn+2 - P2, will appear as such skeleton; all of them are embeddable graphs of diameter two. For example, K7 - P2 appears as the skeleton of an nmanifold of type (ii), but only for n = 4.

+

+ +

This page intentionally left blank

Bibliography

[AndrO5]A.Andreini, Sulle reti di poliedri regolari e semiregolari e sulle corrispondenti reti correlative (in Italian) , Mem. Societa Italiana della Scienze, Ser.3, 14 (1905) 75-129. [AsDe80] €'.Assouad and M.Deza, Espaces mktriques plongeables duns un hypercube: aspects combinatoires, Annals of Discrete Mathematics 8 (1980) 197210. [Ass0811 P.Assouad, Embeddability of regular polytopes and honeycombs in hypercubes, The Geometric Vein, Coxeter Festschrift, Springer-Verlag,Berlin (1981) 141-147. [Avis80] D.Avis, Hypemetric spaces and the Hamming cone, Canadian Journal of Mathematics 33 (1981) 795-802. [AvDeSl] D.Avis and M.Deza, The cut cone, el -embeddability, complexity and multi-commodity flows, Networks 21 (1991) 595-617. [BaChOO] H.-J.Bandelt and V.Chepoi, Decomposition and el-embedding of weakly median graphs, European Journal of Combinatorics 20 (2000) 701-714. [BaSc95] M.Baake and MSchlottman, Geometric aspects of tilings and equivalence concepts, Proc. 5th. Conference on Quasicrystals, World Scientific (1995) 15-21. [BLKBSSR95] A.T.Balaban, X.Liu, D.J.Klein, D.Babic, T.G.Schmalz, W.A.Seitz and M.Randic, Graph invariants for fullerenes, Journal of Chememical Information and Computer Science 35 (1995) 396-404. [Berm711 M.Berman, Regular faced convex polyhedra, Journal of the Franklin Institute, 291-5 (1971) 329-352. [BEZSO] A. Bjorner, P. H. Edelman and G. M. Ziegler, Hyperplane arrangements with a lattice of regions, Discrete and Computational Geometry 5 (1990) 263-288. [BlB191] G.Blind and R.Blind, The semi-regular polyhedra, Comment. Math. Helvetica 66 (1991) 150-154. [BlB198] G.Blind and R.Blind, The almost simple cubical polytopes, Discrete Mathematics 184 (1998) 25-48. [BrDe99] G.Brinkmann and M.Deza, Tables of face-regular polyhedra, Journal of Chemical Information and Computer Science 40-3 (1999) 530-541. 163

164

Scale Isometric Polytopal Graphs

[BCN89] A.E.Brouwer, A.M.Cohen and A.Neumaier, Distance-regular graphs, Springer-Verlag, Berlin, 1997. [Chav84] D.Chavey, Periodic tilings and tilings by regular polygons, Ph.D. Thesis, Univ. of Wisconsin-Madison, 1984. [Chav89] D.Chavey, Tilings by regular polygons - 2; a catalog of tilings, Computers Math. Applic. 17 (1989) 147-165. Reprinted in S Y M M E T R Y 2, ed. by LHargittai, Vol. 18, Int. Series Modern Applied Mathematics and Computer Science, Pergamon Press, 1989. [CDG97] V.Chepoi, M.Deza and V.P.Grishukhin, Clin d’oeil o n el-embeddable planar graphs, Discrete Applied Mathematics 80 (1997) 3-19. [Conw67] J.H.Conway, Four-dimensional Archimedean polytopes, Proc. colloquium on Convexity, Copenhagen 1965, Kobenhavns Univ. Mat. Institut (1967) 38-39. [CoS188] J.H.Conway and N.J.A.Sloane, Sphere Packings, Lattices and Groups, Grundlehren der mathematischen Wissenschaften 290, Springer-Verlag, New York, 1988. [Coxe35] H.S.M.Coxeter, WythofS’s construction for u n i f o r m polytopes, Proceedings of London Mathematical Society 38-2 (1935) 327-339. [Coxe37]H.S.M.Coxeter, Regular skew polyhedra in three and f o u r dimensions and their topological analogues, Proceedings of London Mathematical Society 43-2 (1937) 33-62. [Coxe54] H.S.M.Coxeter, Regular honeycombs in hyperbolic space, Proceedings of the International Congress of Mathematicians, Amsterdam, 1954 Vol. 3 (1954) 155-169. [Coxe73] H.S.M.Coxeter, Regular Polytopes, 3rd ed., Dover, New York, 1973. [Crit7O] K.Critchlow, Order in Space, Viking Press, New York, 1970. [Crom97] P.R.Cromwel1, Polyhedra, Cambridge University Press, Cambridge, 1997. [DbLa81] 1.Debroey and F.Landuyt, Equitransitive edge-to-edge tilings by regular convez polygons, Geometriae Dedicata 11 (1981) 47-60. [Delo37] B.Delaunay (as B.N.Delone), T h e geometry of positive quadratic forms, Uspekhi Mat. Nauk 3 (1937) 16-62; 4 (1938) 102-164. [DezaGO] M.Deza (as M.Tylkin), O n H a m m i n g geometry of unitary cubes (in Russian), Doklady Akademii Nauk SSSR 134 (1960) 1037-1040; English translation in Soviet Physics Doklady 5 (1961). [Deza02] M.Deza, Face-regular polyhedra and tilings with two combinatorial types of faces, in “Codes and Designs”, OSU Math. Research Institute Publ. 10 (2002) 49-71. [DDG98] A.Deza, M.Deza and V.P.Grishukhin, Embedding of fullerenes and coordination polyhedra i n t o half-cubes, Discrete Mathematics 192 (1998) 41-81. [DFS03] M.Deza, P.Fowler and M.I.Shtogrin, Version of zones and Petri circuits of icosahedral fullerenes and icosadeltahedra, Journal of Chemical Information and Computer Science 43 (2003) 595-599. [DeGr93] M.Deza and V.P.Grishukhin, Hypermetric graphs, Quarterly Journal of Mathematics Oxford 44-2 (1993) 399-433. [DeGr97a] M.Deza and V.P.Grishukhin, A zoo ofel -embeddable polyhedral graphs

Bibliography

165

, Bull. Inst. Math. Acad. Sinica 25 (1997) 181-231, [DeGr97b] M.Deza and V.P.Grishukhin, T h e skeleton of the 120-cell i s n o t 5gonal, Discrete Mathematics 165/166 (1997) 205-210. [DeGr99] M.Deza and V.P.Grishukhin, I 1 -embeddable polyhedra, in Algebras and Combinatorics, Int. Congress, ICAC ’97 Hong Kong, ed. by K.P. Shum et al., Springer (1999) 189-210. [DeGrOl] M.Deza and V.P.Grishukhin, Face-regular bifaced polyhedra, Journal of Statistical Planning and Inference 95-1,2,Special Issue in honor of S.SShrikhande (2001) 175-195. [DeLa94] M.Deza and MLaurent, I 1 -rigid graphs, Journal of Algebraic Combinatorics 3 (1994) 153-175. [DeLa97] M.Deza and M.Laurent, Geometry of cuts and metrics, Springer-Verlag, Berlin, 1997. [DePaOl] M.Deza and D.Pasechnik, O n epuicut graphs, Multiple-Valued Logic, Special Issue in honour of 1.G.Rosenberg 7 (2001) 363-377. [DeSh96] M.Deza and SShpectorov, Recognition of e l -graphs with complexity O(nm),or football in a hypercube, European Journal of Combinatorics 172,3 (1996) 279-289. [DeSt96] M.Deza and M.I.Shtogrin, Isometric embedding of semi-regular polyhedra, partitions and their duals i n t o hypercubes and cubic lattices, Russian Math. Surveys, 51-6 (1996) 1193-1194. [DeSt97] M.Deza and M.I.Shtogrin, Embedding of graphs i n t o hypercubes and cubic lattices, Russian Math. Surveys, 52-6 (1997) 1292-1293. [DeSt98] M.Deza and M.I.Shtogrin, Embedding of skeletons of Voronoi’ and Delaun a y partitions i n t o cubic lattices, in: VoronoY’s impact on modern science, Book 2, Institute of Mathematics, Kyiv (1998) 80-84. [DeSt99] M.Deza and M.I.Shtogrin, Mosaics, embeddable i n t o cubic lattices, Preprint LIENS 99-5, Ecole Normale Supgrieure Paris (1999), Discrete Mathematics 244/1-3 (2002) 43-53. [DeStOOa] M.Deza and M.I.Shtogrin, Uniform partitions of %space, their relatives and embedding, European Journal of Combinatorics 21-6,Special Issue “Discrete Metric Spaces” (2000) 807-814. [DeStOOb] M.Deza and M.I.Shtogrin, Embedding of chemical graphs i n t o hypercubes (in Russian), Math. Zametki 68-3(2000) 339-352. English translation in Mathematical Notes 68-3,4(2000) 295-305. [DeStOOc] M.Deza and M.I.Shtogrin, Embedding of the graphs of regular tilings and honeycombs i n t o the graphs of hypercubes and cubic lattices in “Arrangements, Tokyo 1998”, Series Advanced Studies in Pure Mathematics, Math. Society of Japan (2000) 73-92. [DeStOl] M.Deza and M.I.Shtogrin, Clusters of cycles, Journal of Geometry and Physics 40-3,4(2001) 302-319. [DeStOPa] M.Deza and M.I.Shtogrin, Mosaics and their isometric embedding (in Russian), Isvestia of Russian Acadedemy of Sciences Ser. Math. 66-3(2002) 3-22. [DeStOPb]M.Deza and M.I.Shtogrin, Extremal, non-extendible and isohedral polycycles (in Russian), Trudy of Steklov Mathematical Institute, translated in

166

Scale Isometric Polytopal Graphs

Proc. Steklov Inst. Math. 239 (2002) 117-135. [DeSt02c] M.Deza and M.I.Shtogrin, Criterion of embedding of (r,q)-polycycles, Uspechi Math. Nauk = Russian Math. Surveys 57-3 (2002) 149-150 (589591). [DeStOPd] M.Deza and M.I.Shtogrin, Metrics of constant curvature on polycycles (in Russian), Math. Zametki (2003), submitted. [DeTu96] M.Deza and J.Tuma, A note on !I-rigid planar graphs, European Journal of Combinatorics 17-2,3(1996) 157-160. [Dill961 M.B.Dillencourt, Polyhedra of small order and their Hamiltonian properties, Journal of Combinatorial Theory Series B 66 (1996) 87-122. [Djok73] D. 2. DjokoviC, Distance preserving subgraphs of hypercubes, Journal of Combinatorial Theory Series B 14 (1973) 263-267. [DSSSS] N.P.Dolbilin, M.A.Shtan’ko and M.I.Shtogrin, Cubical subcomplexes in regular lattices, Soviet Mathematics Doklady 34-3 (1987) 467-469. [Duto02] M.Dutour, private communication, October 2002. [Enge98] P.Enge1, New investigations of parallelohedra in R d ,in: VoronoY’s impact on modern science, Book 2, Institute of Mathematics] Kyiv (1998) 22-60. [EnGr02] P.Engel and V.Grishukhin, There are exactly 222 L-types of 5dimensional primitive lattices, European Journal of Combinatorics 23-3 (2002) 275-279. [ErRy87] R.M.Erdah1 and S.S.Ryshkov, The empty sphere, Canadian Journal of Mathematics 34-4 (1987) 794-824. [Erda98] R.M.Erdah1, Zonotopes, and Voronoi’s conjecture on parallelohedra in: VoronoY’s impact on modern science, Book 2, Institute of Mathematics] Kyiv (1998) 61-74. [Fed018851 E.S.Fedorov, Introduction in the study of figures (in Russian), St.Petersburg, 1885. [Fix751 J.C.Fischer, Five-valent convex polyhedra with prescribed faces, Journal of Combinatorial Theory Series A 18 (1975) 1-11. [FoMa95] P.W.Fowler and D.E.Manolopoulos, An Atlas of Fullerenes, Clarendon Press, Oxford, 1995. [Fuku95] K.Fukuda, Lecture notes: A constructive approach to polyhedral geometry and mathematical programming, Institute for Mathematical Research, ETH, Zurich, Switzerland, 1995. [Gold351 M.Goldberg, A n isoperimetric problem for polyhedra, Tohoku Mathematical Journal 40 (1935) 226-236. [Gold371 M.Goldberg, A class of multi-symmetric polyhedra, Tohoku Mathematical Journal 43 (1937) 104-108. [GrMo63] B.Grunbaum and T.S.Motzkin, The number of hexagons and the simplicity of geodesics on certain polyhedra, Canadian Journal of Mathematics 15 (1963) 744-751. [GrSh87] B.Griinbaum and G.C.Shephard, Tilings and Patterns, W.H.Freeman, New York, 1987. [GrSh98] B.Griinbaum and G.C.Shephard, Isohedra with nonconvex faces, Journal of Geometry 63 (1998) 76-96. [Grun67] B.Grunbaum, Convex Polytopes, Interscience, New York, 1967.

Bibliography

167

[Grun94] B.Grunbaum, Uniform tilings of 3-space, Geombinatorics 4 (1994) 4956. [Grun96] B.Grunbaum, private communication, May 1996. [HiPe89] P.Hilton and J.Pedersen, Duality and the Descartes deficiency, Computer Mathematics and Applications 17-1,2,3(1989) 73-88. [John661 N.W.Johnson, Convex polyhedra with regular faces, Canadian Journal of Mathematics 18 (1966) 169-200. [John911 N.W.Johnson, Uniform Polytopes, manuscript, 1991, to appear, Cambridge University Press. [Juco~O] E.JucoviE, Characterization of the p-vector of a self-dual 3-polytope, in: Combinatorial structures and their applications, Proceedings of Calgary Conference 1969, ed. by R.Guy and al. (1970) 185-187. [Karz85] A.V.Karzanov, Metrics and undirected cuts, Mathematical Programming 32 (1985) 183-198. [Kats83] I.Katsura, Theory o n the structure and stability of coated vesicles, Journal of Theoretical Biology 103 (1983) 63-75. [Ke1175] J.B.Kelly, H y p e m e t r i c spaces, Lecture Notes in Math. 490, SpringerVerlag, Berlin (1975) 17-31. [Kepll6191 J .Kepler , Hannonice Mundi, 1619. [King911 R.B.King, Topological aspects of chemically significant polyhedra, Journal of Mathematical Chemistry 7 (1991) 51-68. [KoSu92] M.Kobayasi and T.Suzuki, Calculation of coordinates of vertices of all convez polyhedra with regular faces (in Japanese), Bull. Univ. Electro-comm. 5-2 (1992) 147-184. [Kool9O] J.Koolen, O n metric properties of regular graphs, Master's Thesis, Eindhoven University of Technology, 1990. [KoSp94] J.Koolen and S.V.Shpectorov, Distance-regular graphs the distance matrix of which has only one positive eigenvalue, European Journal of Combinatorics 15 (1994) 269-275. [Krot69] O.Krotenheerdt, Die homogenen Mosaike n-ter Ordnung in der euklidischen Ebene, 1 , Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.natur. Reihe 18 (1969) 273-290. [Krot70a] O.Krotenheerdt, Die homogenen Mosaike n-ter Ordnung in der euklidischen Ebene, 2, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.natur. Reihe 19 (1970) 19-38. [Krot70b] O.Krotenheerdt, Die homogenen Mosaike n-ter Ordnung in der euklidischen Ebene, 3, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.natur. Reihe 19 (1970) 97-122. [Macp82] H.D.Macpherson, Infinite distance transitive graphs of finite valency, Combinatorica 2-1 (1982) 63-69. [Maka88] P.V.Makarov, How t o deduce the 4-dimensional semi-regular polytopes (in Russian), Voprosy Discretnoi Geometrii, Matematich. Issledovania Inst. Matem. Akademii Nauk Moldavskoi SSR 103 (1988) 139-150. [Malk70] J.Malkevitch, A survey of 3-valent 3-polytopes with two types of faces, in: "Combinatorial structures and their applications", Proceedings of Calgary Conference 1969, ed. by R.Guy and al. (1970) 255-256.

168

Scale Isometric Polytopal Graphs

[OkHy96] M.O'Keeffe and B.G.Hyde, Crystal Structures, Mineralog. Society of America, Washington DC, 1996. [Novi86] S.P.Novikov, Topology (in Russian), Itogi nauki i tehniki. Series "Modern problems in mathematics". Fundamental sciences. V01.12, Topology-I. VINITI, 1986. (Pear781 P.Pearce, Structure in nature is a strategy f o r design, The MIT Press, Cambridge, 1978. [PSC90] K.F. Prisacaru, P.S. Soltan and V.D. Chepoi, O n embeddings of planar graphs into hypercubes (in Russian), Proceedings of Moldavian Academy of Sciences, Mathematics, 1 (1990) 43-50. [Radi94] C.Radin, The pinwheel tiling of the plane, Annals of Math. 139-2 (1994) 66 1-702. [RyBa76] S.S.Ryshkov and E.P.Baranovskii, C-types of n-dimensional lattices and the Jive dimensional primitive parallelohedrons (with applications to the theory of covering), Trudy Math. Inst. Steklov, 137 (1976) 3-131 = Proc. Steklov Mathematical Institute 137 (1978) 1-140. [RyBa79] S.S.Ryshkov and E.P.Baranovskii, Classical methods in the theory of lattice paclcings, Russian Math Surveys 34-4 (1979) 1-68. [SaMo97] J.F.Sadoc and R.Mosseri, Frustration ge'ome'trique, Ale'a-Saclay, Eyrolles, Paris (1997). [Sah94] C.H.Sah, A generalized leapfrog f o r fullerene structures, Fullerenes Science and Technology 2-4 (1994) 445-458. [ScYoOO] C.Schwabe and N.Yoshimoto, Zonohedra music chart, Hyperspace 9-3 (2000) 31. [Shpe93] S.Shpectorov, O n scale-isometric embeddings of graphs into hypercubes, European Journal of Combinatorics 14 (1993) 117-130. [Shto80] M.I.Shtogrin, Non-normal partitions of 3-space into convex pamllelohedra and their symmetry (in Russian), Proceedings of All-Union Symposium on the Theory of Symmetry and its Generalizations, Kishinev (1980) 129130. [Thur98] W.P.Thurston, Shapes of polyhedra and triangulations of the sphere, in Geometry and Topology Monographs 1, The Epstein Birthday Schrift, Geom. Topol. Publ., Coventry, 1998, 511-549. [Voro1908] G.F.VoronoY, Nouvelles applications des paramttres continus b la the'orie des forms quadratiques, DeuxiBme memoire, J. Reine Angew. Math. 134 (1908) 198-287, 136 (1909) 67-178. [Week851 J.R.Weeks, PhD Thesis, Princeton University, 1985. [We11841 A.F.Wells, Structural Inorganic Chemistry, V ed. Oxford, 1984. [Well911 D.Wells, The Penguin dictionary of curious and interesting geometry, Penguin Books, London-New York, 1991. [Wenn71] J.M.Wenniger, Models of Polyhedra, Cambridge University Press, Cambridge, 1971. [Will721 R.Williams, Natural structure, Eudaeman Press, Moorpark Ca. 1972; reprinted as The Geometrical Foundation of Natural Structure, Dover, New York, 1979. [Zalg69] V.A.Zalgaller, Convex polyhedra with regular faces, Seminar in Mathe-

Bibliography

169

matics of Steklov Mathematical Institute, Leningrad, 2 Consultants Bureau, New York, 1969.

This page intentionally left blank

Index

( r ,q)-polycycle, 75

n-bipyramid B P y r ( P ) , 17 n-cross-polytope &, 17 n-cube yn, 17 n-permutahedron, 111 n-simplex a,,, 17 n-sphere, 35 n-wheel, 3 4 3 , 4 , 3 ) , 71 s(3,4,3,3), 54 t-embeddable graphs, 153 t-truncated distance, 153 tr(octahedron), 45, 46 1-APrism,, 50 120-cell, 40 2-APrismm, 50 24-cell, 40 5-gonal inequality, 9 600-cell, 40

(s x s)-grid, 142

APrisrnk, 50 A,, 107 Barrel&, 51 D-complex, 105 D,, 107 DL, 109 De(L), 107 Es, 107 E7,107 Es, 107 J-complex, 101 Prism;, 45 RhDo-vs, 100 Tower:, 50 V o ( L ) ,107 el-embeddable graph, 5 C1-graph, 4 el-metric, 6 el-rigid graph, 6 tr(cube), 45, 46 tr(cuboctahed.), 45, 46 tr(dodecahedron), 45, 46 tr(icosahedron), 45, 46 tr(icosidodecah.), 45, 46 tr(tetrahedron), 45, 46 +-truncation, 53 +-truncation, 53 i-capping, 54 i-layered dodecahedron, 30 i-truncation, 54

adjacent, 1 alternating cut, 11 alternating zone, 13 ambo-polytope, 18 antipodal doubling, 138 antiweb AW;, 49 aperiodic sequences, 77 Archimedean 4-polytopes, 72 Archimedean polyhedra, 16 augmented sphenocorona, 64 azulene, 78 basic polyhedra, 63 171

172

Scale Isometric Polytopal Graphs

bcc, 101 belt, 10 benzene, 78 bi-lattice, 100 bicupolas, 68 bifaced polyhedra, 120 Bilunabirotunda, 69 bipartite graph, 1 biphenyl, 78 border line, 14 boride FezAlB2, 101 boride UB12, 102 boride CaB, 101 buckminsterfullerene, 25 Cairo net, 86 Campanus sphere, 46 capping, 18 carbon C , 78 Cartesian product GI x Gz, 3 Catalan polyhedra, 16 cell, 35 centering, 109 central circuit, 12 chamfering, 18, 59 circuit C,, 2 coated vesicles cells, 31 cocktail-party graph K n x 2 ,2 convex n-polytope, 15 convex cut, 6 convex subset, 4 coordination polyhedra, 80 copper Cu, 103 coranulene, 78 cube y3, 16 cubic lattice graph Z,, 2 cubical complex, 160 cuboctahedron Cbt, 63 cupola Cupn, 49 cut { S , 3 } , 5 C u t COhC,

5

cut semimetric, 5 Durer’s octahedron, 15 Delaunay partition, 19 Delaunay polytope, 19

deltahedron, 15 density, 36 diametral doubling, 139 diametral switching, 140 diamond bi-lattice, 105 dicing lattice, 110 distance-regular graph, 141 distance-transitive graph, 141 ditrigonal dodecahedron, 39 dodecadodecahedron, 39 dodecahedron Do,16 Doob graph, 141 Double Odd graph D 0 z S + l , 142 dual polytope, 15 Dyck map, 38 edge figure, 83 Edge-coalesced icosahedron, 82 edge-homogeneous, 83 elliptic distance, 47 elongated dodecahedron ElDo, 15 elongation, 17 equicut graph, 137 Euclidean n-space, 35 Euclidean plane R 2 , 75 Eulerian plane graph, 12 extreme hypermetric graph, 158 Foppl partition, 103 face-regular, 89 fcc, 101 fluorentene, 78 fullerene, 25 fundamental region, 36 geodesic, 4 girth of graph, 75 golden isozonohedra, 147 golden number, 72 golden rhombi, 87 golden rhombohedra, 87 golden truncation, 54 Gosset graph G(321), 160 Griinbaum partition, 104 Grand Antiprism, 73 great dodecahedron, 36

Index

great icosahedron, 36 grid distance, 48 grid graph, 48 gyro-elongated Pyr4, 64 gyrobifastigium, 64 Hadamard matrix, 141 half-cube graph $ H,, 2 half-cubic lattice graph $ Z n , 2 Hamming distance, 48 Hamming graph, 48 hcp, 102 hebesphenocorona, 70 hexagonal sheet, 31 hexakis, 54 high-pressure Si, 101 Hilbert cube, 21 honeycomb, 16 hydrogen H, 78 hyperbolic n-space, 35 hyperbolic plane H 2 , 75 hypercube graph H,, 2 hypermetric graph, 8 hypermetric inequality, 8 16 icosahedron ICO, icosidodecahedron, 63 incident, 1 indacene, 78 induced subgraph, 1 infinite chess-board, 106 infinite dimensional cube, 20 infinite distance-transitive graph, 143 infinite prism, 106 infinite regular polyhedra, 38 irreducible root lattices, 107 isometric subgraph, 4 Johnson n-polytope, 16 Johnson graph J ( n , k ) , 3 k-hedron, 15 Kagome net, 86 Karlsruhe distance, 45 Kelvin partition, 103 Klein map, 38

173

Koester’s graph, 51 labyrinths, 38 lattice, 107 lattice complex, 100 Laves phase MgCu2, 103 leapfrog, 125 Lee distance, 47 left opposite edge, 11 left-right circuit, 12 line graph, 3 Lipschitz-embeddable, 157 medial graph, 18 medial polyhedra, 121 metallic cluster, 80 metallopolyhedra, 80 metric, 4 minimal energy, 31 minimal scale, 4 mosaic, 83 Moscow distance, 45 Moscow graph, 45 multipartite graph

,...,nk , 2

naphtalene, 78 non-compact uniform partitions, 106 NP-complete, 9 octahedrites, 120 octahedron ,&, 16 octicosahedric polytope, 71 omnicapping, 54 opposite cut, 11 oriented genus, 38 oriented matroid, 148 outerplanar graph, 14 oxifloride AgTOSF, 102 paracelsian BaAl2SizO8, 90 partial subgraph, 75 path P,, 2 path-metric d ~ 4 , Penrose tiling, 87 pentacle, 39 pentagonal rotunda, 63

174

Scale Isometric Polytopal Graphs

pentagram, 39 pentakis, 54 pentalene, 78 perfect matching, 2 perovskite ( A B X 3 ) ,101 Petersen graph, 142 pinwheel tiling, 89 plane graph, 10 Platonic solids, 16 polar zonohedra P z ( m ) , 147 polonium Po, 103 polycyclic aromatic hydrocarbons, 78 polyhedron, 15 polytopal graph, 6 preferable fullerene, 25 projective plane, 38 quadriliage, 151 quasi-(r, 3)-polycycles, 77 quasi-embedding, 153 quasi-medial polyhedra, 121 quasi-regular n-polytope, 16 radar-discrimination distance, 45 realizable oriented matroid, 148 regular n-polytope, 16 regular compounds, 39 regular maps, 37 regular partition ( r q ) ,76 regular skew polyhedra, 38 regular star-honeycombs, 40 regular-faced n-polytope, 16 regular-faced polyhedra, 63 rhombic dodecahedron RhDo, 149 rhombicicosahedron, 69 rhombicosidodecahedron R I D o , 63 rhombicuboctahedron Rcbt, 63 root lattices, 107 root system Es, 71 Schlafli notation, 36 Schlafli graph G(221), 158 Seidel switching, 140 selenide Pd1-rSels, 102 semi-regular n-polytope, 16 semimetric, 3

Shrikhande graph, 142 Siamese dodecahedron, 63 silicide ThSiz, 102 silicide u3si2, 101 simple n-polytope, 15 simplex as, 16 simplicial n-manifold, 160 simplicial complex, 160 size s ( d c ) , 6 skeleton G ( P ) ,6 snub APrismb, 119 snub 24-cell, 71 snub cube, 45, 46 snub disphenoid, 63 snub dodecah., 45, 46 sodalite, 101 sphenocorona, 64 sphenomegacorona, 70 sphere S2, 75 spherical wavelets, 60 star-polytope, 35 stella octangula, 39 stellated k-gon, 48 stellation, 54 strain energy, 31 strongly regular graph, 141 suspension VG, 3 terphenyl, 78 tetrakis, 54 Tikhonov cube, 21 tile-homogeneous, 83 tiling, 16 top graph, 148 torus, 38 triacontahedron, 147 triakis, 54 triangle inequality, 3 Triangular hebesphenorotunda, 69 triangulation, 12 triaugmented Prisms, 64 tridiminished icosahedron, 70 twisted Rcbt, 44 twisted RhDo, 100 twisted chamfered cube, 126 twisted cuboctahedron, 130

Index

uniform polyhedra, 39 vertex figure, 16 vertex-homogeneous, 83 vertex-split (34), 76 vertex-split (35), 76 vertex-transitive, 72 Voronoi partition, 19 Voronoi polytope P ( z ) ,19 Wiener number, 4 zeolit Linde A, 102 zeolite rho, 101 zinc Z n , 103 zone, 5 zonotope, 148

175