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