ON THE NUMBER OF TOPOLOGICAL TYPES OCCURRING IN
A PARAMETRIZED FAMILY OF ARRANGEMENTS
SAUGATA BASU
Abstract. Let S(R) be an o-minimal structure over R, T ⊂ Rk1+k2+ℓ a
closed definable set, and
π1 : R
k1+k2+ℓ → Rk1+k2 , π2 : R
k1+k2+ℓ → Rℓ, π3 : R
k1+k2 → Rk2
the projection maps as depicted below.
k1+k2+ℓ R
k1+k2
For any collection A = {A1, . . . , An} of subsets of R
k1+k2 , and z ∈ Rk2 , let
Az denote the collection of subsets of R
{A1,z, . . . , An,z}
where Ai,z = Ai ∩ π
3 (z), 1 ≤ i ≤ n. We prove that there exists a constant
C = C(T ) > 0 such that for any family A = {A1, . . . , An} of definable sets,
where each Ai = π1(T ∩ π
2 (yi)), for some yi ∈ R
ℓ, the number of distinct
stable homotopy types amongst the arrangements Az, z ∈ R
k2 is bounded
by C · n(k1+1)k2 while the number of distinct homotopy types is bounded by
C · n(k1+3)k2 . This generalizes to the o-minimal setting, bounds of the same
type proved in [5] for semi-algebraic and semi-Pfaffian families. One technical
tool used in the proof of the above results is a pair of topological comparison
theorems reminiscent of Helly’s theorem in convexity theory and these might
be of independent interest in the quantitative study of arrangements.
1. Introduction
The study of arrangements is a very important subject in discrete and computa-
tional geometry, where one studies arrangements of n subsets of Rk (often referred
to as objects of the arrangements) for fixed k and large values of n (see [1] for a
survey of the known results from this area). The precise nature of the objects in an
arrangements will be discussed in more details below. Common examples consist
of arrangements of hyperplanes, balls or simplices in Rk. More generally one con-
siders arrangements of objects of “bounded description complexity”. This means
that each set in the arrangement is defined by a first order formula in the language
of ordered fields involving at most a constant number of polynomials whose degrees
are also bounded by a constant (see [12]).
Key words and phrases. Combinatorial Complexity, O-minimal Structures, Homotopy Types,
Arrangements.
The author was supported in part by NSF grant CCF-0634907.
2000 MATHEMATICS SUBJECT CLASSIFICATION 14P10, 14P25
http://arxiv.org/abs/0704.0295v3
2 SAUGATA BASU
In this paper we consider parametrized families of arrangements. The question
we will be interested in most, is the number of “topologically” distinct arrange-
ments which can occur in such a family (precise definition of the topological type
of an arrangement is given later (see Definition 1.6)). Parametrized arrangements
occur quite frequently in practice. For instance, take any arrangement A in Rk1+k2
and let π : Rk1+k2 → Rk2 be the projection on the last k2 co-ordinates. Then for
each z ∈ Rk2 , the intersection of the arrangement A with the fiber π−1(z), is an ar-
rangement Az in R
k1 and the family of the arrangements {Az}z∈Rk2 is an example
of a parametrized family of arrangements. Even though the number of arrange-
ments in the family {Az}z∈Rk2 is infinite, it follows from Hardt’s triviality theorem
generalized to o-minimal structures (see Theorem 4.2 below) that the number of
“topological types” occurring amongst them is finite and can be effectively bounded
in terms of the n, k1, k2 up to multiplication by a constant that depends only on
the particular family from which the objects of the arrangements are drawn. If
by topological type we mean homeomorphism type, then the best known upper
bound on the number of types occurring is doubly exponential in k1, k2. However,
if we consider the weaker notion of homotopy type, then we obtain a singly ex-
ponential bound. We conjecture that a singly exponential bound also holds for
homeomorphism types as well.
We now make precise the class of arrangements that we consider and also the
notion of topological type of an arrangement.
1.1. Combinatorial Complexity in O-minimal Geometry. In order to put the
study of the combinatorial complexity of arrangements in a more natural mathe-
matical context, as well as to elucidate the proofs of the main results in the area,
a new framework was introduced in [2] which is a significant generalization of the
settings mentioned above. We recall here the basic definitions of this framework
from [2], referring the reader to the same paper for further details and examples.
We first recall an important model theoretic notion – that of o-minimality –
which plays a crucial role in this generalization.
1.1.1. O-minimal Structures. O-minimal structures were invented and first studied
by Pillay and Steinhorn in the pioneering papers [13, 14]. Later the theory was
further developed through contributions of other researchers, most notably van
den Dries, Wilkie, Rolin, Speissegger amongst others [20, 21, 22, 25, 26, 15]. We
particularly recommend the book by van den Dries [19] and the notes by Coste [6]
for an easy introduction to the topic as well as the proofs of the basic results that
we use in this paper.
Definition 1.1 (o-minimal structure). An o-minimal structure over a real closed
field R is a sequence S(R) = (Sn)n∈N, where each Sn is a collection of subsets of R
(called the definable sets in the structure) satisfying the following axioms (following
the exposition in [6]).
(1) All algebraic subsets of Rn are in Sn.
(2) The class Sn is closed under complementation and finite unions and inter-
sections.
(3) If A ∈ Sm and B ∈ Sn then A×B ∈ Sm+n.
(4) If π : Rn+1 → Rn is the projection map on the first n co-ordinates and
A ∈ Sn+1, then π(A) ∈ Sn.
(5) The elements of S1 are precisely finite unions of points and intervals.
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 3
The class of semi-algebraic sets is one obvious example of such a structure, but
in fact there are much richer classes of sets which have been proved to be o-minimal
(see [6, 19]).
1.1.2. Admissible Sets. We now recall from [2] the definition of the class of sets that
will play the role of sets with bounded description complexity mentioned above.
Definition 1.2 (admissible sets). Let S(R) be an o-minimal structure over R
and let T ⊂ Rk+ℓ be a fixed definable set. Let π1 : R
k+ℓ → Rk (respectively
π2 : R
k+ℓ → Rℓ) be the projections onto the first k (respectively last ℓ) co-ordinates.
T ⊂ Rk+ℓ
We will call a subset S of Rk to be a (T, π1, π2)-set if
S = Ty = π1(π
2 (y) ∩ T )
for some y ∈ Rℓ.
If T is some fixed definable set, we call a family of (T, π1, π2)-sets to be a
(T, π1, π2)-family. We wil also refer to a finite (T, π1, π2)-family as an arrangement
of (T, π1, π2)-sets.
1.2. Stable Homotopy Equivalence. For any finite CW-complex X we denote
by SX the suspension of X and for n ≥ 0, we denote by SnX the n-fold iterated
suspension S ◦ S ◦ · · · ◦ S
︸ ︷︷ ︸
n times
Note that if i : X →֒ Y is an inclusion map, then there is an obvious induced
inclusion map Sni : SnX →֒ SnY between the n-fold iterated suspensions of X and
Recall from [17] that for two finite CW-complexes X and Y , an element of
(1.1) {X ;Y } = lim
[SiX,SiY ]
is called an S-map (or map in the suspension category). An S-map f ∈ {X ;Y } is
represented by the homotopy class of a map f : SNX → SNY for some N ≥ 0.
Definition 1.3 (stable homotopy equivalence). An S-map f ∈ {X ;Y } is an S-
equivalence (also called a stable homotopy equivalence) if it admits an inverse f−1 ∈
{Y ;X}. In this case we say that X and Y are stable homotopy equivalent.
If f ∈ {X ;Y } is an S-map, then f induces a homomorphism
f∗ : H∗(X,Z) → H∗(Y,Z)
between the homology groups of X and Y .
The following theorem characterizes stable homotopy equivalence in terms of
homology.
Theorem 1.4. [8, pp. 604] Let X and Y be two finite CW-complexes. Then X and
Y are stable homotopy equivalent if and only if there exists an S-map f ∈ {X ;Y }
which induces isomorphisms f∗ : H∗(X,Z) → H∗(Y,Z).
4 SAUGATA BASU
1.3. Diagrams and Co-limits. The arrangements that we consider are all finitely
triangulable. In other words, the union of objects of an arrangement is homeomor-
phic to a finite simplicial complex, and each individual object in the arrangement
will correspond to a sub-complex of this simplicial complex. It will be more con-
venient to work in the category of finite regular cell complexes, instead of just
simplicial complexes.
Let A = {A1, . . . , An}, where each Ai is a sub-complex of a finite regular cell
complex. We will denote by [n] the set {1, . . . , n} and for I ⊂ [n] we will denote by
AI (respectively AI) the regular cell complexes
Ai (respectively
Ai). Notice
that if J ⊂ I ⊂ [n], then
AJ ⊂ AI ,
AI ⊂ AJ .
We will call the collection of sets {|AI |}I⊂[n] together with the inclusion maps
iI,J : |AI | →֒ |AJ |, J ⊂ I, the diagram of A. Notice that (even though we do not
use this fact), |A[n]| is the co-limit of the diagram of A. For I ⊂ [n] we will denote
by A[I] the sub-arrangement {Ai | i ∈ I}.
1.4. Diagram Preserving Maps. Now let A = {A1, . . . , An}, B = {B1, . . . , Bn}
where each Ai, Bj is a sub-complex of a finite regular cell complex for 1 ≤ i, j ≤ n.
Definition 1.5 (diagram preserving maps). We call a map f : |A[n]| → |B[n]|
to be diagram preserving if f(|AI |) ⊂ |BI | for every I ⊂ [n]. (Notice that the
above property is equivalent to f(|Ai|) ⊂ |Bi| for every i ∈ [n] but the previous
property will be more convenient for us later when we extend the definition of
diagram preserving maps to homotopy co-limits (see Definition 3.3).) We say that
two maps f, g : |A[n]| → |B[n]| are diagram homotopic if there exists a homotopy
h : |A[n]| × [0, 1] → |B[n]|, such that h(·, 0) = f, h(·, 1) = g and h(·, t) is diagram
preserving for each t ∈ [0, 1].
More generally, we call a map f : SN |A[n]| → SN |B[n]| to be diagram preserving
if f(SN |AI |) ⊂ S
N |BI | for every I ⊂ [n]. We say that two maps f, g : S
N |A[n]| →
SN |B[n]| are diagram homotopic if there exists a homotopy h : SN |A[n]| × [0, 1] →
SN |B[n]| such that h(·, 0) = f, h(·, 1) = g and h(·, t) is diagram preserving for each
t ∈ [0, 1].
We say that f : |A[n]| → |B[n]| is a diagram preserving homeomorphism if there
exists a diagram preserving inverse map g : |B[n]| → |A[n]| such that the induced
maps g ◦ f : |A[n]| → |A[n]| and f ◦ g : |B[n]| → |B[n]| are Id|A[n]| and Id|B[n]|,
respectively.
We say that f : |A[n]| → |B[n]| is a diagram preserving homotopy equivalence
if there exists a diagram preserving inverse map g : |B[n]| → |A[n]| such that the
induced maps g◦f : |A[n]| → |A[n]| and f ◦g : |B[n]| → |B[n]| are diagram homotopic
to Id|A[n]| and Id|B[n]|, respectively.
We say that an S-map f ∈ {|A[n]|; |B[n]|} is a diagram preserving stable homo-
topy equivalence if it is represented by a diagram preserving map
f̃ : SN |A[n]| → SN |B[n]|
such that there exists a diagram preserving inverse map
g̃ : SN |B[n]| → SN |A[n]|
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 5
for which the induced maps
g̃ ◦ f̃ : SN |A[n]| → SN |A[n]|,
f̃ ◦ g̃ : SN |B[n]| → SN |B[n]|
are diagram homotopic to IdSN |A[n]| and IdSN |B[n]|, respectively.
Translating these topological definitions into the language of arrangements, we
say that:
Definition 1.6 (topological type of an arrangement). Two arrangements A,B are
homeomorphic (respectively homotopy equivalent, stable homotopy equivalent) if
there exists a diagram preserving homeomorphism (respectively homotopy equiva-
lence, stable homotopy equivalence) between them.
Remark 1.7. Note that, since two definable sets might be stable homotopy equiv-
alent, without being homotopy equivalent (see [18, pp. 462]), and also homotopy
equivalent without being homeomorphic, the notions of homeomorphism type, ho-
motopy type and stable homotopy type are each strictly weaker than the previous
The main results of this paper can now be stated.
1.5. Main Results. Let S(R) be an o-minimal structure over R, T ⊂ Rk1+k2+ℓ
a closed and bounded definable set, and let π1 : R
k1+k2+ℓ → Rk1+k2 (respectively,
π2 : R
k1+k2+ℓ → Rℓ, π3 : R
k1+k2 → Rk2) denote the projections onto the first
k1 + k2 (respectively, the last ℓ, the last k2) co-ordinates. For any collection A =
{A1, . . . , An} of (T, π1, π2)-sets, and z ∈ R
k2 , we will denote by Az the collection
of sets, {A1,z, . . . , An,z}, where Ai,z = Ai ∩ π
3 (z), 1 ≤ i ≤ n.
A fundamental theorem in o-minimal geometry is Hardt’s trivialization theorem
(Theorem 4.2 below) which says that there exists a definable partition of Rk2 into
a finite number of definable sets {Ti}i∈I such that for each i ∈ I, all fibers Az with
z ∈ Ti are definably homeomorphic. A very natural question is to ask for an upper
bound on the size of this partition (which will also give an upper bound on the
number of homeomorphism types amongst the arrangements Az, z ∈ R
Hardt’s theorem is a corollary of the existence of cylindrical cell decompositions
of definable sets proved in [11] (see also [19, 6]). When A is a (T, π1, π2)-family
for some fixed definable set T ⊂ Rk1+k2+ℓ, with π1 : R
k1+k2+ℓ → Rk1+k2 , π2 :
k1+k2+ℓ → Rℓ, π2 : R
k1+k2 → Rk2 the usual projections, and #A = n, the
quantitative definable cylindrical cell decomposition theorem in [2] gives a doubly
exponential (in k1k2) upper bound on the cardinality of I and hence on the number
of homeomorphism types amongst the arrangements Az, z ∈ R
k2 . A tighter (say
singly exponential) bound on the number of homeomorphism types of the fibers
would be very interesting but is unknown at present. Note that we cannot hope for
a bound which is better than singly exponential because the lower bounds on the
number of topological types proved in [5] also applies in our situation.
In this paper we give tighter (singly exponential) upper bounds on the number of
homotopy types occurring amongst the fibers Az, z ∈ R
k2 . We prove the following
theorems. The first theorem gives a bound on the number of stable homotopy types
of the arrangements Az, z ∈ R
k2 , while the second theorem gives a slightly worse
bound for homotopy types.
6 SAUGATA BASU
Theorem 1.8. There exists a constant C = C(T ) > 0 such that for any collection
A = {A1, . . . , An} of (T, π1, π2)-sets the number of distinct stable homotopy types
amongst the arrangements Az, z ∈ R
k2 is bounded by
C · n(k1+1)k2 .
If we replace stable homotopy type by homotopy type, we obtain a slightly weaker
bound.
Theorem 1.9. There exists a constant C = C(T ) > 0 such that for any collection
A = {A1, . . . , An} of (T, π1, π2)-sets the number of distinct homotopy types occuring
amongst the arrangements Az, z ∈ R
k2 is bounded by
C · n(k1+3)k2 .
2. Background
In this section we describe some prior work in the area of bounding the number of
homotopy types of fibers of a definable map and their connections with the results
presented in this paper.
We begin with a definition.
Definition 2.1 (A-sets). Let A = {A1, . . . , An}, such that each Ai ⊂ R
k is a
(T, π1, π2)-set. For I ⊂ {1, . . . , n}, we let A(I) denote the set
(2.1)
i∈I⊂[n]
j∈[n]\I
(Rk \Aj)
and we will call such a set to be a basic A-set. We will denote by C(A) the set of
non-empty connected components of all basic A-sets.
We will call definable subsets S ⊂ Rk defined by a Boolean formula whose atoms
are of the form, x ∈ Ai, 1 ≤ i ≤ n, an A-set. An A-set is thus a union of basic
A-sets. If T is closed, and the Boolean formula defining S has no negations, then S
is closed by definition (since each Ai is closed) and we call such a set an A-closed
Moreover, if V is any closed definable subset ofRk, and S is anA-set (respectively
A-closed set), then we will call S∩V to be an (A, V )-set (respectively (A, V )-closed
set).
2.1. Bounds on the Betti numbers of Admissible Sets. The problem of
bounding the Betti numbers of A-sets is investigated in [2], where several results
known in the semi-algebraic and semi-Pfaffian case are extended to this general
setting. In particular, we will need the following theorem proved there.
Theorem 2.2. [2] Let S(R) be an o-minimal structure over R and let T ⊂ Rk+ℓ
be a closed definable set. Then, there exists a constant C = C(T ) > 0 depending
only on T such that for any arrangement A = {A1, . . . , An} of (T, π1, π2)-sets of
k the following holds.
For every i, 0 ≤ i ≤ k,
(2.2)
D∈C(A)
bi(D) ≤ C · n
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 7
Remark 2.3. The main intuition behind the bound in Theorem 2.2 (as well as similar
results in the semi-algebraic and semi-Pfaffian settings) is that the homotopy type
(or at least the Betti numbers) of a definable set in Rk defined in terms of n sets
belonging to some fixed definable family, depend only on the interaction of these
sets at most k + 1 at a time. This is reminiscent of Helly’s theorem in convexity
theory (see [7]) but in a homotopical setting. This observation is also used to give
an efficient algorithm for computing the Betti numbers of arrangements (see [3,
Section 8]). However, the proof of Theorem 2.2 in [2] (as well as the proofs of
similar results in the semi-algebraic [4] and semi-Pfaffian settings [10]) depends on
an argument involving the Mayer-Vietoris sequence for homology, and does not
require more detailed information about homotopy types. In Section 3 below, we
make the above intuition mathematically precise.
We prove two theorems (Theorems 3.6 and 3.7 below) and these auxiliary re-
sults are the keys to proving the main results of this paper (Theorems 1.8 and
1.9). Moreover, these auxiliary results could also be of independent interest in the
quantitative study of arrangements.
2.2. Homotopy types of the fibers of a semi-algebraic map. Theorem 2.2
gives tight bounds on the topological complexity of an A-set in terms of the cardi-
nality of A, assuming that the sets in A belong to some fixed definable family. A
problem closely related to the problem we consider in this paper is to bound the
number of topological types of the fibers of a projection restricted to an arbitrary
A-set.
More precisely, let S ⊂ Rk1+k2 be a set definable in an o-minimal structure over
the reals (see [19]) and let π : Rk1+k2 → Rk2 denote the projection map on the
last k2 co-ordinates. We consider the fibers, Sz = π
−1(z) ∩ S for different z in
k2 . Hardt’s trivialization theorem, (Theorem 4.2 below) shows that there exists
a definable partition of Rk2 into a finite number of definable sets {Ti}i∈I such that
for each i ∈ I and any point zi ∈ Ti, π
−1(Ti) ∩ S is definably homeomorphic to
Szi × Ti by a fiber preserving homeomorphism. In particular, for each i ∈ I, all
fibers Sz with z ∈ Ti are definably homeomorphic.
In case S is an A-set, with A a (T, π1, π2)-family for some fixed definable set
T ⊂ Rk1+k2+ℓ, with π1 : R
k1+k2+ℓ → Rk1+k2 , π2 : R
k1+k2+ℓ → Rℓ, π2 : R
k1+k2 →
k2 , the usual projections, and #A = n, the quantitative definable cylindrical cell
decomposition theorem in [2] gives a doubly exponential (in k1k2) upper bound
on the cardinality of I and hence on the number of homeomorphism types of the
fibers of the map π3|S . A tighter (say singly exponential) bound on the number
of homeomorphism types of the fibers would be very interesting but is unknown at
present.
Recently, the problem of obtaining a tight bound on the number of topological
types of the fibers of a definable map for semi-algebraic and semi-Pfaffian sets
was considered in [5], and it was shown that the number of distinct homotopy
types of the fibers of such a map can be bounded (in terms of the format of the
formula defining the set) by a function singly exponential in k1k2. In particular,
the combinatorial part of the bound is also singly exponential. A more precise
statement in the case of semi-algebraic sets is the following theorem which appears
in [5].
Theorem 2.4. [5] Let P ⊂ R[X1, . . . , Xk1 , Y1, . . . , Yk2 ], with deg(P ) ≤ d for each
P ∈ P and cardinality #P = n. Then, for any fixed P-semi-algebraic set S the
8 SAUGATA BASU
number of different homotopy types of fibers π−1(y) ∩ S for various y ∈ π(S) is
bounded by
(2k1nk2d)
O(k1k2).
Remark 2.5. The proof of Theorem 2.4 however has the drawback that it relies
on techniques involving perturbations of the original polynomials in order to put
them in general position, as well as Thom’s Isotopy Theorem, and as such does not
extend easily to the o-minimal setting. The main results of this paper (see Theorem
1.8 and Theorem 1.9) extend the combinatorial part of Theorem 2.4 to the more
general o-minimal category.
Remark 2.6. Even though the formulation of Theorem 2.4 seems a little different
from the main theorems of this paper (Theorems 1.8 and 1.9), they are in fact
closely related. In fact, as a consequence of Theorem 1.9 we obtain bounds on the
number of homotopy types of the fibers of S for any fixed A-set S, analogous to
the one in Theorem 2.4.
More precisely we have:
Theorem 2.7. Let S(R) be an o-minimal structure over R, and T ⊂ Rk1+k2+ℓ a
closed and bounded definable set, and π1 : R
k1+k2+ℓ → Rk1+k2 , π2 : R
k1+k2+ℓ →
ℓ, and π3 : R
k1+k2 → Rk2 the projection maps. Then, there exists a constant
C = C(T ) > 0, such that for any collection A = {A1, . . . , An} of (T, π1, π2)-sets,
for any fixed A-set S the number of distinct homotopy types of fibers π−13 (z)∩S for
various z ∈ π3(S) is bounded by
C · n(k1+3)k2 .
A similar result with a bound of C · n(k1+1)k2 holds for stable homotopy types
as well.
3. A Topological Comparison Theorem
As noted previously, the main underlying idea behind our proof of Theorem 1.8
is that the homotopy type of an A-set in Rk depends only on the interaction of sets
in A at most (k + 1) at a time. In this section we make this idea precise.
We show that in case A = {A1, . . . , An}, with each Ai a definable, closed and
bounded subset of Rk, the homotopy type of any A-closed set is determined by a
certain sub-complex of the homotopy co-limit of the diagram of A. The crucial fact
here is that this sub-complex depends only on the intersections of the sets in A at
most k + 1 at a time.
In order to avoid technical difficulties, we restrict ourselves to the category of
finite, regular cell complexes (see [24] for the definition of a regular cell complex).
The setting of finite, regular cell complexes suffices for us, since it is well known
that closed and bounded definable sets in any o-minimal structure are finitely tri-
angulable, and hence, are homeomorphic to regular cell complexes.
3.1. Topological Preliminaries. Let A = {A1, . . . , An}, where each Ai is a sub-
complex of a finite regular cell complex. We now define the homotopy co-limit of
the diagram of A.
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 9
3.1.1. Homotopy Co-limits. Let ∆[n] denote the standard simplex of dimension n−1
with vertices in [n] (and by |∆[n]| the corresponding closed geometric simplex). For
I ⊂ [n], we denote by ∆I the (#I − 1)-dimensional face of ∆[n] corresponding to I.
The homotopy co-limit, hocolim(A), is a CW-complex defined as follows.
Definition 3.1 (homotopy co-limit).
hocolim(A) =
I⊂[n]
∆I ×AI/ ∼
where the equivalence relation ∼ is defined as follows.
For I ⊂ J ⊂ [n], let sI,J : |∆I | →֒ |∆J | denote the inclusion map of the face |∆I |
in |∆J |, and let iI,J : |AJ | →֒ |AI | denote the inclusion map of |AJ | in |AI |.
Given (s,x) ∈ |∆I |×|AI | and (t,y) ∈ |∆J |×|AJ | with I ⊂ J , then (s,x) ∼ (t,y)
if and only if t = sI,J(s) and x = iI,J(y).
Note that there exist two natural maps
fA : |hocolim(A)| → |A
[n]|,
gA : |hocolim(A)| → |∆[n]|
defined by
(3.1) fA(s,x) = s,
(3.2) gA(s,x) = x.
where (s,x) ∈ |∆Ic | × c, c is a cell in A
[n] and Ic = {i ∈ [n] | c ∈ Ai}.
Notice that we have
|hocolim(A)| =
I⊂[n]
|∆I | × |AI | ⊂
I⊂[n]
|∆I | × A
Definition 3.2 (truncated homotopy co-limits). For any m, 0 ≤ m ≤ n, we will
denote by hocolimm(A) the sub-complex of hocolim(A) defined by
(3.3) hocolimm(A) = g
A (skm(∆[n])).
Definition 3.3 (diagram preserving maps between homotopy co-limits). Replacing
in Definition 1.5, |A[n]| and |B[n]|, by |hocolim(A)| and |hocolim(B)| respectively,
as well as |AI | and |BI | by f
A (|AI |) and f
B (|BI |) respectively, we get definitions
of diagram preserving homotopy equivalences and stable homotopy equivalences
between |hocolim(A)| and |hocolim(B)|, and more generally for anym ≥ 0, between
|hocolimm(A)| and |hocolimm(B)|.
Definition 3.4. We say thatA ≈m B if there exists a diagram preserving homotopy
equivalence
φ : |hocolimm(A)| → |hocolimm(B)|.
We say that A ∼m B, if there exists a diagram preserving stable homotopy
equivalence φ ∈ {hocolimm(A); hocolimm(B)}, represented by
φ̃ : SN |hocolimm(A)| → S
N |hocolimm(B)|,
for some N > 0.
10 SAUGATA BASU
Remark 3.5. Note that in the above definition the map φ need not be induced by
a diagram preserving map φ : A[n] → B[n] (respectively, φ̃ : SN |hocolimm(A)| →
SN |hocolimm(B)|). Indeed if it was the case then the proofs of Theorems 3.6 and
3.7 below would be simplified considerably.
The two following theorems are the crucial topological ingredients in the proofs
of our main results.
Theorem 3.6. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, such that:
(1) Hi(|A
[n]|,Z),Hi(|B
[n]|,Z) = 0, for all i ≥ k, and
(2) A ∼k B.
Then, A and B are stable homotopy equivalent.
Theorem 3.7. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, such that:
(1) dim(Ai), dim(Bi) ≤ k, for 1 ≤ i ≤ n, and
(2) A ≈k+2 B.
Then, A and B are homotopy equivalent.
We now state two corollaries of Theorems 3.6 and 3.7 which might be of interest.
Given a Boolean formula θ(T1, . . . , Tn) containing no negations and a family of
sub-complexes A = {A1, . . . , An} of a finite regular cell complex, we will denote
by Aθ the sub-complex defined by the formula, θA, which is obtained from θ by
replacing in θ the atom Ti by Ai for each i ∈ [n], and replacing each ∧ (respectively
∨) by ∩ (respectively ∪).
Corollary 3.8. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, satisfying the same conditions as in The-
orem 3.6. Let θ(T1, . . . , Tn) be a Boolean formula without negations. Then, |Aθ|
and |Bθ| are stable homotopy equivalent.
Corollary 3.9. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, satisfying the same conditions as in The-
orem 3.7. Let θ(T1, . . . , Tn) be a Boolean formula without negations. Then, |Aθ|
and |Bθ| are homotopy equivalent.
3.2. Proofs of Theorems 3.6 and 3.7. Let A and B as in Theorem 3.6.
We need a preliminary lemma.
Lemma 3.10.
|A[n]| is diagram preserving homotopy equivalent to |hocolim(A)|.
Proof. Consider the map
fA : |hocolim(A)| → |A
defined in (3.1).
Clearly, if x ∈ c, f−1A (c) = |∆Ic |. Now applying Smale’s version of the Vietoris-
Begle Theorem [16] we obtain that fA is a homotopy equivalence. Clearly, fA is
diagram preserving. Moreover, (see for instance the proof of Theorem 6 in [16])
there exists an cellular inverse map
hA : |A
[n]| → |hocolim(A)|
such that fA ◦ hA is diagram preserving, and is a homotopy inverse of fA. �
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 11
We can now prove Theorems 3.6 and 3.7.
Proof of Theorem 3.6. Let hA : |A
[n]| → |hocolim(A)| be a diagram preserving
homotopy equivalence known to exist by Lemma 3.10. Since hA is cellular, and
dim |A[n]| ≤ k, its image is contained in hocolimk(A) since by definition (Eqn.
(3.3))
skk(hocolim(A)) ⊂ hocolimk(A).
We will denote by hA,B : S
N |hocolimk(A)| → S
N |hocolimk(B)| a map represent-
ing a diagram preserving stable homotopy equivalence known to exist by hypothesis
(which we assume to be cellular).
Let iB,k : S
N |hocolimk(B)| →֒ S
N |hocolim(B)| denote the inclusion map. The
map iB,k induces isomorphisms
(iB,k)∗ : Hj(hocolimk(B),Z) → Hj(hocolim(B),Z)
for 0 ≤ j ≤ k − 1.
Consequently, the map fB ◦ iB,k induces isomorphisms
(fB ◦ iB,k)∗ : Hj(hocolimk(B),Z) → Hj(B
[n],Z)
for 0 ≤ j ≤ k − 1.
Composing the maps, SNhA, hAB, iB,k,S
NfB we obtain that the map,
NfB ◦ iB,k ◦ hAB ◦ S
NhA : S
N |A[n]| → SN |B[n]|
induces isomorphisms
(SNfB ◦ iB,k ◦ hA,B,k ◦ S
NhA)∗ : Hj(|A
[n]|,Z) → Hj(|B
[n]|,Z)
for all j ≥ 0.
Moreover, the map SNfB ◦ iB,k ◦ hAB ◦ S
NhA is diagram preserving since each
constituent of the composition is diagram preserving. It now follows from Theorem
1.4 that the S-map represented by
φ = SNfB ◦ iB,k ◦ hAB ◦ S
NhA : S
N |A[n]| → SN |B[n]|,
is a diagram preserving stable homotopy equivalence. �
Before proving Theorem 3.7 we first need to recall a few basic facts from homo-
topy theory.
Definition 3.11 (k-equivalence). A map f : X → Y between two regular cell
complex is called a k-equivalence if the induced homomorphism
f∗ : πi(X) → πi(Y )
is an isomorphism for all 0 ≤ i < k, and an epimorphism for i = k, and we say that
X is k-equivalent to Y . (Note that k-equivalence is not an equivalence relation).
We also need the following well-known fact from algebraic topology.
Proposition 3.12. Let X,Y be finite regular cell complexes with
dim(X) < k, dim(Y ) ≤ k,
and f : X → Y a k-equivalence. Then, f is a homotopy equivalence between X and
Proof. See [23, pp. 69]. �
12 SAUGATA BASU
Proof of Theorem 3.7. The proof is along the same lines as that of the proof of
Theorem 3.6. Let hA : |A
[n]| → |hocolim(A)| be a diagram preserving homotopy
equivalence known to exist by Lemma 3.10. By the same argument as before, its
image is contained in |hocolimk+2(A)|.
We will denote by hA,B : |hocolimk+2(A)| → |hocolimk+2(B)| a diagram preserv-
ing homotopy equivalence known to exist by hypothesis.
Let iB,k+2 : |hocolimk+2(B)| →֒ |hocolim(B)| denote the inclusion map. The
map iB,k+2 induces isomorphisms
(iB,k+2)∗ : πj(hocolimk+2(B)) → πj(hocolim(B))
for 0 ≤ j ≤ k+1. This is a consequence of the exactness of the homotopy sequence
of the pair (hocolim(B), hocolimk+2(B)) (see [18]).
Consequently, the map fB ◦ iB,k induces isomorphisms
(gB ◦ iB,k)∗ : πj(hocolimk+2(B)) → πj(B
for 0 ≤ j ≤ k + 1.
Composing the maps, hA, hAB, iB,k+2, fB we obtain that the map
fB ◦ iB,k ◦ hAB ◦ hA : |A
[n]| → |B[n]|
induces isomorphisms
(fB ◦ iB,k ◦ hA,B,k ◦ hA)∗ : πj(A
[n]) → πj(B
for 0 ≤ j ≤ k + 1.
Moreover, the map fB◦iB,k◦hAB◦hA is diagram preserving since each constituent
of the composition is diagram preserving. It now follows from Proposition 3.12 that
the map
φ = fB ◦ iB,k ◦ hAB ◦ hA : |A
[n]| → |B[n]|
is a diagram preserving homotopy equivalence. �
Proof of Corollary 3.8. First note that since the formula θ does not contain nega-
tions, writing θ as a disjunction of conjunctions, there exists Σ ⊂ 2[n] such that
AI (respectively, Bθ =
BI). Let A
′ = {AI | I ∈ Σ} (respectively,
B′ = {BI | I ∈ Σ}). It follows from the hypothesis that
A′ ∼k B
Now apply Theorem 3.6. �
Proof of Corollary 3.9. The proof is similar to that of Corollary 3.8 using Theorem
3.7 in place of Theorem 3.6 and is omitted. �
4. Proofs of the Main Theorems
4.1. Summary of the main ideas. We first summarize the main ideas under-
lying the proof of Theorem 1.8. The proof of Theorem 1.9 is similar and differs
only in technical details. Let A = {A1, . . . ,An} be a (T, π1, π2)- arrangement in
k1+k2 . Using Proposition 4.7, we obtain a definable partition, {Cα}α∈I (say) of
k2 , into connected locally closed definable sets Cα ⊂ R
k2 , with the property that
as z varies over Cα, we get for each I ⊂ [n] with #I ≤ k1 + 1 isomorphic (and
continuously varying) triangulations of the sub-arrangement A[I]. Moreover, these
triangulations are downward compatible in the sense that the restriction to A[J ]
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 13
of the triangulation of A[I], refines that of A[J ] for each J ⊂ I (cf. Proposition
4.7 below). These facts allow us to prove that for any z1, z2 ∈ Cα the truncated
homotopy co-limits |hocolimk1(Az1)| and |hocolimk1(Az2)| are homotopy equiva-
lent by a diagram preserving homotopy equivalence. More precisely, we first prove
that the thickened homotopy co-limits |hocolim+k1(Az1 , ε̄)| and |hocolim
(Az2 , ε̄)|
are homeomorphic, and then use Proposition 4.8 to deduce that |hocolimk1(Az1)|
and |hocolimk1(Az2)| are homotopy equivalent. Theorem 3.6 then implies that Az1
is stable homotopy equivalent to Az2 by a diagram preserving stable homotopy
equivalence. It remains to bound the number of elements in the partition {Cα}α∈I .
We use Theorem 2.2 to obtain a bound of C · n(k1+1)k2 on this number, where C is
a constant which depends only on T .
In order to prove Theorem 1.8 we recall a few results from o-minimal geometry.
We first note an elementary property of families of admissible sets (see [2] for a
proof).
Observation 4.1. Suppose that T1, . . . , Tm ⊂ R
k+ℓ are definable sets, π1 : R
k+ℓ →
k and π2 : R
k+ℓ → Rℓ the two projections. Then, there exists a definable sub-
set T ′ ⊂ Rk+ℓ+m depending only on T1, . . . , Tm, such that for any collection of
(Ti, π1, π2) families Ai, 1 ≤ i ≤ m, the union
Ai is a (T
′, π′1, π
2)-family, where
π′1 : R
k+m+ℓ → Rk and π′2 : R
k+ℓ+m → Rℓ+m are the projections onto the first k,
and the last ℓ+m co-ordinates respectively.
4.2. Hardt’s Triviality for Definable Sets. One important technical tool will
be the following o-minimal version of Hardt’s triviality theorem.
Let X ⊂ Rk×Rℓ and A ⊂ Rk be definable subsets of Rk×Rℓ and Rℓ respectively,
and let π : X → Rℓ denote the projection map on the last ℓ co-ordinates.
We say that X is definably trivial over A if there exists a definable set F and a
definable homeomorphism
h : F ×A → X ∩ π−1(A),
such that the following diagram commutes.
F ×A X ∩ π−1(A)
In the diagram above π2 : F ×A → A is the projection onto the second factor. We
call h a definable trivialization of X over A.
If Y is a definable subset of X , we say that the trivialization h is compatible with
Y if there is a definable subset G of F such that h(G×A) = Y ∩ π−1(A). Clearly,
the restriction of h to G×A is a trivialization of Y over A.
Theorem 4.2 (Hardt’s theorem for definable families). Let X ⊂ Rk × Rℓ be a
definable set and let Y1, . . . , Ym be definable subsets of X. Then, there exists a
finite partition of Rℓ into definable sets C1, . . . , CN such that X is definably trivial
over each Ci, and moreover the trivializations over each Ci are compatible with
Y1, . . . , Ym.
14 SAUGATA BASU
Remark 4.3. We first remark that it is straightforward to derive from the proof of
Theorem 4.2 that the definable sets C1, . . . , CN can be chosen to be locally closed,
and can be expressed as, C1 = R
ℓ \ B1, C2 = B1 \ B2, . . . , CN = BN−1 \ BN for
closed definable sets B1, . . . , BN . Clearly, the closed definable sets B1, . . . , BN ,
determine the sets Ci of the partition.
Remark 4.4. Note also that it follows from Theorem 4.2, that there are only a finite
number of topological types amongst the fibers of any definable map f : X → Y
between definable sets X and Y . This remark would be used a number of times
later in the paper.
Since in what follows we will need to consider many different projections, we
adopt the following convention.
Notation 4.5. Given m and p, p ≤ m, we will denote by
π≤pm : R
m → Rp
(respectively π>pm : R
m → Rm−p) the projection onto the first p (respectively the
last m− p) coordinates.
4.3. Definable Triangulations. A triangulation of a closed and bounded defin-
able set S is a simplicial complex ∆ together with a definable homeomorphism from
|∆| to S. Given such a triangulation we will often identify the simplices in ∆ with
their images in S under the given homeomorphism.
We call a triangulation h1 : |∆1| → S of a definable set S, to be a refinement of
a triangulation h2 : |∆2| → S if for every simplex σ1 ∈ ∆1, there exists a simplex
σ2 ∈ ∆2 such that h1(|σ1|) ⊂ h2(|σ2|).
Let S1 ⊂ S2 be two closed and bounded definable subsets of R
k. We say that a
definable triangulation h : |∆| → S2 of S2, respects S1 if for every simplex σ ∈ ∆,
h(σ) ∩ S1 = h(σ) or ∅. In this case, h
−1(S1) is identified with a sub-complex of ∆
and h|h−1(S1) : h
−1(S1) → S1 is a definable triangulation of S1. We will refer to
this sub-complex by ∆|S1 .
We introduce the following notational conventions in order to simplify arguments
used later in the paper.
Notation 4.6. If T ⊂ Rk1+k2+ℓ be any definable subset of Rk1+k2+ℓ, for each m ≥ 0,
and (z,y0, . . . ,ym) ∈ R
k2+(m+1)ℓ, we will denote by Tz,y0,...,ym ⊂ R
k1 the definable
1≤i≤m
{x ∈ Rk1 | (x, z) ∈ Tyi}. For {j0, . . . , jm′} ⊂ [m], we will denote by
πm,j0,...,jm′ : R
(m+1)ℓ → R(m
′+1)ℓ the projection map on the appropriate blocks of
co-ordinates.
It is well known that compact definable sets are triangulable and moreover the
usual proof of this fact (see for instance [6]) can be easily extended to produce
a definable triangulation in a parametrized way. We will actually need a family
of such triangulations satisfying certain compatibility conditions mentioned before.
The following proposition states the existence of such families. We omit the proof
of the proposition since it is a technical but straightforward extension of the proof
of existence of triangulations for definable sets.
Proposition 4.7 (existence of m-adaptive triangulations). Let T ⊂ Rk1+k2+ℓ be a
closed and bounded definable subset of Rk1+k2+ℓ and let m ≥ 0. For each 0 ≤ p ≤ m,
there exists
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 15
(1) a definable partition {Cp,α}α∈Ip of R
k2+(p+1)ℓ, into locally closed sets, de-
termined by a sequence of definable closed sets, {Bp,α}α∈Ip (see Remark 4.3
above), and
(2) for each α ∈ Ip, a definable continuous map,
hp,α : |∆p,α| × Cp,α →
(z,y0,...,yp)∈Cp,α
Tz,y0,...,yp
where ∆p,α is a simplicial complex, and such that for each (z,y0, . . . ,yp) ∈
Cp,α, the restriction of hp,α to |∆p,α| × (z,y0, . . . ,yp) is a definable trian-
gulation
hp,α : |∆p,α| × (z,y0, . . . ,yp) → Tz,y0,...,yp
of the definable set Tz,y0,...,yp respecting the subsets, Tz,y0 , . . . , Tz,yp, and
(3) for each subset {j0, . . . , jp′} ⊂ [p], (Idk2 , πp,j0,...,jp′ )(Cp,α) ⊂ Cp′,β for some
β ∈ Ip′ , and for each (z,y0, . . . ,yp) ∈ Cp,α, the definable triangulation of
Tz,yj0 ,...,yjp′
induced by the triangulation
hp,α : |∆p,α| × (z,y0, . . . ,yp) → Tz,y0,...,yp
is a refinement of the definable triangulation,
hp′,β : |∆p′,β| × (z,yj0 , . . . ,yjp′ ) → Tz,yj0 ,...,yjp′
(We will call the family {hp,α}0≤p≤m,α∈Ip an m-adaptive family of triangulations
of T .)
We will also need the following technical result.
Proposition 4.8. Let Ct ⊂ R
k, t ≥ 0 be a definable family of closed and bounded
sets, and let C ⊂ Rk+1 be the definable set
Ct × {t}. If for every 0 ≤ t < t
Ct ⊂ Ct′ , and C0 = π
k+1(C ∩ (π
−1(0)), then there exists t0 > 0 such that, C0
has the same homotopy type as Ct for every t with 0 ≤ t ≤ t0.
Proof. The proof given in [4] (see Lemma 16.17) for the semi-algebraic case can
be easily adapted to the o-minimal setting using Hardt’s triviality for definable
families instead of for semi-algebraic ones. �
We now introduce another notational convention.
Notation 4.9. Let F(x) be a predicate defined over R+ and y ∈ R+. The notation
∀(0 < x ≪ y) F(x) stands for the statement
∃z ∈ (0, y) ∀x ∈ R+ (if x < z, then F(x)),
and can be read “for all positive x sufficiently smaller than y, F(x) is true”.
More generally,
Notation 4.10. For ε̄ = (ε0, . . . , εn) and a predicate F(ε̄) over R
+ we say “for all
sufficiently small ε̄, F(ε̄) is true” if
∀(0 < ε0 ≪ 1)∀(0 < ε1 ≪ ε0) · · · ∀(0 < εn ≪ εn−1)F(ε̄).
16 SAUGATA BASU
4.4. Infinitesimal Thickenings of the Faces of a Simplex. We will need the
following construction.
Let ε̄ = (ε0, . . . , εn) ∈ R
+ , with 0 ≤ εn < · · · < ε0 < 1. Later we will require ε̄
to be sufficiently small (see Notation 4.10).
For a face ∆J ∈ ∆[n], we denote by CJ(ε̄) the subset of |∆J | defined by
CJ (ε̄) = {x ∈ |∆J | | dist(x, |∆I |) ≥ ε#I−1 for all I ⊂ J}.
Note that,
|∆[n]| =
I⊂[n]
CI(ε̄).
Figure 1. The complex ∆[n].
I ⊂ J ⊂ K = [n]
CI(ε̄)
CI(ε̄) ∩ CJ(ε̄) ∩ CK(ε̄)
CI(ε̄) ∩ CJ(ε̄)
CJ(ε̄)
CJ(ε̄) ∩ CK(ε̄)
CK(ε̄)
Figure 2. The corresponding complex C(∆[n]) with I ⊂ J ⊂ K = [n].
Also, observe that for sufficiently small ε̄ > 0, the various CJ (ε̄)’s are all home-
omorphic to closed balls, and moreover all non-empty intersections between them
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 17
also have the same property. Thus, the cells CJ (ε̄)’s together with the non-empty
intersections between them form a regular cell complex, C(∆[n], ε̄), whose underly-
ing topological space is |∆[n]| (see Figures 1 and 2).
Definition 4.11. We will denote by C(skm(∆[n]), ε̄) the sub-complex of C(∆[n], ε̄)
consisting of the cells CI(ε̄)’s together with the non-empty intersections between
them where |I| ≤ m+ 1.
We now use thickened simplices defined above to define a thickened version of
the homotopy co-limit of an arrangement A.
4.5. Thickened Homotopy Co-limits. Given an m-adaptive family of triangu-
lations of T (cf. Proposition 4.7), {hp,α}0≤p≤m,α∈Ip and z ∈ R
k2 , we define a cell
complex, hocolim+m(Az) (best thought of as an infinitesimally thickened version
of hocolimm(Az)), whose associated topological space is homotopy equivalent to
|hocolimm(Az)|.
Definition 4.12 (the cell complex hocolim
m(Az)). Let Cm denote the cell complex
C(skm(∆[n]), ε̄) defined previously (cf. Definition 4.11).
Let C be a cell of Cm. Then, C ⊂ |∆I | for a unique simplex ∆I with I =
{i0, . . . , im′} ⊂ [n], m
′ ≤ m, and (following notation introduced before in Definition
4.11)
C = CI1(ε̄) ∩ · · · ∩ CIp(ε̄),
with I1 ⊂ I2 ⊂ · · · ⊂ Ip ⊂ I and p ≤ m
We denote by K(C, ε̄) the cell complex consisting of the cells
C × hm′,α(|σ|, z,yi0 , . . . ,yim′ )
with α ∈ Im′ , (z,yi0 , . . . ,yim′ ) ∈ Cα,m′ , σ ∈ ∆m′,α, and hm′,α(|σ|, z,yi0 , . . . ,yim′ ) ⊂
Az,I . We denote
(4.1) hocolim+m(Az, ε̄) =
K(C).
The compatibility properties (properties (2) and (3) in Proposition 4.7) of the m-
adaptive family of triangulations of T , {hp,α}0≤p≤m,α∈Ip , ensure that hocolim
m(Az, ε̄)
defined above is a regular cell complex. Notice that, since the map fA defined in
Eqn. 3.1 extends to |hocolim+m(Az, ε̄), the notion of diagram preserving maps ex-
tend to |hocolim+m(Az, ε̄) as well.
We now prove:
Lemma 4.13. Let z ∈ Rℓ and m ≥ 0. Then, for all sufficiently small ε̄ > 0,
|hocolim+m(Az, ε̄)| is homotopy equivalent to |hocolimm(Az)| by a diagram preserv-
ing homotopy equivalence.
Proof. Let N = |hocolim+m(Az, ε̄)|. First replace εm by a variable t in the definition
ofN to obtain a closed and bounded definable set, Nmt , and observe thatN
t ⊂ N
for all 0 < t < t′ ≪ 1.
Now apply Proposition 4.8 to obtain that N is homotopy equivalent to Nm0 .
Now, replace εm−1 by t in the definition of N
0 to obtain N
t , and applying
Proposition 4.8 obtain that Nm0 is homotopy equivalent to N
0 . Continuing in
this way we finally obtain that, N is homotopy equivalent to N00 = |hocolimm(Az)|.
18 SAUGATA BASU
Moreover, the diagram preserving property is clearly preserved at each step of the
proof. �
Proof of Theorem 1.8. Recall that for m ≥ 0, and (z,y0, . . . ,ym) ∈ R
k2+(m+1)ℓ,
we denote by Tz,y0,...,ym the definable set
Tz,yi ⊂ R
Now apply Proposition 4.7 to the set T with m = k1 to obtain an k1-adaptive
family of triangulations {hp,α}1≤p≤k1,α∈Ip .
We now fix {y1, . . . ,yn} ⊂ R
ℓ and let A = {A1, . . . , An} with Ai = Tyi ⊂
k1+k2 . For each z ∈ Rk2 , we will denote by Az = {A1,z, . . . , An,z} where Ai,z =
{x ∈ Rk1 | (x, z) ∈ Ai}.
For α ∈ Ik1 , and 1 ≤ i0 < · · · < ik1 ≤ n, we will denote by Bk1,α,i0,...,ik1 ⊂ R
the definable closed set
Bk1,α,i0,...,ik1 = {z ∈ R
ℓ | (z,y0, . . . ,yk1) ∈ Bk1,α}.
α∈Ik1
{Bk1,α,i0,...,ik1 | 1 ≤ i0 < i1 < · · · < ik1 ≤ n},
and let C ∈ C(B). Theorem 1.8 will follow from the following two lemmas.
Lemma 4.14. For any z1, z2 ∈ C, Az1 is stable homotopy equivalent to Az2 .
Proof. Clearly, by Theorem 3.6 it suffices to prove that |hocolimk1(Az1 )| is diagram
preserving homotopy equivalent to |hocolimk1(Az2 )|.
The compatibility properties of the triangulations ensure that that the complex
|hocolim+k1(Az1 , ε̄) is isomorphic to |hocolim
(Az2 , ε̄) and hence |hocolim
(Az1 , ε̄)|
is homeomorphic to |hocolim+k1(Az1 , ε̄)|.
Using Lemma 4.13 we get a diagram preserving homotopy equivalence
φ : |hocolimk1(Az1 )| → |hocolimk1(Az2 )|.
It now follows from Theorem 3.6 that the arrangements Az1 and Az2 are stable
homotopy equivalent. �
Lemma 4.15. There exists a constant C(T ) such that the cardinality of C(B) is
bounded by C · n(k1+1)k2 .
Proof. Notice that eachBk1,α, α ∈ Ik1 is a definable subset ofR
k2+(k1+1)ℓ depending
only on T . Also, the cardinality of the index set Ik1 is determined by T .
Hence, the set B consists of
definable sets, each one of them is a
(Bk1,α, π
k2+(k1+1)ℓ
, π>k2
k2+(k1+1)ℓ
for some α ∈ Ik1 . Using Observation 4.1, we have that B is a (B, π
2)-set for
some B determined only by T . Now apply Theorem 2.2. �
The theorem now follows from Lemmas 4.14 and 4.15 proved above. �
Proof of Theorem 1.9. The proof is similar to that of Theorem 1.8 given above,
except we use Theorem 3.7 instead of Theorem 3.6, and this accounts for the slight
worsening of the exponent in the bound. �
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 19
Proof of Theorem 2.7. Using a construction due to Gabrielov and Vorobjov [9] (see
also [2]) it is possible to replace any given A-set by a closed bounded A′-set (where
A′ is a new family of definable closely related to A with #A′ = 2k(#A)), such that
the new set has the same homotopy type as the original one. Using this construction
one can directly deduce Theorem 2.7 from Theorem 1.9. We omit the details. �
References
1. Pankaj K. Agarwal and Micha Sharir, Arrangements and their applications, Handbook of
computational geometry (J. Urrutia J.R. Sack, ed.), North-Holland, Amsterdam, 2000, pp. 49–
119. MR 1746675
2. S. Basu, Combinatorial complexity in o-minimal geometry, preprint at
arXiv:math.CO/0612050, 2006, An extended abstract appears in the Proceedings of
the ACM Symposium on the Theory of Computing, 2007.
3. , Algorithmic semi-algebraic geometry and topology – recent progress and open prob-
lems, Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary
Mathematics, vol. 453, American Mathematical Society, 2008, pp. 139–212.
4. S. Basu, R. Pollack, and M.-F. Roy, Algorithms in real algebraic geometry, Algorithms
and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006 (second edition).
MR 1998147 (2004g:14064)
5. S. Basu and N. Vorobjov, On the number of homotopy types of fibers of a definable map,
Journal of the London Mathematical Society (2007), 757–776.
6. M. Coste, An introduction to o-minimal geometry, Istituti Editoriali e Poligrafici Internazion-
ali, Pisa, 2000, Dip. Mat. Univ. Pisa, Dottorato di Ricerca in Matematica.
7. L. Danzer, B. Grunbaum, and V. Klee, Helly’s theorem and its relatives, Convexity, Pro-
ceedings of Symposia In Pure Mathematics, vol. VII, American Mathematical Society, 1963,
pp. 101–180.
8. Jean Dieudonné, A history of algebraic and differential topology. 1900–1960, Birkhäuser
Boston Inc., Boston, MA, 1989. MR 995842 (90g:01029)
9. A. Gabrielov and N. Vorobjov, Approximation of definable sets by compact families and upper
bounds on homotopy and homology, preprint at arXiv:math.AG/0710.3028v1, 2007.
10. D. Grigoriev and N. Vorobjov, Solving systems of polynomial inequalities in subexponential
time, Journal of Symbolic Computation 5 (1988), 37–64.
11. J.F. Knight, A. Pillay, and C. Steinhorn, Definable sets in ordered structures. II., Trans.
Amer. Math. Soc. 295 (1986), no. 2, 593–605. MR 0833698 (88b:03050b)
12. J. Matousek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212,
Springer-Verlag, 2002.
13. A. Pillay and C. Steinhorn, Definable sets in ordered structures. I., Trans. Amer. Math. Soc.
295 (1986), no. 2, 565–592. MR 0833697 (88b:03050a)
14. , Definable sets in ordered structures. III., Trans. Amer. Math. Soc. 309 (1988), no. 2,
469–576. MR 0943306 (89i:03059)
15. J.-P. Rolin, P. Speissegger, and A. J. Wilkie, Quasianalytic Denjoy-Carleman classes and
o-minimality, J. Amer. Math. Soc. 16 (2003), no. 4, 751–777 (electronic). MR 1992825
(2004g:14065)
16. S. Smale, A Vietoris mapping theorem for homotopy, Proc. Amer. Math. Soc. 8:3 (1957),
604–610.
17. E. H. Spanier and J. H. C. Whitehead, Duality in relative homotopy theory, Ann. of Math.
(2) 67 (1958), 203–238. MR 0105105 (21 #3850)
18. E.H. Spanier, Algebraic topology, McGraw-Hill, New York, 1966.
19. L. van den Dries, Tame topology and o-minimal structures., LMS Lecture Notes, vol. 248,
Cambridge University Press, 1998.
20. Lou van den Dries and Chris Miller, Geometric categories and o-minimal structures, Duke
Math. J. 84 (1996), no. 2, 497–540. MR 1404337 (97i:32008)
21. Lou van den Dries and Patrick Speissegger, The real field with convergent generalized power
series, Trans. Amer. Math. Soc. 350 (1998), no. 11, 4377–4421. MR 1458313 (99a:03036)
22. , The field of reals with multisummable series and the exponential function, Proc.
London Math. Soc. (3) 81 (2000), no. 3, 513–565. MR 1781147 (2002k:03057)
20 SAUGATA BASU
23. O. Ya. Viro and D. B. Fuchs, Homology and cohomology, Topology. II, Encyclopaedia Math.
Sci., vol. 24, Springer, Berlin, 2004, Translated from the Russian by C. J. Shaddock, pp. 95–
196. MR 2054457
24. George W. Whitehead, Elements of homotopy theory, Graduate Texts in Mathematics, vol. 61,
Springer-Verlag, New York, 1978. MR 516508 (80b:55001)
25. A. J. Wilkie, Model completeness results for expansions of the ordered field of real numbers
by restricted Pfaffian functions and the exponential function, J. Amer. Math. Soc. 9 (1996),
no. 4, 1051–1094. MR 1398816 (98j:03052)
26. , A theorem of the complement and some new o-minimal structures, Selecta Math.
(N.S.) 5 (1999), no. 4, 397–421. MR 1740677 (2001c:03071)
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, U.S.A.
E-mail address: saugata.basu@math.gatech.edu
	1. Introduction
	1.1. Combinatorial Complexity in O-minimal Geometry
	1.2. Stable Homotopy Equivalence
	1.3. Diagrams and Co-limits
	1.4. Diagram Preserving Maps
	1.5. Main Results
	2. Background
	2.1. Bounds on the Betti numbers of Admissible Sets
	2.2. Homotopy types of the fibers of a semi-algebraic map
	3. A Topological Comparison Theorem
	3.1. Topological Preliminaries
	3.2. Proofs of Theorems ?? and ??
	4. Proofs of the Main Theorems
	4.1. Summary of the main ideas
	4.2. Hardt's Triviality for Definable Sets
	4.3. Definable Triangulations
	4.4. Infinitesimal Thickenings of the Faces of a Simplex
	4.5. Thickened Homotopy Co-limits
	References

  Let ${\mathcal S}(\R)$ be an o-minimal structure over $\R$, $T \subset
\R^{k_1+k_2+\ell}$ a closed definable set, and $$ \displaylines{\pi_1:
\R^{k_1+k_2+\ell}\to \R^{k_1 + k_2}, \pi_2: \R^{k_1+k_2+\ell}\to \R^{\ell}, \
\pi_3: \R^{k_1 + k_2} \to \R^{k_2}} $$ the projection maps.
  For any collection ${\mathcal A} = \{A_1,...,A_n\}$ of subsets of
$\R^{k_1+k_2}$, and $\z \in \R^{k_2}$, let $\A_\z$ denote the collection of
subsets of $\R^{k_1}$, $\{A_{1,\z},..., A_{n,\z}\}$, where $A_{i,\z} = A_i \cap
\pi_3^{-1}(\z), 1 \leq i \leq n$. We prove that there exists a constant $C =
C(T) > 0,$ such that for any family ${\mathcal A} = \{A_1,...,A_n\}$ of
definable sets, where each $A_i = \pi_1(T \cap \pi_2^{-1}(\y_i))$, for some
$\y_i \in \R^{\ell}$, the number of distinct stable homotopy types of $\A_\z,
\z \in \R^{k_2}$, is bounded by $ \displaystyle{C \cdot n^{(k_1+1)k_2},} $
while the number of distinct homotopy types is bounded by $ \displaystyle{C
\cdot n^{(k_1+3)k_2}.} $ This generalizes to the general o-minimal setting,
bounds of the same type proved in \cite{BV} for semi-algebraic and
semi-Pfaffian families. One main technical tool used in the proof of the above
results, is a topological comparison theorem which might be of independent
interest in the study of arrangements.

Introduction
The study of arrangements is a very important subject in discrete and computa-
tional geometry, where one studies arrangements of n subsets of Rk (often referred
to as objects of the arrangements) for fixed k and large values of n (see [1] for a
survey of the known results from this area). The precise nature of the objects in an
arrangements will be discussed in more details below. Common examples consist
of arrangements of hyperplanes, balls or simplices in Rk. More generally one con-
siders arrangements of objects of “bounded description complexity”. This means
that each set in the arrangement is defined by a first order formula in the language
of ordered fields involving at most a constant number of polynomials whose degrees
are also bounded by a constant (see [12]).
Key words and phrases. Combinatorial Complexity, O-minimal Structures, Homotopy Types,
Arrangements.
The author was supported in part by NSF grant CCF-0634907.
2000 MATHEMATICS SUBJECT CLASSIFICATION 14P10, 14P25
http://arxiv.org/abs/0704.0295v3
2 SAUGATA BASU
In this paper we consider parametrized families of arrangements. The question
we will be interested in most, is the number of “topologically” distinct arrange-
ments which can occur in such a family (precise definition of the topological type
of an arrangement is given later (see Definition 1.6)). Parametrized arrangements
occur quite frequently in practice. For instance, take any arrangement A in Rk1+k2
and let π : Rk1+k2 → Rk2 be the projection on the last k2 co-ordinates. Then for
each z ∈ Rk2 , the intersection of the arrangement A with the fiber π−1(z), is an ar-
rangement Az in R
k1 and the family of the arrangements {Az}z∈Rk2 is an example
of a parametrized family of arrangements. Even though the number of arrange-
ments in the family {Az}z∈Rk2 is infinite, it follows from Hardt’s triviality theorem
generalized to o-minimal structures (see Theorem 4.2 below) that the number of
“topological types” occurring amongst them is finite and can be effectively bounded
in terms of the n, k1, k2 up to multiplication by a constant that depends only on
the particular family from which the objects of the arrangements are drawn. If
by topological type we mean homeomorphism type, then the best known upper
bound on the number of types occurring is doubly exponential in k1, k2. However,
if we consider the weaker notion of homotopy type, then we obtain a singly ex-
ponential bound. We conjecture that a singly exponential bound also holds for
homeomorphism types as well.
We now make precise the class of arrangements that we consider and also the
notion of topological type of an arrangement.
1.1. Combinatorial Complexity in O-minimal Geometry. In order to put the
study of the combinatorial complexity of arrangements in a more natural mathe-
matical context, as well as to elucidate the proofs of the main results in the area,
a new framework was introduced in [2] which is a significant generalization of the
settings mentioned above. We recall here the basic definitions of this framework
from [2], referring the reader to the same paper for further details and examples.
We first recall an important model theoretic notion – that of o-minimality –
which plays a crucial role in this generalization.
1.1.1. O-minimal Structures. O-minimal structures were invented and first studied
by Pillay and Steinhorn in the pioneering papers [13, 14]. Later the theory was
further developed through contributions of other researchers, most notably van
den Dries, Wilkie, Rolin, Speissegger amongst others [20, 21, 22, 25, 26, 15]. We
particularly recommend the book by van den Dries [19] and the notes by Coste [6]
for an easy introduction to the topic as well as the proofs of the basic results that
we use in this paper.
Definition 1.1 (o-minimal structure). An o-minimal structure over a real closed
field R is a sequence S(R) = (Sn)n∈N, where each Sn is a collection of subsets of R
(called the definable sets in the structure) satisfying the following axioms (following
the exposition in [6]).
(1) All algebraic subsets of Rn are in Sn.
(2) The class Sn is closed under complementation and finite unions and inter-
sections.
(3) If A ∈ Sm and B ∈ Sn then A×B ∈ Sm+n.
(4) If π : Rn+1 → Rn is the projection map on the first n co-ordinates and
A ∈ Sn+1, then π(A) ∈ Sn.
(5) The elements of S1 are precisely finite unions of points and intervals.
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 3
The class of semi-algebraic sets is one obvious example of such a structure, but
in fact there are much richer classes of sets which have been proved to be o-minimal
(see [6, 19]).
1.1.2. Admissible Sets. We now recall from [2] the definition of the class of sets that
will play the role of sets with bounded description complexity mentioned above.
Definition 1.2 (admissible sets). Let S(R) be an o-minimal structure over R
and let T ⊂ Rk+ℓ be a fixed definable set. Let π1 : R
k+ℓ → Rk (respectively
π2 : R
k+ℓ → Rℓ) be the projections onto the first k (respectively last ℓ) co-ordinates.
T ⊂ Rk+ℓ
We will call a subset S of Rk to be a (T, π1, π2)-set if
S = Ty = π1(π
2 (y) ∩ T )
for some y ∈ Rℓ.
If T is some fixed definable set, we call a family of (T, π1, π2)-sets to be a
(T, π1, π2)-family. We wil also refer to a finite (T, π1, π2)-family as an arrangement
of (T, π1, π2)-sets.
1.2. Stable Homotopy Equivalence. For any finite CW-complex X we denote
by SX the suspension of X and for n ≥ 0, we denote by SnX the n-fold iterated
suspension S ◦ S ◦ · · · ◦ S
︸ ︷︷ ︸
n times
Note that if i : X →֒ Y is an inclusion map, then there is an obvious induced
inclusion map Sni : SnX →֒ SnY between the n-fold iterated suspensions of X and
Recall from [17] that for two finite CW-complexes X and Y , an element of
(1.1) {X ;Y } = lim
[SiX,SiY ]
is called an S-map (or map in the suspension category). An S-map f ∈ {X ;Y } is
represented by the homotopy class of a map f : SNX → SNY for some N ≥ 0.
Definition 1.3 (stable homotopy equivalence). An S-map f ∈ {X ;Y } is an S-
equivalence (also called a stable homotopy equivalence) if it admits an inverse f−1 ∈
{Y ;X}. In this case we say that X and Y are stable homotopy equivalent.
If f ∈ {X ;Y } is an S-map, then f induces a homomorphism
f∗ : H∗(X,Z) → H∗(Y,Z)
between the homology groups of X and Y .
The following theorem characterizes stable homotopy equivalence in terms of
homology.
Theorem 1.4. [8, pp. 604] Let X and Y be two finite CW-complexes. Then X and
Y are stable homotopy equivalent if and only if there exists an S-map f ∈ {X ;Y }
which induces isomorphisms f∗ : H∗(X,Z) → H∗(Y,Z).
4 SAUGATA BASU
1.3. Diagrams and Co-limits. The arrangements that we consider are all finitely
triangulable. In other words, the union of objects of an arrangement is homeomor-
phic to a finite simplicial complex, and each individual object in the arrangement
will correspond to a sub-complex of this simplicial complex. It will be more con-
venient to work in the category of finite regular cell complexes, instead of just
simplicial complexes.
Let A = {A1, . . . , An}, where each Ai is a sub-complex of a finite regular cell
complex. We will denote by [n] the set {1, . . . , n} and for I ⊂ [n] we will denote by
AI (respectively AI) the regular cell complexes
Ai (respectively
Ai). Notice
that if J ⊂ I ⊂ [n], then
AJ ⊂ AI ,
AI ⊂ AJ .
We will call the collection of sets {|AI |}I⊂[n] together with the inclusion maps
iI,J : |AI | →֒ |AJ |, J ⊂ I, the diagram of A. Notice that (even though we do not
use this fact), |A[n]| is the co-limit of the diagram of A. For I ⊂ [n] we will denote
by A[I] the sub-arrangement {Ai | i ∈ I}.
1.4. Diagram Preserving Maps. Now let A = {A1, . . . , An}, B = {B1, . . . , Bn}
where each Ai, Bj is a sub-complex of a finite regular cell complex for 1 ≤ i, j ≤ n.
Definition 1.5 (diagram preserving maps). We call a map f : |A[n]| → |B[n]|
to be diagram preserving if f(|AI |) ⊂ |BI | for every I ⊂ [n]. (Notice that the
above property is equivalent to f(|Ai|) ⊂ |Bi| for every i ∈ [n] but the previous
property will be more convenient for us later when we extend the definition of
diagram preserving maps to homotopy co-limits (see Definition 3.3).) We say that
two maps f, g : |A[n]| → |B[n]| are diagram homotopic if there exists a homotopy
h : |A[n]| × [0, 1] → |B[n]|, such that h(·, 0) = f, h(·, 1) = g and h(·, t) is diagram
preserving for each t ∈ [0, 1].
More generally, we call a map f : SN |A[n]| → SN |B[n]| to be diagram preserving
if f(SN |AI |) ⊂ S
N |BI | for every I ⊂ [n]. We say that two maps f, g : S
N |A[n]| →
SN |B[n]| are diagram homotopic if there exists a homotopy h : SN |A[n]| × [0, 1] →
SN |B[n]| such that h(·, 0) = f, h(·, 1) = g and h(·, t) is diagram preserving for each
t ∈ [0, 1].
We say that f : |A[n]| → |B[n]| is a diagram preserving homeomorphism if there
exists a diagram preserving inverse map g : |B[n]| → |A[n]| such that the induced
maps g ◦ f : |A[n]| → |A[n]| and f ◦ g : |B[n]| → |B[n]| are Id|A[n]| and Id|B[n]|,
respectively.
We say that f : |A[n]| → |B[n]| is a diagram preserving homotopy equivalence
if there exists a diagram preserving inverse map g : |B[n]| → |A[n]| such that the
induced maps g◦f : |A[n]| → |A[n]| and f ◦g : |B[n]| → |B[n]| are diagram homotopic
to Id|A[n]| and Id|B[n]|, respectively.
We say that an S-map f ∈ {|A[n]|; |B[n]|} is a diagram preserving stable homo-
topy equivalence if it is represented by a diagram preserving map
f̃ : SN |A[n]| → SN |B[n]|
such that there exists a diagram preserving inverse map
g̃ : SN |B[n]| → SN |A[n]|
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 5
for which the induced maps
g̃ ◦ f̃ : SN |A[n]| → SN |A[n]|,
f̃ ◦ g̃ : SN |B[n]| → SN |B[n]|
are diagram homotopic to IdSN |A[n]| and IdSN |B[n]|, respectively.
Translating these topological definitions into the language of arrangements, we
say that:
Definition 1.6 (topological type of an arrangement). Two arrangements A,B are
homeomorphic (respectively homotopy equivalent, stable homotopy equivalent) if
there exists a diagram preserving homeomorphism (respectively homotopy equiva-
lence, stable homotopy equivalence) between them.
Remark 1.7. Note that, since two definable sets might be stable homotopy equiv-
alent, without being homotopy equivalent (see [18, pp. 462]), and also homotopy
equivalent without being homeomorphic, the notions of homeomorphism type, ho-
motopy type and stable homotopy type are each strictly weaker than the previous
The main results of this paper can now be stated.
1.5. Main Results. Let S(R) be an o-minimal structure over R, T ⊂ Rk1+k2+ℓ
a closed and bounded definable set, and let π1 : R
k1+k2+ℓ → Rk1+k2 (respectively,
π2 : R
k1+k2+ℓ → Rℓ, π3 : R
k1+k2 → Rk2) denote the projections onto the first
k1 + k2 (respectively, the last ℓ, the last k2) co-ordinates. For any collection A =
{A1, . . . , An} of (T, π1, π2)-sets, and z ∈ R
k2 , we will denote by Az the collection
of sets, {A1,z, . . . , An,z}, where Ai,z = Ai ∩ π
3 (z), 1 ≤ i ≤ n.
A fundamental theorem in o-minimal geometry is Hardt’s trivialization theorem
(Theorem 4.2 below) which says that there exists a definable partition of Rk2 into
a finite number of definable sets {Ti}i∈I such that for each i ∈ I, all fibers Az with
z ∈ Ti are definably homeomorphic. A very natural question is to ask for an upper
bound on the size of this partition (which will also give an upper bound on the
number of homeomorphism types amongst the arrangements Az, z ∈ R
Hardt’s theorem is a corollary of the existence of cylindrical cell decompositions
of definable sets proved in [11] (see also [19, 6]). When A is a (T, π1, π2)-family
for some fixed definable set T ⊂ Rk1+k2+ℓ, with π1 : R
k1+k2+ℓ → Rk1+k2 , π2 :
k1+k2+ℓ → Rℓ, π2 : R
k1+k2 → Rk2 the usual projections, and #A = n, the
quantitative definable cylindrical cell decomposition theorem in [2] gives a doubly
exponential (in k1k2) upper bound on the cardinality of I and hence on the number
of homeomorphism types amongst the arrangements Az, z ∈ R
k2 . A tighter (say
singly exponential) bound on the number of homeomorphism types of the fibers
would be very interesting but is unknown at present. Note that we cannot hope for
a bound which is better than singly exponential because the lower bounds on the
number of topological types proved in [5] also applies in our situation.
In this paper we give tighter (singly exponential) upper bounds on the number of
homotopy types occurring amongst the fibers Az, z ∈ R
k2 . We prove the following
theorems. The first theorem gives a bound on the number of stable homotopy types
of the arrangements Az, z ∈ R
k2 , while the second theorem gives a slightly worse
bound for homotopy types.
6 SAUGATA BASU
Theorem 1.8. There exists a constant C = C(T ) > 0 such that for any collection
A = {A1, . . . , An} of (T, π1, π2)-sets the number of distinct stable homotopy types
amongst the arrangements Az, z ∈ R
k2 is bounded by
C · n(k1+1)k2 .
If we replace stable homotopy type by homotopy type, we obtain a slightly weaker
bound.
Theorem 1.9. There exists a constant C = C(T ) > 0 such that for any collection
A = {A1, . . . , An} of (T, π1, π2)-sets the number of distinct homotopy types occuring
amongst the arrangements Az, z ∈ R
k2 is bounded by
C · n(k1+3)k2 .
2. Background
In this section we describe some prior work in the area of bounding the number of
homotopy types of fibers of a definable map and their connections with the results
presented in this paper.
We begin with a definition.
Definition 2.1 (A-sets). Let A = {A1, . . . , An}, such that each Ai ⊂ R
k is a
(T, π1, π2)-set. For I ⊂ {1, . . . , n}, we let A(I) denote the set
(2.1)
i∈I⊂[n]
j∈[n]\I
(Rk \Aj)
and we will call such a set to be a basic A-set. We will denote by C(A) the set of
non-empty connected components of all basic A-sets.
We will call definable subsets S ⊂ Rk defined by a Boolean formula whose atoms
are of the form, x ∈ Ai, 1 ≤ i ≤ n, an A-set. An A-set is thus a union of basic
A-sets. If T is closed, and the Boolean formula defining S has no negations, then S
is closed by definition (since each Ai is closed) and we call such a set an A-closed
Moreover, if V is any closed definable subset ofRk, and S is anA-set (respectively
A-closed set), then we will call S∩V to be an (A, V )-set (respectively (A, V )-closed
set).
2.1. Bounds on the Betti numbers of Admissible Sets. The problem of
bounding the Betti numbers of A-sets is investigated in [2], where several results
known in the semi-algebraic and semi-Pfaffian case are extended to this general
setting. In particular, we will need the following theorem proved there.
Theorem 2.2. [2] Let S(R) be an o-minimal structure over R and let T ⊂ Rk+ℓ
be a closed definable set. Then, there exists a constant C = C(T ) > 0 depending
only on T such that for any arrangement A = {A1, . . . , An} of (T, π1, π2)-sets of
k the following holds.
For every i, 0 ≤ i ≤ k,
(2.2)
D∈C(A)
bi(D) ≤ C · n
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 7
Remark 2.3. The main intuition behind the bound in Theorem 2.2 (as well as similar
results in the semi-algebraic and semi-Pfaffian settings) is that the homotopy type
(or at least the Betti numbers) of a definable set in Rk defined in terms of n sets
belonging to some fixed definable family, depend only on the interaction of these
sets at most k + 1 at a time. This is reminiscent of Helly’s theorem in convexity
theory (see [7]) but in a homotopical setting. This observation is also used to give
an efficient algorithm for computing the Betti numbers of arrangements (see [3,
Section 8]). However, the proof of Theorem 2.2 in [2] (as well as the proofs of
similar results in the semi-algebraic [4] and semi-Pfaffian settings [10]) depends on
an argument involving the Mayer-Vietoris sequence for homology, and does not
require more detailed information about homotopy types. In Section 3 below, we
make the above intuition mathematically precise.
We prove two theorems (Theorems 3.6 and 3.7 below) and these auxiliary re-
sults are the keys to proving the main results of this paper (Theorems 1.8 and
1.9). Moreover, these auxiliary results could also be of independent interest in the
quantitative study of arrangements.
2.2. Homotopy types of the fibers of a semi-algebraic map. Theorem 2.2
gives tight bounds on the topological complexity of an A-set in terms of the cardi-
nality of A, assuming that the sets in A belong to some fixed definable family. A
problem closely related to the problem we consider in this paper is to bound the
number of topological types of the fibers of a projection restricted to an arbitrary
A-set.
More precisely, let S ⊂ Rk1+k2 be a set definable in an o-minimal structure over
the reals (see [19]) and let π : Rk1+k2 → Rk2 denote the projection map on the
last k2 co-ordinates. We consider the fibers, Sz = π
−1(z) ∩ S for different z in
k2 . Hardt’s trivialization theorem, (Theorem 4.2 below) shows that there exists
a definable partition of Rk2 into a finite number of definable sets {Ti}i∈I such that
for each i ∈ I and any point zi ∈ Ti, π
−1(Ti) ∩ S is definably homeomorphic to
Szi × Ti by a fiber preserving homeomorphism. In particular, for each i ∈ I, all
fibers Sz with z ∈ Ti are definably homeomorphic.
In case S is an A-set, with A a (T, π1, π2)-family for some fixed definable set
T ⊂ Rk1+k2+ℓ, with π1 : R
k1+k2+ℓ → Rk1+k2 , π2 : R
k1+k2+ℓ → Rℓ, π2 : R
k1+k2 →
k2 , the usual projections, and #A = n, the quantitative definable cylindrical cell
decomposition theorem in [2] gives a doubly exponential (in k1k2) upper bound
on the cardinality of I and hence on the number of homeomorphism types of the
fibers of the map π3|S . A tighter (say singly exponential) bound on the number
of homeomorphism types of the fibers would be very interesting but is unknown at
present.
Recently, the problem of obtaining a tight bound on the number of topological
types of the fibers of a definable map for semi-algebraic and semi-Pfaffian sets
was considered in [5], and it was shown that the number of distinct homotopy
types of the fibers of such a map can be bounded (in terms of the format of the
formula defining the set) by a function singly exponential in k1k2. In particular,
the combinatorial part of the bound is also singly exponential. A more precise
statement in the case of semi-algebraic sets is the following theorem which appears
in [5].
Theorem 2.4. [5] Let P ⊂ R[X1, . . . , Xk1 , Y1, . . . , Yk2 ], with deg(P ) ≤ d for each
P ∈ P and cardinality #P = n. Then, for any fixed P-semi-algebraic set S the
8 SAUGATA BASU
number of different homotopy types of fibers π−1(y) ∩ S for various y ∈ π(S) is
bounded by
(2k1nk2d)
O(k1k2).
Remark 2.5. The proof of Theorem 2.4 however has the drawback that it relies
on techniques involving perturbations of the original polynomials in order to put
them in general position, as well as Thom’s Isotopy Theorem, and as such does not
extend easily to the o-minimal setting. The main results of this paper (see Theorem
1.8 and Theorem 1.9) extend the combinatorial part of Theorem 2.4 to the more
general o-minimal category.
Remark 2.6. Even though the formulation of Theorem 2.4 seems a little different
from the main theorems of this paper (Theorems 1.8 and 1.9), they are in fact
closely related. In fact, as a consequence of Theorem 1.9 we obtain bounds on the
number of homotopy types of the fibers of S for any fixed A-set S, analogous to
the one in Theorem 2.4.
More precisely we have:
Theorem 2.7. Let S(R) be an o-minimal structure over R, and T ⊂ Rk1+k2+ℓ a
closed and bounded definable set, and π1 : R
k1+k2+ℓ → Rk1+k2 , π2 : R
k1+k2+ℓ →
ℓ, and π3 : R
k1+k2 → Rk2 the projection maps. Then, there exists a constant
C = C(T ) > 0, such that for any collection A = {A1, . . . , An} of (T, π1, π2)-sets,
for any fixed A-set S the number of distinct homotopy types of fibers π−13 (z)∩S for
various z ∈ π3(S) is bounded by
C · n(k1+3)k2 .
A similar result with a bound of C · n(k1+1)k2 holds for stable homotopy types
as well.
3. A Topological Comparison Theorem
As noted previously, the main underlying idea behind our proof of Theorem 1.8
is that the homotopy type of an A-set in Rk depends only on the interaction of sets
in A at most (k + 1) at a time. In this section we make this idea precise.
We show that in case A = {A1, . . . , An}, with each Ai a definable, closed and
bounded subset of Rk, the homotopy type of any A-closed set is determined by a
certain sub-complex of the homotopy co-limit of the diagram of A. The crucial fact
here is that this sub-complex depends only on the intersections of the sets in A at
most k + 1 at a time.
In order to avoid technical difficulties, we restrict ourselves to the category of
finite, regular cell complexes (see [24] for the definition of a regular cell complex).
The setting of finite, regular cell complexes suffices for us, since it is well known
that closed and bounded definable sets in any o-minimal structure are finitely tri-
angulable, and hence, are homeomorphic to regular cell complexes.
3.1. Topological Preliminaries. Let A = {A1, . . . , An}, where each Ai is a sub-
complex of a finite regular cell complex. We now define the homotopy co-limit of
the diagram of A.
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 9
3.1.1. Homotopy Co-limits. Let ∆[n] denote the standard simplex of dimension n−1
with vertices in [n] (and by |∆[n]| the corresponding closed geometric simplex). For
I ⊂ [n], we denote by ∆I the (#I − 1)-dimensional face of ∆[n] corresponding to I.
The homotopy co-limit, hocolim(A), is a CW-complex defined as follows.
Definition 3.1 (homotopy co-limit).
hocolim(A) =
I⊂[n]
∆I ×AI/ ∼
where the equivalence relation ∼ is defined as follows.
For I ⊂ J ⊂ [n], let sI,J : |∆I | →֒ |∆J | denote the inclusion map of the face |∆I |
in |∆J |, and let iI,J : |AJ | →֒ |AI | denote the inclusion map of |AJ | in |AI |.
Given (s,x) ∈ |∆I |×|AI | and (t,y) ∈ |∆J |×|AJ | with I ⊂ J , then (s,x) ∼ (t,y)
if and only if t = sI,J(s) and x = iI,J(y).
Note that there exist two natural maps
fA : |hocolim(A)| → |A
[n]|,
gA : |hocolim(A)| → |∆[n]|
defined by
(3.1) fA(s,x) = s,
(3.2) gA(s,x) = x.
where (s,x) ∈ |∆Ic | × c, c is a cell in A
[n] and Ic = {i ∈ [n] | c ∈ Ai}.
Notice that we have
|hocolim(A)| =
I⊂[n]
|∆I | × |AI | ⊂
I⊂[n]
|∆I | × A
Definition 3.2 (truncated homotopy co-limits). For any m, 0 ≤ m ≤ n, we will
denote by hocolimm(A) the sub-complex of hocolim(A) defined by
(3.3) hocolimm(A) = g
A (skm(∆[n])).
Definition 3.3 (diagram preserving maps between homotopy co-limits). Replacing
in Definition 1.5, |A[n]| and |B[n]|, by |hocolim(A)| and |hocolim(B)| respectively,
as well as |AI | and |BI | by f
A (|AI |) and f
B (|BI |) respectively, we get definitions
of diagram preserving homotopy equivalences and stable homotopy equivalences
between |hocolim(A)| and |hocolim(B)|, and more generally for anym ≥ 0, between
|hocolimm(A)| and |hocolimm(B)|.
Definition 3.4. We say thatA ≈m B if there exists a diagram preserving homotopy
equivalence
φ : |hocolimm(A)| → |hocolimm(B)|.
We say that A ∼m B, if there exists a diagram preserving stable homotopy
equivalence φ ∈ {hocolimm(A); hocolimm(B)}, represented by
φ̃ : SN |hocolimm(A)| → S
N |hocolimm(B)|,
for some N > 0.
10 SAUGATA BASU
Remark 3.5. Note that in the above definition the map φ need not be induced by
a diagram preserving map φ : A[n] → B[n] (respectively, φ̃ : SN |hocolimm(A)| →
SN |hocolimm(B)|). Indeed if it was the case then the proofs of Theorems 3.6 and
3.7 below would be simplified considerably.
The two following theorems are the crucial topological ingredients in the proofs
of our main results.
Theorem 3.6. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, such that:
(1) Hi(|A
[n]|,Z),Hi(|B
[n]|,Z) = 0, for all i ≥ k, and
(2) A ∼k B.
Then, A and B are stable homotopy equivalent.
Theorem 3.7. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, such that:
(1) dim(Ai), dim(Bi) ≤ k, for 1 ≤ i ≤ n, and
(2) A ≈k+2 B.
Then, A and B are homotopy equivalent.
We now state two corollaries of Theorems 3.6 and 3.7 which might be of interest.
Given a Boolean formula θ(T1, . . . , Tn) containing no negations and a family of
sub-complexes A = {A1, . . . , An} of a finite regular cell complex, we will denote
by Aθ the sub-complex defined by the formula, θA, which is obtained from θ by
replacing in θ the atom Ti by Ai for each i ∈ [n], and replacing each ∧ (respectively
∨) by ∩ (respectively ∪).
Corollary 3.8. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, satisfying the same conditions as in The-
orem 3.6. Let θ(T1, . . . , Tn) be a Boolean formula without negations. Then, |Aθ|
and |Bθ| are stable homotopy equivalent.
Corollary 3.9. Let A = {A1, . . . , An},B = {B1, . . . , Bn} be two families of sub-
complexes of a finite regular cell complex, satisfying the same conditions as in The-
orem 3.7. Let θ(T1, . . . , Tn) be a Boolean formula without negations. Then, |Aθ|
and |Bθ| are homotopy equivalent.
3.2. Proofs of Theorems 3.6 and 3.7. Let A and B as in Theorem 3.6.
We need a preliminary lemma.
Lemma 3.10.
|A[n]| is diagram preserving homotopy equivalent to |hocolim(A)|.
Proof. Consider the map
fA : |hocolim(A)| → |A
defined in (3.1).
Clearly, if x ∈ c, f−1A (c) = |∆Ic |. Now applying Smale’s version of the Vietoris-
Begle Theorem [16] we obtain that fA is a homotopy equivalence. Clearly, fA is
diagram preserving. Moreover, (see for instance the proof of Theorem 6 in [16])
there exists an cellular inverse map
hA : |A
[n]| → |hocolim(A)|
such that fA ◦ hA is diagram preserving, and is a homotopy inverse of fA. �
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 11
We can now prove Theorems 3.6 and 3.7.
Proof of Theorem 3.6. Let hA : |A
[n]| → |hocolim(A)| be a diagram preserving
homotopy equivalence known to exist by Lemma 3.10. Since hA is cellular, and
dim |A[n]| ≤ k, its image is contained in hocolimk(A) since by definition (Eqn.
(3.3))
skk(hocolim(A)) ⊂ hocolimk(A).
We will denote by hA,B : S
N |hocolimk(A)| → S
N |hocolimk(B)| a map represent-
ing a diagram preserving stable homotopy equivalence known to exist by hypothesis
(which we assume to be cellular).
Let iB,k : S
N |hocolimk(B)| →֒ S
N |hocolim(B)| denote the inclusion map. The
map iB,k induces isomorphisms
(iB,k)∗ : Hj(hocolimk(B),Z) → Hj(hocolim(B),Z)
for 0 ≤ j ≤ k − 1.
Consequently, the map fB ◦ iB,k induces isomorphisms
(fB ◦ iB,k)∗ : Hj(hocolimk(B),Z) → Hj(B
[n],Z)
for 0 ≤ j ≤ k − 1.
Composing the maps, SNhA, hAB, iB,k,S
NfB we obtain that the map,
NfB ◦ iB,k ◦ hAB ◦ S
NhA : S
N |A[n]| → SN |B[n]|
induces isomorphisms
(SNfB ◦ iB,k ◦ hA,B,k ◦ S
NhA)∗ : Hj(|A
[n]|,Z) → Hj(|B
[n]|,Z)
for all j ≥ 0.
Moreover, the map SNfB ◦ iB,k ◦ hAB ◦ S
NhA is diagram preserving since each
constituent of the composition is diagram preserving. It now follows from Theorem
1.4 that the S-map represented by
φ = SNfB ◦ iB,k ◦ hAB ◦ S
NhA : S
N |A[n]| → SN |B[n]|,
is a diagram preserving stable homotopy equivalence. �
Before proving Theorem 3.7 we first need to recall a few basic facts from homo-
topy theory.
Definition 3.11 (k-equivalence). A map f : X → Y between two regular cell
complex is called a k-equivalence if the induced homomorphism
f∗ : πi(X) → πi(Y )
is an isomorphism for all 0 ≤ i < k, and an epimorphism for i = k, and we say that
X is k-equivalent to Y . (Note that k-equivalence is not an equivalence relation).
We also need the following well-known fact from algebraic topology.
Proposition 3.12. Let X,Y be finite regular cell complexes with
dim(X) < k, dim(Y ) ≤ k,
and f : X → Y a k-equivalence. Then, f is a homotopy equivalence between X and
Proof. See [23, pp. 69]. �
12 SAUGATA BASU
Proof of Theorem 3.7. The proof is along the same lines as that of the proof of
Theorem 3.6. Let hA : |A
[n]| → |hocolim(A)| be a diagram preserving homotopy
equivalence known to exist by Lemma 3.10. By the same argument as before, its
image is contained in |hocolimk+2(A)|.
We will denote by hA,B : |hocolimk+2(A)| → |hocolimk+2(B)| a diagram preserv-
ing homotopy equivalence known to exist by hypothesis.
Let iB,k+2 : |hocolimk+2(B)| →֒ |hocolim(B)| denote the inclusion map. The
map iB,k+2 induces isomorphisms
(iB,k+2)∗ : πj(hocolimk+2(B)) → πj(hocolim(B))
for 0 ≤ j ≤ k+1. This is a consequence of the exactness of the homotopy sequence
of the pair (hocolim(B), hocolimk+2(B)) (see [18]).
Consequently, the map fB ◦ iB,k induces isomorphisms
(gB ◦ iB,k)∗ : πj(hocolimk+2(B)) → πj(B
for 0 ≤ j ≤ k + 1.
Composing the maps, hA, hAB, iB,k+2, fB we obtain that the map
fB ◦ iB,k ◦ hAB ◦ hA : |A
[n]| → |B[n]|
induces isomorphisms
(fB ◦ iB,k ◦ hA,B,k ◦ hA)∗ : πj(A
[n]) → πj(B
for 0 ≤ j ≤ k + 1.
Moreover, the map fB◦iB,k◦hAB◦hA is diagram preserving since each constituent
of the composition is diagram preserving. It now follows from Proposition 3.12 that
the map
φ = fB ◦ iB,k ◦ hAB ◦ hA : |A
[n]| → |B[n]|
is a diagram preserving homotopy equivalence. �
Proof of Corollary 3.8. First note that since the formula θ does not contain nega-
tions, writing θ as a disjunction of conjunctions, there exists Σ ⊂ 2[n] such that
AI (respectively, Bθ =
BI). Let A
′ = {AI | I ∈ Σ} (respectively,
B′ = {BI | I ∈ Σ}). It follows from the hypothesis that
A′ ∼k B
Now apply Theorem 3.6. �
Proof of Corollary 3.9. The proof is similar to that of Corollary 3.8 using Theorem
3.7 in place of Theorem 3.6 and is omitted. �
4. Proofs of the Main Theorems
4.1. Summary of the main ideas. We first summarize the main ideas under-
lying the proof of Theorem 1.8. The proof of Theorem 1.9 is similar and differs
only in technical details. Let A = {A1, . . . ,An} be a (T, π1, π2)- arrangement in
k1+k2 . Using Proposition 4.7, we obtain a definable partition, {Cα}α∈I (say) of
k2 , into connected locally closed definable sets Cα ⊂ R
k2 , with the property that
as z varies over Cα, we get for each I ⊂ [n] with #I ≤ k1 + 1 isomorphic (and
continuously varying) triangulations of the sub-arrangement A[I]. Moreover, these
triangulations are downward compatible in the sense that the restriction to A[J ]
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 13
of the triangulation of A[I], refines that of A[J ] for each J ⊂ I (cf. Proposition
4.7 below). These facts allow us to prove that for any z1, z2 ∈ Cα the truncated
homotopy co-limits |hocolimk1(Az1)| and |hocolimk1(Az2)| are homotopy equiva-
lent by a diagram preserving homotopy equivalence. More precisely, we first prove
that the thickened homotopy co-limits |hocolim+k1(Az1 , ε̄)| and |hocolim
(Az2 , ε̄)|
are homeomorphic, and then use Proposition 4.8 to deduce that |hocolimk1(Az1)|
and |hocolimk1(Az2)| are homotopy equivalent. Theorem 3.6 then implies that Az1
is stable homotopy equivalent to Az2 by a diagram preserving stable homotopy
equivalence. It remains to bound the number of elements in the partition {Cα}α∈I .
We use Theorem 2.2 to obtain a bound of C · n(k1+1)k2 on this number, where C is
a constant which depends only on T .
In order to prove Theorem 1.8 we recall a few results from o-minimal geometry.
We first note an elementary property of families of admissible sets (see [2] for a
proof).
Observation 4.1. Suppose that T1, . . . , Tm ⊂ R
k+ℓ are definable sets, π1 : R
k+ℓ →
k and π2 : R
k+ℓ → Rℓ the two projections. Then, there exists a definable sub-
set T ′ ⊂ Rk+ℓ+m depending only on T1, . . . , Tm, such that for any collection of
(Ti, π1, π2) families Ai, 1 ≤ i ≤ m, the union
Ai is a (T
′, π′1, π
2)-family, where
π′1 : R
k+m+ℓ → Rk and π′2 : R
k+ℓ+m → Rℓ+m are the projections onto the first k,
and the last ℓ+m co-ordinates respectively.
4.2. Hardt’s Triviality for Definable Sets. One important technical tool will
be the following o-minimal version of Hardt’s triviality theorem.
Let X ⊂ Rk×Rℓ and A ⊂ Rk be definable subsets of Rk×Rℓ and Rℓ respectively,
and let π : X → Rℓ denote the projection map on the last ℓ co-ordinates.
We say that X is definably trivial over A if there exists a definable set F and a
definable homeomorphism
h : F ×A → X ∩ π−1(A),
such that the following diagram commutes.
F ×A X ∩ π−1(A)
In the diagram above π2 : F ×A → A is the projection onto the second factor. We
call h a definable trivialization of X over A.
If Y is a definable subset of X , we say that the trivialization h is compatible with
Y if there is a definable subset G of F such that h(G×A) = Y ∩ π−1(A). Clearly,
the restriction of h to G×A is a trivialization of Y over A.
Theorem 4.2 (Hardt’s theorem for definable families). Let X ⊂ Rk × Rℓ be a
definable set and let Y1, . . . , Ym be definable subsets of X. Then, there exists a
finite partition of Rℓ into definable sets C1, . . . , CN such that X is definably trivial
over each Ci, and moreover the trivializations over each Ci are compatible with
Y1, . . . , Ym.
14 SAUGATA BASU
Remark 4.3. We first remark that it is straightforward to derive from the proof of
Theorem 4.2 that the definable sets C1, . . . , CN can be chosen to be locally closed,
and can be expressed as, C1 = R
ℓ \ B1, C2 = B1 \ B2, . . . , CN = BN−1 \ BN for
closed definable sets B1, . . . , BN . Clearly, the closed definable sets B1, . . . , BN ,
determine the sets Ci of the partition.
Remark 4.4. Note also that it follows from Theorem 4.2, that there are only a finite
number of topological types amongst the fibers of any definable map f : X → Y
between definable sets X and Y . This remark would be used a number of times
later in the paper.
Since in what follows we will need to consider many different projections, we
adopt the following convention.
Notation 4.5. Given m and p, p ≤ m, we will denote by
π≤pm : R
m → Rp
(respectively π>pm : R
m → Rm−p) the projection onto the first p (respectively the
last m− p) coordinates.
4.3. Definable Triangulations. A triangulation of a closed and bounded defin-
able set S is a simplicial complex ∆ together with a definable homeomorphism from
|∆| to S. Given such a triangulation we will often identify the simplices in ∆ with
their images in S under the given homeomorphism.
We call a triangulation h1 : |∆1| → S of a definable set S, to be a refinement of
a triangulation h2 : |∆2| → S if for every simplex σ1 ∈ ∆1, there exists a simplex
σ2 ∈ ∆2 such that h1(|σ1|) ⊂ h2(|σ2|).
Let S1 ⊂ S2 be two closed and bounded definable subsets of R
k. We say that a
definable triangulation h : |∆| → S2 of S2, respects S1 if for every simplex σ ∈ ∆,
h(σ) ∩ S1 = h(σ) or ∅. In this case, h
−1(S1) is identified with a sub-complex of ∆
and h|h−1(S1) : h
−1(S1) → S1 is a definable triangulation of S1. We will refer to
this sub-complex by ∆|S1 .
We introduce the following notational conventions in order to simplify arguments
used later in the paper.
Notation 4.6. If T ⊂ Rk1+k2+ℓ be any definable subset of Rk1+k2+ℓ, for each m ≥ 0,
and (z,y0, . . . ,ym) ∈ R
k2+(m+1)ℓ, we will denote by Tz,y0,...,ym ⊂ R
k1 the definable
1≤i≤m
{x ∈ Rk1 | (x, z) ∈ Tyi}. For {j0, . . . , jm′} ⊂ [m], we will denote by
πm,j0,...,jm′ : R
(m+1)ℓ → R(m
′+1)ℓ the projection map on the appropriate blocks of
co-ordinates.
It is well known that compact definable sets are triangulable and moreover the
usual proof of this fact (see for instance [6]) can be easily extended to produce
a definable triangulation in a parametrized way. We will actually need a family
of such triangulations satisfying certain compatibility conditions mentioned before.
The following proposition states the existence of such families. We omit the proof
of the proposition since it is a technical but straightforward extension of the proof
of existence of triangulations for definable sets.
Proposition 4.7 (existence of m-adaptive triangulations). Let T ⊂ Rk1+k2+ℓ be a
closed and bounded definable subset of Rk1+k2+ℓ and let m ≥ 0. For each 0 ≤ p ≤ m,
there exists
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 15
(1) a definable partition {Cp,α}α∈Ip of R
k2+(p+1)ℓ, into locally closed sets, de-
termined by a sequence of definable closed sets, {Bp,α}α∈Ip (see Remark 4.3
above), and
(2) for each α ∈ Ip, a definable continuous map,
hp,α : |∆p,α| × Cp,α →
(z,y0,...,yp)∈Cp,α
Tz,y0,...,yp
where ∆p,α is a simplicial complex, and such that for each (z,y0, . . . ,yp) ∈
Cp,α, the restriction of hp,α to |∆p,α| × (z,y0, . . . ,yp) is a definable trian-
gulation
hp,α : |∆p,α| × (z,y0, . . . ,yp) → Tz,y0,...,yp
of the definable set Tz,y0,...,yp respecting the subsets, Tz,y0 , . . . , Tz,yp, and
(3) for each subset {j0, . . . , jp′} ⊂ [p], (Idk2 , πp,j0,...,jp′ )(Cp,α) ⊂ Cp′,β for some
β ∈ Ip′ , and for each (z,y0, . . . ,yp) ∈ Cp,α, the definable triangulation of
Tz,yj0 ,...,yjp′
induced by the triangulation
hp,α : |∆p,α| × (z,y0, . . . ,yp) → Tz,y0,...,yp
is a refinement of the definable triangulation,
hp′,β : |∆p′,β| × (z,yj0 , . . . ,yjp′ ) → Tz,yj0 ,...,yjp′
(We will call the family {hp,α}0≤p≤m,α∈Ip an m-adaptive family of triangulations
of T .)
We will also need the following technical result.
Proposition 4.8. Let Ct ⊂ R
k, t ≥ 0 be a definable family of closed and bounded
sets, and let C ⊂ Rk+1 be the definable set
Ct × {t}. If for every 0 ≤ t < t
Ct ⊂ Ct′ , and C0 = π
k+1(C ∩ (π
−1(0)), then there exists t0 > 0 such that, C0
has the same homotopy type as Ct for every t with 0 ≤ t ≤ t0.
Proof. The proof given in [4] (see Lemma 16.17) for the semi-algebraic case can
be easily adapted to the o-minimal setting using Hardt’s triviality for definable
families instead of for semi-algebraic ones. �
We now introduce another notational convention.
Notation 4.9. Let F(x) be a predicate defined over R+ and y ∈ R+. The notation
∀(0 < x ≪ y) F(x) stands for the statement
∃z ∈ (0, y) ∀x ∈ R+ (if x < z, then F(x)),
and can be read “for all positive x sufficiently smaller than y, F(x) is true”.
More generally,
Notation 4.10. For ε̄ = (ε0, . . . , εn) and a predicate F(ε̄) over R
+ we say “for all
sufficiently small ε̄, F(ε̄) is true” if
∀(0 < ε0 ≪ 1)∀(0 < ε1 ≪ ε0) · · · ∀(0 < εn ≪ εn−1)F(ε̄).
16 SAUGATA BASU
4.4. Infinitesimal Thickenings of the Faces of a Simplex. We will need the
following construction.
Let ε̄ = (ε0, . . . , εn) ∈ R
+ , with 0 ≤ εn < · · · < ε0 < 1. Later we will require ε̄
to be sufficiently small (see Notation 4.10).
For a face ∆J ∈ ∆[n], we denote by CJ(ε̄) the subset of |∆J | defined by
CJ (ε̄) = {x ∈ |∆J | | dist(x, |∆I |) ≥ ε#I−1 for all I ⊂ J}.
Note that,
|∆[n]| =
I⊂[n]
CI(ε̄).
Figure 1. The complex ∆[n].
I ⊂ J ⊂ K = [n]
CI(ε̄)
CI(ε̄) ∩ CJ(ε̄) ∩ CK(ε̄)
CI(ε̄) ∩ CJ(ε̄)
CJ(ε̄)
CJ(ε̄) ∩ CK(ε̄)
CK(ε̄)
Figure 2. The corresponding complex C(∆[n]) with I ⊂ J ⊂ K = [n].
Also, observe that for sufficiently small ε̄ > 0, the various CJ (ε̄)’s are all home-
omorphic to closed balls, and moreover all non-empty intersections between them
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 17
also have the same property. Thus, the cells CJ (ε̄)’s together with the non-empty
intersections between them form a regular cell complex, C(∆[n], ε̄), whose underly-
ing topological space is |∆[n]| (see Figures 1 and 2).
Definition 4.11. We will denote by C(skm(∆[n]), ε̄) the sub-complex of C(∆[n], ε̄)
consisting of the cells CI(ε̄)’s together with the non-empty intersections between
them where |I| ≤ m+ 1.
We now use thickened simplices defined above to define a thickened version of
the homotopy co-limit of an arrangement A.
4.5. Thickened Homotopy Co-limits. Given an m-adaptive family of triangu-
lations of T (cf. Proposition 4.7), {hp,α}0≤p≤m,α∈Ip and z ∈ R
k2 , we define a cell
complex, hocolim+m(Az) (best thought of as an infinitesimally thickened version
of hocolimm(Az)), whose associated topological space is homotopy equivalent to
|hocolimm(Az)|.
Definition 4.12 (the cell complex hocolim
m(Az)). Let Cm denote the cell complex
C(skm(∆[n]), ε̄) defined previously (cf. Definition 4.11).
Let C be a cell of Cm. Then, C ⊂ |∆I | for a unique simplex ∆I with I =
{i0, . . . , im′} ⊂ [n], m
′ ≤ m, and (following notation introduced before in Definition
4.11)
C = CI1(ε̄) ∩ · · · ∩ CIp(ε̄),
with I1 ⊂ I2 ⊂ · · · ⊂ Ip ⊂ I and p ≤ m
We denote by K(C, ε̄) the cell complex consisting of the cells
C × hm′,α(|σ|, z,yi0 , . . . ,yim′ )
with α ∈ Im′ , (z,yi0 , . . . ,yim′ ) ∈ Cα,m′ , σ ∈ ∆m′,α, and hm′,α(|σ|, z,yi0 , . . . ,yim′ ) ⊂
Az,I . We denote
(4.1) hocolim+m(Az, ε̄) =
K(C).
The compatibility properties (properties (2) and (3) in Proposition 4.7) of the m-
adaptive family of triangulations of T , {hp,α}0≤p≤m,α∈Ip , ensure that hocolim
m(Az, ε̄)
defined above is a regular cell complex. Notice that, since the map fA defined in
Eqn. 3.1 extends to |hocolim+m(Az, ε̄), the notion of diagram preserving maps ex-
tend to |hocolim+m(Az, ε̄) as well.
We now prove:
Lemma 4.13. Let z ∈ Rℓ and m ≥ 0. Then, for all sufficiently small ε̄ > 0,
|hocolim+m(Az, ε̄)| is homotopy equivalent to |hocolimm(Az)| by a diagram preserv-
ing homotopy equivalence.
Proof. Let N = |hocolim+m(Az, ε̄)|. First replace εm by a variable t in the definition
ofN to obtain a closed and bounded definable set, Nmt , and observe thatN
t ⊂ N
for all 0 < t < t′ ≪ 1.
Now apply Proposition 4.8 to obtain that N is homotopy equivalent to Nm0 .
Now, replace εm−1 by t in the definition of N
0 to obtain N
t , and applying
Proposition 4.8 obtain that Nm0 is homotopy equivalent to N
0 . Continuing in
this way we finally obtain that, N is homotopy equivalent to N00 = |hocolimm(Az)|.
18 SAUGATA BASU
Moreover, the diagram preserving property is clearly preserved at each step of the
proof. �
Proof of Theorem 1.8. Recall that for m ≥ 0, and (z,y0, . . . ,ym) ∈ R
k2+(m+1)ℓ,
we denote by Tz,y0,...,ym the definable set
Tz,yi ⊂ R
Now apply Proposition 4.7 to the set T with m = k1 to obtain an k1-adaptive
family of triangulations {hp,α}1≤p≤k1,α∈Ip .
We now fix {y1, . . . ,yn} ⊂ R
ℓ and let A = {A1, . . . , An} with Ai = Tyi ⊂
k1+k2 . For each z ∈ Rk2 , we will denote by Az = {A1,z, . . . , An,z} where Ai,z =
{x ∈ Rk1 | (x, z) ∈ Ai}.
For α ∈ Ik1 , and 1 ≤ i0 < · · · < ik1 ≤ n, we will denote by Bk1,α,i0,...,ik1 ⊂ R
the definable closed set
Bk1,α,i0,...,ik1 = {z ∈ R
ℓ | (z,y0, . . . ,yk1) ∈ Bk1,α}.
α∈Ik1
{Bk1,α,i0,...,ik1 | 1 ≤ i0 < i1 < · · · < ik1 ≤ n},
and let C ∈ C(B). Theorem 1.8 will follow from the following two lemmas.
Lemma 4.14. For any z1, z2 ∈ C, Az1 is stable homotopy equivalent to Az2 .
Proof. Clearly, by Theorem 3.6 it suffices to prove that |hocolimk1(Az1 )| is diagram
preserving homotopy equivalent to |hocolimk1(Az2 )|.
The compatibility properties of the triangulations ensure that that the complex
|hocolim+k1(Az1 , ε̄) is isomorphic to |hocolim
(Az2 , ε̄) and hence |hocolim
(Az1 , ε̄)|
is homeomorphic to |hocolim+k1(Az1 , ε̄)|.
Using Lemma 4.13 we get a diagram preserving homotopy equivalence
φ : |hocolimk1(Az1 )| → |hocolimk1(Az2 )|.
It now follows from Theorem 3.6 that the arrangements Az1 and Az2 are stable
homotopy equivalent. �
Lemma 4.15. There exists a constant C(T ) such that the cardinality of C(B) is
bounded by C · n(k1+1)k2 .
Proof. Notice that eachBk1,α, α ∈ Ik1 is a definable subset ofR
k2+(k1+1)ℓ depending
only on T . Also, the cardinality of the index set Ik1 is determined by T .
Hence, the set B consists of
definable sets, each one of them is a
(Bk1,α, π
k2+(k1+1)ℓ
, π>k2
k2+(k1+1)ℓ
for some α ∈ Ik1 . Using Observation 4.1, we have that B is a (B, π
2)-set for
some B determined only by T . Now apply Theorem 2.2. �
The theorem now follows from Lemmas 4.14 and 4.15 proved above. �
Proof of Theorem 1.9. The proof is similar to that of Theorem 1.8 given above,
except we use Theorem 3.7 instead of Theorem 3.6, and this accounts for the slight
worsening of the exponent in the bound. �
TOPOLOGICAL TYPES OF PARAMETRIZED ARRANGEMENTS 19
Proof of Theorem 2.7. Using a construction due to Gabrielov and Vorobjov [9] (see
also [2]) it is possible to replace any given A-set by a closed bounded A′-set (where
A′ is a new family of definable closely related to A with #A′ = 2k(#A)), such that
the new set has the same homotopy type as the original one. Using this construction
one can directly deduce Theorem 2.7 from Theorem 1.9. We omit the details. �
References
1. Pankaj K. Agarwal and Micha Sharir, Arrangements and their applications, Handbook of
computational geometry (J. Urrutia J.R. Sack, ed.), North-Holland, Amsterdam, 2000, pp. 49–
119. MR 1746675
2. S. Basu, Combinatorial complexity in o-minimal geometry, preprint at
arXiv:math.CO/0612050, 2006, An extended abstract appears in the Proceedings of
the ACM Symposium on the Theory of Computing, 2007.
3. , Algorithmic semi-algebraic geometry and topology – recent progress and open prob-
lems, Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemporary
Mathematics, vol. 453, American Mathematical Society, 2008, pp. 139–212.
4. S. Basu, R. Pollack, and M.-F. Roy, Algorithms in real algebraic geometry, Algorithms
and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006 (second edition).
MR 1998147 (2004g:14064)
5. S. Basu and N. Vorobjov, On the number of homotopy types of fibers of a definable map,
Journal of the London Mathematical Society (2007), 757–776.
6. M. Coste, An introduction to o-minimal geometry, Istituti Editoriali e Poligrafici Internazion-
ali, Pisa, 2000, Dip. Mat. Univ. Pisa, Dottorato di Ricerca in Matematica.
7. L. Danzer, B. Grunbaum, and V. Klee, Helly’s theorem and its relatives, Convexity, Pro-
ceedings of Symposia In Pure Mathematics, vol. VII, American Mathematical Society, 1963,
pp. 101–180.
8. Jean Dieudonné, A history of algebraic and differential topology. 1900–1960, Birkhäuser
Boston Inc., Boston, MA, 1989. MR 995842 (90g:01029)
9. A. Gabrielov and N. Vorobjov, Approximation of definable sets by compact families and upper
bounds on homotopy and homology, preprint at arXiv:math.AG/0710.3028v1, 2007.
10. D. Grigoriev and N. Vorobjov, Solving systems of polynomial inequalities in subexponential
time, Journal of Symbolic Computation 5 (1988), 37–64.
11. J.F. Knight, A. Pillay, and C. Steinhorn, Definable sets in ordered structures. II., Trans.
Amer. Math. Soc. 295 (1986), no. 2, 593–605. MR 0833698 (88b:03050b)
12. J. Matousek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212,
Springer-Verlag, 2002.
13. A. Pillay and C. Steinhorn, Definable sets in ordered structures. I., Trans. Amer. Math. Soc.
295 (1986), no. 2, 565–592. MR 0833697 (88b:03050a)
14. , Definable sets in ordered structures. III., Trans. Amer. Math. Soc. 309 (1988), no. 2,
469–576. MR 0943306 (89i:03059)
15. J.-P. Rolin, P. Speissegger, and A. J. Wilkie, Quasianalytic Denjoy-Carleman classes and
o-minimality, J. Amer. Math. Soc. 16 (2003), no. 4, 751–777 (electronic). MR 1992825
(2004g:14065)
16. S. Smale, A Vietoris mapping theorem for homotopy, Proc. Amer. Math. Soc. 8:3 (1957),
604–610.
17. E. H. Spanier and J. H. C. Whitehead, Duality in relative homotopy theory, Ann. of Math.
(2) 67 (1958), 203–238. MR 0105105 (21 #3850)
18. E.H. Spanier, Algebraic topology, McGraw-Hill, New York, 1966.
19. L. van den Dries, Tame topology and o-minimal structures., LMS Lecture Notes, vol. 248,
Cambridge University Press, 1998.
20. Lou van den Dries and Chris Miller, Geometric categories and o-minimal structures, Duke
Math. J. 84 (1996), no. 2, 497–540. MR 1404337 (97i:32008)
21. Lou van den Dries and Patrick Speissegger, The real field with convergent generalized power
series, Trans. Amer. Math. Soc. 350 (1998), no. 11, 4377–4421. MR 1458313 (99a:03036)
22. , The field of reals with multisummable series and the exponential function, Proc.
London Math. Soc. (3) 81 (2000), no. 3, 513–565. MR 1781147 (2002k:03057)
20 SAUGATA BASU
23. O. Ya. Viro and D. B. Fuchs, Homology and cohomology, Topology. II, Encyclopaedia Math.
Sci., vol. 24, Springer, Berlin, 2004, Translated from the Russian by C. J. Shaddock, pp. 95–
196. MR 2054457
24. George W. Whitehead, Elements of homotopy theory, Graduate Texts in Mathematics, vol. 61,
Springer-Verlag, New York, 1978. MR 516508 (80b:55001)
25. A. J. Wilkie, Model completeness results for expansions of the ordered field of real numbers
by restricted Pfaffian functions and the exponential function, J. Amer. Math. Soc. 9 (1996),
no. 4, 1051–1094. MR 1398816 (98j:03052)
26. , A theorem of the complement and some new o-minimal structures, Selecta Math.
(N.S.) 5 (1999), no. 4, 397–421. MR 1740677 (2001c:03071)
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, U.S.A.
E-mail address: saugata.basu@math.gatech.edu
	1. Introduction
	1.1. Combinatorial Complexity in O-minimal Geometry
	1.2. Stable Homotopy Equivalence
	1.3. Diagrams and Co-limits
	1.4. Diagram Preserving Maps
	1.5. Main Results
	2. Background
	2.1. Bounds on the Betti numbers of Admissible Sets
	2.2. Homotopy types of the fibers of a semi-algebraic map
	3. A Topological Comparison Theorem
	3.1. Topological Preliminaries
	3.2. Proofs of Theorems ?? and ??
	4. Proofs of the Main Theorems
	4.1. Summary of the main ideas
	4.2. Hardt's Triviality for Definable Sets
	4.3. Definable Triangulations
	4.4. Infinitesimal Thickenings of the Faces of a Simplex
	4.5. Thickened Homotopy Co-limits
	References
