Block cut tree

One of the most important concepts in graph theory is the block cut tree of a graph. The block cut tree of a graph is determined by splitting up the components of a graph into two parts: the cut vertices whose removal disconnects the graph, and the blocks which are biconnected components that don't contain any cut vertices in their own graphs. The block cut tree determines the betweenness relations of the graph, and in particular it completely determines the total betweenness relations which are defined by the set of all points in paths between two points. To consider the block cut tree we will start with the example below.



One thing that is worth realizing about the block cut tree is that cut vertices are singular elements and all blocks have two or more elements in them. This suggests a way of representing the block cut tree as a set system, so I decided to represent it in this way. In order to get the block cut tree like this the function bcset can be used.

(= (bcset graph)
    #{#{0} #{1} #{2} #{3} #{7} #{8}
      #{0 4} #{7 3} #{6 2} #{1 5} #{7 8} 
      #{9 10 8} #{0 1 3 2}})

This produces a height two forest-comparability ordered set system in which cut vertices belong in the blocks associated with them. The block cut tree is merely the inclusion comparability of this set system, which as displayed below is a tree.



One characteristic of the block cut tree, is that every element is either a cut vertex or it is contained in some block. This relates the elements of the graph to the elements of the block cut tree. One interesting aspect of this set system representation is that the block or the cut of the point within the tree can be determined by getting the smallest set containing it. In other words, it can be computed by getting the intersection of the set of all sets that contained the point as a member. This is what the subdimembers function does with respect to the set system.

(= (subdimembers tree 2)
   #{2})
(= (subdimembers tree 10) 
   #{9 10 8})

This relates the members of the graph to the members of the block cut tree. The next thing to be computed is the path between two points in the block cut tree as determined by the sets corresponding to those points. This determines a path between any two points in the block cut tree of the graph. All points between two points can be determined by the union of the elements in this path set system.

(= (bcpath graph 0 9) 
   #{#{0} #{3} #{7} #{8} #{3 7} #{7 8} #{9 10 8} #{0 1 3 2}})
(= (bcinterval graph 0 9) 
   #{0 1 2 3 7 8 9 10})

This demonstrates how the problem of determining all points that are between any two points in the graph regardless of length can be determined by the block cut tree. As a tree is defined as a type of graph that has a unique path between any two points, all the paths between any two points have the same length, so the metric betweenness and the total betweeenness coincide. So well the total betweenness and the metric betweenness don't always coincide, they do coincide in the block cut tree which determines the total betweenness.

Directed and undirected trees

In both graph theory and order theory there is a concept of trees. In graph theory there an undirected trees and in order theory there are directed trees, which are given some root. A tree graph is shown below, its lack of direction is because it is a graph.



One interesting property of graphs is that they have a set of metric intervals associated with them, these metric intervals contain all points between any two points. When the graph is not traceable, then the set of metric intervals will not be upper bounded like it was with the path graph considered earlier. Well the metric intervals of the path graph form a triangular structure, only the maximal sets of the metric intervals of the tree form a triangular structure among there parts in the more general case as shown below.



Well that set of intervals of the tree graph can be considerably larger then the original graph (to a roughly triangular quadratic extent) it is interesting to consider how we can go from the original tree graph to a directed tree graph on the same number of vertices. In order to convert an undirected tree to a directed tree we need some special node to be the root. I realized that the directed version of a tree at some root is simply the set of intervals of the tree with the root as one of its endpoints. This turns into a lower tree with the root as the minimal element, as shown below for the case of the tree graph with the root chosen at zero.



Each set of intervals produced from some root produces a different directed version of the tree. The total set of intervals of the tree is therefore equal to the union of the different rooted orientations of the tree produced in this manner and the empty interval, with non trivial intervals repeated. This rooted set of intervals is also an order containment family. This means that the set of metric intervals centered around some point is also equal to the set of the principal ideals of the corresponding rooted tree.

Triangular family of intervals

Intervals are one of the most basic concepts arises from betweenness relations. A particular family of intervals is shown below. This sort of family can be formed even by metric betweenness on a path graph or order betweenness on a total order. This set system is an atomistic Moore family with a triangular structure. The number of points at some covering distance from the maximum is the covering distance plus one.



The triangular structure of the intervals has three edges. These correspond to the the join irreducibles and the meet irreducibles of the lattice. The edges on the side are the meet irreducibles and the bottom edge is the join irreducibles. The meet irreducibles are the rays and the join irreducibles are the singleton intervals. Every interval can be expressed as an intersection of rays or as a union of singleton intervals. The inner elements of the triangle. The triangular structure seems to be defining character of the set of intervals.

Concepts of betweenness in graph theory

Given a metric space, then metric betweenness can be defined by the metric betweenness formula. This states that a point is between two points if it going to through that point doesn't increase the distance to the endpoints, in other words, if it is in the shortest path between the two points. In the particular case of graphs, their metric can be defined by the shortest path length. Then this concept from the theory of metric spaces can be applied to the special case of graph theory.

$d(x,y)=d(x,z)+d(y,z)$

The actual formula $d(x,y)=d(x,z)+d(y,z)$ should be familiar from the triangle inequality, which is an axiom of the definition of metric spaces. It states that the distance between two points is less then the distance between the two points and a midpoint or it is equal to them in which case it is between them. With this in mind, the axioms of a metric space make perfect sense. The metric betweenness is the main concept of metrics used in both graph theory and metric geometry in general. A different notion is total betweenness defined by all paths rather then just the shortest paths.

Total betweenness:
The most basic context in which to consider total betweenness is trees, where there is only a single path between any two points. In this context, the total betweenness and the metric betweenness coincide. So for example, with a path graph the central vertex is between its two neighbors.


Total betweenness is totally defined by the cut vertices of a graph. To see this, consider that it is only when one reaches a cut vertex then one must make a choice of which direction to go to, which can limit the number of vertices that can be reached between any two points. In a biconnected graph, any points can be reached in a path between any other one. As a consequence, the total betweenness is entirely determined by the block cut tree of the graph. Given any two distinct vertices, all vertices in paths between them can be produced by determining all blocks and cut vertices between the two points in the block cut tree. As this is merely a process of determining betweenness on a tree which is determined by metric betweenness, it can be said that the metric definition is the main form of betweenness worth considering.

Metric betweenness:
Perhaps the simplest case to consider where metric betweenness is different then total betweenness is the case of the cycle graph on five elements. Given two non-adjacent points on this graph, there is a path between them of length three and another one of length four. All the points are between them in the context of total betweenness, but only one of them is under metric betweenness. This demonstrates that metric betweenness can give us more information in some cases.



Once we have a concept of betweenness like this, it is useful to consider convex sets, which are subsets of the graph in which all points between them are contained within the set. A closed metric interval is defined by the set of all points between them plus the endpoints. This leads to a better understanding of subsets of a graph. There is also a concept of betweenness on partial orders, which isn't considered here. This demonstrates how useful betweenness relations can be to a variety of different subjects in mathematics.

Metric recovery theorem

The metric recovery theorem proven by Malament is perhaps the most important theorem for understanding actual space and time, and the relation between order and metric in spacetime. Basically, general relativity describes the structure of spacetime using the metric tensor, which is a four dimensional symmetric bilinear form. This means that the matrix form of the metric tensor is defined by ten points at each point in spacetime. The metric tensor used in general relativity is different from a typical metric used in classical models of spacetime, the euclidean metric, because it carries with it a causal order structure on its points as well.

As the metric tensor used in special and general relativity has a causal factor associated with it, it is useful to consider which relativistic spacetimes can be recovered from a causal ordering relation. The metric recovery theorem basically demonstrates that the metric tensor can be recovered from the causal ordering up to a single conformal scale factor. So nine of the ten distinct terms of the metric tensor can be recovered. The only thing remaining is the conformal factor.

The basic issue of how to construct the conformal factor then is the most important thing that remains. Remember from order topology, that a given partially ordered set can have different topologies associated with it: discrete, scattered, or continuous. One aspect of a discrete partially ordered set, is that concepts like measure and volume come for free from it, and they don't need to be defined separately. It has thus been concluded that spacetime could be modeled as a discrete partial order, with the conformal factor being volume, and then there is no need for any extra structure. This is the program of causal set theory.

It has been said that spacetime looks awfully a lot like a discrete partially ordered set. Rather it is one or another is a separate issue, it certainly looks like one. On the other hand, one can attach a conformal scale factor to a continuous partially ordered in order to allow for an effective continuous model of spacetime. This leads to the metric tensor. In either case, spacetime can be modeled as a partial order. It is either a discrete partial order or a continuous partial order which is equipped with a conformal scale factor.

References: Malament, David B. (July 1977). "The class of continuous timelike curves determines the topology of spacetime". Journal of Mathematical Physics.

World games

I will consider for the purpose of philosophizing about space and time world games which have spatial relations through a world and temporal relations through gameplay of some kind. Of particular interest is the kinematics of units, which can move in certain patterns in the world. I will start with considering combinatorial game theory in particular. In combinatorics, spatial relations can be modeled by graphs and time can be modeled by partial orders. Conway's game of life can be considered a zero-player combinatorial game, the spatial relations are basically a king's graph where each position is related vertically, horizontally, and diagonally. Checkers has its own sort of graph, defined by the movements of units backwards and forwards.

Chess is a separate concept because of the different kinds of motions of its units. This makes one wonder what the space of the world of chess means. Perhaps the most sensible thing, in general is that the spatial relations are the union of the knight's graph and the queen's graph. This is a diameter two graph, which means that no matter what unit you are using there are places that cannot be reached. This means the chess space at least preserves some sense locality which wouldn't be there if its union graph was diameter one.

Then there are a variety of subgraphs of these graph that determine the kinematics of different units. The minor piece graphs the bishop graph, the knight's graph, and the bishop graphs are all perfect. The bishop graphs are defined for different square colors, and the knight's graph is also bipartite. The bishop graphs need to be defined for a subset of the total space, because they cannot change colors. The rook graph is diameter two, which is shared by the queen's graph since it is a supergraph, as well the graph of the whole space, etc. The king's graph is also defined for the king. All of these are different graphs that describe the movement of different units. There are many different variants of chess as well.

Generally the most popular of these games tend to be board games where the world is simply the board and units move around it. War games are another interesting case, where the games tend to have a world map. The world map can have rivers, roads, mountains, forests, plains, and other concepts analogous to these concepts of real world geography. Likewise, units tend to come in a variety of forms, which can be moved around in these world which is a concept of space. Analogous concepts occur in turn-based and real time strategy games, which have spatial maps that units can move around in. A separate concept, something like an action game, tends to have only one main unit but they still tend to have some spatial world they take place in.

Metaphysics of space and time

In the mathematical abstractions of space time I described that I think that space and time can be specified by the mathematical concepts of metric and order. These are mathematical abstractions of our physical concepts of space and time. When space and time are separated from their physical meaning in this way, then they take on a metaphysical meaning.

When considering different metaphysical possibilities, like the notion of a two dimensional flat world like space structure, a space with more dimensions, or something like an automata whose only notion of space is a graph and whose time is merely a discrete total order, quite obviously we are already divorcing the concepts of space and time from their actual physical meaning.

As space and time can be considered both metaphysically as well physically, I would would feel remiss without talking at least a little about the nature of physical space and time. There are two important sources of realizations about physical space and time (1) special relativity and (2) general relativity. Special relativity at least tells us that the type of order that we will use for time must be a partial order rather then a total order. Many of these models mentioned before like automata tend to have absolute time which makes them a bad match for reality. The partial order underlying spacetime, could even be the fundamental structure of the universe as described by causal sets.

Then there is the issue of general relativity and the whole issue of the curvature of spacetime. There are two aspects to the curvature of spacetime (1) the local curvature (2) the global curvature. The global curvature appears to be mostly flat, so the curvature is largely caused by local phenomena in spacetime. The curvature is very much localized, because the gravitational force follows the inverse square law. It is localized both in space and time because the curvature can change over time, which means there is not a constant geometry of the universe. This means that you cannot simply use a separate concept like a metric to describe space separate from time. Nonetheless, it is often useful to consider metrics as a separate concept as described earlier.