text:
# FINDING TOPOLOGY IN A FACTORY: CONFIGURATION SPACES

## 1. Configurations and Braids

Our story begins with a classical construction: that of a configuration space of points. We consider first the configuration space of $`N`$ distinct labelled points in the plane $`^2`$. That is, we consider all ordered $`N`$-tuples of points in $`^2`$ with the property that no two of the points coincide. To each such $`N`$-tuple, visualized as a collection of labeled tokens on a tabletop, we assign a point in the configuration space. Two points in the configuration space are close if the $`N`$-tuples are close as measured in $`^{2N}`$. One can write this mathematically as

$$𝒞^N(^2):=\left(^2\times ^2\times \mathrm{}\times ^2\right)\mathrm{\Delta },$$

where $`\mathrm{\Delta }`$ denotes the “pairwise diagonal”

$$\mathrm{\Delta }:=\{(x_1,x_2,\mathrm{},x_N)(^2)^N:x_i=x_j\text{ for some }ij\}.$$

This configuration space is not easy to visualize, in no small part because the dimension of the space is $`2N`$.

exercise: Show that $`𝒞^2(^2)`$ is homeomorphic to $`^2\times (^2(0,0))`$ or equivalently $`^3\times S^1`$, where $`S^1`$ denotes the unit circle in $`^2`$. Hint: think about placing tokens on the table one at a time. Does your method of proof give a simple presentation for $`𝒞^3(^2)`$?

The configuration space of points on a plane, like so many other mathematical objects, finds multiple applications to physical problems. For example, any loop (closed curve) in $`𝒞^N(^2)`$ is a pure braid on $`N`$ strands, so called because of the space-time graph of the loop in $`𝒞^N(^2)`$: see Figure 1. (The word pure indicates that each token returns to its original location, rather than the tokens getting permuted in some other way. Other permutations give rise to general braids, which are loops in the space of unlabeled configurations of points in the plane.) Braids are ubiquitous in the study of knots and links , and thus find their way into applications ranging from quantum field theory to dynamical systems to DNA modeling.

## 2. Robotics and Topological Motion Planning

The space $`𝒞^N(^2)`$ itself appears naturally in robotics.

Consider an automated factory equipped with a cadre of Automated Guided Vehicles (AGVs), or mobile robots, capable of transporting items from place to place. A common goal is to place several, say $`N`$, of these AGVs in motion simultaneously. It is necessary to enact a control algorithm which perhaps moves the AGVs from their initial positions to their goal positions (in a warehousing application), or which executes a cyclic pattern (as arises in manufacturing applications). As might be expected, these robots are somewhat costly and cannot tolerate collisions without a loss of performance. Thus, modeling the factory floor as $`^2`$ and the AGVs as points, one often wishes to find paths or cycles in $`𝒞^N(^2)`$ to enact specific behaviors.111Obstacles can easily be incorporated into these models — a vast literature on this subject exists . Executing cyclic motions is more complex but can be at first approximated by composed point-to-point motions. There are several assumptions required for the simple construction we present, and various kinematic issues (e.g., steering geometry) must in general be addressed. Of course, since the robots are not truly points, and since no control algorithm implementation is of infinite precision, we require that the control path reside outside of a neighborhood of the diagonal $`\mathrm{\Delta }`$ in $`(^2)^N`$.

Fortunately, this problem is not impossible to solve. The work of Koditschek and Rimon  provides one example of a concrete solution: they write out explicit vector fields on these configuration spaces which can be used to flow from initial to goal positions in the presence of certain types of obstacles. By arranging these vector fields so that they strongly push away from the vestiges of the diagonal $`\mathrm{\Delta }`$ on the boundary of $`𝒞^N(^2)`$, the control scheme is provably safe from collisions (as opposed to being statistically safe via computer simulations): no path can ever intersect the diagonal. Furthermore, since a neighborhood of the diagonal is repelling, the control scheme is stable with respect to perturbations to the system. This is quite important as mechanical systems have an annoying tendency to occasionally malfunction. Drawing the appropriate vector field on a configuration space yields an excellent method of self-correction.

This is a clean, direct application of topological and dynamical ideas to a matter of great practical relevance which is currently used in various industrial settings.

One reason why this problem has a nice solution is evident to anyone who regularly shops at a large supermarket: numerous shopping carts trace out paths in a workspace that consists of wide aisles. If two carts are headed toward each other, one needs merely steer out of the way a little bit (assuming the other does not move in the same direction!) to avoid a collision. The resolution of collisions on $`^2`$ is a local phenomenon.

## 3. Graphs

The robotics community, largely independently of the topology community, has enjoyed great success at identifying and manipulating configuration spaces to their advantage in control problems. There is, however, a class of simple, physically relevant scenarios whose configuration spaces have been untapped: the configuration spaces of points on a graph, or a network of edges and vertices.

Consider the situation where the AGVs must move about on a collection of tracks embedded in the floor, or via a path of electrified guide-wires from the ceiling (see  for examples). Such a restricted network is quite common, mainly because it is more cost-effective than a full two-degree-of-freedom steering system for AGVs. In this setting, the state of the system at any instant of time is a point in the configuration space of the graph $`\mathrm{\Gamma }`$:

$$𝒞^N(\mathrm{\Gamma }):=\left(\mathrm{\Gamma }\times \mathrm{}\times \mathrm{\Gamma }\right)\mathrm{\Delta }.$$

The same principles previously mentioned still apply. To navigate safely on a graph, one must construct appropriate paths which remain strictly within $`𝒞^N(\mathrm{\Gamma })`$ and are repulsed by any boundaries near $`\mathrm{\Delta }`$. Several problems have arisen which heretofore have prevented an analogous solution.

1. What do these spaces look like?
2. How does one resolve an impending collision?

Notice the differences between this problem and the problem of $`𝒞^N(^2)`$. First of all, in relation to (1) above, $`𝒞^N(\mathrm{\Gamma })`$ is not a manifold: that is, you cannot hope that every point has a neighborhood which is locally homeomorphic to a Euclidean space. Indeed, if we ignore the trivial graphs which are homeomorphic to a line segment or a circle, then the graph itself is not locally Euclidean and products of the graph will share this feature. Second, concerning (2) above, collisions within the interior of an edge are no longer locally resolvable. Imagine that the aisles of the grocery store are only as wide as the shopping carts, so that passing another person is impossible. A store full of shoppers (using carts) would pose a difficult coordinated control problem. How can carts avoid a collision in the interior of an aisle? Clearly at least one of the participants must make a large-scale change in plans and back up to the end of the aisle. The resolution of a collision on a graph is a non-local phenomenon.

## 4. Examples: two robots

Since a graph is a one-dimensional object, the configuration space $`𝒞^N(\mathrm{\Gamma })`$ is $`N`$-dimensional. Thus configuration spaces of two robots are two-dimensional objects, which (at least in simple cases) one should be able to visualize. We therefore give numerous examples of configuration spaces of two robots.

example 1: $`𝒞^2(\text{})`$

Let denote the graph of three edges attached at a central vertex. The cellular structure of $`𝒞^2(\text{})`$ is simple to procure. There are six (two robots times three-choose-two edges) squares or “2-cells”, each with one corner punctured, corresponding to those configurations where the two robots are on distinct edges of . Since there are three edges in , those remaining configurations in which both robots are on the same edge yield three square cells, each of which is divided by the diagonal $`\mathrm{\Delta }`$ into a pair of triangular cells. Thus there are six triangular 2-cells corresponding to those configurations where both robots are on the same edge, but distinct. By enumerating the behaviors of each of these 2-cells, one can make the identifications to arrive at the space given in Figure 2 (or, one can use a slightly more sophisticated argument as in ).

exercise: Place two coins on a piece of paper with a large drawn on it so that both coins are on the same edge of the graph. Using two fingers, execute a path which exchanges the coins’ positions without collisions. Draw this motion as a path on Figure 2.

example 2: $`𝒞^2(\text{})`$

Let denote the graph with three edges obtained from by gluing two boundary vertices together. One method of constructing $`𝒞^2(\text{})`$ would be to first remove the configurations where both robots are on the vertices to be glued. Then identify those portions of the boundary of $`𝒞^2(\text{})`$ which have a robot at the vertices to be glued in , and glue these portions of $`𝒞^2(\text{})`$ together. The result, although a very simple configuration space, is already somewhat difficult to visualize: we illustrate the space, embedded in $`^3`$, in Figure 3\[left\]. There are three “punctures” at which both robots collide at one of the three vertices. The six dotted edges are the images of the diagonal curves from Figure 2.

example 3: $`𝒞^2(\text{})`$

Increasing the incidence number of the central vertex complicates the configuration space. Consider a radial tree of four edges emanating from a central vertex. The visualization of $`𝒞^2(\text{})`$ is a bit more involved and requires some work to obtain. For the purpose of stimulating curiosity, we include this configuration space as Figure 3\[right\].

## 5. Simplification: discretization

To visualize these configuration spaces, it is clear that some simplification into a more manageable form is necessary. There are two principal methods we use: the first is a way of removing the “unsafe” cells of the space near the diagonal $`\mathrm{\Delta }`$. The second, deformation retraction, is a more drastic crushing of the space down to a lower dimensional “skeleton,” as discussed in the subsequent section.

Any graph $`\mathrm{\Gamma }`$ comes equipped with a cellular structure: 0-cells (vertices) and 1-cells (edges). The $`N`$-fold cross product of $`\mathrm{\Gamma }`$ with itself inherits a cell structure, each cell being a product of $`N`$ (not necessarily distinct) cells in $`\mathrm{\Gamma }`$: cf. Example 1. However, the configuration space does not quite have a natural cell structure, since the diagonal $`\mathrm{\Delta }`$ slices through all product cells with repeated factors. Notice, however, that in several of the previous examples, these partial cells dangle “inessentially” and could be collapsed onto a more “essential” skeleton of the configuration space.

Such an operation can be interpreted as follows . Consider the discretized configuration space of $`\mathrm{\Gamma }`$, denoted $`𝒟^N(\mathrm{\Gamma })`$, defined as $`\left(\mathrm{\Gamma }\times \mathrm{}\times \mathrm{\Gamma }\right)\stackrel{~}{\mathrm{\Delta }}`$, where $`\stackrel{~}{\mathrm{\Delta }}`$ denotes the set of all product cells in $`\mathrm{\Gamma }\times \mathrm{}\times \mathrm{\Gamma }`$ whose closures intersect the diagonal $`\mathrm{\Delta }`$. An equivalent description of $`𝒟^N(\mathrm{\Gamma })`$ is that it is the set of configurations for which, given any two robots on $`\mathrm{\Gamma }`$ and any path in $`\mathrm{\Gamma }`$ connecting them, the path contains at least one entire edge. Thus, instead of restricting robots to be at least some intrinsic distance $`ϵ`$ apart (i.e., removing an $`ϵ`$ neighborhood of $`\mathrm{\Delta }`$), one now restricts robots on $`\mathrm{\Gamma }`$ to be “at least one full edge apart.” This is a natural kind of configuration space in the context of random walks on graphs . Note that $`𝒟^N(\mathrm{\Gamma })`$ is a subcomplex of $`𝒞^N(\mathrm{\Gamma })`$ (it does not contain “partial cells” which arise when cutting along the diagonal), and is, in fact, the largest subcomplex of $`𝒞^N(\mathrm{\Gamma })`$ which does not intersect $`\mathrm{\Delta }`$.

With this natural cell structure, one can think of the vertices (0-cells) of $`𝒟^N(\mathrm{\Gamma })`$ as “discretized” configurations — arrangements of labeled tokens at the vertices of the graph. The edges of $`𝒟^N(\mathrm{\Gamma })`$, or 1-cells, tell you which discrete configurations can be connected by moving one token along an edge of $`\mathrm{\Gamma }`$. Each 2-cell in $`𝒟^N(\mathrm{\Gamma })`$ represents two independent (or “commuting”) edges: one can move a pair of tokens independently along disjoint edges. A $`k`$-cell in $`𝒟^N(\mathrm{\Gamma })`$ likewise represents the ability to move $`k`$ tokens along $`k`$ disjoint edges in $`\mathrm{\Gamma }`$.

Returning to Figure 2, the discretization of $`𝒞^2(\text{})`$ removes much of the space. For example, the triangular two-dimensional cells represent configurations where both robots are on the interior of the same edge. Since these are not “one full edge apart,” these cells are deleted. The same is true of all the other two-dimensional cells which represent robots in the interior of separate edges. Which configurations of two robots on are separated by a full edge?

exercise: Show that discretizing the configuration spaces of Examples 1 through 3 yields the configuration spaces of Figure 4. How good of an “approximation” are these spaces?

One could compute the discretization of Example 1 in a less direct manner which generalizes to some lovely examples to follow. Recall that the discretized configuration spaces inherit a cell structure from $`\mathrm{\Gamma }`$: all the product cells of $`\mathrm{\Gamma }^N`$ not entirely in $`𝒞^N(\mathrm{\Gamma })`$ are removed by the discretization. Thus, in the case of Example 1, simple counting reveals that the space $`𝒟^2(\text{})`$ possesses twelve 0-cells (where both robots are at distinct vertices of ), twelve 1-cells (where one robot is at a vertex and the other is on an edge whose closure does not contain said vertex), and zero 2-cells (since every pair of edges intersect along their boundaries). With a little thought, one can see that $`𝒟^2(\text{})`$ is a connected manifold: each zero-cell connects to exactly two 1-cells, and all of the 1-cells are joined end-to-end cyclically. Thus, $`𝒟^2(\text{})`$ is a topological circle, precisely as obtained by deleting all the near-diagonal cells from $`𝒞^2(\text{})`$ in Figure 2. The discretization operation yields a subcomplex of $`𝒞^2(\text{})`$ which appears to contain all the “essential” topology (more specifically, the spaces $`𝒞^N(\text{})`$ and $`𝒟^N(\text{})`$ are of the same homotopy type — see the next section for definitions); however, this is certainly not the case for the discretization of $`𝒞^2(\text{})`$, which becomes disconnected! In the next section, we will state the criteria under which discretization is topologically faithful.

The counting arguments used above often can determine the discretized configuration space, even when the full configuration space is unknown. The following are some surprising examples of interesting spaces arising as the discretized configuration space of non-planar graphs .

example 4: $`𝒟^2(K_5)`$

Consider the complete bipartite graph $`K_5`$ pictured in Figure 5\[left\]. The discretized configuration space of two robots on this graph is a two-dimensional complex. A simple counting argument reveals the cell-structure:

1. Each 0-cell corresponds to a configuration in which the two robots are at distinct vertices. Since $`K_5`$ has five vertices, there are exactly $`(5)(51)=20`$ such 0-cells. (Remember, there is no vertex where two edges cross in the picture; there are only vertices at the corners of the pentagon.)
2. Each 1-cell corresponds to a configuration in which one robot is at a vertex and the other is on an edge whose endpoints do not include the vertex already occupied. From the diagram of $`K_5`$ one counts that there are $`(2)(5)(6)=60`$ such 1-cells, as in Figure 6\[left\]. The factor of two comes from the fact that we label the two robots on $`K_5`$.
3. Each 2-cell corresponds to a configuration in which the two robots occupy edges whose closures are disjoint. Again, from the diagram (and Figure 6\[middle\]) one counts that there are $`(10)(3)=30`$ such 2-cells in the complex.

One then demonstrates that each edge borders a pair of 2-cells preserving an orientation and that each vertex is incident to six edges, as in Figure 6\[right\]. Also, the space $`𝒟^2(K_5)`$ is connected: it is not hard to see that you can move from any configuration to any other. Thus $`𝒟^2(K_5)`$ is a connected orientable surface, and the Classification Theorem for surfaces implies that the space is determined uniquely up to homeomorphism by the Euler characteristic,

(5.1)
$$\chi (𝒟^2(K_5)):=\mathrm{\#}\text{faces}\mathrm{\#}\text{edges}+\mathrm{\#}\text{vertices}=3060+20=10.$$

Thus, $`𝒟^2(K_5)`$ is a closed orientable surface of genus $`g:=1\frac{1}{2}\chi =6`$. It is not at all obvious that the motion of two robots on this graph should produce a genus six surface. Obtaining a manifold is surprising enough, but a manifold with genus larger than one really goes against the notion that all of the interesting topology in these spaces is “localized” in configurations about a vertex.

example 5: $`𝒟^2(K_{3,3})`$

A near-identical analysis on the graph $`K_{3,3}`$ of Figure 5\[right\] reveals that $`𝒟^2(K_{3,3})`$ is also a connected closed orientable surface. The natural cell structure on $`𝒟^2(K_{3,3})`$ possesses exactly 36 faces, 72 edges, and 30 vertices. Thus,

(5.2)
$$\chi (𝒟^2(K_5))=3672+30=6,$$

and we conclude that the genus of this surface is four.

In order to understand discretizations of higher-dimensional configuration spaces, one can employ an appropriate version of duality : instead of tracking how distinct robots on $`\mathrm{\Gamma }`$ move about, one considers configurations of “holes” — regions on $`\mathrm{\Gamma }`$ which have no robots on them. As the holes have no natural labeling, the duality applies directly to the unlabeled configuration spaces. It nevertheless implies a relationship between $`𝒟^N(\mathrm{\Gamma })`$ and $`𝒟^{VN}(\mathrm{\Gamma })`$, where $`V`$ is the number of vertices of $`\mathrm{\Gamma }`$. Using this duality, one obtains the following examples.

example 6: The space $`𝒟^3(K_5)`$ is homeomorphic to a connected closed orientable surface of genus 16.

example 7: Likewise, $`𝒟^4(K_{3,3})`$ is homeomorphic to a connected closed orientable surface of genus 37.

## 6. Simplification: deformation

We are naturally led to the question of how good an approximation the discretized configuration space is. Heuristically, the spaces $`𝒞^N`$ and $`𝒟^N`$ should be “similar,” since the latter is a subset of the former obtained by collapsing out those cells which border the remains of the diagonal $`\mathrm{\Delta }`$. That the discretization is not always faithful is evidenced by the fact that $`𝒞^2(\text{})`$ is connected while $`𝒟^2(\text{})`$ is not. Indeed, by definition, $`𝒟^N(\mathrm{\Gamma })`$ is the empty set whenever $`N`$ is greater than the number of vertices of $`\mathrm{\Gamma }`$: i.e., when the discretization of $`\mathrm{\Gamma }`$ is too “coarse.”

The notion of “sameness” appropriate here is that of deformation retract. A subspace $`A`$ of a space $`X`$ is a (strong) deformation retract of $`X`$ if there exists a continuous family of continuous maps $`f_t:XX`$ such that $`f_0`$ is the identity map on $`X`$ and $`f_1`$ is a map which sends $`X`$ onto $`A`$, and such that $`f_t`$ fixes $`A`$ pointwise for all $`t`$. The image of each $`f_t`$ can be seen as frames in a movie which exhibits a continuous shrinking of $`X`$ onto $`A`$. Deformation retractions are an excellent way to simplify a space without changing any essential topological properties.222Except perhaps dimension, but for the applications at hand, reducing the dimension of the configuration space is a boon. The most fundamental notion of topological equivalence, homotopy type, can be defined in terms of deformation retracts: two spaces $`X`$ and $`Y`$ are of the same homotopy type if and only if they are both deformation retracts of a “larger” space $`Z`$.

The key result is that $`𝒟^N(\mathrm{\Gamma })`$ is a deformation retract of $`𝒞^N(\mathrm{\Gamma })`$ as long as the discretization of the graph $`\mathrm{\Gamma }`$ is not too coarse. More specifically,

Theorem 1: \[Abrams \] For any $`N>1`$ and any graph $`\mathrm{\Gamma }`$ with at least $`N`$ vertices, $`𝒞^N(\mathrm{\Gamma })`$ deformation retracts to $`𝒟^N(\mathrm{\Gamma })`$ if and only if

1. Each path between distinct vertices of valence not equal to two passes through at least $`N1`$ edges; and
2. Each loop from a vertex to itself which cannot be shrunk to a point in $`\mathrm{\Gamma }`$ passes through at least $`N+1`$ edges.

(The valence of a vertex is the number of incident edges.)

It thus follows that the spaces $`𝒞^2(K_5)`$ and $`𝒞^2(K_{3,3})`$ deformation retract to the discretized configuration spaces computed in Examples 4 and 5. This is extremely useful information: trying to compute the configuration space $`𝒞^2(K_5)`$ directly would appear hopelessly complex. Note that the second condition fails for the discretization of $`𝒞^2(\text{})`$, but adding one more vertex would yield a faithful discretized configuration space. The discretizations of Examples 6 and 7 are not fine enough to give an equivalence.

The dimension of the smallest subcomplex to which a configuration space deformation retracts is an important quantity in practice, since a large dimension greatly increases the complexity of the computational work needed to control the system. The following theorem reveals that the essential dimension of the configuration space is governed by properties of the graph, independent of the number of robots on the graph.

Theorem 2: \[Ghrist \] Given a graph $`\mathrm{\Gamma }`$ having $`V`$ vertices of valence greater than two, the space $`𝒞^N(\mathrm{\Gamma })`$ deformation retracts to a subcomplex of dimension at most $`V`$.

example 8: $`𝒞^N(\mathrm{{\rm Y}}_k)`$

Consider the radial $`k`$-prong tree $`\mathrm{{\rm Y}}_k`$ having $`k>2`$ edges and $`k+1`$ vertices, all edges being attached at a single central vertex. For example, $`\mathrm{{\rm Y}}_3=\text{}`$, and $`\mathrm{{\rm Y}}_4=\text{}`$. From the above theorem, we see that $`𝒞^N(\mathrm{{\rm Y}}_k)`$ must deformation retract to a 1-dimensional subcomplex — that is, a graph. Since the essential topological features of a graph are determined by its Euler characteristic, one need merely compute the number of vertices and edges to classify these spaces. Using a double-induction argument on $`N`$ and $`k`$ , one derives a two-variable recursion relation for the Euler characteristic. By solving this equation, one can prove that $`𝒞^N(\mathrm{{\rm Y}}_k)`$ has the homotopy type of a graph which is a “bouquet” of $`P`$ distinct loops joined together like petals on a daisy, where

(6.1)
$$P=1+(Nk2Nk+1)\frac{(N+k2)!}{(k1)!}.$$

Note, for example, that $`𝒞^2(\mathrm{{\rm Y}}_3)`$ has exactly one generating loop, as Figures 2 and 4\[left\] confirm. Figure 4\[right\] provides another confirmation of this equation for $`k=4`$, as the reader should verify. The factorial growth of $`P`$ in $`N`$ is due to the fact that we label the $`N`$ robots on $`\mathrm{{\rm Y}}_k`$. If one considers the unlabeled configuration spaces, then the second term in the expression above is reduced by a factor of $`N!`$.

It is worth emphasizing that while the control problem of robots on a graph is rather intuitive for two robots, it quickly builds in complexity. Since the dimension alone makes the configuration spaces in general nearly impossible to visualize, Theorem 2 is quite helpful — the “essential” dimension of the configuration space is independent of the number of robots on the graph. For the graph $`\mathrm{{\rm Y}}_k`$, Theorem 2 implies that there is a one-dimensional roadmap which gives a perfect representation of the configuration space: no topological data is lost. Since the proof of Theorem 2 is constructive, one can use standard algorithms for determining shortest paths on a graph in order to develop efficient path planning for multiple robots on $`\mathrm{{\rm Y}}_k`$ via the roadmap.

## 7. Conclusions

Applications of configuration spaces to robotics are by no means novel: ideas by mathematicians, computer scientists, and engineers have been steadily developing since the 1960’s (see, e.g.,  for an introduction). In addition, various kinds of configuration spaces arise in topology and physics rather often, as in the study of braids , abstract linkages , or invariants of manifolds .

In the particular application involving multiple independent robots, the global aspect of the control problem is the principal difficulty when the robots are constrained to a network. It is this global nature which hints at the efficacy of a topological viewpoint. Indeed, the determination and simplification of the configuration spaces of graphs can be used to construct practical control schemes (see  for some simple examples).

Reversing the perspective, it is remarkable that this class of topologically rich configuration spaces were virtually untouched until motivated by problems from other fields. There are many deeper properties of these spaces which one can prove . We list a few below:

1. For any graph $`\mathrm{\Gamma }`$, $`𝒞^N(\mathrm{\Gamma })`$ is an Eilenberg-MacLane space of type $`K(\pi ,1)`$. That is, the image of any continuous map from a $`k`$-dimensional sphere $`S^k`$, $`k>1`$, into $`𝒞^N(\mathrm{\Gamma })`$ can be shrunk to a point in $`𝒞^N(\mathrm{\Gamma })`$. Such a space is sometimes descriptively called “aspherical.”
2. The discretized configuration space has a natural structure of a cube-complex, since all the cells are products of intervals. This allows one to use recent fast algorithms from computational homology to determine homology groups and generators in practical settings.
3. From the cube complex structure of $`𝒟^N(\mathrm{\Gamma })`$, one can show that $`𝒞^N(\mathrm{\Gamma })`$ is an NPC (non-positively curved) space: there exists a metric whose curvature (defined appropriately at the non-manifold points) is never positive.
4. The fundamental groups of these spaces are all torsion-free. In other words, if a loop in $`𝒞^N(\mathrm{\Gamma })`$ cannot be shrunk to a point, then neither can any multiple of the loop. This property is also true for configuration spaces of $`^2`$, but not for $`𝒞^N(S^2)`$ — robots on a two-dimensional sphere.
5. The fundamental groups of these spaces have solvable word problem, which means that there is an algorithm which can be used to decide whether any given loop in $`𝒞^N(\mathrm{\Gamma })`$ can be shrunk to a point in $`𝒞^N(\mathrm{\Gamma })`$.
6. The fundamental group $`\pi _1(𝒞^N(\mathrm{\Gamma }))`$ can be realized as a graph of groups — that is, as a collection of groups (abstractly thought of as vertices in some graph) which are pairwise glued together or “amalgamated” along a network of subgroups (each gluing represented by an edge between vertices).

For those not familiar with these more subtle features of topological spaces and their fundamental groups, we would offer the examples presented here as an excellent concrete manifestation of these properties. One can easily explain what a configuration space of robots is to a high-school class333Both authors have done this on several occasions with positive results., and, upon demonstrating that, e.g., two robots on $`K_5`$ yields a genus six surface, one has an excellent demonstration of the sublime nature of configuration spaces and of topology in general.


format: text

text:
# A Deep Multicolor Survey VII. Extremely Red Objects and Galaxy Formation Based on observations obtained at MDM Observatory, operated by Columbia University, Dartmouth College, the University of Michigan, and the Ohio State University

## 1 Introduction

The most well-known, modern method of using color selection to find high-redshift galaxies is the Lyman-break technique (e.g., Steidel & Hamilton, 1993) and this method has isolated large numbers of galaxies at $`z3`$ and $`z4`$ (Steidel et al., 1996, 1999). The great efficiency of the Lyman-break technique in selecting high-redshift candidates for follow-up spectroscopy from visible wavelength colors has made it easier to preselect samples of $`z3`$ galaxy candidates than galaxies at $`z12`$. A complimentary technique to preselect $`z1`$ galaxy candidates is to use a combination of near-infrared (NIR) and visible wavelength photometry to search for Extremely Red Objects (EROs), which have large visible–NIR colors (Elston, Rieke, & Rieke, 1988; McCarthy et al., 1992).

A sample of galaxies at $`z1`$ can test galaxy evolution theories by measuring both the surface density of these galaxies and the relative fraction of different spectrophotometric types. Hierarchical galaxy formation predicts that present day massive galaxies assemble between $`z1`$ and the present (e.g. White & Rees, 1978; White & Frenk, 1991; Lacey et al., 1993; Baugh et al., 1998). In contrast, the passive evolution model postulates that galaxies assembled at $`z>3`$ and the comoving space density of bright galaxies at $`z1`$ should be comparable to the local value (e.g. Tinsley, 1977; Bruzual & Kron, 1980). Kauffmann & Charlot (1998) showed that hierarchical galaxy formation predicts a significantly smaller fraction of $`z1`$ galaxies in a $`K`$-selected redshift survey relative to passive galaxy evolution. $`K`$band selection is particularly sensitive to differences between these two galaxy formation models because it measures the old stellar population that dominates the mass, rather than recent starbursts which may enhance the luminosity at visible wavelengths. Several $`K`$-selected redshift surveys have indeed found smaller numbers of $`z1`$ galaxies than predicted by passive evolution, in support of the hierarchical galaxy formation picture (Songaila et al., 1994; Cowie et al., 1996; Fontana et al., 1999).

Well-studied EROs to date are all at $`z0.8`$ and appear to be either old ellipticals or dusty starbursts. However, EROs are generally classified as “ellipticals” because their rest-frame visible spectrum is dominated by an old stellar population, rather than on the basis of kinematic or surface brightness criteria. Old ellipticals at these redshifts have very red colors because the 4000 Å break falls between the $`R`$ and $`K`$ bands. Dusty starbursts have similarly extreme colors due to a combination of the Balmer continuum break and the relative suppression of the $`UV`$ light from young stars by dust. The first deep sky survey at $`K`$ by Elston, Rieke, & Rieke (1988) found 2 EROs, which additional photometry and spectroscopy showed were old ellipticals at $`z=0.8`$ (Elston, Rieke, & Rieke, 1989). Several more EROs were found by McCarthy et al. (1992) in a $`K`$ imaging survey of the fields of high-redshift radio galaxies and two EROs were found by Hu & Ridgway (1994) in an imaging survey of a $`z=3.790`$ quasar field. One of these, HR10, has a spectroscopic redshift of $`z=1.44`$ and has since been detected at radio (Graham & Dey, 1996) and submillimeter (Cimatti et al., 1998; Dey et al., 1999) wavelengths. These observations provide strong evidence that HR10 is a dusty starburst galaxy. Another well-studied ERO, LBDS 53W091, was discovered in a NIR study of a sample of weak radio sources. Spectroscopy by Spinrad et al. (1997) showed that it is an old, red galaxy at $`z=1.55`$. Soifer et al. (1999) observed the ERO Cl 0939+4713B, serendipitously discovered by Persson et al. (1993), and found it is an old elliptical at $`z=1.58`$. The spectroscopic observations of HR10, LBDS 53W091, Cl 0939+4713B, and others show that EROs are at $`z0.8`$ and either appear as old ellipticals or dusty starbursts.

The definition of what constitutes an ERO is highly variable and cuts in color include $`RK5`$, 5.3, and 6 and $`IK4`$. Recent surveys for EROs have mapped large areas of the sky at NIR wavelengths to statistically study the ERO population (Thompson et al., 1999; Yan et al., 2000; Scodeggio & Silva, 2000; Daddi et al., 2000). Cimatti et al. (1999) spectroscopically followed up a sample of nine EROs and found that two are dusty starbursts and the remaining seven are consistent with passively evolved ellipticals. Cohen et al. (1999) have obtained spectra of four of the 19 EROs in the Caltech Faint Galaxy Redshift Survey and all appear to be ellipticals with little dust. This spectroscopic work indicates that most EROs are ellipticals, rather than dusty starbursts. While the larger ERO samples only include imaging, Daddi et al. (2000) showed that the EROs in their 700 arcmin2 survey are strongly clustered and their surface density can be used to test galaxy formation models. The clustering of EROs helps to explain the dispersion in measurements of the ERO surface density for a fixed color and magnitude threshold.

This survey for EROs is based on the visible and NIR imaging of the Deep Multicolor Survey (DMS) described in Hall et al. (1996a) and Martini (2001). The original DMS included $`UBVRI_{75}I_{86}`$ photometry of 6 high-galactic latitude fields over a total area of 0.83 deg2. The DMS has been used to study the luminosity function of quasars (Hall et al., 1996b; Kennefick et al., 1997), galactic stars (Martini & Osmer, 1998), the luminosity function of galaxies (Liu et al., 1998), and NIR $`JHK`$ number counts (Martini, 2001). In this paper I discuss the nature of the nine objects with $`RK5.3`$ and $`K18`$ mag in the DMS and the implications of the ERO surface density for galaxy evolution models. §§2 and 3 briefly describe the photometry and object selection. In §4 I use colors and model fits to the 9-filter spectral energy distributions (SEDs) to compute redshifts and classify the EROs as either ellipticals or dusty starbursts. These results are discussed in §5.

## 2 Photometry

The observations, data reduction, and photometric solutions for these observations are described in Hall et al. (1996a) and Martini (2001). To measure the objects detected in the NIR frames (plate scale of $`0.3^{\prime \prime }`$ pix-1) on the CCD data ($`0.529^{\prime \prime }`$ pix-1), I used the DMS stellar catalog (Osmer et al., 1998) to solve for the coordinate transformations using GEOTRANS in IRAF111IRAF is distributed by the National Optical Astronomy Observatories, which are operated by the Association of Universities for Research in Astronomy, Inc., under cooperative agreement with the National Science Foundation.. The photometric zeropoints for each of the 21 fields was determined with the DMS stellar catalog for the CCD images and the photometric solutions from Martini (2001) for the NIR images. Because the subfields with NIR data are small, variations in the PSF across the CCD fields described by Hall et al. (1996a) are negligible over these individual subfields. For the CCD fields with more than one NIR subfield, the variation in the photometric zeropoint for different regions of the same CCD image was $`0.02`$ mag or less.

I measured the brightness of each object using aperture photometry and a stellar-profile aperture correction. The main purpose of these measurements is to accurately determine the colors of the galaxies, rather than their total integrated brightness in each filter. The same size aperture will sample the same physical region in each galaxy and provide a better estimate of the shape of the SED than methods such as isophotal magnitudes, which will depend on the isophotal limit in each filter. Variations in seeing from filter to filter can complicate this issue as a larger fraction of the light within a fixed physical radius will fall outside the aperture if the seeing FWHM is larger. The optimal aperture for these measurements will be a compromise between a decrease in aperture size, which will increase the signal-to-noise ratio, and an increase in the uncertainty of the stellar aperture correction. While the image quality is on average superior in the NIR frames relative to the CCD data, the NIR fields are significantly smaller (9 arcmin2 compared to 225 arcmin2) and generally only have one or two stars of sufficient brightness to determine the seeing and aperture correction. The NIR frames were therefore the limiting factor in minimizing the aperture size. To derive the optimal aperture I measured the aperture correction in the NIR frames at a range of radii from $`0.5^{\prime \prime }`$ to $`4^{\prime \prime }`$. I found that for $`R<2^{\prime \prime }`$ the uncertainty in the aperture correction for many of the frames was comparable or greater than the photometric errors at $`K18`$ mag. I therefore chose to use an $`R=2^{\prime \prime }`$ aperture for the photometry.

To measure the amount of lost light from a galaxy in excess of the stellar aperture correction, I simulated measurements of exponential disks and $`r^{1/4}`$ profiles with half-light radii $`r_h=0.25^{\prime \prime }`$, $`0.5^{\prime \prime }`$, $`0.75^{\prime \prime }`$, and $`1^{\prime \prime }`$ over the range of seeing from $`1^{\prime \prime }`$ to $`2.5^{\prime \prime }`$ FWHM exhibited by these images following the procedure described in Martini (2001). This range of possible ERO angular sizes span that found by Moriondo et al. (2000) in their study of EROs with HST imaging. For an $`R=2^{\prime \prime }`$ aperture, the galaxy light lost in addition to the stellar aperture correction ranges from essentially zero for $`r_h=0.25^{\prime \prime }`$ to 0.2 mag for an $`r_h=1^{\prime \prime }`$ exponential disk and 0.25 mag for an $`r_h=1^{\prime \prime }`$ $`r^{1/4}`$ profile.

## 3 Selection Criteria

NIR imaging surveys for EROs have defined numerous selection criteria (Thompson et al., 1999; Yan et al., 2000; Scodeggio & Silva, 2000), including objects with $`RK6`$, $`RK5`$, $`IK4`$, and $`K`$ magnitude upper limits from 18 to 20 mag. An extreme red color is a fairly efficient means of selecting candidate galaxies at $`z1`$ because it brackets the 4000 Å break in ellipticals and the Balmer continuum plus reddening in dusty starburst galaxies. This color space could also be inhabited by late-type stars, emission line galaxies, or very high redshift ($`z>7`$) galaxies, where the Lyman continuum falls between $`R`$ and $`K`$. Stellar contamination is probably the dominant contaminant in ERO samples and can be avoided by including only resolved sources. The upper limit in magnitude, which is approximately the spectroscopic limit of the largest current telescopes, avoids “contamination” of the $`z1`$ sample by galaxies at higher redshift as they have much lower surface densities than $`z1`$ objects at these magnitude limits. For example, a $`K=18`$ mag galaxy at $`z=1`$ has an absolute magnitude $`M_K=25`$ \+ log $`h`$ ($`\mathrm{\Omega }_M=0.3`$, $`\mathrm{\Omega }_\mathrm{\Lambda }=0.7`$), two magnitudes brighter than $`M_{,K}(z=0)=23`$ \+ log $`h`$ (Gardner et al., 1997). The $`z0.8`$ galaxies in a survey to $`K18`$ mag will therefore mostly be at $`z<2`$ due to the exponential decline in the galaxy luminosity function.

For this study I have adopted $`RK5.3`$, $`K18`$ mag to select for EROs in the DMS sample. The $`K18`$ mag limit is brighter than at least the $`r_h=0.25^{\prime \prime }`$ completeness limit for nearly all 185 arcmin2 of the $`K`$ survey (Martini, 2001). $`RK5.3`$ was suggested by Pozzetti & Mannucci (2000) based on models of ellipticals and dusty starbursts as well as observations of known EROs at $`z1`$. In total, nine resolved objects in the DMS sample met these two selection criteria for a surface density of 0.05 arcmin-2. This surface density is a lower limit due to the variation in detection efficiency for different galaxy sizes and from field to field. The photometry for the EROs is listed in Table 1. The only correction that has been applied to the apparent magnitudes in Table 1 is a stellar aperture correction. As these measurements may underestimate the total integrated brightness, this survey may underestimate the true ERO surface density (see § 5).

## 4 Analysis

### 4.1 ERO Colors

Colors are one means of breaking the degeneracy between ellipticals and starbursts. The SED of an elliptical galaxy at $`z1`$ drops off sharply at the 4000 Å break between the $`R`$ and $`K`$ bands, while the SED of a dusty starburst declines more gradually due to reddening. As discussed by Pozzetti & Mannucci (2000), observations between the $`R`$ and $`K`$ bands, such as $`I`$, $`z`$, $`J`$, or $`H`$ can be used to measure the sharpness of the spectral break and thus discriminate between these two scenarios. By this argument, ellipticals appear bluer in $`JK`$ than dusty starbursts. Figure 1 shows $`RK`$ vs. $`JK`$ for the galaxies in Table 1 (open circles), where ellipticals lie to the left, towards bluer $`JK`$ colors, and dusty starbursts to the right, towards redder $`JK`$ colors. Pozzetti & Mannucci (2000) convolved a range of models and observed galaxy spectral energy distributions with $`R`$, $`I`$, $`J`$, and $`H`$ filters and found that ellipticals and dusty starbursts separate in the $`IK`$ vs. $`JK`$ plane and $`RK`$ vs. $`JK`$ plane. Their relation between $`RK`$ and $`JK`$ is shown in Figure 1, along with their suggested $`RK5.3`$ selection criterion (dotted lines). This color space does successfully classify three EROs from the literature with spectroscopic classifications, visible, and NIR photometry (open triangles): HR10 (Graham & Dey, 1996), LBDS 53W091 (Spinrad et al., 1997), and CL0939+4713B (Soifer et al., 1999). It is possible, however, that galaxies with a mix of old stars and dusty star formation could fall into either class on this diagram. For example, Hall et al. (2001) found evidence of this in their study of EROs associated with radio-loud quasars, where objects best fit by star formation and dust still had relatively blue $`JK`$ colors. Of the nine DMS EROs shown in the Figure, seven have colors consistent with elliptical galaxies and two are consistent with dusty starbursts. However, six of the EROs fall within $`1\sigma `$ of the dividing line between these two classes and therefore either interpretation is consistent with the photometry.

### 4.2 SED Template Fits

Photometric redshifts with SED template fits are one way to expand on simpler color discrimination techniques and solve for both the object redshift and spectrophotometric galaxy type. Photometric redshifts that fit SED templates to photometric data rely on three pieces of information: a template SED for the source object, the relative transmission of the system (filter, detector, and optics) in each band, and a measurement of the source brightness in that band. Of these three quantities, the system transmission profile should be the best-known quantity, in principle, and the true galaxy SED the most uncertain. The templates used in photometric redshift codes are either empirical SEDs, such as the set compiled by Coleman et al. (1980), or spectral synthesis templates, such as those based on the Bruzual & Charlot evolutionary code (e.g. GISSEL98, Bruzual & Charlot, 1993).

Photometric redshift codes are most accurate in the $`z1`$ – 2 range when NIR photometry is available (e.g., Gwyn, 1995; Bolzonella et al., 2000). At this range of redshifts, the strongest spectral feature, the 4000 Å break, has shifted into the NIR region and the Lyman continuum has not yet shifted into the ground-based $`U`$ filter bandpass. Using mock galaxy catalogs produced with hyperz (Bolzonella et al., 2000), I measured the accuracy of the photometric redshift measurements for a $`K18`$ mag galaxy sample with the same magnitude limits and noise properties as this survey in all nine filters. For a uniform distribution in redshifts, the scatter is $`\sigma _z=0.08`$. The scatter for galaxies with $`0.8z2`$ is $`\sigma _z=0.1`$, compared to $`\sigma _z=0.3`$ for the same sample if only $`UBVRI_{75}I_{86}`$ photometry were available. The accuracy of photometric redshifts, and the associated best-fit templates, depends on photometric quality as well as the number of filters. While the EROs are all expected to be at $`z0.8`$ due to their $`RK`$ colors, they are often undetected in several filters (none are detected in $`U`$ or $`B`$) and the photometric uncertainties in the remaining filters are generally $`>0.1`$ mag. The larger the photometric errors, the less well contrained the best-fit redshift, and particularly the best-fit galaxy template.

The empirical galaxy templates in hyperz are from Coleman et al. (1980) and represent the local galaxy population. The GISSEL98 galaxy templates are the 1998 update of the spectral synthesis models described by Bruzual & Charlot (1993). All of the models have solar metallicity and a Miller & Scalo (1979) initial mass function. Each model corresponds to a different present-day spectrophotometric galaxy type. The elliptical template has all star formation occurring at high redshift and thus represents classic passive luminosity evolution. The burst model represents the opposite extreme with significant recent star formation. The remaining galaxy types are represented by exponentially decaying star formation with different $`e`$folding timescales.

I used hyperz to find the best-fit empirical galaxy template, GISSEL98 elliptical template, and GISSEL98 starburst templates for each of the EROs listed in Table 1. The basic operation of this code is to take a series of input galaxy templates, vary the redshift and amount of reddening, and solve for the best combination of these quantities that match an input catalog of photometric measurements or upper limits. For these model fits I adopted the Calzetti et al. (2000) reddening law. While there are a large number of filters predefined in hyperz, the DMS $`I_{75}`$ and $`I_{86}`$ filters are not included. Because of the importance of the system transmission profiles in each band, I added the profiles of the DMS filters from Hall et al. (1996a), which include the detector response, and scans of the $`J`$, $`H`$, and $`K`$ filters from TIFKAM, which I convolved by a measurement of the atmospheric transmission at Kitt Peak.

In all cases the photometric redshift predictions of the three fits shown in Table 2 are similar. One feature of the SED fits to these EROs is that on average the best-fit elliptical template has a lower photometric redshift than the best starburst template. This is because the dominant break in the SED of elliptical galaxies is at 4000 Å while the closest spectral break in starburst galaxies is the Balmer continuum at 3650 Å. The rms scatter in the photometric redshift prediction for these three fits is $`\sigma _z<0.1`$. The photometric redshifts are thus quite robust and show clearly that these EROs are $`z0.8`$ galaxies. The relative quality of the three SED fits is comparable, with the difference between the fits $`\mathrm{\Delta }\chi _\nu ^21`$. These galaxies can therefore not be reliably classified as either ellipticals or dusty starbursts due to the large photometric errors. Most of the best fits with the Coleman et al. (1980) empirical SEDs are the elliptical template with no dust or spirals with some dust. These fits suggest that most EROs are ellipticals, although old stellar populations at $`z1`$ are on order half the age of old stellar populations at $`z0`$ and thus this empirical SED may not be an accurate representation of $`z1`$ ellipticals. The GISSEL98 models do take the change in the age of the universe with redshift into account. The GISSEL98 elliptical templates fit the data with only a small amount of extinction, while the starburst models require on average $`A_V=1`$ mag.

## 5 Discussion

The reported surface density of EROs has a large dispersion. Elston, Rieke, & Rieke (1988) found two galaxies with $`RK5`$ and $`K18`$ mag in 10 arcmin2 for a surface density of 0.2 arcmin-2. Figure 1 of Thompson et al. (1999) shows they found seven of these objects for a surface density of 0.05 arcmin-2. Daddi et al. (2000) surveyed 700 arcmin2 and derived a surface density of $`0.08`$ arcmin-2 for $`RK5`$ and $`K18`$ mag. Their study also showed that EROs are clustered, which helps to explain the dispersion in measurements of the surface density. In this survey I have identified nine EROs with $`RK5.3`$ and $`K18`$ mag, which corresponds to a surface density of 0.049$`{}_{0.016}{}^{}{}_{}{}^{+0.022}`$ arcmin-2, where these uncertainties only correspond to the $`1\sigma `$ confidence limits (Gehrels, 1986). This surface density is nearly a factor of two higher than the surface density of 0.027 arcmin-2 found by Daddi et al. (2000) for $`RK5.3`$ and $`K18`$ mag (see Table 3), although based on Poisson statistics these measurements are marginally consistent at the $`1\sigma `$ level.

In addition to the random errors due to counting statistics, Eddington bias and light lost outside the $`R=2^{\prime \prime }`$ aperture could systematically lower and raise the measured surface density, respectively. Eddington bias is important near the detection limit when objects with a steep number–magnitude relation are preferentially scattered into the sample and artificially enhance the observed space density. Based on the surface density vs. magnitude measurements published by Daddi et al. (2000), the slope of the ERO number–magnitude relation (for $`RK5.3`$) is $`\alpha 0.9`$ at $`K18`$ mag. The correction for the Eddington bias is $`2.65\sigma ^2\alpha ^2`$ and for a mean photometric uncertainty of $`\sigma 0.1`$, the surface density may be overestimated by approximately 2%. If the slope were a factor of two steeper, the overestimate is still less than 10%. A more significant potential source of error arises if the EROs are large galaxies and a $`R=2^{\prime \prime }`$ aperture misses some fraction of their light. Then the surface density has been underestimated as effectively the photometric scale assigns them too faint a magnitude, thus the surface density at $`K=18`$ mag is really the surface density at $`K=18\delta m`$ mag. The increase in surface density scales as $`10^{\alpha \delta m}`$, where for example $`\delta m=0.2`$ ($`r_h=1^{\prime \prime }`$ for an exponential or $`r^{1/4}`$ profile) corresponds to an increase of 50%, although a significant contribution from such large EROs appear to be ruled out by observations (Moriondo et al., 2000).

While clustering will not change the true mean surface density, it will increase the possible variation from survey to survey over the pure Poisson uncertainties quoted above. The DMS EROs are clearly strongly clustered as, for example, five of these objects are in one of the subfields in Field01W (01WC, 01WC150W, and CF3), only 20% of the total area with NIR data. The rms number counts of EROs in the DMS are $`\sigma =0.85`$, compared to $`\sigma _{\mathrm{Poisson}}=0.67`$ for a surface density of $`0.05`$ arcmin2 and an average area per field of 9 arcmin2. If I adopt the correlation amplitude $`A=0.024`$ from Daddi et al. (2000) for $`RK5`$, $`K18`$ mag (they had insufficient statistics to measure this quantity at $`RK5.3`$) the predicted rms counts (Roche et al., 1999; Daddi et al., 2000) are $`\sigma =0.75`$. The clustering signal in this suvey may be exaggerated by variations in the field to field sensitivity.

The high surface density of EROs in this and other surveys provides a constraint for passive evolution and hierarchical galaxy formation models. Hierarchical models predict relatively few large, bright galaxies at $`z1`$ as most these galaxies assemble at $`z<1`$. In a simple test of hierarchical galaxy formation, Kauffmann & Charlot (1998) predicted that less that 1% of all galaxies with $`16<K<18`$ mag are at $`z0.8`$ and $`10`$% of galaxies with $`18<K<19`$ mag are at $`z0.8`$ (see their Figure 4). Measurements of the $`K`$ number–magnitude relation (e.g. Minezaki et al., 1998; Martini, 2001) show the galaxy surface density is $`1.7`$ arcmin-2 for galaxies with $`16<K<18`$ mag and $`3.3`$ arcmin-2 for galaxies with $`18<K<19`$ mag. As all EROs with spectroscopic or photometric redshifts are at $`z0.8`$, the surface density of EROs can be taken as a lower limit to the surface density of all $`z0.8`$ galaxies to test the Kauffmann & Charlot (1998) prediction of hierarchical galaxy formation. Their predicted fraction of galaxies at $`z0.8`$ implies that the surface density of EROs should be $`<0.017`$ arcmin-2 for $`16<K<18`$ mag, in conflict with the higher value I measure and the value measured by Daddi et al. (2000). According the passive evolution model in Kauffmann & Charlot (1998), $``$ 50% of all galaxies at $`K18`$ mag are at $`z0.8`$, which corresponds to over an order of magnitude greater surface density of all $`z0.8`$ galaxies than the ERO surface density presented here, even if the ERO surface density has been underestimated by as much as 50% due to lost light in the aperture.

The ERO surface density I measure and also the measurement of Daddi et al. (2000) is still consistent with the results of $`K`$-selected spectroscopic and photometric redshift surveys (Songaila et al., 1994; Cowie et al., 1996; Fontana et al., 1999), which have found a somewhat higher surface density of $`z0.8`$ galaxies than the hierarchical model predictions. The cosmic variance between different redshift and ERO surveys should be large given the clustering of EROs. The redshift distribution from a spectroscopic survey is also most likely to be incomplete for the reddest and highest-redshift galaxies and could underestimate the $`z1`$ contribution.

EROs provide such a good means to test the hierarchical galaxy formation model because their surface density is greater than the predicted surface density of all $`z0.8`$ galaxies and they are only a lower limit on the total $`z0.8`$ galaxy population in a $`K`$selected galaxy survey. From the discussion of the systematic uncertainties in the surface density above, the overestimate due to Eddington bias is less significant than an underestimate due to lost galaxy light and therefore 0.05 arcmin-2 may be a lower limit to the true ERO surface density. The surface density is therefore nearly a factor of three higher than the predicted surface density of all $`z0.8`$ galaxies. Two other effects could bring the ERO surface density into better agreement with the hierarchical prediction, either by decreasing the observed number of EROs or increasing their expected number. Some fraction of EROs appear to be dusty starburst galaxies, rather than old ellipticals. While this fraction is very likely less than 50% based on the colors of these EROs and spectroscopic observations of ERO samples from the literature (Cimatti et al., 1999; Cohen et al., 1999), decreasing the surface density from this survey by a factor of two still yields a higher surface density of objects than the hierarchical model. A more important effect, however, is that the current model predictions from Kauffmann & Charlot (1998) are for an $`\mathrm{\Omega }_M=1`$ universe. In a flat, $`\mathrm{\Lambda }`$dominated universe, which appears to be the best fit cosmological model, the comoving volume element vs. redshift is larger than in a flat, matter-dominated universe. For example, at $`z=1`$ a given surface area on the sky corresponds to a factor of 2.8 ($`h_M`$/$`h_\mathrm{\Lambda }`$)3 more comoving volume in an $`\mathrm{\Omega }_M=0.3,\mathrm{\Omega }_\mathrm{\Lambda }=0.7`$ universe than in an $`\mathrm{\Omega }_M=1,\mathrm{\Omega }_\mathrm{\Lambda }=0`$ universe. The volume per unit area on the sky is greater and implies a larger surface density of high-redshift objects than the matter-dominated model considered by Kauffmann & Charlot (1998). The growth factor is also larger at fixed redshift in a $`\mathrm{\Lambda }`$dominated universe than in an $`\mathrm{\Omega }_M=1`$ model, which implies more large structures have formed and consequently a larger space density and surface density of bright galaxies. The increase in surface density due to the change from a matter-dominated to a $`\mathrm{\Lambda }`$dominated universe is partially offset, however, by the increase in the luminosity distance.

In this paper I have presented a new measurement of the ERO surface density and used photometric redshifts to show these objects are galaxies at $`z0.8`$. The surface density of EROs is a lower limit to the total $`z0.8`$ surface density, yet it is still a factor of three larger than the hierarchical galaxy formation model prediction for a matter-dominated universe. Hierarchical galaxy formation in a $`\mathrm{\Lambda }`$dominated universe, rather than a matter-dominated universe, could account for this discrepancy.

I would like to thank Darren DePoy, Patrick Osmer, and David Weinberg for helpful discussions and comments on this manuscript. In addition, helpful comments from an anonymous referee have improved and clarified this presentation. I also acknowledge the staff of the MDM Observatory. I was supported in part by a Presidential Fellowship from Ohio State University and received additional travel and other support from a PEGS grant and the Department of Astronomy at Ohio State University. TIFKAM was funded by the Ohio State University, the MDM consortium, MIT, and NSF grant AST-9605012. NOAO and USNO paid for the development of the ALADDIN arrays and contributed the array currently in use in TIFKAM.