Defining the Dimension of Isometric Graphs,
Local Honecomb dimension, Polytopes,
Kissing Numbers and
Dimensions of Discretized Spaces.



[Home Page] [Physics Page] [Dynamical Dimension] [Graph Counting]


Let G be an Isometric graph. As the dimension of G increases, so should its number of lines. If there are no lines, the dimension of the G should be the dimension of a point, i.e., 0. Consider the other extreme case of the complete isometric graph with n vertices, this is equivalent to the regular simplex in (n-1) dimensions. The number of lines coming into any vertex of the complete graph with n vertices is also (n-1). There will be, however, isometric graphs where the number of lines into a vertex is not uniform over the graph, and it would appear that this is not a suitable definition.

Instead of confronting the definition of isometric graph dimension head on, or globally, consider that dimension is a local concept of a graph, in fact, local to a vertex. Define the dimension at a vertex to be the number of lines attached to the vertex. This commonly called the "weight of the vertex". The dimension of G can then be defined as the average weight of it vertices.

The following is well known. Let G be any graph and v a vertex of G, w(v) the weight of v, n, the number of vertices, and p the number of lines in G. If we sum w(v) over all v in G, the lines of G have all been counted exactly twice:



        SUM(v) w(v)  =  2p


The dimension of an isometric graph is then defined as the average of the w(v)


        dim( G )  :=  (1/n) SUM(v) w(v)  =  2p/n


This definition is sensible for the extreme cases above: A graph with no lines has dimension zero. An equilateral triangle (complete isometric 3-vertex graph) has dimension 2. A regular tetrahedron (complete 4-vertex graph) has dimension 3. The graph


                  o - o - o
                  |   |   |
                  o - o - o

has dimension (2)(7)/6 = 7/3, a number closer to 2 than to three. The graph is bendable at the middle vertical of the digaram, and can sit in a 3-dimensional space, and so the dimension definition is sensible even for intermediate graphs. Construct a few and test the dimension for sensibility.

The definition is sensible for the physical use for which it is intended: the dimension is directly proportional to the number of lines, and presumably, the number of lines is a measure of the interaction energy.

The isometricity assumption is necessary for (2p/n) to make sense as a dimension. Take a regular tetrahedron. If we can shorten the 3 legs attached to one of the vertices, the vertex in question can be pushed down into the plane containing its opposing triangle and make it a planar graph. The isometricity assumption prevents this kind of dimensional degeneration.


But a good general dimension function is not quite so simple as one can see by examining the graphs formed by the regular polyhedra of Euclidean 3-space. [Sommerville 1958]



   The regular tetrahedron (as considerd above) has
        4 vertices
        6 lines
        4 triangular faces

        3 lines meet at vertex

   The calculated dimension is then 2(6)/4 = 3
   
   The regular hexahedron (cube) has
        8 vertices
       12 lines
        4 square faces

        3 lines meet at vertex

   The calculated dimension is then 2(12)/8 = 3

   The regular octahedron has
        6 vertices
       12 lines
        8 triangular faces

        4 lines meet at vertex

   The calculated dimension is then 2(12)/6 = 4

   The regular dodecahedron has
       20 vertices
       30 lines
       12 pentagonal faces

        3 lines meet at vertex

   The calculated dimension is then 2(30)/20 = 3
   
   The regular icosahedron has (dodecahedron reciprocal)
       12 vertices
       30 lines
       20 triangular faces

        5 lines meet at vertex

   The calculated dimension is then 2(30)/12 = 5

So clearly, the definition (2p/n) does not give a sensible dimension for the octahedral graph nor for the icosahedral graph.


Let's look at the analogous regular polytopes in a Euclidean space of 4 dimensions. There are 6 regular polytopes in Euclidean space of four dimensions. [Sommerville 1958]



   The regular simplex or 5-cell (self reciprocal)
        5 vertices
       10 lines
       10 triangular faces
        5 tetrahedra
   The calculated dimension is then 2(10)/5 = 4

   The regular orthotope or 8-cell
       16 vertices
       32 lines
       24 square faces
       8 cubes
   The calculated dimension is then 2(32)/16 = 4

   The reciprocal of the regular orthotope or 16-cell (octahedron analog)
        8 vertices
       24 lines
       32 triangular faces
       16 cubes
   The calculated dimension is then 2(24)/8 = 6

   The self-reciprocal 24-cell
       24 vertices
       96 lines
       96 triangular faces
       24 octahedra
   The calculated dimension is then 2(96)/24 = 8

   The 600-cell
      120 vertices
      720 lines
     1200 triangular faces
      600 tetrahedra
   The calculated dimension is then 2(720)/120 = 12

   The 120-cell (reciprocal to the 600-cell)
      600 vertices
     1200 lines
      720 triangular faces
      120 dodecahedra
   The calculated dimension is then 2(1200)/600 = 4


So, only three out of the six regular polytopes in four dimensions present a good dimension in (2p/n).


In two dimensions, the number of regular polygons is countably infinite. In three dimensions, there are 5 regular polyhedra (the platonic solids). In four dimensions there are 6 regular polytopes. If one expected that as the number of dimensions increases, the increasing richness of the space would allow for more and more regular polytopes, one would be quite wrong. For a Euclidean space of 5 or more dimensions, there are exactly 3 regular polytopes. These are the higher dimensional analogs of the tetrahedron, the orthotope (cube), and the reciprocal of the orthotope. The tetrahedron generalizes to the



   n-dimensional regular simplex with

        (n+1) vertices
        n(n+1)/2 lines.

   The calculated dimension

        2n(n+1)/2(n+1) = n,

   as desired.





   For the orthotope or n-cube, there will be

        2^n      vertices
        n2^(n-1) lines
                 square faces
                 cubes
           ...

        2n(n-1)  (n-2)-dimensional hypercubes
        2n       (n-1)-dimensional hypercubes

   The calculated dimension

        2 n2^(n-1) /2^n  =  n,

   as desired.





   For the reciprocal of the n-cube, there will be

        2n      vertices
        2n(n-1) lines

              ...

        n2^(n-1)  (n-2)-dimensional hypercubes
        2^n       (n-1)-dimensional hypercubes

   The calculated dimension

        2 2n(n-1) /2n  =  2(n-1),

   NOT as desired.





   In n dimensions, where n > 1,  The  regular simplex and the
   regular orthotope present a correct dimension (2p/n) = n



The simplex and the orthotope in any dimension, in some intuitive sense, are the simplest of regular polytopes. What is there about the other polytopes that makes the value of (2p/n) a number higher than n? If one excludes the more complicated polytopes from consideration what kind of contraint is being imposed on the set of vertices? Is it a toplogical constraint? Euclidean spaces En, can always be honeycombed by orthotopes; for n > 4, this the only possible honeycomb. Elliptic spaces (positive curvature) with n > 4 have regular honeycombs by simplicies, orthotopes and orthotopic reciprocals while hyperbolic spaces for n > 4 have no regular honeycombs at all!

If one wishes to consider a regular lattice type of structure of the kind induced by the existence of a finite an fundamental tolerance or "minimal interstitial distance" between points of a set, and also wants the dimension of the set to be free floating and essentially dependent on a density of lines connecting the set points, then a good choice for interstitial structure (an assumption) is that of an orthotopic honeycomb. This has the additional freedom of allowing spaces of positive curvature as well as flat Euclidean spaces. In this kind of context it seems that there is no hope for hyperbolic spaces.

In examining the regular polytopes for various dimensions, the specialness of dimension 4 is hard to miss, it being the dimension with the richest structure and greatest number of possibilities. The specialness of dimension 4 spreads itself, almost mystically throughout the body of mathematics. Many structural theorems of topology, differential geometry have general proofs for all dimensions greater than 4 which fail for dimension 4; while dimensions 2 and 3 are either trivial or easy, similar special cases for dimension turn out to be rather more complicated, ultimately showing once again the peculiar richness of that dimension. Does that have anything to do with the fact of the experienced dimension of our spactime existence happens to be 4? Perhaps, but, I don't know any good physics that can show just how. One shouldn't get too carried away with fourness of our spacetime of existence: when galaxies become the points of a set, the fractal dimension looks more like 2, and if superstring theories turn out to be correct, then on a small scale, the local dimension of the "space of existence" turns out to be 10, 11 or possibly higher. Seeing that the dimension 4 may not always be the dimension of the space of existence actually gives some hope for a physical explanation of how it happens that at a certain scale between elementary particles and galaxies spacetime looks to be four dimensional.


Another approach to dimension is by way of kissing number. The kissing number in n dimensions is the answer to the question: what is the maximal number of n-dimensional hyperspheres of radius r that can be simultaneously tangent to, i.e., "kissing", a central n-dimensional hypershere of radius r.

The configuration, hence the problem is invariant under a scaling transformation, so one can take r=1 with no loss of generality. Unfortunately, to my knowleged this problem has not been solved generally for arbitrary n, though there are bounds and asymptotic formulae for the kissing number for any n. The kissing number concept has clear and close connections with crystalline structure or more mathematically, lattice structures in n dimensions, coding theory etc., but not so close a connection with graphs. Yet, there is a close connection with regular simplexes.



   From  [Conway 1993]  Table 1.5 p.23
   of known kissing numbers for low dimensions:
   (Ranges reflect different possible lattice structures)
      
      Dim        Kissing number range of possible values
       1                2
       2                6
       3                12
       4                24-25
       5                40-46
       6                72-82
       7                126-140
       8                240
       9                306-380
      10                500-595
      11                582-915
      12                840-1416
      13                1130-2233
      14                1582-3492
      15                2564-5431
      16                4320-8313
      17                5346-12215
      18                7398-17677
      19                10668-25901
      20                17400-37974
      21                27720-56952
      22                49896-86537
      23                93150-128096
      24                196560
   
   The general kissing number T_n in n dimensions is bounded by
   
   2^( 0.2075n( 1 + o(1) ) )  =<  T_n  =<  2^( 0.401n( 1 + o(1) ) )
   
   NB log2( 3 ) = 1.58496
   
   If T_n is estimated by
   
           T_n  =  3*2^( n-1 )
               =  (2^(log2 3))*(2^( n-1 )
               =  2^( n - 1 + log2(3) )
               =  2^( n + 0.58496 )
   
   which exceeds the known upper bound.
   
   If n = 2^m for the Barnes-Wall lattice BW_n, the kissing
   number is exactly known to be
   
                     m
           T_n  =  PRODUCT (2^k + 2)
                    k=1
   
               approx= (4.768...) 2^(m(m+1)/2)
   
               =  2^( 0.5 log2( n ) (log2 n + 1))
   



If the consideration is a lattice packing (periodic and space filling), then the highest possible density packing in four dimensions is the "checkerboard lattice" D_4 in which each sphere has exactly 24 neighbors. See [Conway 1993] pp. 9-11, for the numerical details.

The Leech Lattice LAMBDA_{24} also has connections with hyperbolic geometry and the "monster group". If the centers of the neighboring spheres of an arbitrary sphere in D_4 are points relative to a center are quantized, a linear space of 24 dimensions is generated, which is an underlying space suitable for the construction of the Leech lattice. The Leech lattice then exists in the real subspace of a complex space of 24 dimensions, not in a projective Hilbert space but rather in an affine space with a periodic structure.

One must somehow allow a proper Quantum Theory to transcend the restriction to projective spaces, and thus apparently allow that probability may not be conserved. Instead of a unitary group acting effectively on a projective sphere, consider a nonunitary group acting on complex hyperbolic hypersurface. This hyperbolic space can be mapped analytically by a "Poincare transformation" to the interior of a unit ball. The action of the group preserves pseudonorm values. Pseudonorm takes value 0 on the unit ball boundary ("lightcone").

Assuming they exist, how do similar constructions in other dimensions behave?

If one thinks of physical spatial "points" with an isotropic indetermancy limited by the planck length, points become more like spheres with radius equal to the planck length. That these spheres might be considered as small black holes within a spacetime foam in accordance with the original ideas of John A. Wheeler has been suggested by several authors in the current literature.

The idea of kissing number and the dimensionality of space then come together in a physical way.


                    ------- TO BE CONTINUED ------




[Top of Page] [Dynamical Dimension] [Graph Counting]


Home Page
Physics Page

Email me, Bill Hammel at
bhammel@graham.main.nc.us
READ WARNING BEFORE SENDING E-MAIL

The URL for this document is:
http://graham.main.nc.us/~bhammel/PHYS/grafdim.html
Created: 1997
Last Updated: May 28, 2000
Last Updated: January 25, 2012
Last Updated: