Abstract
In the following we undertake to describe how macroscopic spacetime (or rather, a microscopic protoform of it) is supposed to emerge as a superstructure of a web of lumps in a stochastic discrete network structure. As in preceding work (mentioned below), our analysis is based on the working philosophy that both physics and the corresponding mathematics have to be genuinely discrete on the primordial (Planck scale) level. This strategy is concretely implemented in the form of cellular networks and random graphs. One of our main themes is the development of the concept of physical (proto)points or lumps as densely entangled subcomplexes of the network and their respective web, establishing something like (proto)causality. It may perhaps be said that certain parts of our programme are realisations of some early ideas of Menger and more recent ones sketched by Smolin a couple of years ago. We briefly indicate how this twostoryconcept of quantum spacetime can be used to encode the (at least in our view) existing nonlocal aspects of quantum theory without violating macroscopic spacetime causality!
(Quantum) SpaceTime as a
Statistical Geometry of Lumps
in Random Networks
Manfred Requardt
email:
Institut für Theoretische Physik
Universität Göttingen
Bunsenstrasse 9
37073 Göttingen Germany
1 Introduction
In recent papers ([1] to [4]) we developed some facets of an extensive programme we formulated there, i.e. reconstruct ordinary continuum physics or mathematics as kind of a coarse grained limit from a much more primordial and genuinely discrete substrate, including, in particular, a discrete theory of (proto) spacetime as the universal receptacle or substratum of all physical processes.
A corresponding philosophy is presently hold by a substantial minority of workers in quantum gravity and we commented on some of the various approaches, at least as far as we are aware of them, in the foregoing papers. We therefore refer the interested reader to these papers as to references we do not mention in the following just for sake of brevity. As an exception we mention only the early and prophetic remarks made by Penrose in e.g. [5] about the surmised combinatorial substratum underlying our continuous spacetime , the ideas of Smolin, sketched at the end of [6], because they are surprisingly close to our working philosophy and the work of ’t Hooft ([7]) which is based on the model system of cellular automata (the more rigid and regular relatives of our dynamic cellular networks introduced in the following).
Our personal working philosophy is that spacetime at the very bottom (i.e. near or below the notorious Planck scale) resembles or can be modeled as an evolving information processing cellular network, consisting of elementary modules (with, typically, simple internal discrete state spaces) interacting with each other via dynamical bonds which transfer the elementary pieces of information among the nodes. That is, the approach shares the combinatorial point of view in foundational spacetime physics which has been initiated by e.g. Penrose. It is a crucial and perhaps characteristic extra ingredient of our framework that the bonds (i.e. the elementary interactions) are not simply dynamical degrees of freedom (as with the nodes their internal state space is assumed to be simple) but can a fortiori, depending on the state of the local network environment, be switched on or off, i.e. can temporarily be active or inactive! This special ingredient of the dynamics hopefully allows the network to perform geometric phase transitions into a new ordered phase having a certain twostory structure to be explained below. This conjectured geometric order we view as kind of a discrete proto spacetime carrying metrical, causal and dimensional structures. The main content of the paper consists of a description and analysis of these structural elements and their interplay.
In paper [1] we dealt primarily with dimensional concepts on such discrete and irregular spaces. It furthermore became aparent that there exist close ties to the theory of fractal sets. Papers [3] and [4], on the other hand, are, among other things, devoted to the developement of several possible versions of discrete analysis and discrete differential geometry respectively discrete functional analysis with certain zones of contact with noncommutative geometry.
As has been beautifully reviewed by Isham in various papers (see e.g. [8]) one could, among several possible attitudes, adopt the perhaps most radical working philosophy in quantum gravity and speculate that both quantum theory and gravity are merely secondary and derived aspects or, expressed in more physical terms, socalled effective theories of an underlying more primordial theory of a markedly combinatorial flavor. But a theory comprising quantum theory and gravitation as emergent subtheories should, first of all, provide a framework in which both the emergence of something we may consider as a proto form of classical spacetime respectively quantum vacuum can be expressed or discussed, most notably the emergence of the continuum from the discrete and the concept of physical spacetime points (having an internal dynamical structure) and their intricate web. In a companion paper, which is in preparation, we will show how quantum theory emerges as a coarse grained stochastic theory within such a framework.
Some months ago, after the preparation of the first draft, we were kindly informed by El Naschie that a very early source where a couple of related ideas can be found is the contribution of Menger in [9], perhaps better known from his research on topological dimension or fractal sets like the Menger sponge. In this essay he entertains very interesting ideas about the necessity of a new geometry of the microcosmos based on the geometry of lumps and the concept of a statistical metric space. We note in passing that some of the concepts we develop in the following seem to be very much in accord with this point of view. Quite remarkable in this respect is also Einsteins openminded attitude towards the possibility of a more primordial discrete spacetime theory expressed at the end of the same volume. As to this particularly important point see also his many utterances compiled by Stachel in [10], p.27ff. We think, our discrete framework may exactly realize some of the ideas he had in mind. (In this context we also want to mention the Cantorian spacetime approach of El Naschie et al. who tries to model microspace as a particular type of (random) fractal (see e.g. [11]). Another interesting early source with a possible bearing on our approach may also be v.Neumann s concept of continuum geometry (geometry without points) which is briefly described in [12], the original source can be found in [13]. Furthermore, there exist surprising links to other seemingly unrelated areas of current research as we learnt very recently, a catchword being smallworld networks (see [14]). Some of the mechanisms being effective in our cellular network environment are also observed there.
After having nearly completed this second version we received a message from S.Roy who informed us that the framework sketched by Menger has been developed further by Menger himself together with several coworkers and later by other groups (seee e.g. [15]). The state of affairs is described in his monograph ([16]), the more mathematical aspects are developed in [17]. From these monograhs one may see that the early ideas of Menger have meanwhile unfolded into various branches of their own right and it is not easy at the moment to relate all of them with our own working philosophy. Anyhow, the situation looks very promising and interesting; we will deal with the geometric web of lumps (we also called them cliques) in section 4 (which is the central section of the paper) and make some remarks concerning the metric aspects in subsection 4.3.
Some clarifying comments are perhaps in order at this point. The modelling of the depth structure of spacetime as a cellular network consisting of nodes and bonds should not necessarily be understood in a plain bodily sense. One should rather consider it as a representation or emulation of the main characteristics of the physical scenario. In this connection we want to mention the following interesting and purely discrete approaches in [18] and [19].There may, in particular, exist a variety of superficially different systems, the logical structure of which can nevertheless be encoded in roughly the same abstract underlying network model. It is our belief that such a discrete network, governed by a relatively simple but cleverly chosen dynamical law, is capable of generating most if not all of the phenomena and emergent laws on which our ordinary continuum physics is usually grounded. That such a hypothesis is not entirely farfetched may e.g. be inferred from the emerging complexity of such a simple cellular automaton model as the famous game of life created by Conway. A typical example is the geometry of lumps envisaged by Menger. Take as lumps the hypothetical infinitesimal grains of space or spacetime which cannot be further resolved (be it in a practical or principal sense). Let them overlap according to a certain rule so that they can interact or exchange information. Draw a node for each such lump and a bond for each two lumps which happen to overlap. In combinatorial topology such a combinatorial complex is called the nerve of the set system (cf. e.g. [20]). In a next step one may encode the respective strengths of interaction or degrees of overlap in a valuation of the corresponding bonds, yielding a cellular network of the kind we are having in mind. A fortiori one can make these mutual overlaps into dynamical variables, i.e. let them change in the course of evolution.
It may seem, at first glance, that our bottomup approach, which starts almost from first principles, has the disadvantage, if compared with other more topdown oriented approaches as e.g. string theory or loop quantum gravity, to be rather arbitrary. These other frameworks are based (at least to a large part) on more or less continuum concepts and ideas theoretical physics has got accustomed to and detect some discrete behavior (e.g. spin networks) only at the end of the road if at all. Furthermore, in the case of e.g. string theory, the quantum principles (whatever that means exactly) are taken for granted down to arbitrarily fine scales (at least as far as we can see) and both rely on such approved concepts as functional integrals or sum over configurations. To such a potential criticism we would like to reply in the following way. For one, it is far from obvious that the (typically euclidean) functional integral philosophy does still hold sway in e.g. the Planck regime, as it is (implicitly) based on some kind of action principle which, on its side, may have its roots in classical physics. On the other side, it may turn out that such concepts are only the surface aspect of a deeper, more hidden reality. Such a possibility can of course not be precluded, but we do not want to base our approach on such a heuristic principle from the outset. Quite to the contrary, we want to deduce quantum theory (and by the same token the functional integral framework) as an effective theory from our presumably more fundamental theory. How this may work we undertake to show in our above mentioned companion paper. We expect however that these approaches may merge on some intermediate level.
We would like to add yet another, as we think, important remark. Quite a few researchers in this field expect physics at the Planck scale to be quite different from the kind of physics we are accustomed to (take e.g. the interesting remarks in [21]). The situation may be comparable to the physics near or at the critical point in, say, renormalisation theory where different microscopic theories (the socalled universality class) lead to basically the same macroscopic behavior as the microscopic details happen to be washed out in the coarsegraining process. This does of course not mean that the search for such a underlying microscopic theory is futile or useless. The lesson is rather that one should be prepared to employ perhaps other guiding principles in the quest for this presumed more primordial laws and concentrate, at least in a first step, rather on a whole class of possible primordial model theories instead of a single theory of everything. As we will show in the mentioned companion paper, quantum behavior may just emerge as such a coarsegrained stochastic behavior of a whole class of discrete microscopic model theories. In other words, one of our more heuristic guiding principles is the following. We consider a class of microscopic (discrete) theories worth to be studied if they have the propensity to generate e.g. quantum behavior or a kind of proto spacetime in some classical limit. It would even be nicer if, at an intermediate level, they develop links to, say, string theory or loop quantum gravity. That there are relations to noncommutative geometry was already shown in the above mentioned papers.
2 The Cellular Network Environment
We briefly describe in this section the general framework within which our investigation will take place. Among other things we introduce a simple example of a local dynamical network law (for more details see [22] or [3]. A certain class of relatively simple cellular networks is the following.
Definition 2.1 (Class of Cellular Networks)

“Geometrically” our networks represent at each fixed ‘clock time’ ‘labeled graphs’, i.e. they consist of nodes {} and bonds {}, with the bond connecting the nodes (cells) , . We assume that the graph has neither elementary loops nor multibonds, that is, only nodes with are connected by at most one bond.

At each site we have a local node state with , for the time being, a certain not further specified elementary quantum. The bond variables , attached to , are in the most simplest cases assumed to be two or threevalued, i.e.

There exist a variety of possibilities concerning the class of bonds being active in the network. The simplest and perhaps most natural choice is to assume that, at least in the initial configuration (see below), every pair of nodes is connected by a bond. On the other hand, one can restrict the set of admissible bonds to a certain subset (motivated perhaps by the physical context).
A simple example of such a local dynamical law we are having in mind is given in the following definition.
Definition 2.2 (Example of a Local Law)
At each clock time step a certain ‘quantum’ is exchanged between, say, the nodes , , connected by the bond such that
(1) 
(i.e. if a quantum flows from to etc.)
The second part of the law describes the back reaction on the bonds
(and is, typically, more subtle). This is the place where the
socalled ‘hysteresis interval’ enters the stage. We assume the
existence of two ‘critical parameters’
with:
(2) 
(3) 
with the special proviso that
(4) 
On the other side
(5) 
In other words, bonds are switched off if local spatial charge fluctuations are too large, switched on again if they are too small, their orientation following the sign of local charge differences, or remain inactive.
Remarks:

It is important that, generically, such a law does not lead to a reversible time evolution, i.e. there will typically exist attractors in total phase space (the overall configuration space of the node and bond states). On the other hand, there exist strategies to develop reversible network laws (cf. e.g. [25]).

In the above class of laws a direct bondbond interaction is not yet implemented. We are prepared to incorporate such a (possibly important) contribution in a next step if it turns out to be necessary. In any case there are not so many ways to do this in a sensible way. Stated differently, the class of possible physically sensible interactions is perhaps not so numerous.

The above clock time should not be confused with socalled physical time, which is, as is the case with many other physical continuum concepts, considered to be an emergent collective quantity, living on a higher level of the hierarchy. Note that its correct implementation is a big issue anyhow in quantum gravity and we refrain from overburding our paper with addressing this difficult topic (a recent review is e.g. [23]).

As in the definition of evolution laws of spin networks by e.g. Markopoulou, Smolin and Borissov (see [26] or [27]), there are in our case more or less two possibilities: treating evolution laws within an integrated spacetime formalism or regard the network as representing space alone with the time evolution being implanted via some extra principle ( which is the way we have chosen above). The interrelation of these various approaches and frameworks, while being very interesting, is however far from obvious at the moment and needs a separate detailed investigation.
Observation 2.3 (Gauge Invariance)
The above dynamical law depends nowhere on the absolute values of the node charges but only on their relative differences. By the same token, charge is nowhere created or destroyed. We have
(6) 
as far as the rhs is meaningful. One could e.g. choose as initial condition respectively constraint
(7) 
There are many different aspects of our class of cellular network one can study in this context. One can e.g. regard them as complex dynamical systems, or one can decide to develop a statistical or stochastic framework etc. In a purely geometric sense, however, they are graphs. On the other side, we are, at least in this paper, primarily concerned with the analysis of the microstructure of (quantum) spacetime. Therefore, in a first step, it may be a sensible strategy to supress all the other features like e.g. the details of the internal state spaces of nodes and bonds and concentrate instead on their pure wiring diagram and its reduced (graph) dynamics. This is already an interesting characteristic of the network (perhaps somewhat reminiscent of the Poincaré map in the theory of chaotic systems) as bonds can be switched on and off in the course of clock time so that already the wiring diagram will constantly change. Furthermore, as we will see, it encodes the complete near and farorder structure of the network, that is, it tells us which regions are experienced as near by or far away (in a variety of possible physical ways such as strength of correlations or with respect to some other physical metric like e.g. statistical distance) etc. Evidently this is one of the crucial features we expect from something like physical spacetime. To give an example. In the above simple scenario with or one can e.g. draw a directed bond, , if , with implied, and delete the bond if . This leads to a (clock) time dependent graph, , or wiring diagram.
We close this section with a brief résumé of the characteristics an interesting network dynamics should encode (in our view).
Résumé 2.4
Irrespectively of the technical details of the dynamical evolution law under discussion it should emulate the following, in our view crucial, principles, in order to match certain fundamental requirements concerning the capability of emergent and complex behavior.

As is the case with, say, gauge theory or general relativity, our evolution law on the surmised primordial level should implement the mutual interaction of two fundamental substructures, put sloppily: “geometry” acting on “matter” and vice versa, where in our context “geometry” is assumed to correspond in a loose sense with the local and/or global bond states and “matter” with the structure of the node states.

By the same token the alluded selfreferential dynamical circuitry of mutual interactions is expected to favor a kind of undulating behavior or selfexcitation above a return to some uninteresting ‘equilibrium state’ as is frequently the case in systems consisting of a single component which directly acts back on itself. This propensity for the ‘autonomous’ generation of undulation patterns is in our view an essential prerequisite for some form of “protoquantum behavior” we hope to recover on some coarse grained and less primordial level of the network dynamics.

In the same sense we expect the overall pattern of switchedon and off bonds to generate a kind of “protogravity”.
3 The Cellular Network as a (Random) Graph
We start with the introduction of some graph theoretical definitions (see e.g. [24]).
Definition 3.1 (Simple Locally Finite (Un)directed Graph))

We write the simple labeled graph as where is the countable set of nodes (or vertices) and the set of bonds (edges). The graph is called simple if there do not exist elementary loops and multiple edges, in other words: each existing bond connects two different nodes and there exists at most one bond between two nodes. (We could of course also discuss more general graphs). Furthermore, for simplicity, we assume the graph to be connected, i.e. two arbitrary nodes can be connected by a sequence of consecutive bonds called an edge sequence or walk. A minimal edge sequence, that is one with each intermediate node occurring only once, is called a path (note that these definitions may change from author to author).

We assume the graph to be locally finite (but this not always really necessary), that is, each node is incident with only a finite number of bonds. Sometimes it is useful to make the stronger assumption that this vertex degree, , (number of bonds being incident with ), is globally bounded away from .
Observation/Definition 3.2
Among the paths connecting two arbitrary nodes there exists at least one with minimal length. This length we denote by . This d has the properties of a metric, i.e:
(8)  
(9)  
(10) 
(The proof is more or less evident).
Corollary 3.3
With the help of the metric one gets a natural neighborhood structure around any given node, where comprises all the nodes, , with , the nodes with .
Remark: The restriction to connected graphs is, for the time being, only made for convenience. If one wants to study geometric phase transitons of a more fragmented type, it is easy to include these more general types of graphs. In the context of random graphs ( which we will introduce below) one can even derive probabilistic criteria concerning geometric properties like connectedness etc.
We said above that, for the time being, we want to concentrate our investigation on the geometric i.e. graph properties of our cellular network which are themselves (clock) time dependent. On the other hand, the graphs or networks we are actually interested in are expected to be extremely large (number of nodes ). According to our philosophy they are to emulate the full physical vaccum together with all its more or less macroscopic excitations, or, in other words, the entire evolving universe. Furthermore the assumed clocktime interval is extremely short (in fact of Plancktime order). On the other side, it is part of our working philosophy that the phenomena we are observing in e.g. present day high energy physics and, a fortiori, macroscopic physics are of the nature of collective (frequently large scale) excitations of this medium both with respect to space and time (in Planck units). In other words, each of these patterns is expected to contain, typically, a huge amount of nodes and bonds and to stretch over a large number of clocktime intervals. This then suggests the following approach which has been fruitful again and again in modern physics.
The Statistical Hypothesis 3.4
Following the above arguments, it makes sense to study socalled graph properties within a certain statistical framework to be further explained below as long as one is interested in patterns which are quasi macroscopic compared to the Planck scale.
Remark: Similar strategies have been pursued in the investigation of
cellular automata (see e.g. [28] or [29])
One strategy, i.e. errecting a probability space of graphs over
the given set of nodes, will be introduced now.
The Random Graph Idea 3.5
Take all possible labeled graphs over nodes as probability space (i.e. each graph represents an elementary event). The maximal possible number of bonds is , which corresponds to the unique simplex graph (denoted usually by ). Give each bond the independent probability , (more precisely, is the probability that there is a bond between the two nodes under discussion). Let be a graph over the above vertex set having bonds. Its probability is then
(11) 
where . There exist different labeled graphs and the above probability is correctly normalized, i.e.
(12) 
This probability space is sometimes called the space of binomially random graphs and denoted by . Note that the number of edges is binomially distributed, i.e.
(13) 
and
(14) 
Proof of the latter statement:
(15) 
or, with being the independent Bernoulli variables (as to this notion cf. e.g. [30]) belonging to the bonds:
(16) 
(The use of the above Bernoulli variables leads also to some
conceptual clarifications in other calculations).
A Variant Approach 3.6
A slightly different probability space can be constructed by considering only graphs with a fixed number, , of bonds and give each the probability as there are exactly of them. The corresponding probability space, , is called the space of uniform random graphs.
The latter version is perhaps a little bit more common in pure mathematics as this concept was introduced mainly for purely combinatorial reasons which have nothing to do with our own strand of ideas. The whole theory was rather developed by Erdös and Rényi in the late fifties and early sixties to cope with certain notorious (existence) problems in graph theory (for more information see e.g. [31] and [34], brief but concise accounts can also be found in chapt.VII of [24] or [35]).
Observation 3.7
The two random graph models behave similarly if . Note however, that there exists a subtle difference between the two models anyway. In the former model all elementary bond random variables are independent while in the latter case they are (typically weakly) dependent.
(While being plausible this statement needs a proof which can be found in e.g. [31]).
The really fundamental observation made already by Erdös and Rényi (a rigorous proof of this deep result can e.g. be found in [34]) is that there are what physicists would call phase transitions in these random graphs. To go a little bit more into the details we have to introduce some more graph concepts.
Definition 3.8 (Graph Properties)
Graph properties are certain particular random variables (indicator functions of socalled events) on the above probability space . I.e., a graph property, , is represented by the subset of graphs of the sample space having the property under discussion. To give some examples: i) connectedness of the graph, ii) existence and number of certain particular subgraphs (such as subsimplices etc.), iii) other geometric or topological graph properties etc.
Remark: In addition to that there are other more general random variables (‘graph characteristics’) describing the fine structure of graphs, some of which we will introduce below.
In this context Erdös and Rényi made the following important observation.
Observation 3.9 (Threshold Function)
A large class of graph properties (e.g. the monotone increasing ones, cf. the above cited literature) have a socalled threshold function, , so that for the graphs under discussion have property almost shurely for and almost shurely not for or vice versa (more precisely: for ; for the details see the above literature). The above version applies to the second kind of graph probability space, . A corresponding result holds for with replacing . That is, by turning on the probability , one can drive the graph one is interested in beyond the phase transition threshold belonging to the graph property under study. Note that, by definition, threshold functions are only unique up to “factorization”, i.e. is also a threshold function.
Example 3.10 (Connectedness)
The threshold function for the graph property connectedness is
(17) 
Note that with the help of the above observation, i.e. for , we have for large: and hence , i.e.
In the following our main thrust will go towards the developement of the concept of proto spacetime as an order parameter manifold or superstructure floating in our network and the concept of physical points. We therefore illustrate the method of random graphs, graph properties and graph characteristics by applying it to a particular feature being of importance in the sequel.
Definition 3.11 (Subsimplices and Cliques)
With a given fixed graph and a subset of its vertex set , the corresponding induced subgraph over is called a subsimplex (ss), , or complete subgraph, if all its nodes are connected by a bond. In this class there exist certain maximal subsimplices , that is, every addition of another node destroys this property. These are called cliques in combinatorics and are the candidates for our physicaal points carrying a presumably rich internal (dynamical) structure.
We consider all possible graphs, , over the fixed vertex set of nodes. For each subset of order (i.e. number of elements) we define the following random variable:
(18) 
where is the corresponding induced subgraph over with respect to (the probability space). Another random variable is then the number of simplices in , denoted by and we have:
(19) 
with the number of subsets . With respect to the probability measure introduced above we then have for the expectation values:
(20) 
and
(21) 
With the sum running over all and being one or zero we get
(22) 
where is the remaining graph after all the edges belonging to have been eliminated. This yields
(23) 
where is the probability space of graphs over with all the bonds being omitted. The maximal possible number of bonds belonging to is
(24) 
Each of these bonds can be on or off with probability or . To each graph of belongs a unique labeled sequence of ’s and ’s and every such sequence does occur (i.e. with either or at label ). We hence have
(25) 
and we get
(26) 
The case that such a simplex is already maximal, i.e. is actually a clique, can be calculated as follows. The addition of a single further vertex would destroy the property of being a . In other words, each of the vertices in the graph , not lying in the nodeset , is connected with the above vertex set, , by fewer than bonds. This can now be quantitatively encoded as follows: The probability that the induced subgraph over arbitrarily chosen vertices is already a is the product of the independent probabilities that it is a and that each of the remaining vertices is connected with by fewer than bonds. The latter probability is , hence
(27) 
There are now exactly possible subsimplices over the node set . We arrive therefore at the following important conclusion:
Conclusion 3.12 (Distribution of Subsimplices and Cliques)
The expectation value of the random variable number of subsimplices is
(28) 
For , the number of cliques in the random graph, we have then the following relation
(29) 
It is remarkable, both physically and combinatorially, that these quantities, as functions of (the order of subsimplices) have quite a peculiar numerical behavior. We are, among other things, interested in the typical order of cliques (where typical is understood in a probabilistic sense).
Observation/Definition 3.13 (Clique Number)
The maximal order of cliques contained in is called its clique number, . It is another random variable on the probability space .
An analysis of the above expression as a function of shows that it is typically very large (for sufficiently large) for all lying in a certain interval below some critical value, , and drops rapidly to zero for .
Conclusion 3.14
From the above one can infer that this value is a good approximation for the above defined clique number of a typical random graph, depending only on and . In other words, it approximates the order of the largest occurring cliques in a typical random graph. can be approximated as
(30) 
(cf. chapt. XI.1 of [31]).
Remark: A numerical analysis of the geometric web of cliques and
various of its characteristics is given in sect.4.
Conclusion 3.15
By an estimation of the variance of we can conclude that the typical orders of occurring cliques lie between and .
Remark 3.16
To make the above reasoning perhaps more transparent, it is again helpful to exploit the properties of the elementary edgevariables . The probability that arbitrarily selected bonds exist in the random graph is , the complimentary possibility (i.e., that some of these bonds are missing), has hence the probability .
Résumé 3.17 (Random Graph Approach)
There is of course no absolute guarantee that our network, following a deterministic evolution law and typically reaching after a certain transient one of possibly several attractors, can in every respect be regarded as the evolution of true random graphs. In other words, its behavior cannot be entirely random already by definition. Quite to the contrary, we expect a shrinking of the huge accessible phase space during its evolution which manifests itself on a more macroscopic level as pattern creation.
The underlying strategy is rather the following. At each clock time step, is a graph having a definite number of active bonds, say . Surmising that is sufficiently generic or typical we may be allowed to regard it as a typical member of the corresponding family or (at least as far as certain gross features are concerned). Via this line of inference we are quite confident of being able to get some clues concerning the qualitative behavior of our network, the microscopic time evolution of which is too erratic to follow in detail. As to this working philosophy the situation is not so different from the state of affairs in many areas of, say, ordinary statistical physics or complex dynamical systems . But nevertheless, a more detailed analysis (underpinned by concrete numerical simulations) of the validity or limits of such an ansatz would be desirable but has to be postponed in order not to blow up the paper to much (cf. e.g. the completely similar situation in the context of cellular automata, being expounded to some extent in the above mentioned literature).
Some steps in this direction were taken by our former student Th. Nowotny as part of his diploma thesis. Other perhaps characteristic numerical deviations between theoretical results based on certain apriori statistical assumptions and computer simulations of concrete models were also found in [32] by Antonsen, who presented an approach which is different from ours in several respects but belongs to the same general context.
4 The Emergence of (Proto) SpaceTime
In this core section of our investigation we are going to describe how the presumed underlying (discrete) fine structure of our continuous spacetime may look like. We want however to emphasize at this place that, while most of the details and observations we will present are rigorously proved, the overall picture is still only hypothetical. That is, we are able to describe a, as we think, fairly interesting scenario in quite some detail but are not yet able to show convincingly that our network actually evolves into exactly such a phase we are going to expound in the following under one of the dynamical laws we described above. We will in fact show, that the unfolding of something like an extended, macroscopically stable spacetime structure having, afortiori, an integer macroscopic dimension, is quite a subtle phenomenon from a purely probabilistic point of view and that only the understanding of the nature of these subtleties will lead us to the correct class of dynamical laws.
The central theme of this paper is the description and analysis of a certain superstructure, , emerging within our network as a consequence of a process which can be interpreted as a geometrical phase transition. In this picture , which we experience as spacetime, plays the role of an order parameter manifold. Its emergence signals the transition from a disordered and chaotic initial phase to a phase developing a near/farorder, i.e. a causal structure, and stable physical points or lumps (Menger).
Our qualitative picture concerning the initial scenario is the following (more details can be found in e.g. section 4 of [22]). The network, , started from a presumed densely entangled initial phase, , in which on average every pair of nodes was connected by an active bond with high probability (i.e. it was almost a simplex). This chaotic initial phase was characterized by extremely large fluctuations of local node/bond charges and very shortlived/shortranged correlations. This is a result of the dense entanglement and the kind of network laws we described in sect.2 (they typically favor to some extent an overshooting). There are, in particular, no stable cliques or lumps and no traces of a kind of proto spacetime.
We conjecture now that, under certain favorable conditions, that is, an appropriately chosen dynamical law together with the occurrence of a suitably large collective spontaneous deviation of the network state in some region, the network is capable of leaving this chaotic initial phase, starting from such a nucleation center, and unfolds towards a new more ordered attractor, the above mentioned phase . This geometric phase transition is triggered respectively accompanied by an annihilation of a certain fraction of active bonds (in the language of our network laws: ) due to too large differences in neighboring node charges. In this process the individual and incoherent elementary fluctuations are expected to be reorganized in a more macroscopic pattern (in the language of synergetics they become slaved; see e.g. [33]). We note in passing that what we indicated above may be described in a more conventional context as the big bang scenario and it remains a big task to fill out all the intermediate steps.
We now describe in broad outline our idea of the underlying discrete substratum of spacetime and relate it, in a next step, to the more rigorously defined mathematical correlatives within the random graph framework. We want to emphasize that, for the time being, the only structural or quantitative input we are employing to encode the effects of the presumed geometric phase transition is the decrease in the number of occupied bonds in the wiring diagram of the network. That is, we will mainly be occupied with the description and analysis of the structural and geometric changes, occurring in the underlying graph, when the bond probability, , decreases with the clock time.
The Qualitative Picture 4.1 (Physical Points)

Physical points have a (presumably rich) internal structure, i.e. they consist of a (presumably) large number of nodes and bonds. In the words of Menger they are lumps.

We suppose that, what we are used to decribe as fields at a spacetime point (in fact, rather distributions in e.g. quantum field theory), are really internal excitations of these lumps.

In order to have a qualitative measure to tell the physical points apart, that is, to discern what happens within a certain point or between different points, we identify the physical points with particularly densely connected subgraphs of our network or graph. This then motivates our interest in maximal subsimplices or cliques as natural candidates.

Typically (i.e. if a certain fraction of bonds has been eliminated), some of these lumps overlap with each other in a stronger or weaker sense, forming so to say local groups while other will cease to overlap. This will then establish a kind of protocausality or near/farorder in our protospacetime and will be one of the central topics in our analysis.
To get an idea how the order of the typical cliques depends on the bond probability, , we apply the formula for the clique number, provided in sect.3 to a graph having, say, nodes with varying (we omitted the term).
(31) 
We will proceed by compiling a couple of simple observations concerning , proofs being partly omitted (if they are obvious).
Observation 4.2

If the node degree, , of is smaller than then can lie in at most a finite set of different simplices, an upper bound being provided by the number of different subsets of bonds emerging from , that is .

The set of subsimplices is evidently partially ordered by inclusion

Furthermore, if S is a simplex, each of its subsets is again a simplex (called a face)

It follows that each of the chains of linearly ordered simplices (containing a certain fixed node) is finite. The corresponding length can be calculated in a similar way as in item 1 by selecting chains of sets of bonds, ordered by inclusion. In other words each chain has a maximal element. By the same token each node lies in at least one (but generically several) mss

A with being a member can comprise at most nodes, in other words, its order is bounded by the minimum of these numbers when varies over the mss.
Proof of item 1: Assume that are two different simplices containing . By definition is linked with all the other nodes in or . As these sets are different by assumption, the corresponding subsets of bonds emerging from are different. On the other side, not every subset of such bonds corresponds to a simplex (there respective endpoints need not form a simplex), which proves the upper bound stated above.
Observation 4.3
The class of simplices, in particular the mss, containing a certain fixed node, , can be generated in a completely algorithmic way, starting from . The first level consists of the bonds with an end node, the second level comprises the triples of nodes (triangles), , with the nodes linked with each other and so forth. Each level set can be constructed from the preceding one and the process stops when a mss is reached.
Remark: Note that at each intermediate step, i.e. having already constructed a certain particular subsimplex, one has in general several possibilities to proceed. On the other hand, a chain of such choices may differ at certain places from another one but may lead in the end to the same final simplex (in other words, being simply a permutation of the nodes of the former simplex).
Denoting the under discussion by capital with certain indices or labels attached to it, this process can be pictorially abreviated as follows:
(32) 
With given, each permutation will yield the same , i.e:
(33) 
Furthermore each can be constructed in this way, starting from one of its nodes. Evidently this could be done for each node and for all possible alternatives as to the choice of the next node in the above sequence.
Definition 4.4
Let be a class of subgraphs of .

is the graph with if every ,
if every 
is the graph with if for at least one
if for at least one .
As every node or bond belongs to at least one (as can be easily inferred from the above algorithmic construction), we have
Corollary 4.5
(34) 
After these preliminary remarks we now turn to our main task, that is, the analysis of the web of these as the elementary building blocks of the next higher level of organisation.
4.1 The Embryonic Epoch
In its surmised transition from the almost maximally connected and chaotic initial phase to the fully developed phase, (i.e. plus superstructure ), the underlying graph passes through several clearly distinguishable epochs. In the following we study two main phases of the network. The first one, which we call embryonic, is characterized by a still pronounced common overlap of the emerging lumps or physical points. That is, they can still interact directly with each other which implies that there exist no true farorder or larger distances on the network of lumps. This epoch should be typical (in our picture) for the infinitesimal time interval just after the big bang.
We begin with the epoch where only a small fraction of bonds is shut off. Let us e.g. assume that bonds with
(35) 
are temporarily dead with the order of the graph or network (number of nodes) and the maximal possible number of bonds. In other words, the network is supposed to be still near the initial phase. We observe that arbitrarily selected bonds can at most connect different nodes, hence there still exist at least nodes which are maximally connected, viz. they are spanning a still huge subsimplex . On the other hand there are at most nodes with one or more incident bonds missing in the corresponding induced subgraph.
can hence be split in the following way:
(36) 
with the unique set of those nodes so that to each node in there exist other nodes (also lying in ) with the respective bonds to missing. , on the other side, is the set of remaining nodes which are maximally connected (by construction); i.e. they form a .
(37) 
Definition 4.6
is the induced subgraph spanned by the nodes occurring in . Note that in general , that is, it may rather be called its ‘closure’.
Observation 4.7

The simplex is contained in each of the occurring , , i.e:
(38) We hence have
(39) 
Note that itself is never maximal since is always a larger simplex with and being the induced subgraph spanned by and .

To each maximal simplex belongs a unique maximal subsimplex with
(40) 
It is important for what follows that can be uniquely characterized, without actually knowing the , by the following two properties: i) is a so that all bonds connecting nodes from with are “on”. ii) is maximal in this class of , that is, each node in has at least one bond missing with respect to the other nodes in . An induced subgraph in , having these properties is automatically the uniquely given !
Corollary 4.8
From the maximality of the follows a general structure relation for the and :
(41) 
and neither
(42) 
viz. there always exists at least one s.t. and vice versa.
Proof of the above observation:

Starting from an arbitrary node , it is by definition connected with all the nodes in , since if say are not connected they both belong to (by definition). I.e., irrespectively how we will proceed in the construction of some , can always be added at any intermediate step, hence . On the other side assume that . This implies that is connected with each node in . We showed above that , hence is connected with all the other nodes, i.e. it is not in , that is, , which proves the statement.

As is connected with each (by definition of and ), the subgraph is again a (larger) simplex.

We have for all , hence
(43) with the corresponding subgraphs in .
With being a simplex, is again a subsimplex which is maximal in . Otherwise would not be maximal in .
On the other side each is uniquely given by a maximal in as each node in is connected with all the nodes in .
We see from the above that as long as , the number of dead (missing) bonds, is sufficiently small, i.e. , there does necessarily exist a nonvoid overlap , among the class of , . This overlap will become smaller as increases. By the same token the number of will increase for a certain range of the parameter while the respective size of the will shrink. The above results hold for each given graph. On the other side, the above unique characterization of in item 4 makes it possible to attack the problem of the order of within the framework of random graphs in a more quantitative manner. Given a member of , is fixed by item 4 of the above observation. We are interested in the probability of having, say, nodes.
The strategy is, as usual, to try to express the probability of such a configuration within as the product of certain more elementary and (if possible) independent probabilities. Unfortunately this turns out to be relatively intricate in the above case and we are, at the moment, only able to provide certain upper and lower bounds for the probability under discussion. As this example shows that such questions may not always have simple and straightforward answers, it is perhaps worthwhile to dwell a little bit on this point.
The typical difficulties one usually encounters in this context are the following: The structure of the set of graphs in having a prescribed property may be rather complicated, so that it is difficult to avoid multiple counting of members when trying to calculate the order of such a set. A frequent reason for this is the intricate entanglement of the various pieces of a complicated graph, a case in point being the above description of in . In our case the peculiar entanglement can be seen as follows.
Selecting arbitrary vertices, the probability that the corresponding induced subgraph forms a is (see section 3). If this subgraph is to qualify as , i.e. , , each of the nodes in is connected with every node in . The probability for this property is . The difficult part of the reasoning concerns the subgraph . We call the probability that has just the structure being described above, .
The following observation is helpful. As is unique in , i.e. occurs only once, the corresponding random variable, , that we hit at such an of order , when browsing through the set of induced subgraphs, is zero with at most one possible exception, that is, if has just the order . Therefore the corresponding expectation value of is, by the same token, also the probability of the property ().
Conclusion 4.9
The probability that a random graph contains such a of order r is
(44) 
As far as we can see, it is not easy to disentangle into more elementary independent probabilities and master the complex combinatorics. Therefore we will, at the moment, only give (possibly crude) upper and lower bounds.
, having nodes, is characterized as follows. Labeling the nodes from to , none of them is allowed to have the maximal possible degree (with respect to ), i.e. . The first step is simple. Starting with, say, node , the probability that at least one bond is missing is the complement of the probability that all possible bonds are present, i.e. . The following steps will however become more and more cumbersome. Take e.g. node . In the above probability is already contained both the probability that either the bond is missing or not. If is not missing then some other bond has to be absent (by the definition of ). These two alternatives influence the possible choices being made at step two. In the former case the configuration where all bonds are present is admissible, in the latter case this possibility is forbidden. Depending of which choice we make at each step the algorithmic construction bifurcates in a somewhat involved manner. Evidently this first step yields a crude upper bound on . Making at each step the particular choice that there are always missing bonds among the bonds pointing to nodes with provides a lower bound. We hence have.
Conclusion 4.10
(45) 
and for :
(46) 
Observation 4.11
The lower bound is interesting! Perhaps surprisingly, the occurring product is an important number theoretic function belonging to the field of partitions of natural numbers (see any good textbook about combinatorics or the famous book of Hardy and Wright, [36], the standard source being [37]). Our above random graph approach offers the opportunity to (re)derive and prove this number theoretic formula by purely probabilistic means, i.e. give it an underpinning which seems to be, at first glance, quite foreign. We will come back to this interesting point elsewhere.
It is important to have effective estimates for the regime of probabilities, , so that is empty with a high probability. According to our philosophy this signals the end of the embryonic epoch, where all the supposed protopoints still overlap (and hence are capable of direct interaction) and the beginning of the unfolding of a new phase with, as we hope, a more pronounced near and farorder among the physical points.
Such an estimate can in fact be provided with the help of the above inequality. We have
(47) 
for . The following (highly nontrivial) observation is due to Euler (cf. the above mentioned literature for more recent proofs):
Theorem 4.12
(48) 
for small.
Conclusion 4.13
For p near zero, is empty with arbitrarily large probability .
This shows that there exists in fact a regime of small values where the embryonic epoch no longer prevails. This holds the more so for an dependent (which is very natural) and . On the other side, note that there exists a possibly substantial class of bond configurations which have, up to now, been excluded in the above estimate, the inclusion of which would increase the relevant probability further.
To get a feeling how good the above exact estimate may be, we construct a (as we think, not untypical) example. The construction goes as follows. Take nodes, choose a subset consisting of exactly nodes , make a simplex. With the remaining nodes we proceed in the same way, i.e. we now have two subsimplices . We now choose a oneonemap from to , say:
(49) 
We now connect all the with the except for the pairs . The graph so constructed has
(50) 
We see from this that, as in our above network scenario, the number of missing bonds is a relatively small fraction. We can now make the following sequence of (easy to prove) observations:
Observation 4.14
is already a as each has one bond missing with respect to . One gets new by exchanging exactly one with its partner , pictorially:
(51) 
yielding further . One can proceed by constructing another class of , now deleting and adding their respective partners, i.e:
(52) 
This can be done until we end up with the
(53) 
The combinatorics goes as follows:
(54) 
i.e., our nodegraph (with bonds missing) contains exactly of order . Evidently
We showed above that is nonempty as long as , the number of missing bonds, is smaller than , the order of the graph , since bonds can at most connect different nodes. On the other side, implies
(55) 
or an average vertex degree
(56) 
which is still very large. The example constructed in the preceeding observation has
(57) 
In other words, the parameter is just the critical one given in 4.7. One may hence surmise that is perhaps the threshold for in the sense that, say,
(58) 
for .
On the other side, within the framework of random graphs, we have obtained the rigorous but presumably not optimal estimate
(59) 
for small. For a large graph implies however
(60) 
That is, there is still a wide gap between these two values, a point which needs further clarification.
4.2 The Unfolded Epoch
For values away from we expect the cliquegraph, , to consist of a huge number of cliques, , each being surrounded by its local group, that is cliques having an overlap with , while there is no longer an overlap with the majority of cliques in the graph. In other words, in this scenario the clique graph is much more unfolded and has at least the potential to figure as a kind of proto spacetime. This epoch shall now be analysed in more detail.
From the general analysis we learned that the majority of cliques has an order lying between and , . The expected number of cliques is . We want the average order of cliques to be much larger than one, so that the internal structure of the lumps or physical points is still sufficiently complex but, on the other side, the order should be infinitesimal compared to the number of nodes in the graph, that is
(61) 
In a first step we will now estimate the number of relevant cliques in the network or graph for given bondprobability which implies an of the above type (the numerical calculation follows below). We approximate factorials by the following version of Stirling s formula:
(62) 
This yields
(63) 
(the exponentials drop out)
As we have to deal with extremely large numbers it is useful to take
logarithms:
(64) 
where we have left out marginal contributions and approximated by . We hence have for the assumed range of values:
(65) 
With this estimate we can now estimate , the expected number of cliques.
(66) 
For the range of parameters we are interested in we can approximate by . Evaluating the latter expression for e.g. the values of the list (31), we see that irrespective of the huge prefactor the second term in the above equation becomes negligibly small (for e.g. , and we have . Henceforth we will therefore work with the formula
(67) 
To get an idea of the size of the numbers being involved we provide the following list for the parameters , , taken from (31)
(68) 
Observation 4.15
We see that over a large scale of values, ranging from, say, , we have a of . On the other side, we noted above that from general estimates ([31]) one can infer that the typical cliques are supposed to have values between and . The above list shows that, at least for our possibly extreme values, this number is still appreciable below . On the other side, the upper critical value, i.e. seems to be more reliable.
In a next step we want to estimate the average number of cliques which overlap with a given fixed clique, of a generic order between, say, and . This set of cliques we dubbed the local group or infinitesimal neighborhood of the respective lump or physical point, . This problem winds up to a calculation of certain conditional probabilities. As subset of graphs we take those containing a fixed clique, . The respective relative probability (which is the same as the measure of the set of graphs under discussion) is . In this subclass of graphs we now consider another subset, consisting of the graphs containing yet another clique, having an overlap of order with the fixed given .
The (conditional) probability that an set and an set of nodes span an clique, , clique, , respectively, with common overlap of order is
(69) 
with to be calculated in the following way. We have to apply the same principle as in the calculation of individual cliques, i.e. incorporate the fact that they are maximal members in the class of simplices. On the other side, they now overlap and we have to avoid a double counting of elementary events (i.e. configurations). Maximality plus overlap is then encoded in the following way:
(70) 
with describing the probability that there is no other node in the graph under consideration which has all its links to nodes in being occupied.
In this new probability space of graphs, containing a fixed clique, , there exist possibilities to place an clique with overlap . Hence we have the result
Conclusion 4.16
The expected number of cliques, overlapping with a fixed given clique, , is
(71) 
with
(72) 
To estimate the cardinality, , of the local group of , one has first to sum over all values between, say, and . We showed in the above tabel,(68), that the numbers are rather uniform over a wide range of values so that it is sufficient to estimate the cardinality for some generic value, say, and simply multiply this result with the width of the interval (e.g. in the above table). In a first step we have to convince ourselves that, as in the above numerical calculation, we can again neglect the factors if we are only interested in estimates of the kind order of. Taking logarithms we see that all terms arising from are either very small or at most of . The same holds for the term . They can be neglected compared with the other terms and we hence end up with
(73) 
On the other side, the expected number of cliques not overlapping with is
(74) 
which is for e.g. of the same order as itself (with for ). In other words, we observe already a certain degree of unfolding on the level of the clique graph as compared to the underlying graph, . But nevertheless, as all the estimates are only of orderof type, we cannot use the latter estimate as a substitute for (73) which can also be very large in principle.
Remark 4.17
Previously we approximated in expressions like by , neglecting the term . This suffices as long as . But if as in the above expression, we have to take a further term into account in the approximation of the Stirling formula (cf. (64).
We have
(75) 
For we can still neglect the correction term and get
(76) 
For (and both generic, i.e. of roughly the same order) we have on the other side
(77) 
which is much smaller than the preceding expression.
Conclusion 4.18 (Typical Size of Local Group in Clique Graph )
From the above we infer that the dominant contribution comes from cliques having a relatively small overlap with the given lump, . Neglecting small factors and correction terms we have approximately for generic :
(78) 
with the main contribution coming from