Leray numbers of projections and a topological Helly type theorem
arXiv:0704.0277v1  [math.CO]  2 Apr 2007
7 Leray Numbers of Projections and
a Topological Helly Type Theorem
Gil Kalai∗ Roy Meshulam†
November 4, 2018
Abstract
Let X be a simplicial complex on the vertex set V . The rational
Leray number L(X) of X is the minimal d such that H̃i(Y ;Q) = 0 for
all induced subcomplexes Y ⊂ X and i ≥ d.
Suppose V =
i=1 Vi is a partition of V such that the induced sub-
complexes X[Vi] are all 0-dimensional. Let π denote the projection
of X into the (m − 1)-simplex on the vertex set {1, . . . ,m} given by
π(v) = i if v ∈ Vi. Let r = max{|π
−1(π(x))| : x ∈ |X|}. It is shown
L(π(X)) ≤ rL(X) + r − 1 .
One consequence is a topological extension of a Helly type result
of Amenta. Let F be a family of compact sets in Rd such that for any
F ′ ⊂ F , the intersection
F ′ is either empty or contractible.
It is shown that if G is a family of sets such that for any finite G′ ⊂ G,
the intersection
G′ is a union of at most r disjoint sets in F , then
the Helly number of G is at most r(d+ 1).
Math Subject Classification. 55U10, 52A35
Keywords and Phrases. Helly’s Theorem, d-Leray Complexes
∗Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel, and
Departments of Computer Science and Mathematics, Yale University. e-mail:
kalai@math.huji.ac.il . Research supported by ISF, BSF and NSF grants.
†Department of Mathematics, Technion, Haifa 32000, Israel. e-mail: meshu-
lam@math.technion.ac.il . Research supported by the Israel Science Foundation.
http://arxiv.org/abs/0704.0277v1
1 Introduction
Let F be a family of sets. The Helly number h(F) of F is the minimal
positive integer h such that if a finite subfamily K ⊂ F satisfies
K′ 6= ∅
for all K′ ⊂ K of cardinality ≤ h, then
K 6= ∅. Helly’s classical theorem
(1913, see e.g. [3]) asserts that the Helly number of the family of convex sets
in Rd is d+ 1.
Helly’s theorem and its numerous extensions are of central importance
in discrete and computational geometry (see [3, 10]). It is of considerable
interest to understand the role of convexity in these results, and to find
suitable topological extensions. Indeed, it is often the case that topological
methods provide a deeper understanding of the underlying combinatorics
behind Helly type theorems. Helly himself realized in 1930 (see [3]) that in
his theorem, convex sets can be replaced by topological cells if you impose
the additional requirement that all non-empty intersections of these cells are
again topological cells. Helly’s topological version of his theorem also follows
from the later nerve theorems of Borsuk, Leray and others (see below).
The following result was conjectured by Grünbaum and Motzkin [8] , and
proved by Amenta [1]. A family of sets G is an (F , r)-family if for any finite
G ′ ⊂ G, the intersection
G ′ is a union of at most r disjoint sets from F .
Theorem 1.1 (Amenta). Let F be the family of compact convex sets in Rd.
Then for any (F , r)-family G
h(G) ≤ r(d+ 1) .
The main motivation for the present paper was to find a topological ex-
tension of Amenta’s Theorem.
Let X be a simplicial complex on the vertex set V . The induced sub-
complex on a subset of vertices S ⊂ V is X [S] = {σ ∈ X : σ ⊂ S}. The
link of a subset A ⊂ V is lk(X,A) = {τ ∈ X : τ ∪ A ∈ X, τ ∩ A = ∅ } .
The geometric realization of X is denoted by |X|. We identify X and |X|
when no confusion can arise. All homology groups considered below are with
rational coefficients, i.e. Hi(X) = Hi(X ;Q) and H̃i(X) = H̃i(X ;Q).
The rational Leray number L(X) ofX is the minimal d such that H̃i(Y ) =
0 for all induced subcomplexes Y ⊂ X and i ≥ d. The Leray number can be
regarded as a simple topologically based “complexity measure” of X . Note
that L(X) = 0 iff X is a simplex, and L(X) ≤ 1 iff X is the clique complex
of a chordal graph (see [9]). It is well-known (see e.g. [7]) that L(X) ≤ d
iff H̃i(lk(X, σ)) = 0 for all σ ∈ X and i ≥ d. Leray numbers have also
significance in commutative algebra, since L(X) is equal to the Castelnuovo-
Mumford regularity of the Stanley-Reisner ring of X over Q (see [7]).
From now on we assume that V1, . . . , Vm are finite disjoint 0-dimensional
complexes, and denote their join by V1 ∗ · · · ∗ Vm. Let ∆m−1 be the simplex
on the vertex set [m] = {1, . . . , m}, and let π denote the simplicial projection
from V1 ∗ · · · ∗ Vm onto ∆m−1 given by π(v) = i if v ∈ Vi. For a subcomplex
X ⊂ V1 ∗ · · ·∗Vm, let r(X, π) = max{|π
−1(π(x))| : x ∈ |X|}. Our main result
is the following
Theorem 1.2. Let Y = π(X) and r = r(X, π). Then
L(Y ) ≤ rL(X) + r − 1 . (1)
Example: For r ≥ 1, d ≥ 2 let m = rd, and consider a partition [m] =
k=1Ak with |Ak| = d. For i ∈ [m] let Vi = {i} × [r]. Denote by ∆(A) the
simplex on vertex set A, with boundary ∂∆(A) ≃ S |A|−2. For k, j ∈ [r] let
Akj = Ak × {j}, and let
Xk = ∆(A1k) ∗ · · · ∗∆(Ak−1,k) ∗ ∂∆(Akk) ∗∆(Ak+1,k) ∗ · · · ∗∆(Ark) .
Let X =
k=1Xk. Then L(X) = d − 1, and the projection π : X → ∆m−1
satisfies r(X, π) = r. Since π(X) = ∂∆m−1, it follows that L(π(X)) = m−1.
Hence equality is attained in (1).
As mentioned earlier, Theorem 1.2 is motivated by an application in com-
binatorial geometry. The nerve N(F) of a family of sets F , is the simplicial
complex whose vertex set is F and whose simplices are all F ′ ⊂ F such that
F ′ 6= ∅. It is easy to see that
h(F) ≤ 1 + L(N(F)). (2)
A finite family F of compact sets in some topological space is a good cover if
for any F ′ ⊂ F , the intersection
F ′ is either empty or contractible. If F
is a good cover in Rd, then by the Nerve Lemma (see e.g. [2]) L(N(F)) ≤ d,
hence follows the Topological Helly’s Theorem: h(F) ≤ d + 1. Theorem 1.2
implies a similar topological generalization of Amenta’s theorem.
Theorem 1.3. Let F is a good cover in Rd. Then for any (F , r)-family G
h(G) ≤ r(d+ 1) .
The proof of Theorem 1.2 combines a vanishing theorem for the multiple
point sets of a projection, with an application of the image computing spec-
tral sequence due to Goryunov and Mond [5]. In Section 2 we describe the
Goryunov-Mond result. In Section 3 we prove our main result, Proposition
3.1, which is then used to deduce Theorem 1.2. The proof of Theorem 1.3 is
given in Section 4.
2 The Image Computing Spectral Sequence
For X ⊂ V1 ∗ · · · ∗ Vm and k ≥ 1 define the multiple point set Mk by
Mk = {(x1, . . . , xk) ∈ |X|
k : π(x1) = · · · = π(xk)} .
Let W be a Q-vector space with an action of the symmetric group Sk.
Denote Alt = 1
sign(σ)σ ∈ Q[Sk]. Then
AltW = {Altw : w ∈ W} =
{w ∈ W : σw = sign(σ)w for all σ ∈ Sk} . (3)
The natural action of Sk on Mk induces an action on the rational chain
complex C∗(Mk) and on the rational homology H∗(Mk). The idempotence of
Alt implies that
Alt H∗(Mk) ∼= H∗(AltC(Mk)) . (4)
The following result is due to Goryunov and Mond [5] (see also [4] and [6]).
Theorem 2.1 (Goryunov and Mond). Let Y = π(X) and r = r(X, π). Then
there exists a homology spectral sequence {Erp,q} converging to H∗(Y ) with
E1p,q =
AltHq(Mp+1) 0 ≤ p ≤ r − 1, 0 ≤ q
0 otherwise
Remark: The E1 terms in the original formulation of Theorem 2.1 in [5],
are given by E1p,q = AltHq(D
p+1) where
k = closure{(x1, . . . , xk) ∈ |X|
k : π(x1) = · · · = π(xk), xi 6= xj for i 6= j} .
The isomorphism
AltHq(D
p+1) ∼= AltHq(Mp+1)
which implies (5), is proved in Theorem 3.4 in [6]. Indeed, as noted there, the
inclusionDp+1 → Mp+1 induces an isomorphism Alt Cq(D
p+1) ∼= AltCq(Mp+1)
already at the alternating chains level.
3 Homology of the Multiple Point Set
In this section we study the homology of a generalization of the multiple
point set. For subcomplexes X1, . . . , Xk ⊂ V1 ∗ · · · ∗ Vm, let
M(X1, . . . , Xk) = {(x1, . . . , xk) ∈ |X1| × · · · × |Xk| : π(x1) = · · · = π(xk)} .
In particular, if X1 = · · · = Xk = X then M(X1, . . . , Xk) = Mk.
We identify the generalized multiple point set M(X1, . . . , Xk) with the
simplicial complex whose p-dimensional simplices are {wi0 , . . . , wip}, where
1 ≤ i0 < · · · < ip ≤ m, wij = (vij ,1, . . . , vij ,k) ∈ V
and {vi0,r, . . . , vip,r} ∈ Xr
for all 1 ≤ r ≤ k. The main ingredient in the proof of Theorem 1.2 is the
following
Proposition 3.1. H̃j
M(X1, . . . , Xk)
= 0 for j ≥
i=1 L(Xi).
The proof of Proposition 3.1 depends on a spectral sequence argument
given below. We first recall some definitions. Let K be a simplicial complex.
The subdivision sd(K) is the order complex of the set of the non-empty
simplices of K ordered by inclusion. For σ ∈ K let DK(σ) denote the order
complex of the interval [σ, ·] = {τ ∈ K : τ ⊃ σ}. Let
DK(σ) denote the
order complex of the interval (σ, ·] = {τ ∈ K : τ % σ}. Note that
DK(σ) is
isomorphic to sd(lk(K, σ)) via the simplicial map τ → τ − σ. Since DK(σ)
is contractible, it follows that Hi
DK(σ),
DK(σ)
∼= H̃i−1
lk(K, σ)
for all
i ≥ 0.
For σ ∈ V1 ∗ · · · ∗ Vm, let σ̃ =
i∈π(σ) Vi. Note that if σ2 ∈ X2, . . . , σk ∈ Xk
then there is an isomorphism
M(X1, σ2, . . . , σk) ∼= X1[∩
i=2σ̃i] . (6)
For 0 ≤ p ≤ n =
i=2 dimXi let
S ′p = {(σ2, . . . , σk) ∈ X2 × · · · ×Xk :
dim σi ≥ n− p}
and let Sp = S
p − S
p−1. For σ = (σ2, . . . , σk) ∈ S
p let
Aσ = M(X1, σ2, . . . , σk)×DX2(σ2)× · · · ×DXk(σk) ,
Bσ = M(X1, σ2, . . . , σk)×
DX2(σ2)× · · · ×
DXj (σj)× · · · ×DXk(σk)
Proposition 3.2. There exists a homology spectral sequence {Erp,q} converg-
ing to H∗
M(X1, . . . , Xk)
such that
E1p,q =
i1,...,ik≥0
i1+···+ik=p+q
i=2σ̃i]
H̃ij−1
lk(Xj, σj)
for 0 ≤ p ≤ n , 0 ≤ q , and E1p,q = 0 otherwise.
Proof: For 0 ≤ p ≤ n let
σ∈S′p
Aσ ⊂ M(X1, . . . , Xk)× sd(X2)× · · · × sd(Xk).
Write K = Kn, and consider the projection on the first coordinate θ : K →
M(X1, . . . , Xk). Let (x1, . . . , xk) ∈ M(X1, . . . , Xk), and let σi denote the
minimal simplex in Xi that contains xi. Then the fiber
(x1, . . . , xk)
= {(x1, . . . , xk)} ×DX2(σ2)× · · · ×DXk(σk)
is a cone, hence K is homotopy equivalent to M(X1, . . . , Xk). The filtration
∅ ⊂ K0 ⊂ · · · ⊂ Kn = K gives rise to a homology spectral sequence {E
converging to H∗(K) ∼= H∗(M(X1, . . . , Xm)). The E
p,q terms are computed
as follows. First note that
Kp−1 =
Bσ . (8)
Secondly,
Aσ −Bσ
∩ Aσ′ = ∅ for σ 6= σ
′ ∈ Sp. Hence
H∗(Aσ, Bσ) . (9)
Applying excision, (8),(9), and the Künneth formula we obtain:
E1p,q = Hp+q(Kp, Kp−1)
∼= Hp+q
Hp+q(Aσ, Bσ) ∼=
i1,...,ik≥0
i1+···+ik=p+q
M(X1, σ2, . . . , σk)
DXj (σj),
DXj(σj)
i1,...,ik≥0
i1+···+ik=p+q
i=2σ̃i]
H̃ij−1
lk(Xj , σj)
Proof of Proposition 3.1: If L(Xj) = 0 for all 1 ≤ j ≤ k, then all the
Xj’s are simplicies, say Xj = σj . It follows that M(X1, . . . , Xk) is isomorphic
to the simplex
j=1 π(σj) and thus has vanishing reduced homology in all
nonnegative dimensions. Suppose then that m =
j=1 L(Xj) > 0. Without
loss of generality we may assume that L(X1) > 0. Let i1, . . . , ik ≥ 0 such that
j=1 ij ≥ m. Then either i1 ≥ L(X1) and then Hi1
i=2σ̃i]
= 0, or there
exists a 2 ≤ j ≤ k such that ij − 1 ≥ L(Xj) and then H̃ij−1
lk(Xj, σj)
By (7) it follows that E1p,q = 0 if p + q ≥ m, hence H̃j
M(X1, . . . , Xk)
for all j ≥ m.
Remark: If all the Vj’s are singletons then M(X1, . . . , Xk) is isomorphic to
j=1Xj . Hence Proposition 3.1 implies the following result of [7].
Corollary 3.3 ([7]). If X1, . . . , Xk are simplicial complexes on the same
vertex set, then
Xj) ≤
L(Xj) .
Proof of Theorem 1.2: Let Y = π(X) and r = r(X, π). Assuming as we
may that L(X) > 0, we have to show that Hm(Y ) = 0 for m ≥ rL(X)+r−1.
By Theorem 2.1 it suffices to show that Alt Hq(Mp+1) = 0 for all pairs (p, q)
such that p ≤ r − 1 and p + q ≥ rL(X) + r − 1. Indeed, p ≤ r − 1 implies
that q ≥ rL(X) ≥ (p + 1)L(X), thus Hq(Mp+1) = 0 by Proposition 3.1.
4 A Topological Amenta Theorem
Proof of Theorem 1.3: Suppose G = {G1, . . . , Gm} is an (F , r)-family.
Write Gi =
j=1 Fij , where ri ≤ r and Fij
Fij′ = ∅ for 1 ≤ j 6= j
′ ≤ ri.
Let Vi = {Fi1, . . . , Firi} and consider the nerve
X = N({Fij : 1 ≤ i ≤ m, 1 ≤ j ≤ ri}) ⊂ V1 ∗ · · · ∗ Vm .
Let ∆m−1 be the simplex on the vertex set {G1, . . . , Gm} and let π denote
the projection of V1 ∗ · · · ∗Vm into ∆m−1 given by π(Fij) = Gi. Then π(X) =
N(G). Let y ∈ |N(G)| and let σ = {Gi : i ∈ I} be the minimal simplex in
N(G) such that y ∈ |σ|. Then
|π−1(y)| = |{ (ji : i ∈ I) :
Fiji 6= ∅ }| . (10)
On the other hand
(ji:i∈I)
Fiji (11)
and the union on the right is a disjoint union. The assumption that G is an
(F , r) family, together with (10) and (11), imply that |π−1(y)| ≤ r for all
y ∈ |N(G)|. Since F is a good cover in Rd, the Leray number of the nerve
satisfies L(X) = L(N(F)) ≤ d. Therefore by (2) and Theorem 1.2
h(G) ≤ 1 + L(N(G)) = 1 + L(π(X)) ≤
1 + rL(X) + r − 1 ≤ r(d+ 1) .
References
[1] N. Amenta, A short proof of an interesting Helly-type theorem. Discrete
Comput. Geom. 15(1996), 423–427.
[2] A. Björner, Topological methods, in Handbook of Combinatorics (R.
Graham, M. Grötschel, and L. Lovász, Eds.) , 1819–1872, North-
Holland, Amsterdam, 1995.
[3] J. Eckhoff, Helly, Radon and Carathéodory type theorems, in Handbook
of Convex Geometry (P.M. Gruber and J.M. Wills Eds.), North–Holland,
Amsterdam, 1993.
[4] V. Goryunov, Semi-simplicial resolutions and homology of images and
discriminants of mappings. Proc. London Math. Soc. 70(1995), 363–385.
[5] V. Goryunov, D. Mond, Vanishing cohomology of singularities of map-
pings. Compositio Math. 89(1993), 45–80.
[6] K. Houston, An introduction to the image computing spectral sequence.
Singularity theory (Liverpool, 1996), 305–324, London Math. Soc. Lec-
ture Note Ser., 263, Cambridge Univ. Press, Cambridge, 1999.
[7] G. Kalai, R. Meshulam, Intersections of Leray complexes and regu-
larity of monomial ideals, Journal of Combinatorial Theory Ser. A.,
113(2006), 1586–1592.
[8] B. Grünbaum, T. Motzkin, On components in some families of sets,
Proc. Amer. Math. Soc. 12(1961), 607–613.
[9] G. Wegner, d-Collapsing and nerves of families of convex sets, Arch.
Math. (Basel) 26(1975) 317–321.
[10] R. Živaljević, Topological methods, in Handbook of discrete and compu-
tational geometry, (J. Goodman and J. O’Rourke Eds.), 209–224, CRC
Press, Boca Raton, 1997.
