4
Equipartitions of measures in R
Rade T. ~Zivaljevi'c
November 2004
Abstract
A well known problem of B. Gr"unbaum [Gr"u60] asks whether for ev-
ery continuous mass distribution (measure) d~ = f dm on Rn there exist
n hyperplanes dividing Rn into 2n parts of equal measure. It is known
that the answer is positive in dimension n = 3 [Had66 ] and negative
for n 5, [Avis84] [Ram96 ]. We give a partial solution to Gr"unbaum's
problem in the critical dimension n = 4 by proving that each measure ~
in R4 admits an equipartition by 4 hyperplanes, provided that it is sym-
metric with respect to a 2-dimensional affine subspace L of R4. Moreover
we show, by computing the complete obstruction in the relevant group
of normal bordisms, that without the symmetry condition, a naturally
associated topological problem has a negative solution. The computation
is based on the Koschorke's exact singularity sequence [Kosch81] and the
remarkable properties of the essentially unique, balanced binary Gray
code in dimension 4, [Toot56] [Knu01 ].
1 Introduction
A notorious open problem in geometric combinatorics and discrete and compu-
tational geometry is the question whether each continuous mass distribution
~ in R4 admits an equipartition by hyperplanes. This is an "essentially 4-
dimensional" problem by the classification of V. Klee [Klee99], indicating that
the answer is known and positive in all dimensions 3 and negative in di-
mensions 5. Recall that a collection H1, H2, . .,.Hn of hyperplanes in Rn
is an equipartition for a mass distribution (measure) ~ if each of the 2n "or-
thants" associated to {Hj}nj=1contains the fraction 1=2n of the total mass.
In other words, ~(Hffl) = 1=2n~(Rn) for each ffl = (ffl1, . .,.ffln) 2 {0, 1}n,*
* where
Hffl:= Hffl11\ . .\.Hfflnnis the "orthant" associated to ffl and H0i(respective*
*ly
H1i) is the positive (respectively negative) closed halfspace associated to the
hyperplane Hi.
The progress in the general problem was slow after B. Gr"unbaum posed
the question in 1960, [Gr"u60]. H. Hadwiger showed in [Had66 ] that equipar-
titions exist for n = 3. D. Avis showed in [Avis84] that there exist non-
equipartitionable mass distributions for n 5. In the mean-time many related
questions were formulated and many of them solved [BM01 ] [BM02 ] [Mak01 ]
[Ram96 ] [VZ92 ], a connection with discrete and computational geometry was
established [YY85 ] [YDEM89 ] and the subject grew into a separate branch
1
of geometric combinatorics [~Ziv04]. Nevertheless, the 4-equipartition problem
itself has resisted all attempts and remains one of the central open problems
in the field.
In this paper we prove, Theorem 5.1, that a measure ~ in R4 admits a
4-equipartition if it is symmetric with respect to a 2-plane L in R4. Moreover
we demonstrate in Theorem 5.9, by computing the obstruction in the relevant
normal bordism group, that there are no "obvious" topological obstacles for
the existence of non-equipartitionable measures. This result may be an indi-
cation that such a peculiar measure does exist in R4 and it is an intriguing
question whether the "topological counterexample", provided by Theorem 5.9,
can be turned into a genuine counterexample.
2 The CS/TM-scheme
The configuration space/test map scheme [~Ziv04] has emerged as one of the
key principles for the application of topological methods in geometric com-
binatorics and discrete and computational geometry. The basic idea can be
outlined as follows.
One starts with a configuration space or manifold MP of all candidates
for the solution of a geometric/combinatorial problem P. The next step is a
construction of a test map f : MP ! VP which measures how far is a given
candidate configuration C 2 MP from being a solution. More precisely, there
is a subspace Z of the test space VP such that a configuration C 2 MP is
a solution if and only if f(C) 2 Z. The inner symmetries of the problem
P typically show up at this stage. This means that there is a group G of
symmetries of XP which acts on VP , such that Z is a G-invariant subspace
of VP , which turns f : MP ! VP into an equivariant map. If a configuration
C with the desired property f(C) 2 Z does not exist, then there arises an
equivariant map f : MP ! VP \ Z. The final step is to show by topological
methods that such a map does not exist.
The reader can follow the genesis of the method in review papers [Alon88 ]
[Bar93 ] [Bj"or91] [~Ziv96] [~Ziv98] [~Ziv04] and see how the solutions of well*
* known
combinatorial problems like Kneser's conjecture (L. Lov'asz [Lov78 ]), "the
splitting necklace problem" (N. Alon [Alon87 ] ), the Colored Tverberg problem
(R. ~Zivaljevi'c, S. Vre'cica, [~ZV92] [V~Z94]) etc. eventually led to the form*
*ulation
and codification of the general principle.
2.1 The equipartition problem
Our first choice for the configuration space suitable for the equipartition pro*
*b-
lem is the manifold of all ordered collections H = (H1, . .,.Hn) of oriented
hyperplanes in Rn.
Suppose that e : Rn ! Rn+1 is the embedding defined by e(x) = (x, 1).
Each oriented hyperplane H in e(Rn) ~= {x 2 Rn+1 | xn+1 = 1} Rn+1 is
obtained as an intersection H = e(Rn) \ H0 for a unique oriented, (n + 1)-
dimensional subspace H0 Rn+1. The oriented subspace H0 is determined
2
by the corresponding orthogonal unit vector u 2 Sn Rn+1, so the natural
environment for collections H = (H1, . .,.Hn), and our second choice for the
configuration space is MP := (Sn)n. The group which acts on the config-
uration manifold MP is the reflection group Wn := (Z=2)n o Sn where Sn
permutes the factors while the subgroup (Z=2)n is in charge of the antipodal
actions on individual spheres. The action of Wn on MP := (Sn)n is not free,
so our third choice for the configuration space associated to the equipartition
problem is
MffiP= (Sn)nffi:= {x 2 (Sn)n | xi6= xj fori 6= j}. (1)
This space is a relative of the (standard) "configuration space" Fm (Sn) :=
{x 2 (Sn)m | xi6= xj fori 6= j} [FaHu01 ]. It has already appeared in Combi-
natorics, for example in [FeZi02], where it is referred to as the "signed confi*
*g-
uration space".
The associated "orbit configuration space" (Sn)nffi=Wn can be identified as*
* a
submanifold of the symmetric product SP n(RP n) of the projective space RP n.
This is the reason why we occasionally denote this quotient by SPffi(RP n) and
view its elements as unordered collections of n distinct lines in Rn+1.
The test space V = VP is defined as follows. If ~ is a measure defined on
Rn, let ~0 be the "push-down" measure induced on Rn+1 by the embedding
e : Rn ,! Rn+1, ~0(A) := ~(e(Rn) \ A). A n-tuple (u1, . .,.un) 2 (Sn)n of unit
vectors determines a n-tuple H = (H01, . .,.H0n) of oriented (n+1)-dimensional
subspaces of Rn+1. The n-tuple H dissects Rn+1 into 2n-orthants Ortfi(H)
which are naturally indexed by 0-1 vectors fi 2 {0, 1}n. Let bfi: MP ! R be
the function defined by bfi(H) := ~0(Ortfi(H)) = ~(Ortfi(H)\e(Rn)). Let B~ :
(Sn)n ! R2n be the function defined by B~(H) = (bfi(H))fi2{0,1}n. The test
space V = VP ~=R2n has a natural action of the group Wn := (Z=2)noSn such
that the map B~ is Wn-equivariant. Note that the real Wn-representation V ,
restricted to the subgroup (Z=2)n ,! Wn, reduces to the regular representation
Reg ((Z=2)n) of the group (Z=2)n. The "zero" subspace ZP is defined as the
trivial, 1-dimensional Wn-representation V0 contained in V . Let U = Un be
the complementary Wn-representation, Un ~= V=V0 and A~ : (Sn)n ! Un
the induced, Wn-equivariant map. By the construction we have the following
proposition which says that A~ is a genuine test map for the ~-equipartition
problem.
Proposition 2.1. A n-tuple H = (H1, . .,.Hn) 2 MP = (Sn)n of oriented
hyperplanes in Rn is an equipartition of a measure ~ defined on Rn if and
only if A~(H) = 0.
Corollary 2.2. If there does not exist a Wn-equivariant map A : MP ! Un \
{0}, then each positive, continuous mass distribution (measure) d~ = f dm,
where dm is the Lebesgue measure, admits an equipartition by n hyperplanes.
Remark 2.3. The assumption that ~ is a measure absolutely continuous to
the Lebesgue measure on Rn is unnecessary restrictive. All we need is the
continuity of the test map A~ : (Sn)n ! Un, a condition satisfied by a very
3
large class of measures having the desired continuity properties. Notable ex-
amples of interesting measures that are not in this class are counting measures
D of finite sets D Rn defined by D (X) := |D \ X|. Note however, that
all equipartition results can be suitably extended to weak limits of continuous
measures, cf. [MVZ ] for a general set up. An example of such a result applying
to counting measures is Corollary 5.2 from Section 5.1.
2.2 Singular sets ~
It is a well known fact that for a free G-space P and a G-representation V ,
there does not exist a G-equivariant map f : P ! V \ {0} if and only if the
associated vector bundle V ! P xG V ! P=G does not admit a non-zero,
continuous cross-section, cf. Proposition I.7.2 in [Dieck87].
A well known approach to the last question, applicable in the case when P
is a free G-manifold, is the singularity approach, cf. [Kosch81 ]. Given a G-map
h : P ! V , the singularity set (h) of h is the, possibly empty, G-subspace of
P defined by (h) := h-1(0). In the case when h is transverse to 0 2 V , the
singularity set (h) is a G-manifold.
If h = A~ is the test map of a measure ~, then the associated singularity
set ~ := (A~) is simply the set of all solutions to the equipartition problem
for ~. In this case ~ is often referred to as the solution set (manifold) of ~.
The singularity manifold (h) of a map h, sometimes accompanied by the
additional information recording the behavior of h in the tubular neighbor-
hood of (h) (the normal data), can be used for computation of an associated
obstruction element in a suitable group of bordisms. The singularity mani-
fold and the associated normal data together yield a very strong obstruction
invariant which is in a number of important cases complete in the sense that
an equivariant map exists if and only if these obstruction vanish. The reader
is referred to [Kosch81 ] for the general theory.
2.3 Equipartitions of planar measures
The case n = 2 of the equipartition problem is well known and elementary.
Nevertheless, we briefly review this case since it serves as a fairly good illu*
*s-
tration of general ideas in their rudimentary form. According to the CS/TM-
scheme, as presented in Section 2.1, the problem is to prove that there does
not exist a W2-equivariant map f : MP ! U2 \ {0}, where W2 = D8 is the
dihedral group, MP = S2 x S2, and U2 the 3-dimensional real representation
of W2, described in Section 2.1.
One can establish a slightly stronger statement that there does not exist a
W2-equivariant map f : MffiP! U2\{0} where MffiP= (S2)2ffi= S2xS2\{(x, y) |
x = y or x = -y}. The advantage of (S2)2ffiover (S2)2 is that the former is a
free W2-space.
Let us see how the singularity approach works in the case of planar equipar-
titions. For a generic measurable set A R2, the singularity A of A, that
is the collection of all pairs (L1, L2) of oriented lines in R2 which form an
equipartition for A, is a 1-dimensional W2-manifold. For example if A is a
4
unit disc D, the singularity D is a union of 4 circles. Here we do not make
precise what is meant by a generic measure. Instead we naively assume, for
the sake of this example, that there exists such a notion of genericity for mea-
surable sets/measures so that each measurable set A can be well approximated
by generic measures. Moreover, we assume that for any two measurable sets
A and B there exists a path of generic measures ~t, t 2 [0, 1], so that ~0 is an
approximation of A, ~1 is an approximation for B and the solution set
{~t}t2[0,1]:= {(L1, L2; t) | (L1, L2) is an equipartition for~t} (S2)2ffix [*
*0, 1]
is a 2-dimensional manifold (bordism) connecting solution sets for measures
~0 and ~1. The group 1(D8) of classes of 1-dimensional, free D8-manifolds
is isomorphic to Z=2 Z=2 and the D8-solution manifold D , associated to
the unit disc in R2, is easily shown to represent a nontrivial element in this
group. It immediately follows that for any measurable set A R2, or more
Figure 1: An equipartition in the plane.
generally for any continuous mass distribution, the singularity A is nonempty.
Indeed, suppose A = ;. Let {~t}t2[0,1]be a path of generic measures such
that ~0 approximates A and ~1 approximates D. If these approximations are
sufficiently good, we deduce that the solution set ~0 is empty and that [ ~1]
and [ D ] represent the same element in 1(D8). This is a contradiction since
~1 = @( ) where = {~t}t2[0,1], i.e. D would represent a trivial element
in 1(D8).
Remark 2.4. It is worth noting that the scheme outlined above, if applicable,
shows that a general equipartition problem can be solved by a careful analysis
of the singularity set of a well chosen, particular measure/measurable set, the
unit disc D2 in our example above. Unfortunately, in higher dimensions the
unit balls do not represent generic measures, i.e. their solution manifolds are
very special and cannot be used for the evaluation of the relevant obstruction
elements. Instead, for this purpose one can use measures distributed along a
convex curve in Rn, Section 3.
5
3 From convex curves to Gray codes
3.1 Convex curves
A simple, smooth curve in Rn is called convex if the total multiplicity of its
intersection with an affine hyperplane does not exceed n. Convex curves are
classical objects appearing in many different fields including the real algebra*
*ic
geometry ("ecstatic points" of curves), theory of convex polytopes (neighborly
polytopes), interpolations of functions (Tschebycheff systems), linear ordi-
nary differential equations (disconjugate equations) etc., see [Anis98] [Arn96 ]
[Copp71 ] [Scho54 ] [SeSh96 ] and the references in these papers. Standard ex-
amples of convex curves are the "moment curve", or the rational normal curve
Mn := {(t, t2, . .,.tn) | t 2 R} Rn and the standard trigonometric curve
2n := {(cost, sint, cos2t, . .,.cosnt, sinnt) | t 2 [0, 2ss]} R2n.
The importance of convex curves for the equipartition problem stems from
the fact that they minimize the number of intersections with hyperplanes. As
a consequence, each collection H = {H1, . .,.Hn} of n hyperplanes in Rn has
at most n2 intersection points with . It follows that if n = 2d is even, and
is a simple, closed convex curve, then H divides in at most n2 arcs. Suppose
that ~ is a measure concentrated on a closed, convex curve R2d. Then if
H is an equipartition for ~ then n2 2n, i.e. n 4. This explains why the
dimension 4 is so special in this context.
3.2 Gray codes
Gray codes arise in an attempt to describe the solution manifold (singularity
set) ~ of a measure ~ distributed along a closed convex curve R4. Our
preferred example of such a curve is 4 = {(z, z2) | |z| = 1} C2 ~= R4.
From here on we assume that d~0 = d`0, `0 = arg(z), is the "arc length"
measure on the circle C = {z 2 C | |z| = 1} and d~ = d` the associated
measure on 4, where ` = `0O ss1 and ss1 : C2 ! C is the first projection.
Similar analysis can be carried on for other measures concentrated on 4.
Each collection P = {p1, p2, p3, p4} of 4 points in 4 is contained in a unique
hyperplane H R4, hence the combinatorics of ~-equipartitions can be read
off from the circle C, see Figures 2, 3 and 4. As a consequence, an equipartiti*
*on
H = {H1, H2, H3, H3} of the measure d` is essentially a division of the circle
C into 16 arcs of equal length and associating each of the 16 division points
{xj}15j=0, where xj = fflj x0 and ffl = exp2ssi=16, to one of hyperplanes Hi. N*
*ote
that not all maps ff : {xj}15j=0! H are allowed, cf. [Ram96 ] p. 157. Each of
the arcs [xj, xj+1] belongs to an orthant coded by an associated 4-bit word
fij 2 {0, 1}4. Each of the 4-bit words fi 2 {0, 1}4 appears exactly once in the
cyclic order inherited from the order of intervals [xj, xj+1]. Moreover, moving
from one orthant to another along the curve 4, that is from the interval
[xj, xj+1] to the consecutive interval [xj+1, xj+2], changes only one bit at a
time. It follows that sequence {fij}15j=0of 4-bit words forms a so called Gray
code, [Knu01 ] [Ram96 ]. For a graph theorist, a Gray code is a Hamiltonian
path on a hypercube {0, 1}n. For an engineer, a Gray code is a device useful
6
for converting digital signals into analog and vice versa, [Knu01 ].
Figure 2: The unique, balanced 4-bit Gray code.
Our next observation is that Gray codes arising in the equipartitions of
the convex curve 4 are quite special. Indeed, each hyperplane Hi intersects
the convex curve 4 precisely 4 times implying that the code must have the
same number of bit changes in each of four coordinate tracks. Such codes are
called balanced, Figure 2. A Gray code with these properties was originally
discovered by G.C. Tootill [Toot56 ]. One of its remarkable properties is that
it is unique up to permutation of coordinate tracks, see [Gil58] or [Knu01 ],
Exercise 56. In particular if one reads the code clockwise the same code is
obtained, except that the second and the third track interchange places, see
Figures 2-4.
There is one more attractive way to describe this code. As a variation on
the theme of the play "Quad" by S. Beckett [Quad ] where "... Four actors,
whose colored hoods make them identifiable yet anonymous, accomplish a re-
lentless closed-circuit drama ..." (R. Frieling), one can design a scheme for a
play based on the balanced Gray code. In this scheme the stage begins and
ends empty; 4 actors enter and exit one at a time, running through all 16 pos-
sible subsets, and each actor is supposed to enter (leave) the stage precisely 2
times, see [Knu01 ] Exercise 65 (attributed to B. Stevens) for a similar idea.
3.3 The solution set `
The analysis from Sections 3.1 and 3.2 allows us to describe the solution man-
ifold (singular set) ` of the measure ` on the convex curve 4, arising from
the "arc length" measure on the unit circle C C, Section 3.2. This solution
set is a W4-invariant subset of the configuration space MffiP= (S4)4ffi.
Suppose that H = {H1, H2, H3, H4} 2 `. Each hyperplane Hj intersects
the curve 4 in four points, vertices of a 3-simplex oej Hj. The image ss1(oe*
*j)
of oej by the projection map ss1 : C2 ! C, sending the curve 4 to the circle C,
Section 3.2, is a convex polygon in the plane. Figure 3 displays these polygons
7
in the order corresponding to the chosen order of hyperplanes in H.
Figure 3: An element of `...
By taking into account the (chosen) orientation of hyperplanes Hj and the
induced orientations of simplices oej Hj, we arrive at the conclusion that Fi*
*g-
ure 3 is a fairly accurate description of an element H = {H1, H2, H3, H4} 2 `.
This element belongs to an oriented circle ` of all solutions, obtained
essentially by rotating Figure 3 counterclockwise. All other circles in ` are
obtained by the action of the group W4, in other words by changing the orien-
tations of simplices oej, performed by the subgroup (Z=2)4, and by permuting
the circumcircles of polygons in Figure 3. In other words the permutation of
polygons is achieved by permuting the circles, the tracks in the balanced Gray
code.
For example if we move Figure 3 clockwise, we obtain the circle ,( ) `
where , : [4] ! [4] is the permutation which keeps tracks 1 and 4 fixed and
interchanges tracks 2 and 3. We see this as a manifestation of the symmetry
of diagrams in Figures 3 and 4 with respect to the vertical axes.
Let us turn to the question of non-degeneracy of the solution manifold `.
This is by definition the condition that the associated test map A` : (S4)4ffi!
U4 is transverse to 0 2 U4. Suppose that H 2 ` and assume that {xj}15j=0
are the associated division points, Section 3.2. Then for a small positive real
number ffl > 0, the angles yj 2 (xj-ffl, xj+ffl) can be used as the coordinates*
* on
(S4)4ffiin the neighborhood of H 2 (S4)4ffi. The associated tangent vectors are
@=@yj 2 TH ((S4)4ffi). Similarly, the functions bfiintroduced in Section 2.1 are
coordinates on V , consequently the functions cj := bfij+1- bfij, where {fij}15*
*j=0
is the sequence defined in Section 3.2, are coordinates on U4. The proof is
completed by the observation that dA`(@=@yj) = -@=@cj.
For the future reference we record an essential part of this analysis in the
following proposition.
Proposition 3.1. The solution manifold ` MffiP= (S4)4ffiof all equipar-
titions for the measure d` on the convex curve 4 is a (non-degenerated)
1-dimensional W4-manifold which has |W4| = 244! connected components.
The quotient manifold 0 := `=W4 is a circle in the manifold (S4)4ffi=W4 ~=
8
SPf4fi(RP 4) SP 4(RP 4), where SP m(X) := Xm =Sm is the symmetric product
of X and SPfmfi(X) its subspace of "square-free" divisors.
Figure 4: ... and the associated element in `=W4.
Remark 3.2. Figure 4 (B) symbolically represents an element of the circle
0 = `=W4. The orientations of polygons are forgotten and all 4 circles,
representing different tracks in the balanced Gray code visible in Figure 4
(A), "merged together" in Figure 4 (B).
4 From Gray codes to normal bordisms
According to Corollary 2.2, the 4-equipartition problem is closely related to
the question if there exists a W4-equivariant map f : (S4)4ffi! U4 \ {0}. In
turn, this is equivalent to the question if the vector bundle
E : U4 ! (S4)4ffixW4 U0 ! (S4)4ffi=W4 (2)
admits a non-zero, continuous cross-section. A complete topological obstruc-
tion ! for the existence of such a section lives in the normal bordism group
1(M; E - T M) [Kosch81 ], where T M is the tangent bundle of the manifold
M := (S4)4ffi=W4 and E is the bundle (2). This group can be computed from
the Koschorke's exact singularity sequence, [Kosch81 ] Theorem 9.3. The com-
putation of the obstruction ! 2 1(M; E - T M) is based on this sequence and
the analysis of the singularity ` of the measure ` distributed along a closed,
convex curve 4 R4, Section 3.
4.1 Koschorke's exact singularity sequence
One of the consequences of Koschorke's exact singularity sequence [Kosch81 ,
Section 7], is a short exact singularity sequence, [Kosch81 ] Theorem 9.3., in-
volving low dimensional normal bordism groups j(X; OE) and e j(X; OE) for
j 4, where OE = OE+ - OE- is a virtual vector bundle over X. The final
fragment of this sequence has the following form,
-ffi2! f2 e oeOj2 ffi1 f1 e
2(X; OE) -! 2(X; OE) -! Z=2 -! 1(X; OE) -! 1(X; OE) -!(0.3)
9
We are interested in this sequence in the case when X = M = (S4)4ffi=W4 and
OE = OE+ - OE- = E - T M. More precisely, our objective is to evaluate the
obstruction element ! 2 1(M; E - T M) defined in Section 4.
4.2 The image of ffi1
According to [Kosch81 ], the image ffi1(1) of the generator 1 2 Z=2 "... can
be represented by the unit circle with constant map and the standard par-
allelization, suitably stabilized ...". In this section we show that the image
ffi1(1) coincides with the obstruction element ! 2 1(M; E - T M). This is a
consequence of the following proposition.
Proposition 4.1. f1(!) = 0.
Proof: The configuration space (S4)4ffiis simply connected, hence the pro-
jection (S4)4ffi! (S4)4ffi=W4 is a universal covering map. Let be a circle,
connected component of the solution manifold `, and let 0 := `=W4
(S4)4ffi=W4. Suppose that , is the orientation line bundle of the virtual bundle
E - T M. Then, by definition of e 1(X; OE), [Kosch81 ] x 9, the image f1(!) of
! in e 1(X; E - T M) is determined by 0and the restriction ,| 0of , on 0.
Since the circle 0 can be lifted to the circle , we conclude that 0 is
contractible, hence ,| 0is a trivial bundle. It follows that there exists a map
g : D2 ! M such that @(D2) is mapped bijectively to 0and extension of the
bundle g*(,| 0) to trivial bundle over D2. Hence, f1(!) is a trivial element in
e1(X; E - T M).
4.3 The image of oe O j2
In this section we focus on the calculation of the image of the map e 2(X, OE) *
*oeOj2-!
Z=2 in the Koschorke's singularity exact sequence (3). By definition, an ele-
ment ff = [N, g, or] 2 e 2(X, OE) is mapped to oe O ffi2(ff) := g*(w2(OE))[N], *
*where
w2(OE) is the second Stiefel-Whitney class of the virtual bundle OE = OE+ - OE-
and [N] 2 H2(N, Z=2) is the fundamental class of the surface N. From here
we conclude that elements ff = [N, g, or] such that both g*(OE+ ) and g*(OE- ) *
*are
trivial vector bundles can be ignored, in particular we ignore those elements
where g is homotopic to a constant map. Recall the exact sequence
-! N2 -! N2(X) -! H2(X, Z=2) -! 0 (4)
where N2(X) is the group of unoriented bordisms and N2 := N2(*). It fol-
lows that in the evaluation of the image of oe O ffi2 we are allowed to pick a
representative ff = [N, g, or] in each of the homology classes x 2 H2(X, Z=2).
The following standard lemma reduces the calculation of w2(OE)[N] to the
calculations of Stiefel numbers of individual bundles OE+ and OE- .
Lemma 4.2.
w(OE) = w(OE+ ) . w(OE- )-1
= (1 + w1(OE+ ) + w2(OE+ ) + . .).(1 + w1(OE- ) + w2(OE- ) + w1(OE- )*
*2 + . .).
= 1 + A1 + A2 + . .,.where
10
A1 = w1(OE+ )+w1(OE- ) and A2 = w2(OE+ )+w1(OE+ )w1(OE- )+w1(OE- )2+w2(OE- )
are terms of graduation 1 and 2 respectively. Consequently if OE = OE+ - OE- is
a virtual vector bundle over a surface N, then
w2(OE)[N] = w2(OE+ )[N] + (w1(OE+ )w1(OE- ))[N] + w1(OE- )2[N] + w2(OE- )[N].
In our case X = SPf4fi(RP 4). The following lemma, an easy consequence
of Poincar'e duality, allows us to search for surfaces N representing nontrivial
homology 2-classes in the symmetric product SP 4(RP 4).
Lemma 4.3. There is an isomorphism H2(SPf4fi(RP 4)) -! H2(SP 4(RP 4))
of homology groups, induced by the inclusion map SPf4fi(RP 4) ,! SP 4(RP 4).
It is easy to see that H2(SP 4(RP 4)) ~= H2(SP 1(RP 4)). By the Dold-
Thom theorem, [Ha02 ]
SP 1(RP 4) ' K(Z=2, 1) x K(Z=2, 2) x K(Z=2, 3) x K(Z=2, 4).
From here we deduce that H2(SP 4(RP 4)) ~=Z=2 Z=2.
It is not difficult to describe surfaces N1 and N2, embedded in SPf4fi(RP 4)
SP 4(RP 4), representing the generators of this homology group. Suppose that
e1 and e01are two disjoint circles embedded in RP 4, both representing the
nontrivial element in H1(RP 4; Z=2). Let e2 ~= RP 2be a projective plane
embedded in RP 4, representing the generator of H2(RP 4; Z=2) ~=Z=2. Finally
suppose that *1, *2, *3 are three distinct points in RP 4such that *i2=e1[e01[e2
for each i = 1, 2, 3. As usual, elements of the symmetric product SP m(X) are
thought of as positive "divisors", i.e. commutativePand associative formal sums
D = n1x1+ . .+.nkxk where ni2 N, xi2 X and ki=1= m. By definition let
N1 := *1 + *2 + e1 + e01 and N2 := *1 + *2 + *3 + e2. (5)
In other words N1 ~=S1 x S1 is a torus embedded in SPf4fi(RP 4) where D 2
N1 , D = *1 + *2 + x + y for some x 2 e1 and y 2 e01. Similarly, N2 ~=RP 2
consists of all divisors of the form D = *1 + *2 + *3 + x for some x 2 e2.
In our case OE+ = E and OE- = T (SPf4fi(RP 4)). We focus our attention
on the bundles OE+i := OE+ |Ni and OE-i := OE- |Ni for i = 1, 2. Recall that
E ~= (S4)4ffixW4 U where U = U4 is the 15-dimensional representation of W4
described in Section 2.1. If ss : (S4)4ffi-! SPf4fi(RP 4) is the projection map
then Zi:= ss-1(Ni) is a free, W4-submanifold of (S4)4ffiand OE+i~=ZixW4 U. It
is not difficult to describe these manifolds.
The connected component of Z1 is a torus T 2= S1 x S1 (S4)4ffiand the
stabilizer of T 2is the group H1 = Z=2 Z=2 (Z=2)4 W4 = (Z=2)4 o S4
where H1 = Z=2 Z=2 acts on T 2= S1 x S1 by the product action. It follows
that Z1 ~=T 2xH1 W4 and
OE+1~=Z1 xW4 U ~=(T 2xH1 W4) xW4 U ~=T 2xH1 U.
11
Similarly, the connected component of Z2 is the sphere S2 (S4)4ffiand its
stabilizer is the group H2 = Z=2 (Z=2)4 W4 where H2 acts on S2 by the
antipodal action. It follows that Z2 ~=S2 xH2 W4 and
OE+2~=Z2 xW4 U ~=(S2 xH2 W4) xW4 U ~=S2 xH2 U.
Keeping in mind that the restriction ResW4Z(4U) is the regular (real) repre-
sentation of Z 4, minus the trivial 1-dimensional representation, it is easy to
identify the bundles OE+1 = T 2xH1 U and OE+2 = S2 xH2 U. As a prelimi-
nary step, let us describe some canonical line bundles over N1 ~= T 2=H1 ~=
S1=Z=2 x S1=Z=2 ~=T 2and N2 ~=S2=H2 ~=RP 2.
There are 4 real, 1-dimensional representations of H1 = Z=2 Z=2. If !1
and !2 are the generators of H1, then Lffl1ffl2, ffl1, ffl2 2 {-1, +1}, is the *
*repre-
sentation characterized by the condition !i(v) = ffliv for each v 2 Lffl1ffl2. *
*Let
~~ffl1~ffl2:= T 2xH1 Lffl1ffl2be the associated line bundle where ~ffli2 {0, 1}*
* and
(-1)~ffli= ffli. For example ~00 is the trivial bundle, usually denoted by ffl,*
* while
~11is the Cartesian product of 2 canonical bundles over RP 1~=S1. Let fl = fln
be the canonical line bundle over RP n. The decompositions of bundles OE+1and
OE+2into line bundles is recorded in the following statement.
Proposition 4.4.
OE+1= T 2xH1 U ~=ffl 3 ~041 ~140 ~141
OE+2= S2 xH2 U ~=ffl 7 fl 8 .
The next step is the identification of the restrictions OE-1:= T M|N1 and
OE-2:= T M|N2 of the tangent bundle T M = T (SPf4fi(RP 4)) on the surfaces N1
and N2 respectively.
Lemma 4.5. For each point D = p1 + p2 + p3 + p4 2 SPf4fi(RP 4) there is an
isomorphism
TD (SPf4fi(RP 4)) ~= 4i=1Tpi(RP 4).
Lemma 4.6. ([MS74 ]) Let fln be the canonical line bundle over the real pro-
jective space RP nand ffl the trivial line bundle. Then there is an equality of
virtual vector bundles T (RP n) = fln(n+1) - ffl. As a consequence, the total
Stiefel-Whitney class of the restriction bundle , = T (RP n)|RPm is
` ' ` ' ` '
n + 1 n + 1 2 n + 1 m
w(,) = (1 + t)n+1 = 1 + t + t + . .+. t .
1 2 m
Proposition 4.7.
OE-1 = T M|N1 ~= ffl 6 ~051 ~150
OE-2 = T M|N2 ~= ffl 11 fl 5 .
Proof: By Lemmas 4.5 and 4.6, there is an equality of virtual bundles
T M|N1 = ffl 8 + (T (RP 4)|e1 x T (RP=4)|e01)ffl 8 + (fl45|e1- ffl) x (fl45*
*|e01- ffl)
= ffl 8 + ~051+ ~150- ffl 2 = ffl 6 + ~051+ ~150.
12
Similarly,
T M|N2 ~=ffl 12 + T (RP 4)|e2 = ffl 12 + (fl45 |e2) - ffl) = ffl 11 + fl *
*5 .
Corollary 4.8.
OE+1- OE-1= ~141- ~01- ~10- ffl 3
OE+2- OE-2= fl 3 - ffl 4.
Proposition 4.9. Im (oe O j2) = Z=2.
Proof: It is a basic fact that H*(RP 2; Z=2) ~=(Z=2)[t]=(t3) and H*(T 2; Z=2) ~=
[a, b], where [a, b] is a (Z=2)-exterior algebra generated by two elements of
degree 1. The first two characteristic classes of line bundles ~~ffl1~ffl2and f*
*l, defined
over N1 = T 2and N2 = RP 2respectively, are
w1(~~ffl1~ffl2) = ~ffl1a + ~ffl2b, w1(fl) = t, w2(~~ffl1~ffl2)(=6w2*
*(fl))= 0.
From here we deduce that the total Stiefel-Whitney classes of bundles OE+1and
OE-1are respectively w(~141) = 1 and w(~01 + ~10) = 1 + a + b + ab. This,
together with the Lemma 4.2 and the first equality from Corollary 4.8, implies
that
w2(OE+1- OE-1) = w1(~01+ ~10)2 + w2(~01+ ~10) = ab. (7)
Similarly,
w2(OE+2- OE-2) = w2(fl 3 ) = t2. (8)
In other words
w2(OE+1- OE-1)[N1] = w2(OE+2- OE-2)[N2] = 1 (9)
and we finally conclude that Im(oe O j2) = Z=2.
5 Results and proofs
5.1 Measures admitting a 2-plane of symmetry
In this section we show that each measure with a 2-dimensional plane of sym-
metry admits a 4-equipartition.
Theorem 5.1. Suppose that ~ is a measure on R4 admitting a 2-dimensional
plane of symmetry in the sense that for some 2-plane L R4 and the as-
sociated reflection RL : R4 ! R4, for each measurable set A R4, ~(A) =
~(RL(A)). Then ~ admits a 4-equipartition.
Proof: Without loss of generality we assume that L = C(2)in the decompo-
sition R4 ~=C2 ~=C(1) C(2). In that case the reflection R = RL is the map
described by R(z1, z2) = (-z1, z2), in particular R is a symmetry of the convex
curve (Section 3) 4 = {(z, z2) 2 C2 | |x| = 1}.
13
In pursuit of an equipartition of a general measure in R4, we introduced
in Section 2.1 the configuration space (S4)4ffi= {v 2 S4 | vi 6= vj fori 6= j}.
Recall that the group W4 = (Z=2)4o S4 acts freely on this configuration space
and that the problem of 4-equipartitions was reduced, Corollary 2.2, to the
question of the existence of a W4-equivariant map f : (S4)4ffi! U4\ {0}, where
U4 is the 15-dimensional, real representation of W4 defined in Section 2.1.
If the measure ~ admits an additional symmetry, e.g. if it admits a plane
of symmetry L such that the associated reflection RL keeps ~ invariant, it is
natural to enlarge the group W4 by this transformation.
Assume as before that R4 is identified to the affine subspace R4+ e5 R5.
The isometry RL : R4 ! R4 is extended to the unique isometry bRLof R5 such
that bRL(e5) = e5.
Let Z=2 be the group generated by RbL. Define the enlarged group of
symmetries as the direct product G := W4 x Z=2. The action of W4 on
(S4)4ffican be extended to the action of the group G by the requirement that
RbL(v1, v2, v3, v4) = (RbL(v1), bRL(v2), bRL(v3), bRL(v4)). In order to make t*
*his
action free, let us introduce an even smaller configuration space
(S4)4 := (S4)4ffi\ F (10)
where F (S4)4 is the subset of points v = (v1, v2, v3, v4) such that the
stabilizer StabG(v) is a non-trivial group.
Note that bRL is the reflection with respect to the 3-plane L + Re5 R5.
Consequently, v 2 (S4)4ffiis in F if (up to a permutation of coordinates vi)
either,
(RbL(v1) = v2, bRL(v3) = v4) or (RbL(v1) = v1, bRL(v2) = v2, bRL(v3) = v4).
Key observation: The solution manifold ` (S4)4ffiof all 4-equipartitions
of the convex curve 4, defined in Section 3.3, is RbL-invariant. Moreover
` (S4)4 , or in other words the Z=2-action on ` induced by bRL is free.
Indeed, bRLacts on the element displayed in Figure 3 by the rotation through
the angle of 180O.
Denote by ~ both the non-trivial, 1-dimensional real representation of Z=2
and the associated, 1-dimensional G-representation induced by the projection
homomorphism G ! Z=2. Similarly, U4 is both the 15-dimensional real W4-
representation defined in Section 2.1 and the representation induced by the
projection homomorphism G ! W4.
According to results of Section 2.1, for the proof of the theorem it is suf-
ficient to show that a W4-equivariant map f : (S4)4ffi! U4 must have a zero.
This is a consequence of the following stronger result.
Claim: There does not exist a G-equivariant map f : (S4)4 ! S(U4 ~),
where S(U4 ~) is the G-invariant unit sphere in U4 ~. In other words each
G-invariant map f : (S4)4 ! U4 ~ has a zero.
Proof of the Claim: The claim is equivalent to the statement that the vector
bundle , : (S4)4 xG (U4 ~) ! (S4)4 =G does not admit a non-zero continuous
14
cross-section. For this it is sufficient to show that the top Stiefel-Whitney
class wn(,) is non-zero. By duality this is equivalent to the fact that for some
(each) smooth cross-section s : (S4)4 =G ! (S4)4 xG (U4 ~), transverse to
the zero section Z, the number of elements in s-1(Z) (S4)4 =G is odd. In
the language of equivariant maps, this is equivalent to the statement that for
some smooth, G-equivariant map s = (OE, _) : (S4)4 ! U4 ~, transverse to
0 2 E ~, the number of G-orbits in s-1(0) is odd.
Define OE : (S4)4 ! U4 as the restriction of the test map A` : (S4)4ffi! U4
introduced in Section 2.1, where d` is the "arc length"-measure on 4 =
{(z, z2) 2 C2 | |z| = 1} introduced in Section 3.2.
Since A` is W4-equivariant and A` O bRL= A`, we conclude that OE is G-
equivariant. The orbit space SP 4(RP 4) := (S4)4 =W4 is a smooth manifold.
Note, Section 3, that the unique balanced Gray code allowed us to identify
the "solution manifold" of all equipartitions of the curve 4 R4 as the circle
0 SP 4(RP 4). Moreover, this solution manifold was shown to be non-
degenerated, Proposition 3.1, in the sense that the associated test map A` is
transverse to 0 2 U4.
The Z=2-action on SP 4(RP 4), induced by the involution bRL, is free. Let
_0: SP 4(RP 4) ! ~ be a Z=2-equivariant, smooth map such that 0 2 ~ is not
a critical value of the restriction _00:= _0| 0of _0on the circle 0. Define _ *
*as
the composition of _0 with the natural projection map (S4)4 ! SP 4(RP 4).
Then it is not difficult to check that s = (OE, _) is a smooth, G-equivaria*
*nt
map such that 0 2 ~ is not one of its critical values.
Let us show that the number of G-orbits in the set s-1(0) is always an
odd number. Note that s-1(0) = OE-1(0) \ Z(_) where Z(_) := _-1(0) is
the zero set of _. Since OE-1(0)=G = OE-1(0)=W4 = 0, we observe that the
number of G-orbits in the set s-1(0) is equal to the number of Z=2-orbits in
the zero set Z(_00) of the Z=2-equivariant map _00: 0! ~. Since 0 is not a
critical value of _00, the proof is completed by an elementary observation that
a Z=2-equivariant map p : S1 ! ~, transverse to 0 2 ~, must have an odd
number of Z=2-orbits.
Corollary 5.2. Suppose that D is a finite set of 16d distinct points in R4
which is symmetric with respect to a 2-plane L R4. Then there exists a
collection H = {H1, H2, H3, H4} of distinct hyperplanes such that each of 16
associated open orthants contains not more than d points from the set D.
Moreover, if D is in general position in the sense that no 5 points belong to
the same hyperplane, than each of the open orthants contains at least d - 16
elements from D. In particular, if D is a not necessarily symmetric set of 16d
distinct points in R4, then for some collection H of hyperplanes each of the
associated open orthants contains not more than 2d points from D.
Remark 5.3. Note that the proof of Theorem 5.1 is based on the "acci-
dent" that the convex curve 4 and the associated solution manifold 0 are
Z=2-spaces, where Z=2 is the group generated by the reflection RL. As a
consequence 0 determines a nontrivial element in the group (Z=2) of Z=2-
bordisms [CoFl64 ] which means that one should be able to repeat the pattern
15
of the proof of the equipartition theorem in the planar case, Section 2.3. Our
proof essentially follows this idea. For example the definition of _0corresponds
to the choice of a non-trivial Z=2-equivariant, line bundle on the circle 0, a
step used in the proof that 0defines a non-trivial element in (Z=2).
5.2 Measures admitting a center or a 3-plane of symmetry
For completeness we include proofs of 4-equipartition results for measures
in R4 which admit a center or a 3-plane of symmetry, Proposition 5.6 and
Proposition 5.8. These results formally resemble Theorem 5.1 but there are
important differences. Both Propositions 5.6 and 5.8 are easily deduced from
Hadwiger's result about 3-equipartitions of measures in R3, Theorem 5.4. Con-
trary to this, the proof of Theorem 5.1 relies on the existence of a unique,
ballanced, 4-bit binary Gray code, so this result appears to be an essential
4-dimensional phenomenon.
Theorem 5.4. ([Had66 ]) Each continuous mass distribution ~ in R3 admits a
3-equipartition, that is a collection H1, H2, H3 of three planes in R3 dissecti*
*ng
the ambient space into eight octants of equal measure. Moreover, the first of
these planes can be chosen to contain arbitrary two points A, B 2 R3 prescribed
in advance.
Remark 5.5. Hadwiger [Had66 ] deduced Theorem 5.4 from the result that
any two measures in R3 admit a simultaneous equipartition by 2 hyperplanes.
Both results of Hadwiger can be proved, along the lines of the CS/TM-scheme,
by an analysis of the set of all equipartitions for measures with compact sup-
port, concentrated on the convex curve M3 = {(t, t2, t3) | t 2 R}, see [~Ziv98]
Proposition 4.9.
Proposition 5.6. ([Zie04]) Suppose that ~ is a continuous mass distribution
in R4 which has a center of symmetry O. Then ~ admits a 4-equipartition.
Moreover, one of the hyperplanes can be choosen in advance as an arbitrary
3-plane passing through the center of symmetry O.
Proof: Choose a "halving" hyperplane H1 for ~. One can assume that O 2
H1. Let ss : R4 ! H1 be the orthogonal projection and let be the measure
on H1 defined by (A) := ~(ss-1(A) \ H+1) where H+1 is a closed halfspace
bounded by H1. Find 2-planes P2, P3, P4 in H1 which form a 3-equipartition
for such that O 2 Pi for each i. This is always possible by Theorem 5.4.
Then H = {H1, H2, H3, H4} is a 4-equipartition for ~ where Hj := ss-1(Pj)
for j 2 is the hyperplane orthogonal to H1 at Pj.
Corollary 5.7. There does not exist a centrally symmetric, convex closed
curve in R4.
Proof: The "arc length"-measure on such a curve would be centrally sym-
metric. According to Proposition 5.6, its space of 4-equipartitions is "fibered"
over the Grassmannian of all affine 3-planes in R4, hence it is at least 4-
dimensional. This is a contradiction. Indeed, by the results of Section 3, the
16
solution manifold of all 4-equipartitions of a measure concentrated on a closed,
convex curve in R4 must be 1-dimensional.
Proposition 5.8. Suppose that ~ is a continuous mass distribution in R4
which has a 3-plane of symmetry. Then there exists a 4-equipartition for ~.
Proof: The proof is similar to the proof of Proposition 5.6, so we omit the
details.
5.3 Topological "counterexample"
Theorem 5.9. There exists a W4-equivariant map f : (S4)4ffi! S(U4).
Proof: By [Kosch81 ] x3, a W4-equivariant map f : (S4)4ffi! S(U4) exists if
and only if the obstruction ! 2 1(M; E - T M) in the corresponding group of
normal bordisms vanishes, cf. Section 4. By Proposition 4.1, ! is in the image
of the map ffi1. By Proposition 4.9 the map oe O j2 is onto and the result foll*
*ows
from the exactness of the sequence (3).
References
[Alon87]N. Alon. Splitting necklaces, Advances in Math. 63: 247-253, 1987.
[Alon88]N. Alon. Some recent combinatorial applications of Borsuk-type theorems,
Algebraic, Extremal and Metric Combinatorics, M.M. Deza, P. Frankl, D.G
Rosenberg, editors, Cambridge Univ. Press, Cambridge 1988, pp. 1-12.
[Anis98]S.S. Anisov. Convex curves in RP n. Trudy MIRAN, Proc. V.A. Steklov
Mathematics Institute Vol. 221 (1998), 3-39.
[Arn96] V.I. Arnold. On the number of flattening points on space curves. In:
Ya. G. Sinai's Moscow Seminar on Dynamical Systems. Providence, RI: Amer.
Math. Soc., 1996, 11-22.
[Avis84]D. Avis. Non-partitionable point sets. Inform. Process. Lett. 19 (19*
*84),
125-129.
[Bar93]I. B'ar'any, Geometric and combinatorial applications of Borsuk's theor*
*em,
New trends in Discrete and Computational Geometry, J'anos Pach, ed., Algo-
rithms and Combinatorics 10, Springer-Verlag, Berlin, 1993.
[BM01] I. B'ar'any, J. Matou~sek. Simultaneous partitions of measures by k-fans*
*, Dis-
crete Comput. Geometry, 25:317-334, 2001.
[BM02] I. B'ar'any, J. Matou~sek. Equipartitions of two measures by a 4-fan. Di*
*screte
Comput. Geom. To appear. (preprint).
[Quad] S. Beckett. Quad. In "Collected Shorter Plays", Faber, London 1984.
[Bj"or91]A. Bj"orner, Topological methods, In R. Graham, M. Gr"otschel, and
L. Lov'asz, editors, Handbook of Combinatorics. North-Holland, Amsterdam,
1995.
[CoFl64]P.E. Conner, E.E. Floyd. Differentiable periodic maps. Springer-Verlag
1964.
[Copp71] W.A. Coppel. Disconjugacy. Lecture Notes in Mathematics Vol. 220,
Springer-Verlag 1971.
[Dieck87]T. tom Dieck. Transformation Groups. de Gruyter Studies in Mathematics
8, de Gruyter, Berlin 1987.
17
[FaHu01] E.R. Fadell, S.Y. Husseini. Geometry and Topology of Configuration Spa*
*ces.
Springer 2001.
[FeZi02]E.M. Feichtner, G.M. Ziegler. On orbit configuration spaces of spheres.
Topology and its Applications, (2002) 118, pp. 85-102.
[Gil58]E.N. Gilbert. Gray codes and paths on the n-cube. Bell. Syst. Tech. J. (*
*1958)
815-826.
[Gr"u60]B. Gr"unbaum. Partitions of mass-distributions and convex bodies by hyp*
*er-
planes, Pacific J. Math., 10 (1960), 1257-1261.
[GuMa86] L. Guillou, A. Marin. A la Recherche de la Topologie Perdue. Birkh"au*
*ser
1986.
[Had66] H. Hadwiger. Simultane Vierteilung zweier K"orper, Arch. Math. (Basel),*
* 17
(1966), 274-278.
[Ha02] A. Hatcher. Algebraic Topology. Cambridge University Press 2002. Availab*
*le
online at http://math.cornell.edu/~hatcher.
[Knu01] D.E. Knuth. Generating all n-tuples, Ch. 7.2.1.1, prefascicle 2A of "T*
*he
Art of Computer Programming" (vol. 4), released September 2001, http://
www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz.
[Klee99]V. Klee. Shapes of the future. Some unsolved problems in high-dimension*
*al
intuitive geometry. http://www.cs.ubc.ca/conferences/CCCG/elec\_proc/
klee.pdf.
[Kosch81]U. Koschorke. Vector Fields and Other Vector Bundle Morphisms - A
Singularity Approach. Lect. Notes Math. 847. Springer-Verlag, Berlin 1981.
[Lov78]L. Lov'asz. Kneser's conjecture, chromatic number and homotopy, J. Combi*
*n.
Theory A, 25, 319-324, 1978.
[Mak01] V.V. Makeev. Equipartitions of continuous mass distributions on the sph*
*ere
and in the space (in Russian). Zap. Nauchn. Sem. S.-Petersburg (POMI), 279
(2001), 187-196.
[MVZ] P. Mani-Levitska, S. Vre'cica, R. ~Zivaljevi'c. Topology and combinator*
*ics of
partitions of masses by hyperplanes. arXiv:math.CO/0310377 v1 23 Oct 2003.
[Mat92] J. Matou~sek. Efficient partition trees, Discrete Comput. Geom. 8 (19*
*92),
315-334.
[Mat93] J. Matou~sek. Range searching with efficient hierarhchical cuttings, Di*
*screte
Comput. Geom. 10 (1993), 157-182.
[MS74] J. Milnor and J.D. Stasheff. Characteristic Classes. Princeton Univers*
*ity
Press, Princeton (1974).
[Ram96] E. Ramos. Equipartitions of mass distributions by hyperplanes. Discre*
*te
Comput. Geom., 15:147-167, 1996.
[Scho54]I.J. Schoenberg. An isoperimetric inequality for closed convex curves i*
*n even
dimensional Euclidean spaces. Acta Math. 91 (1954), 143-164.
[SeSh96]V. Sedykh and B. Shapiro. On Young hulls of convex curves in R2n.
[Toot56]G.C. Tootill. Proc. IEE 103, Part B Supplement (1956), p. 435.
[VZ92] S. Vre'cica and R. ~Zivaljevi'c. The ham sandwich theorem revisited. Isr*
*ael J.
Math., 78:21-32, 1992.
[V~Z94]S. Vre'cica, R. ~Zivaljevi'c, New cases of the colored Tverberg theore*
*m,
Jerusalem Combinatorics '93, H. Barcelo, G. Kalai (eds.) Contemporary mathe-
matics, A.M.S. Providence 1994.
18
[YY85] A.C. Yao, F.F. Yao. A general approach to d-dimensional geometric querie*
*s,
in Proceedings of the 17th ACM Annual Symposium on the Theory of Computing,
1985, 163-169.
[YDEM89] F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson. Partitioning space f*
*or
range queries, SIAM J. Comput., 18 (1989), 371-384.
[Zie04]G.M. Ziegler. Personal communication, October 2004.
[~Ziv96]R. ~Zivaljevi'c. User's guide to equivariant methods in combinatorics,*
* Publ.
Inst. Math. Belgrade, vol. 59(73) (1996), pp. 114-130.
[~Ziv98]R. ~Zivaljevi'c. User's guide to equivariant methods in combinatorics I*
*I, Publ.
Inst. Math. Belgrade, vol. 64(78) (1998), pp. 107-132.
[~Ziv04]R. ~Zivaljevi'c. Topological methods, in CRC Handbook of Discrete and C*
*om-
putational Geometry (new edition), J.E. Goodman, J. O'Rourke (eds.), Boca
Raton 2004.
[~ZV92]R. ~Zivaljevi'c, S. Vre'cica. The colored Tverberg's problem and complex*
*es of
injective functions, J. Combin. Theory, Ser. A, vol. 61 (2) (1992), pp. 309*
*-318.
19