Abstract
Starting from the working hypothesis that both physics and the corresponding mathematics have to be described by means of discrete concepts on the Planckscale, one of the many problems one has to face in this enterprise is to find the discrete protoforms of the building blocks of continuum physics and mathematics. A core concept is the notion of dimension. In the following we develop such a notion for irregular structures like (large) graphs and networks and derive a number of its properties. Among other things we show its stability under a wide class of perturbations which is important if one has ’dimensional phase transitions’ in mind. Furthermore we systematically construct graphs with almost arbitrary ’fractal dimension’ which may be of some use in the context of ’dimensional renormalization’ or statistical mechanics on irregular sets.
Dimension Theory of Graphs
and Networks
Thomas Nowotny Manfred Requardt
Institut für Theoretische Physik
Universität Göttingen
Bunsenstrasse 9
37073 Göttingen Germany
1 Introduction
In two recent papers ([1],[2]) we developed a certain framework in form of a class of ’cellular network dynamics’ which are designed to mimic the dynamics of the physical vacuum or spacetime on the Planckscale. In doing this our working philosophy was that both physics and the corresponding mathematics are genuinely discrete on this primordial level. The continuum concepts of ordinary spacetime physics are then supposed to emerge from certain discrete patterns via a kind of ’renormalization group process’ on the much coarser scale of resolution given by the comparatively small energies of present day high energy physics. It is one of our aims to find these discrete protoforms.
A crucial concepts in this context is a version of ’intrinsic dimension’ of such discrete irregular networks which geometrically are graphs. This concept should be defined in an intrinsic way, without making open or implicit recourse to continuum concepts whatsoever or kind of an embedding dimension, as we want to understand, among other things, what properties actually are encoded in a notion like dimension on the most fundamental physical level. On the other side, we want to know how the continuum concept of dimension, which is to a large extent of an a priori mathematical viz. geometrical origin, comes into being, starting from an intrinsic property of discrete irregular systems like e.g. general, typically very large and almost randomly organized graphs which are supposed to encode the ‘geometrodynamics’ of spacetime on Planck scale.
In section 5 of [1] we introduced such a concept which seems suitable to us and which characterizes to some extent the ’wiring’ of the network. At the time of writing [1] we scanned the literature accessible to us in vain for similar ideas and got the impression that such lines of thought had not been pursued in this context. Some time later we were kindly informed by Thomas Filk that a similar concept had been studied by himself and a couple of other physicists (see [3],[4],[5] and further references given there) in an however slightly different context. (They typically investigated the simplicial resolution of continuous manifolds and their numerical treatment via Monte Carlo simulations).
On the other side, at least as far as we can see, this concept had not been systematically developed and many questions of principal interest remained open. In the following we attempt to formulate and solve a couple of problems which naturally emerge in this context, more specifically we embark on developing a full fledged mathematical machinery around this concept which then may be applied to quite diverse fields of physics and mathematics.
Among other things we clarify the somewhat hidden relations to certain parts of ’fractal geometry’ and construct graphs with almost arbitrary ’fractal dimensions’ along these lines. Furthermore we show that the two at first glance almost identical definitions of dimension we introduced in [1] are actually different on certain ’exceptional’ sets while, on the other side, being identical on ’generic’ sets. This is a phenomenon also well known from the various notions of dimension in fractal geometry.
While the first one, which we will call ’internal scaling dimension’ in the following (it is the version which occurs under this label in e.g. [3]), appears to be more natural from a mathematical point of view, the second one, on the other side, is in our opinion more fundamental as far as the encoding of physical data as e.g. the wiring of the graphs under discussion is concerned. For this reason we call it the ’connectivity dimension’ as it reflects to some extent the way the node states are interacting with each other over larger distances via the various bond sequences connecting them.
Another interesting point is the structural stability of such a concept under local and extended perturbations. We showed e.g. that if we start from a given graph with a dimension this value remains stable under a rather large class of bond insertions. As a consequence one has to add bonds between increasingly distant nodes in order to change the dimension of a graph. This is of some relevance if one wants to invent dynamical mechanisms which are designed to trigger dimensional phase transitions.
Presently we pursue several lines of research concerning applications in quite diverse fields of physics and mathematics as e.g. noncommutative geometry, dimensional phase transitions (see also [2]), statistical mechanics and functional analysis.
2 Graph Theoretical Definitions
In this section we give the necessary definitions to define the internal scaling dimension of graphs. Most of the notions are well known in graph theory but we nevertheless want to repeat them to avoid any confusion concerning the exact definitions.
First of all we need to define an undirected simple graph. This will be our primary object of interest. {definition}[Undirected Simple Graph] An undirected simple graph consists of two countable sets and . We denote the elements of as with , . The elements of are denoted as , . The set is isomorphic to a subset of and the existence of implies the existence of . {remark} Many mathematicians use a slightly different notation. They denote (nodes) as (vertices) and (bonds) as (edges). In the following will always be an undirected simple graph. We also need the notion of the degree of a node . {definition}[Degree] The degree of a node is the number of bonds incident with it, i.e. the number of bonds which have at one end. We count and only once as we interpret them as the same bond. We assume the node degree of any node of the graphs under consideration to be finite. The next step is to define a metric structure on . To this end we need to define paths in and their length. {definition}[Path] A path of length in is an ordered tuple of nodes , , with the properties and . {remark} A single node is a path of length . This definition encodes the obvious idea of a path in allowing multiple transversals of nodes or bonds. Jumps across nonexistent bonds and stays at a single node are not allowed. Sometimes this notion of a path is also called a bond sequence.
Slightly different definitions are also quite common. The path often is restricted to contain any bond in at most once. Sometimes even the repetition of nodes in a path is excluded. We will call a path with this property – that all are pairwise different – a simple path.
The concept of paths on now leads to a natural definition for the distance of two nodes and , namely the length of the shortest path connecting and . {definition}[Metric] A metric on is defined by
(1) 
in which denotes the length of . That this actually defines a metric is easily established. Finally we need the notion of neighborhoods which follows canonically from the metric. {definition}[Neighborhood] Let be an arbitrary node in . An  neighborhood of is the set . {remark} The topology generated by the neighborhoods is the discrete topology as should be expected from the construction and the discreteness of graphs. We will denote the surface or boundary of the neighborhood as , and the cardinality of and as and respectively.
3 Dimensions of Graphs and Networks
Now we have all the tools to define the central notion of this paper, the notion of the internal scaling dimension of . {definition}[Internal Scaling Dimension] Let be an arbitrary node of . Consider the sequence of real numbers is the lower and the upper internal scaling dimension of starting from . If we say has internal scaling dimension starting from . Finally, if , we simply say has internal scaling dimension . A second notion of dimension we want to introduce is the connectivity dimension which is based on the surfaces of neighborhoods rather than on the whole neighborhoods . {definition}[Connectivity Dimension] Let again be an arbitrary node of . We set as the lower and as the upper connectivity dimension. If lower and upper dimension coincide, we say has connectivity dimension starting from . If for all we call simply the connectivity dimension of . One could easily think that both notions of dimension are equivalent. This is however not the case as one definition is stronger than the other which will be shown in detail in 3.2. and define . We say
The internal scaling dimension is rather a mathematical concept and is related to well known dimensional concepts in fractal geometry as we will see in 4.2. The connectivity dimension on the other hand seems to be a more physical concept as it measures more precisely how the graph is connected and thus how nodes can influence each other.
In the following section we want to establish the basic properties of the internal scaling dimension of graphs.
3.1 Basic Properties of the Internal Scaling Dimension
The first lemma gives us a criterion for the uniform convergence of or to some common or for all nodes in . {lemma} Let , be two arbitrary nodes in with . Then and . {proof} Let be the distance of the nodes and . We have
(2)  
(3)  
(4)  
(5) 
Similarly we get .
Another rather technical lemma provides us with a convenient method to calculate the dimension of certain graphs, e.g. the selfsimilar or hierarchical graphs we construct in 4.2. It shows that under one technical assumption the convergence of a subsequence of is sufficient for the convergence of itself. {lemma} Let be an arbitrary node of and let be a subsequence of . There may exist a number such that holds for all . Then and similar for . {proof} Let be an arbitrary natural number. We find a such that . As the sequence is monotone this implies . Therefore we get
(6)  
(7)  
(8)  
(9) 
The same proof holds for . This result is well known in the context of calculation schemes for dimensions in fractal geometry, see e.g. [6].
Naturally one also may ask how the internal scaling dimension behaves under insertion of bonds into . We were able to show that it is pretty much stable under any local changes. We state this in the following lemma. {lemma} Let be a positive natural number and a node in . Insertion of bonds between arbitrary many pairs of nodes (, ) obeying the relation does not change or . {proof} We denote the new graph built by insertion of new bonds into as and accordingly the neighborhoods in as . Being a node in , is also a node in . The restriction on the choice of additional bonds in implies that even if we connect every node with every node in , which is the maximum we are allowed to do, we still can’t get beyond with less or equal steps,
(10)  
(11) 
Because , we immediately get for sufficiently large
(12)  
(13) 
where in the last step lemma 3.1 has been used. The identical result holds for . {remark} Obviously the insertion of a finite number of additional bonds between nodes and with doesn’t change the internal scaling dimension either. Therefore we can slightly generalize lemma 3.1 by changing our requirements to the following. Only bonds between nodes of finite distance and only finitely many bonds between nodes of distance are inserted into to form . Then still has the same internal scaling dimensions and as .
Conclusions.
We have seen that the internal scaling dimension does not depend on the node from which we start our calculation and that under not too strong conditions even the convergence of a subsequence of the relevant sequence is sufficient to calculate and . Furthermore the dimension is stable under local changes in the wiring of the graph. This is a very desirable feature for physical reasons. Furthermore it shows that a mechanism inducing dimensional phase transitions has to relate nodes of increasing distance, i.e. has to change the graph nonlocally. We will illustrate this fact with an example in 4.2.5.
3.2 Relations Between Internal Scaling Dimension and Connectivity Dimension
As already stated above the two concepts of dimension we introduced are not equivalent. In the following lemma we show that the existence of the connectivity dimension implies the existence of the internal scaling dimension and that they then have the same value. {lemma} Let again be an arbitrary node in . In the case that the limit , has internal scaling dimension starting from . {proof} We know that exists and have to show that this implies the existence of . Let and be an arbitrary positive number small enough such that . From the convergence of such that we know that we can find and that the limit is exists with
(14)  
(15)  
(16)  
(17) 
On the other hand we naturally have
(18)  
(19) 
in which . Now we can give a lower bound for the sum on the left hand side and an upper bound for the one on the right hand side by replacing them with integrals.
(20)  
(21) 
With these bounds we get
(22)  
(23)  
Because the arguments of the second logarithm on each side are uniformly bounded for any and , such that , we can find an
(24)  
(25) 
From this we immediately find
(26) 
Inversely, the existence of the internal scaling dimension does not imply the existence of the connectivity dimension. We illustrate this fact with the following example.
We will construct a graph with uniformly bounded node degree, degree of less or equal , which has internal scaling dimension but the connectivity dimension . To this end we construct a “linear graph” in the fashion depicted in figure 1. In the figure is equal to . The main idea of the construction is to let oscillate so much that does not exist any more but we still can have convergence of and thus the internal scaling dimension exists. , i.e. does not exist and even
We choose the numbers such that with some . For technical reasons we choose . With this choice we already fulfill the prerequisite to use lemma 3.1.
Let us denote the “leftmost” node as . All distances will refer to as the origin. The construction is determined by the following requirements. From distance to the graph is a simple string of nodes and from distance to a complete^{1}^{1}1In a complete tree graph every node has maximal degree. nary^{2}^{2}2In a nary tree graph every node has or less children such that the degree of each node is bounded by . tree graph. is chosen to be . This means that we start the nary tree as late as possible to still be sure to surpass our aim of . It is easily established that gets large enough for with some to contain the necessary nary tree. A necessary and sufficient condition for this is
(27)  
(28)  
(29) 
which certainly holds for any with sufficiently large because the exponential function grows faster than any polynomial. The part of the graph where might be to small for the above construction, we choose to be of arbitrary form with .
Now we calculate the internal scaling dimension of the constructed graph. We know
(30) 
where is the additional number of nodes we get because of the usage of complete tree graphs. From the construction principle we know
(31) 
which is a rather crude estimate. Nonetheless we get
(32)  
(33) 
Using lemma 3.1 we get
(34) 
Finally we apply lemma 3.1 and get the dimension starting from any node.
On the other hand we have to consider and of the sequence is trivial because which implies that is concerned we know . As far as the . The
(35) 
with . On the other hand
(36) 
Using (35), (36), , , and , we get after a short calculation that
(37)  
(38) 
But we always have
(39)  
(40) 
Taking this together with (38) we finally get
(41) 
This example shows that we can’t get much information about the behavior of from the existence and value of the internal scaling dimension of . The only always valid assertion is .
4 Construction of Graphs
In the following we want to show how to construct graphs of arbitrary real internal scaling dimension. We also want to investigate the connections between the internal scaling dimension of graphs and the box counting dimension of fractal sets. As will been seen below there is a strong relationship between self similar sets and what we also want to call self similar graphs with noninteger internal scaling dimension.
4.1 Conical Graphs with Arbitrary Dimension
For the sake of simplicity we concentrate our discussion on graphs with dimension . Graphs with higher dimension are easily constructed using a nearly identical scheme.
Let be an arbitrary real number. Now we construct the graph like in figure 2. On level we use a width of boxes. The construction is continued “downwards” to infinity. To calculate the dimension we observe that starting from we reach level after steps. Thus we get with
(42) 
Using lemmas 3.2, 3.1 and 3.1 we see that this graph has internal scaling dimension . If we close the construction horizontally, i.e. introduce bonds between the leftmost and the rightmost nodes on each level we even can achieve a completely homogeneous node degree .

The constructed graph has privileged nodes, the one we denoted as node and its counterpart on the same level.

Locally the constructed conical graph is completely isomorphic to a twodimensional lattice. The noninteger dimension is only implemented as a global property of the graph.
4.2 SelfSimilar Graphs
It is well known in graph theory that it is notoriously difficult to construct large graphs with prescribed properties. It also proved quite difficult to construct graphs with a prescribed (internal scaling) dimension which don’t exhibit the disadvantages of the conical graphs described above. The main idea which solves the problem is to use the well known theory of self similar sets or fractals and their dimension theory. In the following we want to show how this works and that we indeed can construct adjoint graphs to self similar sets which have internal scaling dimension equal to the box counting dimension of the self similar sets.
Given a strictly self similar set in we canonically construct an adjoint graph which also will be called selfsimilar. The construction principle is based on an algorithm to compute the box counting dimension of a selfsimilar set. We will illustrate our proceedings with one main example. We construct a selfsimilar set generated with the open unit square in with lower left corner at the origin and the similarity transforms
(43)  
(44) 
This set is sometimes called Maltese Cross, cf. [7]. The first construction steps are shown in figure 3. For details concerning selfsimilar sets and dimensions of fractals see [6].
4.2.1 Construction Based on SelfSimilar Sets
Let be a strictly selfsimilar set with similarity transforms , , and . The contraction factors of may all be equal, . Now we cover with cubic lattices with closed cubes of edge length , , and replace every cube which has nonvoid intersection with by a node. Nodes will be connected iff the corresponding cubes in the covering cubic lattices have a nonvoid intersection, i.e. have a common corner or edge.
By this construction we get a finite graph for each . The degree of these is uniformly bounded because an dimensional cube can only touch a finite number of neighbor cubes in the cubic lattice. The graph we are interested in is , the graph we get through infinite continuation of our construction. The first steps of this construction scheme for our example are shown in figure 4.

We will see later on, that no problems arise from the infinite continuation of the construction steps.

The selfsimilarity of transfers to in the sense that we can also define an equivalent of the similarity transforms of the selfsimilar set . Details will become clear when we give a selfcontained algorithm for the construction of selfsimilar graphs.

Connected selfsimilar sets produce connected selfsimilar graphs. The inverse is not true in general as our example shows. Here is connected but the self similar set we started with is not.
4.2.2 SelfContained Construction Algorithm
We want to illustrate two different views of a selfcontained construction algorithm for selfsimilar or hierarchical graphs.

Construction by insertion:

We start with a single node, .

is the socalled generator, some finite graph. We denote the number of nodes in as .

We construct from by replacing every node in by the generator and interpret the original bonds in as bonds between some “marginal” nodes of the different copies of . In figure 5 we have drawn the first construction steps of our example.


It becomes clear when looking at examples that the above construction algorithms are equivalent.

The construction is – of course – not unique. The result strongly depends on the choice of the nodes in which carry the bonds of in the first construction or in the second one respectively. In our example all “marginal” nodes of the generator are equivalent because of the symmetry of the generator and therefore the construction is unique.

Seen from the viewpoint of the second construction it becomes clear that the local neighborhood of any node doesn’t change in the course of the further construction. Therefore we can investigate any property of in some with sufficiently large . Thus the infinite continuation of construction steps needn’t worry us at all.

The first construction scheme provides us with the analogon of the similarity transforms of the selfsimilar set. These transforms correspond to the mapping of on where is formed from like some from . Clearly is invariant under this mapping.
As we can see from our example, all three construction algorithms, the selfcontained ones as well as the one based on a selfsimilar set, are equivalent provided the selfsimilar set and the choice of the generator match. Seen in this light we can use all the construction principles simultaneously in our arguments.
4.2.3 Dimension of SelfSimilar Graphs
Now we calculate the dimension of the graphs we get by the above construction using some selfsimilar set . For the sake of simplicity we assume that has a central node in the sense that all “marginal” nodes which carry the “outer” bonds have all the same distance to this node. We further assume that ( the contraction parameter) is a natural number which is true in most of the well known examples of selfsimilar sets and finally that the selfsimilar set produces a connected adjoint graph. Then it is easy to see that starting from node we can exactly reach all nodes of construction step after steps in the graph, with  of course  . Thus is equal to the number of nodes in construction step , i.e. .^{3}^{3}3 is the number of cubes of edge length intersecting M, see the calculation of the box counting dimension in e.g. [6]. Explicitly we get for
(45) 
Now let us relate to the contraction parameter of the selfsimilar set. We assumed that the graph constructed from the selfsimilar set is connected. This implies that there are nodes on the “diagonal” of the generator, i.e. . Now we have for the internal scaling dimension of
(46)  
(47)  
(48) 
in which is the box counting dimension of . Of course lemmas 3.1 and 3.1 provide us with the knowledge that this is the dimension of starting from any node.
Thus we established equality of the box counting dimension of selfsimilar sets and the internal scaling dimension of the adjoint selfsimilar graphs under the assumptions stated above. {remark} The assumed existence of a central node is not essential for the equality of the dimensions of the fractal and the graph. The equality still holds in a more general context, e.g. for fractals like the Sirpinski Triangle. It is difficult though to give a general proof for arbitrary selfsimilar sets.
4.2.4 Approximation of a Two Dimensional Lattice
In this paragraph we want to show how it now becomes possible to do a dimensional approximation of a dimensional cubic lattice. Again, for the sake of simplicity, we discuss the idea only with a twodimensional lattice but the generalization to dimensions is obvious.
We introduce generators as shown in figure 6. With these we get graphs of dimensions
(49) 
in which is the number which labels the generators in figure 6. Obviously we have
(50) 
In this sense we have a dimensional approximation of a twodimensional lattice as alleged above. This might have some relevance in connection with the dimensional regularization used in many renormalization approaches to quantum field theory. {remark} The generators above correspond to fractal sets known as “sponges”, see e.g. [7]. We can construct such “sponges” for any dimension , we just need to modify the generators appropriately.
4.2.5 How to Change the Dimension of a Graph
To enlarge the dimension of a graph it is necessary to add either bonds or nodes to the graph. In the former case we showed that adding only bonds between nodes with original distance less than some does not change the dimension. We want to illustrate this with an example. Let us try to get a twodimensional lattice starting from an onedimensional one. The procedure is shown in figure 7. The dotted bonds are those we added. As is easily seen, the former distance between the newly connected nodes grows unboundedly with , the number of the nodes in the original graph.
If we choose to add nodes instead, it is equivalent to adding bonds to new nodes which formerly had infinite distance to the nodes of the original graph. This also illustrates the general result because adding finitely many nodes certainly doesn’t change the dimension.
References
 [1] M. Requardt, Göttingen preprint (submitted to J. Phys. A), hepth/9605103
 [2] M. Requardt, Göttingen preprint, hepth/9610055
 [3] Th. Filk, Mod. Phys. Lett. A 7 (1992) 2637
 [4] A. Billoire, F. David, Nucl. Phys B 275 (1986) 617
 [5] M. E. Agishtein, A.A. Migdal, Nucl. Phys. B 350 (1991) 690
 [6] K. J. Falconer, “Fractal Geometry. Mathematical Foundations and Applications”, J. Wiley & Sons, Chichester 1990
 [7] G. A. Edgar, “Measure, Topology and Fractal Geometry”, Springer, New York 1990