Coxeter graphs

What Are Coxeter Graphs?

It is a subfamily of finite connected graph with edges labeled by numbers between 3 and ∞ (inclusive). Shape variations among family members are limited so all can be presented visually on a single page. There is no obvious characteristic that distinguishes these shapes from other labeled graphs. Such characteristic does exist but can be easily formulated only in terms of entities related to these graphs (see below) and not in terms of the graphs themselves.

How is Coxeter Graph Drawn?

Exact Graph Representaion

Using following conventions

3-labels are omitted
Every combinatoric symmetry should be realizable as a plane Euclidean symmetry
Replacing a label by a numeric range represents a collection of graphs with labels in that range

Schematic Representation

This is a notation which uses an edge drawn to be easily distinguishable from any other edge (for example by using a different length, stroke or both) which stands for an un-labeled chain of variable length. The span of the chain is inferred from a range of node counts placed next to the graph. These conventions lead to a mixture of exact and schematic graphs shown in the adjacent table.

Symbolic Representation

A symbolic representation is just a way of naming the schematics obtained above. This is done so that the graphs can be easily referenced in a written text. Each graph in the table is associated with a letter in the A-I range. A letter is placed in a column to the left of the shape it is associated with. In many cases the same letter is used by more than one shape. One of the shapes is associated with a pair BC so it spans 2 rows. For any row in the A-G range the associated shapes are further subdivided into two groups, shown in 2 columns entitled: Spherical and Flat. That subdivision is again a property of entities related to the graphs rather then of the graphs themselves. The symbols from the A-I range are used to name the graphs from the Spherical column. To name the Flat graphs we use a decorated-Latin range Ȧ-Ġ. With these conventions, any Coxeter graph, except for the I-type, can now be named using a letter symbol with a numeric subscript. That subscript indicates the node count for Spherical graphs and 1 less than the node count for the Flat graphs. An I-graph labeled with p is symbolized by I₂(p). We found it useful to depart from a traditional way of listing the rows in alphabetic-type order. Instead, we order by the value of the largest label present and then by the node-count.

Special Node

A node of a Flat graph is called Special if removing it (along with its adjacent edges) produces the Spherical graph from the same row.

For the loop-graphs Ȧ_3-∞ every node is special
For other graphs, a Special node must be an end-node but, in general, not every end-node is Special

Any Flat graph has one (and up to an equivalence only one) Special node. The symbol of the Spherical graph obtained by removal of the Special node is obtained by erasing the decoration from the letter-symbol of the Flat graph (with an understanding that for Ḃ_p and Ċ_p, where p ≥ 3, erasing the decoration results in BC_p).

Dynkin Ordering

An ordering of a graph is a full order relation among its nodes: for any node pair {a, b} either a ≤ b or a ≥ b holds. However if both conditions hold it does not necessarily mean that a and b are the same. (Similar relation is introduced when numbers are compared by their absolute values.) One way to show an ordering in a graph is by placing an inequality symbol on the join in cases where only one holds. The effect of placing the ≥ symbol on a join a—b can be approximated using an arrow symbol a → b. A Dynkin ordering of a Flat Coxeter graph is one which satisfies

An edge labeled 4 or 6 is replaced by an arrow
Special nodes are maximal

Every Flat graph can be Dynkin-ordered and in one-way only. In such graph, the arrows tell us the location of the special nodes without a need to examine the adjacent Spherical graph.

Reciprocal Graphs

If we remove a special node from a Flat graph, its Dynkin ordering will induce an ordering of nodes on the resulting spherical graph. A pair of flat graphs is called reciprocal if the corresponding Spherical graphs are identical but the induced orderings are reversed. Ḃ_n and Ċ_n are reciprocal (for n ≥ 3). Any other Flat Coxeter graph is reciprocal of itself.

Alternative Symbolic Representations

When looking up this topic in the literature you may find minor variations to the conventions presented here.

Tilde

A diacritic, almost universally used to indicate a Flat graph is the tilde (~). Unfortunately this diacritic is available only for certain letters (e.g. Ã, Ñ) and not for the whole A-I range.

Alternative Lettering

The I₂()-notation is an alternative name for any Spherical graph with node-count 2 and İ₂() for any Flat graph with node-count 3. Sometimes the 1-node graph A₁ and the corresponding Flat graph Ȧ₁ are placed in the I-row and denoted by I₁ and İ₁ respectively. Ḃ₂ is often used as an alias to (or a replacement for) Ċ₂

Dynkin Diagrams

Some people call Dynkin Diagram a Spherical diagram in the A-G range with an ordering induced from a (unique) Flat graph. That Flat Graph is then called the Completion of the Dynkin diagram. For every such Spherical graph, except for BC, there is only one way to convert it to a Dynkin diagram and the same letter is used to symbolize both. There are 2 ways to convert a BC graph into a Dynkin diagram. The ordering can be derived from either Ḃ or Ċ and these diagrams are hence denoted by B and C respectively. When showing Dynkin diagrams and their completions, an edge carrying label 4 is indicated by a double-line and that carrying label 6 by a triple-line.

Relation of A-I Graphs to Polytopes

(See Concept of Polytope). A polytope is a movable geometric object: it can flip across its boundary hyperplanes. Any motif drawn inside a polytope can be propagated in this way to cover the entire hyperspace. If the resulting pattern has no gaps or overlaps and it does not depend on the order of flipping then the polytope is called tessellating and the resulting partition of the Hyperspace - a tessellation. For example a regular hexagon is not tessellating, but a regular triangle is. A sum of 2 tessellating Polytopes is again tessellating. A Solid-angle at a vertex of a tessellating polytope is tessellating. Tessellation is also a result of partitioning the Hyperspace using bounding hyperplanes of the Polytopes resulting from the flips. The A-I graphs from the Coxeter table are related to Angle graphs of tessellating Polytopes as follows: A dihedral angle of a tessellating polytope has to be of the form π/n where n ≥ 2. For such polytopes it is convenient to use n as the Angle-graph label, to draw only the edges where n ≥ 3, and to skip labels with n = 3.

Ċ₃ tetrahedral tile shown as 1/48-th portion of a unit cube. Red arrow is the axis of a single 180°-rotational symmetry. Note that the base of Ċ₃ is a Ċ₂ triangular tile which is a 1/8-th portion of a square. This suggests that a d-dimensional Hypercube can be partitioned into (2*1)*(2*2)*(2*3)...(2*d) = 2^d*d! copies of a Ċ_d simplex.
Wireframe of Ċ₃ showing dihedral angles.
Angle graph of Ċ₃ obtained by transposing labels on the opposite edges and then switching to the Coxeter notation. Both end-nodes are special. They correspond to the vertices at the center and at the corner of the cube. Standard, planar representation of the Ċ₃ graph is a flattening of the this shape. The 2-fold symmetry of the flat Ċ₃ graph comes from the 180°-rotational symmetry of the tile.

If W⊕P₁⊕P₂⊕ … ⊕P_n is a maximal decomposition of P then P is tessellating precisely when the Angle graph of each P_i is one of the A-I graphs. Flat graphs correspond to Simplices and Spherical graphs to Simplicial Angles. In particular, the numeric subscript used in the symbolic representation is the dimension of the Polytope. A special node of a Flat Coxeter graph is a Hyperface which lies opposite to a special (pointy) vertex of the Simplex. Hence the Spherical graph adjacent to a Flat graph is simply the graph of the Solid angle at a Special vertex.

What Does Dynkin Ordering Represent?

For any bounded tessellating polytope, the collection of bounding hyperplanes of its tessellation is a finite union of families composed of parallel Hyperplanes. These families are called Pencils. Adjacent Hyperplanes in a Pencil are at a fixed distance form each other. The ratio of Hyperplane distances for any pair of non-orthogonal Pencils is related to the dihedral angle between pairs of hyperplanes from the 2 pencils:

Dihedral Angle	Distance Ratio
π/3	1
π/4	√2
π/6	√3

Dynkin ordering of a Flat graph is a result of using the hyperplane distance to compare Hyperfaces. One hyperface is bigger than another if its Pencil-distance is smaller.

Hyperplane Distance and Simplex Altitude

The hyperplane distance is a whole multiple of the simplex altitude perpendicular to the hyperplane. If the summit of the altitude is a special vertex then the hyperplane distance is equal to the altitude. Dynkin ordering and the table of distance ratios allow us to derive all hyperplane distances once a single one is known. Inspecting the Coxeter table we see that

A, D, E - have equal hyperplane distances.
For B, C, F - there are 2 hyperplane distances. Their ratio is √2.
For G - there are 2 hyperplane distances. Their ratio is √3.

Bragg Equation

When a beam of light bounces off 2 parallel semi-transparent mirrors then the travel distance for the portion bouncing off the behind-mirror is greater than that for the beam bouncing off the front-mirror. If the beam's path is perpendicular to the mirrors, that extra distance is 2d where d is the distance between the mirrors. In general, that extra distance will be 2d*sin(θ) where θ is the beam's glancing angle.

An extra distance means that the wave amplitudes of the reflected beams will be shifted and will amplify each other only in special cases when the extra distance is a multiple of the wave length λ. This leads to the condition

2d*sin(θ) = n*λ, n = 1, 2, ...

known as the Bragg Equation. As sin(θ) ≤ 1 this condition occurrs only when λ ≤ 2d. It is amazing that such a simple trigonometric formula has yielded its author the Nobel prize. Physics is not about formulas but about insight into what they represent.

Bragg Angles for element W (Tungsten)

Speculations that matter contains repeating layers goes back to antiquity but the presence of the angles θ predicted by the Bragg equation was not noticed until early 20th century when beams with sufficiently small λ (X-rays) became available. Here is an example of the θs for a metal Tungsten when λ = 1.54Å:

#	θº	d/n(Å)	n
1	20.15	2.23	1
2	29.15	1.58	1
3	36.60	1.29	1
4	43.55	1.12	2

The d/n values for rows #1-3 correspond to n = 1 so these are actual interplanar distances. The d-value for rows #1 and #4 is the same: the 2 angles correspond to values 1 and 2 of n. The ratio of d-values for rows #1 and #2 is √2. The row #3 will not be analyzed here. It is listed just to show that other pencils (not necessarily tessellation pencils) may produce Bragg's angles. Presence of a √2 ratio suggests that the distribution pattern of Tungsten is of type B or C. The combined mass of Tungsten present in a unit cube equals the mass of 2 W-atoms (see the calculation). This is consistent with a BCC-pattern formed by a stack of cubes with W-atoms at the corners and at the center of each cube. The center contributes 1 atom mass and each of the 8 corners contributes 1/8-th of the atom mass. Such pattern is a result of a Ċ₃ tessellation with W-atoms placed at the 2 special vertices of the tetrahedral tile. The interplanar distance 1.58Å is half the length of cube's edge and the interplanar distance 2.23Å is half the length of the diagonal of the cube's square face. If we imagine Tungsten atoms to be small ball-bearings lined up next to each other along the cube's diagonal (which length is 2*1.58*√3Å) then the diameter of each ball-bearing will be 1/2 the length of the diagonal or 1.58*√3 = 2.74Å and the radius will be 1.37Å. This value is known as the Metalic Radius of a Tungsten atom. Note that in this arrangement, the ball-bearings at adjacent corners of the cube will not touch. A polyhedron superscribed over the centrall ball-bearing and passing through the 6 points of contact on its surface will be an octahedron. The interection of this octahedron with the unit cube is called a Truncated Octahedron - its surface consists of 8 hexagons and 6 cubes. This costruction leads to a partition of space known as a Bitruncated cubic honycomb. This honeycomb does not fit into our definition of a tessalation because 2 polyhedra which share a hexagon are related by a mirror flip followed by a 60° rotation.

Density Calculation for Tungsten (W)

The density of Tunsten is 19.3g/cm³ and, based on the X-ray analysis, the volume of a unit Tungsten cube is (2*1.58*10^-8)³ =31.6*10^-24cm³. Periodic table gives us a molar mass of 183.86amu, so an atom of Tungsten weighs (183.86/N_A)g where N_A is the Avogadro number. If Z is the number of atoms per cube, each cube weighs Z*183.86/6.02*10²³ = Z*30.5*10^-23g. From Z*(30.5/31.6)*10=19.3 we conclude that Z = 2.

How are Polytopes from Reciprocal Graphs Related?

Let us transform each Pencil by changing its Hyperplane distance from d into some other value d'. The resulting family of Hyperplanes partitions the Hyperspace into Polytopes. In general, these Polytopes will not be congruent so this partition may not be a tessellation. Let d₁ and d₂ be the distances for any pair of non-orthogonal Pencils and d'₁ and d'₂ be the new distances. If the new partition is a tessellation then, in view of the angle-ratio rule (and since there is no change in the dihedral angles) d'₁/d'₂ is either d₁/d₂ or d₂/d₁. In view of this, it is reasonable to expect that when d' = 1/d for all Pencils then the new partition will again be a tessellation. This happens to be the case; the new tessellation is called the Reciprocal to the original. The reciprocal relation among Simplices corresponds to the reciprocal relation among the Ȧ-Ġ graphs. In particular, the Simplices Ḃ_n and Ċ_n for n≥3 are reciprocals of each other. For Ċ₂ and for any type other than Ḃ or Ċ a Simplex and its reciprocal are similar.

Reciprocal Tessellation and X-Ray Crystalography

If we want to examine ralative positions of multiple tessellation pencils using X-rays we need to reformulate the Bragg equation in a coordinate-free way. Let s be a vector along the path of the incident beam and s' be a vector along the path of the reflected beam, both of length 1/λ. Consider now the vector difference Δs = s' - s. Clearly, Δs is orthogonal to the mirror plane and, taking Bragg into account, its length will be λ/d. If we collect all such Δs for different beam directions we will end up with a vector star, namely the root system of the reciprocal tessellation. From the reciprocal root system we get the direct root system, simply be inverting vector magnitudes and from the Dynkin diagram of the direct root system we can reconstruct the Coxeter diagram of the tessellation. The calculations used to reconstruct the tessellation from bended X-rays appears quite different from those performed when our brain determines the shape of an object from rays of light reflecting from the surface. Both are however equally valid. The way bats analyse reflected sound waves is also different but they find their way in a forest at night. It is an exagerration to say that X-ray analysis shows us atomic arrangements. We still need to figure out the locations of individual atoms (or ions) within the polyhedron. That is accomplished by other means, such as calculations of the density or the atomic radius,

Other Patterns

So far the tiles in our pattern were related by a sequence of reflections across faces. However other types of repeating patterns, both natural and man-made, do exist. (See the list of 17 bounded Wallpaper Patterns). This section extends Coxeter approach to cover these additional types.

Even-odd Patterns

Let us choose a motif M₀ and propagate it using some tile, but apply it only when the propagation includes an even number of of flips. Let us repeat the process using another motif M₁ but apply it only when the propagation includes an odd number of of flips. If we group together pairs of face-adjacent tiles we obtain a partition of Hyperspace into congruent polytopes each painted with an indentical combined motif.

Sub-Tiles

Coxeter approach can be applied to any bounded polytope but instead of arbitrary hyperplanes we consider only those which are symmetries of the polytope. Such hyperplanes pass through the center of the polytope. Hence a polytope within polytope is just like a solid angle around the center except that it is viewed as a portion of the polytope's surface. If the solid angle is tessellating it will define a tessellating sub-polytope of the polytope. If the main polytpe tessellates Hyperspaces, then the sub-polytope will do so as well. This may produce new types of tessellations, say, when we use even-odd tessellation with the inner tile and a standard mirror-tessellation with the outer tile.

Revisiting Tungsten

We have succeeded in reducing a Tungten pattern to 2 special corners of a Ċ₃ tile. But this motif conforms to the 2-fold symmetry of the Ċ₃ tile. This indicates that the true Tungsten tile is half of Ċ₃ which has a shape of a distorted, triangular prism. The motif will be a single atom at the corner. However, the replication across the quadrileter face opposite to the atom is no longer a reflection but a 180° rotation relative to the diagonal. Replications around the atom are standard mirror reflections and enclose the atom by a truncated octahedron - cell of a tessalating honeycomb.