Immediate Snapshot Subdivisions
Abstract
Throughout this book, we have relied on the fact that 
, the standard chromatic subdivision of the 
-simplex 
defined in Chapter 3, is indeed a subdivision of 
. In this chapter, we give a rigorous proof of this claim.
Keywords
Schlegel diagram; Affinely independent; Cross-polytope; Polytope; Subdivision
Throughout this book, we have relied on the fact that 
, the standard chromatic subdivision of the 
-simplex 
defined in Chapter 3, is indeed a subdivision of 
. In this chapter, we give a rigorous proof of this claim.
The complex 
captures all single-layer immediate snapshot executions for 
processes. Recall that a single-layer immediate snapshot execution is given by a schedule 
, where each 
is the set of processes that participate in step 
, the 
are disjoint, and the complete set of processes 
is their union. We call 
an ordered partition of 
.
16.1 A glimpse of discrete geometry
16.1.1 Polytopes
Recall from basic linear algebra that a hyperplane in 
is a solution of a single linear equation 
. Given such an equation, we also have two open half-spaces: the set of points for which 
and the set for which 
. It also defines two closed half-spaces: the unions of the hyperplane with the open half-spaces.
A 
-dimensional convex polytope1 
is the convex hull of finitely many points in 
, where we assume that not all points lie on the same hyperplane. A face of a polytope 
is the intersection of 
with a hyperplane that does not intersect the interior of 
. An 
-dimensional polytope 
is bounded by a number of 
-dimensional faces, which are themselves polytopes. In fact, 
is an intersection of the closed half-spaces associated to its 
-faces.
16.1.2 Schlegel diagrams
In general, it can be complicated to prove that one simplicial complex is a subdivision of another, even for a subdivision of a simplex. A straightforward argument would need to go into the technical details of topology of a geometric simplicial complex, possibly having to deal with explicit point descriptions as convex combinations of the vertices and so on.
Fortunately, in this case there is a short-cut: Schlegel diagrams. Informally, a Schlegel diagram is constructed by taking a “photograph” (perspective projection) of the polytope from a vantage point just outside of it, centered over a chosen 
-face 
. Since the polytope is convex, it is possible to choose the vantage point so that all the faces project onto 
and the projections of disjoint faces are themselves disjoint.
Let us make this more specific. Pick a 
-dimensional face 
of the polytope 
. As noted, 
itself is a 
-dimensional polytope obtained as an intersection of 
with some hyperplane 
so that the rest of the polytope lies entirely on one side of this hyperplane. Let 
denote the open half-space bordered by 
, which does not intersect the polytope 
. Choose a point 
in 
very close to the barycenter of 
(in fact, any point in the interior of 
will do). Now project the boundary of the polytope 
along the rays connecting it to 
into the hyperplane 
. If 
is sufficiently close to the barycenter of 
, the image of that projection will be contained in 
. (In fact, topologically it will be precisely 
.) Furthermore, by linearity, the images of the faces on the boundary of 
, excluding 
itself, will constitute a polyhedral subdivision of 
, which we denote 
. See Figure 16.1 for examples of Schlegel diagrams of a tetrahedron, cube, and dodecahedron.
16.1.3 Schlegel diagrams of cross-polytopes
A polytope whose 
-faces are simplices is said to be simplicial. If the polytope 
is simplicial, then the Schlegeldiagram is a simplicial subdivision of the 
-simplex 
. We now consider a specific simplicial polytope in 
. For 
, let 
denote the point whose 
coordinate is 
, and all other coordinates are 
. Let 
be the convex hull of the point set 
. It is easy to see that these 
points are in convex position and that the obtained polytope is simplicial. This is the so-called cross-polytope. Since for any pair of 
-faces of 
there exists a symmetry of 
moving one of the faces to the other one, the Schlegel diagram will not depend on which face of 
we choose, so we just write 
. Examples of Schlegel diagrams for crosspolytopes of dimensions 1 and 2 are shown in Figure 16.2. Note that the boundary complex of 
is precisely the simplicial join of 
copies of the simplicial complex consisting of two points with no edge between them.
We shall need the following combinatorial description of the simplicial complex 
. The set of vertices is indexed by 
, where for every 
, the pair 
denotes the inner point of 
corresponding to the 
axis, whereas the pair 
denotes the vertex of the 
-simplex used as the initial face for constructing the Schlegel diagram, corresponding to the 
axis. The 
-dimensional simplices of 
are all tuples 
such that 
.
Clearly, the advantage of using Schlegel diagrams is that one gets the fact that the diagram is a subdivision of the face for free. Figure 16.2 shows that 
is isomorphic to 
, whereas 
is different from 
. To get from 
to 
one needs to further subdivide each of the edges of the triangle and extend these subdivisions to the subdivision of 
. For higher 
, one needs to do this several times.
16.1.4 Extending subdivisions of simplices
To generalize the construction to higher dimensions, we need the following standard fact about simplicial complexes. Let 
be an arbitrary simplicial complex, and let 
be any simplex of 
. Recall that the (closed) star of 
is the union of all simplices that contain 
, denoted by 
. The complex 
is the union of 
and the deletion 
. The intersection of these two pieces is precisely the join of the link 
with the boundary 
. The closed star itself is the simplicial join of 
with its link (see Section 3.3).
Now assume that 
is a subdivision of 
that only subdivides the interior of 
while leaving the boundary of 
unchanged. A Schlegel diagram is an example of such a subdivision. In this case, the join of 
with 
is a subdivision of 
.
Fact 16.1.1
Whenever we have a join of two simplicial complexes 
, we can replace 
with any simplicial subdivision 
and the obtained complex 
will be a subdivision of 
. One can see this geometrically if one remembers the realization of the join from Section 3.3. Indeed, when 
and 
are embedded in complementary dimensions and the join is obtained by drawing all the line segments connecting points in 
and in 
, then it is immediate that replacing 
with its subdivision will subdivide the join.
Back to our subdivision: We notice that since it does not change the link of 
, and it does not change the boundary 
, it will also not change their join. Since this is precisely the space along which we attach 
, we can extend our local subdivision to a global subdivision of the entire 
.
We now have all the tools at hand to describe how to obtain the chromatic subdivision 
. Start with 
. Subdivide it as a Schlegel diagram of the cross-polytope. Proceed with the faces of 
of codimension 
; replace them with corresponding Schlegel diagrams and extend these subdivisions using the argument above to the global subdivision of the entire complex. After this, proceed to do the same for the faces of 
of codimension 
and so on. We denote the simplicial complexes constructed in this way by 
. In short: To go from 
to 
, we replace all boundary simplices of codimension 
of the original simplex 
with Schlegel diagrams 
and then extend this to the subdivision of the entire 
as described previously.
We are now ready to give a combinatorial description of the simplicial structure that we get at every step of the process.
, the simplicial complex 
has the following combinatorial description:
are indexed by pairs 
such that 
, and either 
or 
.
-simplices of 
are indexed by all sets of 
vertices corresponding to tuples 
, with 
, satisfying the following conditions:
whenever 
and 
Proof
First we note that for 
, we get only vertices 
, with 
, i.e., the vertices 
. These form a single 
-simplex; so our combinatorial description is correct for 
.
Let us now show that for 
, the transformation from 
to 
produces the combinatorial simplicial structure described in the proposition. For convenience, we define 
to be the minimal index such that 
, and set 
.
First we consider what happens to vertices. For every simplex of 
of codimension 
, i.e., for every subset 
such that 
, we add new vertices 
, where 
. This is consistent with the Schlegel construction and with the description of the set of vertices of 
.
Next we analyze what happens with the 
-simplices. Many 
-simplices stay intact. Those that get subdivided are of the form 
such that 
. Each such 
gets replaced by new 
-simplices, which are obtained as follows: Choose a non-empty subset 
. For ease of presentation, we can reindex the vertices so that there exists 
such that 
, i.e., 
. Then the new simplex is
We have 
and 
. To see that this is exactly what happens when Schlegel diagrams are extended to the entire complex, one can think of the part 
as the maximal face of the corresponding cross-polytope indexed by the tuple 
. In the Schlegel constructions it gets replaced by simplices indexed by all possible nonempty subsets of 
. Then the extension of these subdivisions to the entire complex corresponds to appending this with the rest of the vertices, which is exactly what we do. The obtained 
-simplices are precisely those occurring in our description of the 
-simplices of 
, where the order of the vertices is given by the construction. 
Corollary 16.1.3
.
Proof
For 
we have 
, which means that there is at most one singleton set among 
. We see that the vertices of 
are all the pairs 
for 
, 
, whereas a set of 
vertices forms a 
-simplex if and only if it can be ordered into a tuple 
satisfying 
, 
, and 
whenever 
. In other words, the conditions for the sets of 
vertices to form 
-simplices translate precisely into our previous description of the simplicial complex 
. 
Remark 16.1.4
For 
, the transient simplicial complexes 
can also be given a distributed computing interpretation. Namely, we consider all the executions where in the initial stage a certain number of processes, numbering at most 
, will only perform the write operation, with the rest of processes functioning normally and performing a write with the immediate snapshot read operation. In particular, the views of those first “write-only” processes consist solely of their own names. Note that this also explains the equality 
, since it does not matter whether the first process also reads or not after it wrote its name into the shared memory.
16.2 Chapter notes
The material in this chapter is adapted from Kozlov [101].
More information on Schlegel diagrams can be found in Grunbaum [74] and more on cross-polytope in Coxeter [42].
16.3 Exercises
Exercise 16.1
Let 
denote the number of 
-simplices in the chromatic subdivision 
. Give recursive formulas for the numbers 
. Can you estimate their asymptotics? What is the answer in the special cases 
and 
?
Exercise 16.2
Describe the links of vertices in 
as complexes constructed from standard chromatic subdivisions of simplices of lower dimension. How many different types of links are there?
Exercise 16.3
Describe the links of 
-simplices of 
for arbirary 
, using standard chromatic subdivisions of simplices of lower dimension.
1This is a special case of what is called polytope in some literature, which will be sufficient for our purposes.