Skip to main content

Full text of "Convex Equipartitions via Equivariant Obstruction Theory"

See other formats


Convex Equipartitions via Equivariant Obstruction Theory 



Pavle V. M. Blagojevic 
Mathematicki Institut SANU 
Knez Mihajlova 36 
11001 Beograd, Serbia 
^pavlebQmi . sanu . ac . rsj 



Giinter M. Ziegler 
Institut fiir Mathematik, FU Berlin 
Arnimallee 2 

14195 Berlin, Germany 

[zieglerOmath . f u-berlin . de| 



April, 2012 



Abstract 

We describe a regular cell complex model for the configuration space _F(K'^, n). Based on 
this, we use equivariant obstruction theory to prove the prime power case of the conjecture 
by Nandakumar and Ramana Rao that every polygon can be partitioned into n convex parts 
of equal area and perimeter. For a generalization of the conjecture we get a complete answer: 
It holds if and only if n is a, prime power. 

1 Introduction 

R. Nandakumar and N. Ramana Rao in June 2006 posed the following problem, which was 
characterized "interesting and annoyingly resistant" in 

Conjecture 1.1 (Nandakumar &; Ramana Rao [33]). Every convex polygon P in the plane 
can be partitioned into any prescribed number n of convex pieces that have equal area and equal 
perimeter. 

The conjecture was proved by Nandakumar & Ramana Rao [33] for n = 2, where it follows 
from the intermediate value theorem, that is, the Borsuk-Ulam theorem for maps f : ^ S^; 
the same authors also gave elementary arguments for the result for n = 2^. For n = 3 the 
conjecture was proven by Barany, Blagojevic & Sziics \7\ via advanced topological methods. 

For general n, it was noted by Karasev |29j and Hubard & Aronov |25] that the conjec- 
ture would follow from the non-existence of an (5„-equivariant map F(M?,n) — t- S{Wn), where 
F(M?, n) denotes the configuration space of n labeled points in the plane, that is, the set of all real 

2 X n matrices with pairwise distinct columns, and Wn '■= {{xi, ■ ■ ■ , Xn) G : xi + • • • + x„ = 0} 
is the set of all row vectors in with vanishing sum of coordinates. Both F(M^,n) and Wn 
have the obvious action of 6„ by permuting columns. Similarly, for d-dimensional versions of 
the problem one would need the non-existence of S„-equivariant maps F{W^,n) — ?■ S{W®'^~^). 
First Karasev [29j and later Hubard & Aronov [25] proposed to show this non-existence for 
prime power n = p^ based on a cell-decomposition of the one-point compactification of the 
configuration space that appears in work by Fuks [21] and Vassiliev |40j . Thus they have to 
deal with twisted Euler classes on non-compact manifolds resp. on compactifications that are 
not manifolds. In this paper, we avoid these difficulties, and obtain the same results and more 
via equivariant obstruction theory. Indeed, we obtain an "if and only if" statement: 

*The research leading to these results has received funding from the European Research Council under the Eu- 
ropean Union's Seventh Framework Programme (FP7/2007-2013) / ERG Grant agreement no. 247029-SDModels. 
The first author was also supported by the grant ON 174008 of the Serbian Ministry of Science and Environment. 



Theorem 1.2. For d,n>2, an 6n-equivariant map 

exists if and only if n is not a prime power. 

For this, we describe in Section [s] a beautiful ©n-equivariant {d — l)(n — l)-dimensional cell 
complex with n! vertices and n! facets that is an ©^-equivariant retract of F{W^, n). For d = 2 
this complex is implicit in work by Deligne [18] and explicit in Salvetti's work [36|. For d > 2 
we obtain it by specialization of a construction due to Bjorner & Ziegler 

Theorem |1.2| in particular proves the original problem by Nandakumar & Ramana Rao for 
prime powers n. However, we also get a much stronger theorem for the prime power case, which 
fails if n is not a prime power. 

Theorem 1.3. Let d > 2 and let be a continuous positive probability measure on M.'^. 

If n is a prime power, then for any d — 1 continuous real functions fi, . . . , fd-i on the space 
of convex polyhedra C <Z with non-empty interior there is a regular partition of into n 
convex regions Ci, . . . , C„ that equiparts fi, 

MCi) = --- = Mc„) = ^, 

and equalizes the functions /i, . . . , fd-i-' 

fi{Ci) = --- = f;{Cn) forl<i<d-l. 

If n is not a prime power, then this is false: For any given d > 2, any continuous pos- 
itive probability measure /i on W^, and n not a prime power, there are continuous functions 
/i, . . . , fd~i on the space of d-dimensional convex polyhedra with nonempty interior, such that 
no regular subdivision equiparts the measure fi and equalizes the functions fi. 

The "regular subdivisions" appearing in the statement of this theorem are partitions that 
arise from Monge-Kantorovich type optimal transport for a quadratic assignment function; 
see Villani |42l Chap. 2]. The same type of partitions are called "regular" in the set-up of 
Gelfand, Kapranov & Zelevinsky [22] . In Computational Geometry they are known as generalized 
Voronoi diagrams or power diagrams. The equivalence between partitions induced by optimal 
transport and those given by the domains of linearity of a minimum of n linear functions was 
proved by Aurenhammer |2j, and certainly also by others; see Siersma & van Manen [37j . 
Theorem 



1.3 



is equivalent to Theorem 1.2 as regular equipartitions are parametrized by F(]R'^, n). 
This remarkable observation can be traced back to Minkowski |30| [31] . It was independently 
developed in Optimal Transport (see Villani [A2\ Chap. 2]) and in Computational Geometry (see 
Aurenhammer, Hoffmann & Aronov [313]). 

Our proof of Theorem |1.2| relies on equivariant obstruction theory as formulated by tom 
Dieck [39, Sec. II. 3]. We happen to be in the fortunate situation where we have to deal only 
with primary obstructions, for mapping a cell complex of dimension (d — l)(n — 1) to a sphere 
of dimension (d — l)(n — 1) — 1. Moreover, the cell complex has a single orbit of maximal cells 
("facets"), where the obstruction cocycle evaluates to 1. At the same time, we have n — 1 orbits 
of ridges, of sizes ("). The proof is completed via the number theoretic fact about the n-th row 
of the Pascal triangle 



gcd{(^),G),...,(„^)} 



if n is a prime power, n = p^, 
otherwise. 



This may be derived from the work by Legendre and Kummer on prime factors in factorials 
and binomial coefficients, apparently was first proved by Ram [35] in 1909, extended by Joris et 
al. [26], and was later rediscovered by A. Granville (see Soule and Kaplan &; Levy [28]). 



2 



2 From Partitioning Polygons to Equivariant Maps of Configu- 
ration Spaces 



According to Gelfand et al. |22j . a polyhedral subdivision is regular if it is given by the domains 
of linearity of a convex, piecewise-Iinear lifting function. See also [43^ Lect. 4]. According to 
Aurenhammer [2], the regular partitions are exactly the ones obtained by optimal transport for 
quadratic distance functions. 

The classical partitions of this form are known in Computational Geometry as Voronoi 
diagrams and in Number Theory as Dirichlet tesselations. They are obtained as V(xi, . . . , Xn) = 
(Ci, . . . ,C„) via 

Ci := {x G M'^ : — Xi\\ < \\x — Xj\\ for 1 < j < n} 

= {x e M'^ : \\x - Xilp - llxll^ < \\x - Xjlp - for 1 < j < n}. 

Thus Ci is the domain in M"' where the linear (!) function fi{x) = \\ OC X 2 1 1 II X II yields the 
minimum among all functions fj{x) of the same type, and thus the Voronoi diagram is given by 
the domains of linearity of the piecewise-Iinear convex function f{x) = min{||x — — ||a;|p : 
1 < i < n}. 

For generalized Voronoi diagrams or power diagrams we introduce additional real weights 
wi, . . . , t(7„ G M, and set V{xi, . . . , x„; wi, . . . , Wn) = {Pi, • • • , Pn) with 

Pi := {x S M'^ : ||x — Xi|p — Wi < \\x — Xj\\'^ — wj for 1 < j < n}. 

As an additive constant does not change the partition, we may w.l.o.g. replace Wi by Wi — ^{wi + 
• • • + Wn), and thus assume that wi + ■ ■ ■ + Wn = 0, that is, {wi, . . . , Wn) G Wn- 

Again, the partition of space given by a generalized Voronoi diagram is a regular subdivision. 
However, now some of the parts Pi may be empty, and Xi G Pi does not hold in general. We 
refer to Aurenhammer & Klein [5] and Siersma &: van Manen [37] for further background. 

The major part of the following theorem (except for the continuity, which of course is essential 
for us) was provided by Aurenhammer, Hoffmann & Aronov [3] in 1992. The 1998 journal 
version [4] of their paper noted the connection to optimal transport; thus, the proof can be 
done using optimal assignment and linear programming duality, as developed (for this purpose) 
by Kantorovich in 1939 [57], with the "double convexification" trick. For a modern exposition 
see Villani |42| Chap. 2]. Evans [19] provides a very nice and simple combinatorial treatment 
(which needs minor adjustments in the use of LP duality, as the dual programs [191 (1.15), 
(13.6)] should not have nonnegativity constraints Uj > 0, Vj > 0). 

Theorem 2.1 (Kantorovich 1939, etc.). Let ^ be a continuous probability measure on . 
For any xi, . . . , x„ E with Xj ^ xj for all 1 < i < j < n there are weights wi, . . . , Wn S 
wi + - ■ ■+Wn = 0, such that the power diagram V{xi, . . . , x„; t^i, . . . , Wn) equiparts the measure 
Moreover, the weights wi, . . . ,Wn 
o are unique, 

o depend continuously on xi, . . . , Xn, and 

o can be characterized/ computed via optimal assignment with respect to quadratic cost functions. 

In short, this theorem states that the configuration space F(K'^,n) of n distinct labeled 
points in M'^ parametrizes the regular n-equipartitions of any continuous measure //. Thus any 
counterexample to Theorem |1.3| would yield an ©n-equivariant continuous map 

F(M^n) Wr-'\{0}. 

In the following we will show that, indeed, this map does not exist if n is a prime power, but 
that it does exist otherwise. 



3 



3 A Cell Complex Model for n) 



In order to apply obstruction theory to F(M.'^, n), we specialize the cell complex models given for 
complements of real subspace arrangements by Bjorner & Ziegler For d = 2, the barycentric 
subdivision of this cell complex is treated implicitly in Deligne [18]. The cell complex for a 
general complement of a complexified hyperplane arrangements is developed in more detail by 
Salvetti |36] and thus known as the "Salvetti complex." 

These cell complex models are closely related to the cell complex structures described already 
in 1962 by Fox & Neuwirth [20], and later by Fuks [H] for 5^" = M^" u {*} D F{R'^,n). The 
analogous constructions for F{W^,n) were done by Vassiliev [U]. See also de Concini & Salvetti 
|17| and Basabe et al. [8], as well as very recently Guisti & Sinha [23] and Ayala & Hepworth [6]. 

To obtain our cell complex model, we first retract F(R'^, n) by Xi := Xi — ^(a^i + • • • + Xn) to 

F(M'*,n) := {(xi,.. . G M'^''" : xi + • • • + x„ = 0, Xj / x^ for 1 < i < j < n], 

which is the complement of an essential arrangement of linear subspaces of codimension d in 
the vector space W®'^ = {(xi, . . . , x„) € M'^^" : xi + • • • + x^ = 0} of dimension d{n — 1). 
(An arrangement of linear subspaces is essential if the intersection of all the subspaces is the 
origin.) All the subspaces in the arrangement have codimension d and all their intersections 
have codimensions that are multiples of d, so this is a d-arrangement in the sense of Goresky &; 
MacPherson [231 Sect. III. 4]. See Bjorner [9j for more background on subspace arrangements. 

To construct the Fox-Neuwirth stratification of this essential arrangement of linear subspaces 
(which, except for the ordering of the coordinates, is equivalent to the "s^^-'-stratification" of 
[m Sect. 9.3]), we order the n columns of the matrix (xi, . . . , Xn) G W®'^ in lexicographic order. 
That is, we find the permutation a = oxoi ■ ■ ■ an & S„ such that for 1 < j < n, 

• either for some ij, 1 < ij < d, we have Xi^^o-j < Xi-^a^+i with Xj/^o-j = Xi/^o-j+i for all i' < ij, 

• or Xa- = Xaj_f_i', in this case we set ij = d+1 and impose the extra condition that < cjj+i. 
Then we assign to (xi, . . . , x„) the combinatorial data 

(o"i<nO'2<j2 ■ ■ ■ <i„-i(^n), 

where a = aia2 ■ ■ ■ C7n G &n is a permutation and i = (ii, . . . , in-i) G {1, . . . , d, d + l}"^-*^ is a 
vector of coordinate indices. 

Example 3.1. Let d = 2, n = 8: The 8 points xi, . . . , xg G in the left part of Figure [l] 
correspond to the permutation a = 38147652. The combinatorial data for this configuration 



fX4 



*Xl 



^X7 



• X2 

I 
I 

I 



*x 



• X 



•^2 

jxC 



• Xi 



+ x' 



f Xv 



tx'e 



Figure 1: Two point configurations for d = 2, n = 8 

are (cr, i) = (3<28<il<24<i7<i6<25<22). For the point configuration on the right we get the 
permutation a' = 31847652 and the combinatorial data {a' , i') = (3<2l<28<24<i7<i6<25<22). 



4 



All the points in W®'^ with the same combinatorial data {a, i) make up a stratum that we 
denote by C(fT, i). This stratum is the relative interior of a polyhedral cone of codimension 
(ii — 1) H + (in-i — 1), that is, of dimension (d + l)(n — 1) — (ii • • • + i„-i) in W®'^. 



Example 3.2. The stratum C{a,i) = (3<28<il<24<i7<i6<25<22) of Example 3.1 has dimen- 
sion 10. It is 



^ ^©2 ^ ]^2x8 . ^13 = a;i8 < Xn = Xu < Xyj < XiQ = Xi5 = Xi2 1 
8 ■ X23 < 3^28 2^21 < X24 X27 X26 < X25 < X22 J ' 

Lemma 3.3. The closure of each stratum C{a,i) C W®"^ is a union of strata, namely of all 
strata C{cr',i') such that 



Xn xi2 ... xis 

X21 X22 ■■■ X28 



(*) If . . .Gk ■ ■ ■ <i'^ . . .ae ■ ■ ■ appear in this order in [a then 

either . . .a^ ■ ■ ■ <ip . . .ai . . . appear in this order in (cj, i) with ip < ip, 
or . . .ai . . . . . . (Tfc . . . appear in this order in {a, i) with ip < ip. 

Proof. Let {xi, . . . , Xn) be a configuration of points that lies in the stratum C{a, i), which is a 
relatively open polyhedral cone characterized by equations and strict inequalities. The closure 
of the cone is given by the condition that the equations still hold, and the inequalities still hold 
weakly. Thus the smallest index of a coordinate in which two points Xa^ and x^^ differ may not 
go down when moving to x'^^ and x^^, and if it stays the same, then the order in this coordinate 
must be preserved. 

Thus if . . . (Tfc . . . . . .a£ . . . appear in this order in (a', i') and ip is not the smallest such 

index, then no condition is posed. If i'p is the smallest such index, then we either have the same 
in (o", i), or there is a smaller index ip. If there is no smaller index, then we still require that 
. . . (Tfc . . . <j/^ . . . o"£ . . . appear in this order in {a, i). If there is a smaller index ip < between 
CTfc and ai, then the order is arbitrary. 

Condition (*) describes this. □ 



Example 3.4. For the point configurations of Example |3.l| the 9-dimensional stratum C{a',i') 
lies in the boundary of the 10-dimensional stratum C{a, i). 

Definition 3.5. For d > 1, n > 2 the set of pairs (cr, i) with the partial order (cr, i) > 



(cr',i') described by Condition (*) in Lemma 3.3 is denoted by S{d,n). Its minimal element 
{l<d+i2<d+i . . ■ <d+in) is denoted by 6. 

Example 3.6. The face poset of 5'(2,3) is displayed in Figure [2j (Compare [HI Fig. 2.3].) 
Here black dots denote cells in the complement of the arrangement given by the codimension 2 
subspaces " (that is, lying in the configuration space F(M^3)), while the white dots 

correspond to cells on the arrangement. 

By Lemma 



3.3 



the intersection of the strata of the Fox-Neuwirth stratification of W®'^ 
with the unit sphere SiW®'^) yields a regular CW decomposition of this sphere of dimension 
d{n — 1) — 1, whose face poset is given by S{d,n). (Here the stratum {0} corresponds to 
G S{d,n); it corresponds to the empty cell in the cellular sphere.) 

The union of the arrangement is composed of all the strata with at least one entry <d+i, 
while the strata where all comparisons <k have A; < d lie in the complement. In particular, the 
link of the arrangement (its intersection with the unit sphere) is given by a subcomplex of the 
cell decomposition of the unit sphere in W®"^ induced by the stratifiction. 

Example 3.7. For d > 1, n = 2 the CW decomposition of the unit sphere in PF^'^ = M'^ we obtain 
is the minimal, centrally-symmetric cell decomposition of the (d— l)-sphere that has two vertices, 
two edges, two 2-cells, etc.: The two i-cells are C{l<d-i2) n S{W^'^) and C{2<d-il) n S{W^'^), 
for < i < d. Both i-cells lie in the boundary of both j-cells, for < i < j < ci. 



5 




6 



Example 3.8. For d = 1, n > 2 the stratification of Wn is given by tlie real arrangement of 
(2) hyperplanes Xi = Xj in Wn- The CW decomposition of the unit sphere in Wn has 2" — 2 
vertices, indexed by {cri<2 • • • <20'k-i<iO'k<2 • • • <20'n) with 1 < A; < n, cti < • • • < ak-i and 
CTfc < • • • < an, and n\ facets corresponding to the regions of the hyperplane arrangement, 
indexed by (cri<i • • • <icr„) for permutations a E 6„. 

We are deahng with a partition ("stratification") of a Euclidean space into a finite 
number of relative-open polyhedral cones such that the relative boundary of each cone C (i.e. 
its boundary in the affine hull) is a union of (necessarily: finitely many, lower-dimensional) cones 
of the stratification. Furthermore the stratification is weakly essential in the following sense: 
some of the strata may not be pointed (i.e., have {0} as a face of the closure), but {0} is a 
stratum that lies in the boundary of all other strata, which thus are proper subsets of their 
affine hulls. In this situation any selection of points vq in the relative interiors of the strata C 
induces a PL-homeomorphism between the order complex of the face poset of the stratification 
to a starshaped PL-ball that is a neighborhood of the origin in M™. 

Example 3.9. Figure [s] shows a weakly essential stratification of M^, its face poset, and a real- 
ization of the order complex of its face poset. 




We now implement this construction for our specific stratification of W® ■ 

Lemma 3.10. For d > 1, n > 2, in each stratum C(a,i) a relative-interior point v{a,i) = 
{xi, . . . , Xn) G W®"^ is obtained as follows: Set 

where ei denotes the ith standard unit vector in M*^, with Cd+i '■= 0. The point f(fT, i) is the 
image of this x(a", i) under the orthogonal projection map v from M*^^" to the subspace W®'^, 
which translates the barycenter of the configuration to the origin, given by Xj := i^{xj) = xj — 

^(Xi H h Xn). 



7 



These points v{a, i) yield the vertices of a geometric realization of the order complex AS{d, n) 
by a starshaped PL neighborhood sdB{d,n) ofW®'^. Its boundary is a geometric realization 
of the barycentric subdivision of the cell decomposition of S{W®'^) given by the Fox-Neuwirth 
stratification. 

Example 3.11. For the data (cr, i) = (3<28<il<24<i7<i6<25<22) of the first configuration in 
Example 3.1 , Lemma 3.10 yields the following configuration of Figure|4j which is then normalized 
by the map v. 



X4 Xj 



•X2 

I 
I 



X8 



*Xl 



^3 



Figure 4: The coordinates of Lemma 3.10 for the first configuration of Example 3.1 



Example 3.12. For n = 3, d = 1 the starshaped PL neighborhood sd;B(l, 3) of C M'^ has 13 
vertices, some of whose coordinates according to Lemma 3.10 are indicated in Figure [5| 




I<i2<i3) ^ zv(0, 1, 2) = (-1, 0, 1) G Ws 



(I<i3<i2)^zy(0,2,l) 



-1,1,0) e W3 



z.(0,l,l) = (-|,i,i)GT^3 



Xl = X3 



(3<il<i2) ^ z.(l, 2, 0) = (0, 1, -1) G Ws 



X2 = X3 



(3<i2<il 



Figure 5: Coordinates for the realization of sdi3(l,3) in VF3 according to Lemma 3.10 



In particular, the boundary of the star-shaped PL neighborhood sd B{d, n) is an S„-invariant 
PL sphere. The link of the arrangement is represented by an induced subcomplex of this sphere. 



8 



The dual cell complex of the sphere contains, as a subcomplex, a cellular model for the com- 
plement of the arrangement - that is, a simplicial complex that is a strong deformation of the 
configuration space F(R'^,n). The cell complex is regular in the sense that the attaching maps 
of cells do not make identifications on the boundary; in particular, the barycentric subdivision 
of any such complex is a simplicial complex, given by the order complex of the face poset (see 
e.g. Bjorner et al. ^ Sect. 4.7], Cooke & Finney jIB], Munkres [32]). 

Theorem 3.13 (CeU complex model for F{R'^,n)). Let d > 1 and n > 2. Then F{R'^,n) 
contains, as a strong deformation retract, a finite (and thus compact) regular CW complex 
J-{d,n) of dimension (d — l){n — 1) with nl vertices, nl facets, and {n — l)n! ridges. 
The nonempty faces of J-{d, n) are indexed by the data of the form 

{a, i) := (cri<ij(T2<i2 . . . <i„_i<7n), 

where a = a\a2 . . . o"™ G ©„ is a permutation, and i = (ii, . . . , in-i) G {1, . . . , d}"^^. Let F{d, n) 

he the set of these strings. 

The dimension of the cell c{a, i) associated with (a, i) is (ii + • • • + in-i) ~ ('^ ~ !)• 

The inclusion relation between cells c{a, i), and thus the partial order of the face poset F{d, n), 

is as follows: 

holds if and only if 



(**) whenever . . .a^ . . . <ii^ . . .a^. . . appear in this order in (cr', i'), then 
either . . .ak ■ ■ ■ <ip . . .ag . . . appear in this order in (cj, i) with ip < i'p, 
or . . .a£ . . . . . . (Tfc . . . appear in this order in (o", i) with ip < i'p. 

The barycentric subdivision of the cell complex (that is, the order complex AF{d,n) of its face 
poset) has a geometric realization in W®'^ with vertices v{a,i) = G W®'^ placed 

according to 

■= 0, ^<7(j + l) := ^a(i) + 

where Ci denotes the ith standard unit vector in R'^, followed by orthogonal projection M"'^" — )• 
W,®"^, given by xj := Xj — -{xi + • • • + Xn). This geometric realization in W®'^ C M"^^" is an 
&n-equivariant strong deformation retract of F(\R.'^,n). 

The group ©„ acts on the poset F{d,n) via it ■ (cr, i) = (vru, i), and correspondingly by 
IT • v{a,i) = v{TTa,i} on the geometric realization sdT{d,n) with vertex set {v{a,i) : (tr, i) G 
F{d,n)}. 

Proof. Orthogonal projection ©n-equivariantly retracts F(M°',n) to F(K'^,n) C W®'^, and fur- 
ther radial projection 6„-equivariantly retracts this to a subset of the boundary of the starshaped 
neigborhood of the origin, dsd B{d, n), which is a simplicial realization of the cell decomposition 
of the {d{n — 1) — l)-dimensional sphere S{W®'^) given by the Fox-Neuwirth stratification. 

The same maps identify the link of the arrangement (that is, the intersection of its union 
with the unit sphere) with the induced subcomplex of dsdB{d,n) on the vertices v{a,i) that 
have some index ij = d + 1. 

As the cell decomposition of the {d{n — 1) — l)-sphere S(W®^) is PL, following Munkres |32|, 
§ 64] we can pass to the "Alexander dual" cell decomposition. Thus any nonempty cell C{a, i) 
of dimension {d + l){n — 1) — (ii + ■ ■ ■ + in) — 1 has an associated dual cell c(cr, i) of dimension 
{d{n — l) — 1) — ((d-|- l)(n — 1) — (ii + • • - + 1^1-1) — 1) = {ii + - • • + in-i) — {n — l), and the inclusion 



relation is just the opposite of the one in the primal complex, as described in Lemma 3.3 



9 



According to the Retraction Lemma [10^ Lemma 4.7.27] |32l Lemma 70.1], the complement 
admits a strong deformation retraction to the subcomplex whose ceUs are indexed by all pairs 
(cT, i) with all indices ij ^ d + 1. (This retraction is easy to describe in barycentric coordinates 
in the barycentric subdivision of the cell complex, that is, on the order complex of the face 
poset. The (5„-action restricts to the subcomplex, and the retraction is canonical, and thus 
©ri-equivariant.) 

So we obtain a strong deformation retract of F(M'^, n) that is a cell complex with cells 
indexed by (a, i) with all indices ij ^ 0. The barycentric subdivision of this cell complex is 
realized as a simplicial complex in W,®"^ as the induced subcomplex of dN{d, n) on the vertices 
f (cj, i) with all indices ij ^ d + 1. Thus also the ©^-action restricts to this simplicial model for 
the complement. □ 

Example 3.14. For n = 2 the cell complex J^{d,2) turns out to be the centrally-symmetric cell 
decomposition of S"^~^ whose {i — l)-cells are given by c(l<i2) and c(2<jl) for 1 < i < d. 



(Compare to Example 3.7 



Example 3.15. For d = 1 the configuration space F(R,n) is the complement of a real hyper- 
plane arrangement in Wn- The cell complex J^{l,n) is 0-dimensional, given by the n! vertices 
v{(Ti<ia2 ■ ■ ■ <iO"n) G Wn, One in each chamber of the arrangmenent. (Compare to Fixam- 

Example 3.16. For d = 2 the configuration space F(M^,n) = F{C,n) may be viewed as the 
complement of a complex hyperplane arrangement, known as the braid arrangement. This is 
the particular situation studied by Arnol'd [I], Deligne [T8|, and many others. The cell complex 
that we obtain is a particularly interesting instance of the cell complex constructed by Salvetti 
|36j for the complements of complexified hyperplane arrangements (see also |llj). 

In this case we may simplify our notation a bit: The non-empty cells of the complex are 
indexed by {ai<i-^ . . . <i^_-^(Tn) with ij E {1,2}. Thus we can identify our cells uniquely if we 
just write a bar instead of "<i", no bar for "<2". The inclusion of a cell into the boundary of 
a higher-dimensional cell is then represented in the partial order by (repeatedly) "removing a 
bar, and shuffling the two blocks that were separated by the bar" . 

For example, for n = 3 we obtain the face poset F(2, 3) displayed in Figure [6} It is obtained 



by taking the elements of the partial order 5'(2, 3) displayed in Example 3.6 that are marked by 
black dots, with labels simplified, and the partial order reversed. 



213 231 321 312 132 123 




21113 21311 31211 31112 1|3|2 1|2|3 



Figure 6: The poset F(2, 3) 



10 



We see that the ceh complex J-"(2, n) is particularly nice: 

• The cell complex T{2,n) is a regular cell complex of dimension n — 1. 

• It has nl facets, given by permutations cria2 ■ ■ -(Jn-, and n\ vertices, given by the barred 
permutations o"i|(T2| • • • |cTn. 

• It has ("~|)n! cells of dimension i, given by permutations with n — i — 1 bars. 

• The order relation is generated by the operation of "remove a bar, and merge the two 
adjacent blocks separated by the bar by a shuffle" . 

• The maximal cells have the combinatorial structure of an (n — l)-dimensional permuta- 
hedron. (Thus all cells have the combinatorial structure of simple polytopes, namely of 
products of permutahedra.) 

Figure [7] indicates the structure of the cell complex J- {2, 3): This is a regular cell complex with 
3! = 6 vertices, 2 • 3! = 12 edges, and 3! = 6 2-cells, which are hexagons. The figure displays 
the six 2-cells shaded in separate drawings; for example, the 2-cell c(123) is bounded by the 
six edges c(l|23), c(13|2), c(3|12), c(23|l), c(2|13), c(12|3). In the complex J"(2,3) each edge is 
contained in three of the six hexagon 2-cells. The six edges in the boundary of each 2-cell lie in 
two different orbits of the group ©3; for the 2-cell c(123) displayed in Figure [Tj the three edges 
c(l|23),c(3|12),c(2|13) lie in one ©3-orbit, while c(13|2), c(23|l), c(12|3) lie in the other one. 

Our drawing also specifies orientations of the cells that will be discussed in the next section 
(namely, the edges and 2-cells). 

3.1 A small summary 

We have constructed and described the following objects: 

• S{d,n): the face poset of the Fox-Neuwirth stratification of W®'^, with minimal element 0; 

• S{d,n): a regular cell complex homeomorphic to S{W®^) = S'^^^~^^~^, a PL sphere; its face 
poset is S{d,n)\{0}; 

• B{d,n): a regular cell complex homeomorphic to B{W®'^), a PL ball, given by S{d,n) plus 
one additional d(n — l)-cell; 

• sdB{d,n): the barycentric subdivision of B{d,n); a simplicial complex, geometrically em- 
bedded starshaped neighborhood of the origin in VF^*^. 

• F{d, n): the poset of all strata that lie in the complement of the arrangement (that is, have 
no ij = 1), ordered by reversed inclusion; it is the subposet of S{d, n)°P given by all (cr, i) 
without any index ij = d + 1; 

• J-'{d,n): a regular cell complex of dimension (d — l)(n — 1); it is a subcomplex of the dual 
cell complex to S{d,n); its poset of non-empty faces is F{d,n). 

• sdJ^(d, n): the barycentric subdivision of J-{d,n), the order complex AF{d,n); a simplicial 
complex, geometrically embedded into the complement F{W^, n) C W®'^ as a subcomplex of 
the boundary of the ball sdB{d,n). 



11 




Figure 7: The six 2-cells of J^(2, 3) 
12 



4 Equivariant Obstruction Theory 



Our task now is to prove that for any d > 1 and n > 2 an equivariant map 
exists if and only if n is not a prime power. Here 

• J-{d,ri) is a finite regular CW complex of dimension M := {d — l)(n — 1) on which (3„ acts 
freely, permuting the M-dimensional cells, as described in Theorem |3.13[ 

• S{W®'^^^) is the set of all [d — 1) x n matrices of column sum and sum of the squares of 
all entries equal to 1. This is a sphere of dimension (d — l)(n — 1) — 1 = M — 1, on which Gn 
acts by permutation of columns; this action is not free for n > 2, but it has no fixed points. 

We proceed to apply equivariant obstruction theory, according to tom Dieck [391 Sect. II. 3]: 
Since 

• J-{d, n) is a free (3„-cell complex of dimension M, 

• the dimension of the Sn-sphere S{W®'^~^) is M — 1, and 

• 5(W®'^-^) is (M - l)-simple and (M - 2)-connected, 

the existence of an ©^-equivariant map is equivalent to the vanishing of the primary obstruction 

Here c/ denotes the obstruction cocycle associated with a general position equivariant map 
/ : F{d,n) W®'^'^ (cf. il2i Def. 1.5, p. 2639]). Its values on the M-cells c are given by the 
degrees 

Cf{c) = deg{r o f : dc ^W®''-\{Q} ^ S{W®''-^)), 

where r denotes the radial projection. 

The Hurewicz isomorphism gives an isomorphism of the coefficient (5„-module with a ho- 
mology group: 

^M-i(5(Tvr-')) = i^M-i(5(wr-');z) =: z. 

As an abelian group this Sn-module Z = (^) is isomorphic to Z. The action of the permutations 
T E Gn on the module Z is given by 

r-e = (sgn^)'^-!^. 

Indeed, each transposition Tij in S„ acts on Wn by reflection in the hyperplane Thus 
the action of &n on Wn reverses orientations according to the sign character, and the action on 
W®'^~^ is given by sgn'^"-'^. 

4.1 Computing the obstruction cocycle 

We will now compute the equivariant obstruction cocycle c/ in the cellular cochain group 

c^[{mny,z) 

and then show that Cf is a coboundary of an equivariant (M — l)-cochain if and only if n is not 
a power of a prime. 

To compute the obstruction cocycle, we use the ©n-equivariant linear projection map 

obtained by deleting the last row from any matrix {yi, . . . , y„) S W®'^ of row sum 0. This map 
clearly commutes with the projection map u : M"'^" — )• W®'^ which subtracts from each column 
the average of the columns. 



13 



Lemma 4.1. The linear map f maps all M -cells of sdT{d,n) C W®"^ homeomorphically to the 
same starshaped neighborhood sd B{d — 1, n) of in W®'^~'^. 

The symmetric group 6„ acts on this neighborhood by homeomorphisms that reverse orien- 
tations according to sgn'^~^. 

Thus the M -cells and the (M— l)-cells of the complex T{d,n) can be oriented in such a way 
that the Gn-o-ction on the M-cells and on the {M — l)-ceUs changes orientations according to 
ggj^d-i^ iti/iz/e the boundary of any M-cell is the sum of all (M — l)-cells in its boundary with 
+1 coefficients. 

With these orientations, the obstruction cocycle Cf has the value +1 on all oriented M-cells 
ofT{d,n). 

Proof. The M-cells of F{d, n) are given as c((7i<d(T2<d . . . <d(^n) for some permutation a G 6„. 
The (M — l)-cells are given by c((Ji<d • • • (Tj<d_iO"j+i . . . <rfcr„) for some a G 6„ and 1 < i < n. 

The vertices of the barycentric subdivision of the cell c{ai<(icr2<d ■ ■ ■ <dO'n) are exactly those 
vertices v{a[<i^ . . . <i^_^cr'^) for which the letters a'j that are separated only by "<d"s appear 
in the same order in a. 

The projection / deletes the last row, and thus maps the vertex v{ai<i-^ ■ ■ ■ <i„-i'^n) to 
the vertex with the same symbol f (cTi<i^ . . . <j„_iO"„) of sdB{d — l,n), except for reordering of 
symbols separated only by <d. Thus exactly the vertices which differ only by reordering letters 
a'j that are separated only by "<d"s are mapped by / to the same vertex of sd B{d— l,n). 

Thus we get that each maximal cell is mapped homeomorphically to the starshaped neigh- 
borhood sdB{d — 1, n) of the origin in W.®'^^^. In particular, the vertex v{ai<d(T2<d ■ ■ ■ <d<^n) 
is the only point of the M-cell c{ai<dcr2<d ■ ■ ■ <d'^n) that is mapped to G W®"^"^. 

We interpret sd B{d — l,n) as the barycentric subdivision of a cellular M-ball B{d — l,n) 
with one M-ccU. The (M— l)-cells in its boundary are given by c{ai<d . ■ ■ crj<d-if^j+i ■ ■ ■ <d'^n) 
with exactly one index ij = d — 1 and all other i^s equal to d. Clearly there are 2" — 2 of those, 
as they are given by the proper nonempty subsets {ai, . . . ,aj} C {1, . . . , n}. 

As / induces a surjective cellular map from T{d, n) to B{d — 1, n) that is a homeomorphism 
restricted to each cell, we can proceed as follows. We fix an orientation of the one M-cell 
of B{d — l,n). (This amounts to fixing an orientation of W®'^^^.) We define orientations of 
the (M — l)-cells in the boundary of the M-cell of B(d — l,n) by demanding that the cellular 
boundary of the M-cell is given by the formal sum of all the (M — l)-cells with coefficients. 
We then define the orientation of the (M — l)-cells of T{d,n) by demanding that the map / 
preserves orientation for all of them. □ 

4.2 When is the obstruction cocycle a coboundary? 

Lemma 4.2. Let b be any equivariant (M — 1) -dimensional integral equivariant cellular cochain 
on F{d,n), then the value of its coboundary is 

^i(i)+^i(2) + ---+^n-iL:!j 

on all M-cells, for integers xi, . . . , Xn-i- 

Proof. As b needs to be equivariant, we get the condition that the values are constant on orbits. 
(Indeed, this is since the boundary operator does not introduce any signs, and the symmetric 
group acts by introducing the same signs sgn*^"^ both on the (M — l)-cells and on the 6„- 
module Z.) 

Finally, the ©„-orbit of the (M — l)-cell c{a\<d . . ■ aj<d-\o-j+\ . . . KdCn) has size (") . □ 



14 



Proof of Theorem 1.2. By [39j Sect. II. 3, pp. 119-120], the equivariant map exists if and only 



if the cohomology class o = [cf] vanishes, that is, if cj is the coboundary Cf = 6b of some 



(M — l)-dimensional equivariant cochain b. We have seen in Lemmas 4.1 and 4.2 that this is 
the case if and only if 

-lil) + ^1(2) + ■ ■ ■ + ^n-lL-d = 1 (1) 

has a solution in integers. By the Chinese remainder theorem, this happens if and only if the 
binomial coefficients do not have a non-trivial common factor. By Ram's result, as quoted in 
the introduction and proved below, this holds if and only if n is not a prime power. □ 



Proposition 4.3. For all n £N we have 
gcd 



n\ / n\ / n \^ \ p if n is a prime power, n = p^ 
ij' V2y''"' U-ly i |l otherwise 

Proof. Ifn = p^, k > 1, then p appears only once as a factor of , and at least once in every 
other binomial coeffient considered. Since (") = p'', we obtain gcd{("), (2), . . . , = P- 

If n is not a prime power, let n = YViLiPi"^ m > 1 and distinct primes pi. The number 
of times pi appears as a factor in p^^\ and in ^ — ^^^^^ is Yl'j=iP^ so pi does not divide (J^i). 

Hence gcd{n = (1), ^^),^,),. ■ ■ , (^L)} = 1 and thus gcd{(^), Q,..., = 1. ' □ 

In the case when n is a power of 2 the equation ([T]) has no solution modulo 2, which implies 
that the top Stiefel- Whitney class of the bundle 

Wn ^ F(M^n) X6„ Wn ^ F(M^n)/6„ 

is non-trivial. This fact was first proved by Cohen &: Handel \15\ Lemma 3.2, page 203] in the 
case d = 2, and by Chisholm |14i Lemma 3] in the case when d is a power of 2. For further 
application of this fact in the context of /c-regular mappings of Euclidean spaces consult |13j . 

Two corollaries 

Our calculation above implies a complete calculation for the top equivariant cohomology group 
of the cell complex T{d, n). 

Corollary 4.4. For d,n>2, 

^7-^^ ^cm^erf-iNN\ _ /r. i\ _ \'^Ip if n = p^ is a prime power, 



H^^{T{d,n);7rM-i{S{Wr-'))) = (M) 



otherwise. 



Indeed, our cell complex model has only one orbit of maximal cells, thus the group of 
equivariant M-dimensional cochains is isomorphic to Z. Our calculation shows that the subgroup 
of coboundaries is generated by the element gcd{("), (2), . . . , 



Moreover, we note a stronger version of the non-existence part of Theorem 1.2 
Corollary 4.5. For d> 2 and prime powers n = p'^ , there is no G-equivariant map 

F{R^,n) S{W^^-') 
for any p-Sylow subgroup G C Gn- 



This follows from our proof for Theorem 1.2 using transfer; see |13j . Moreover, in [T3j we 



will derive from equivariant cohomology calculations (the Fadell-Husseini index) that in the 
case when n = p is a prime, the equivariant map does not exist for the cyclic (Sylow) subgroup 

Z„ C Gn- 



15 



Acknowledgement 

Thanks to Imre Barany, Roman Karasev, Wolfgang Liick, and Jim Stasheff for interesting and 
useful discussions and to Moritz Firsching for many comments, the reference to Ram's result 
[35] . and the proof we give for it above. 

Thanks to Till Tantau for TikZ and to Miriam Schloter for the TikZ figures. 

When the first version of this paper was released on the arXiv, Dev Sinha pointed us to the 
recent preprints [23] and [6]. In response to this, we decided to change our notation to be in line 
with these papers, which continue the developments started by Fox & Neuwirth and Fuks. 

We are grateful to Aleksandra and Torsten for their constant support. 



References 

V. I. Arnol'd, The cohomology ring of the colored braid group, Mathematical Notes, 5 (1969), 
pp. 138-140. 

F. AuRENHAMMER, A criterion for the affine equivalence of cell complexes in M'' and convex poly- 
hedra in Discrete Comput. Geometry, 2 (1987), pp. 49-64. 

F. AuRENHAMMER, F. HOFFMANN, AND B. Aronov, Minkowski-type theorems and least-squares 
partitioning, in 8th Annual Symp. Comput. Geometry (SoCG), Berlin, June 1992, ACM, 1992, 
pp. 350-357. 

, Minkowski-type theorems and least-squares clustering, Algorithmica, 20 (1998), pp. 61-76. 

F. AuRENHAMMER AND R. Klein, Voronoi diagrams, in Handbook of Computational Geometry, 
J. Sack and G. Urrutia, eds., Elsevier, 2000, ch. V, pp. 201-290. 

D. Ayala AND R. Hepworth, Configuration spaces and On- Preprint, February 2012, 12 pages, 
Ihttp : //arxiv . org/abs/1202 . 2806 

L Barany, P. V. M. Blagojevic, and A. Szucs, Equipartitioning by a convex 3-fan, Advances 
in Math, 223 (2010), pp. 579-593. 

L Basabe, J. Gonzales, Y. B. Rudyak, and D. Tamaki, Higher topological complexity and 
homotopy dimension of configuration spaces of spheres. Preprint, 36 pages, Sept. 2010; version 4, 
50 pages, April 2011; | http : //arxivT org/abs/1009 . 1851| 

A. BjORNER, Subspace arrangements, in Proc. of the First European Congress of Mathematics 
(Paris 1992), vol. I, Birkhauser, 1994, pp. 321-370. 

A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler, Oriented 
Matroids, vol. 46 of Encyclopedia of Mathematics, Cambridge University Press, Cambridge, second 
(paperback) ed., 1999. 

A. Bjorner and G. M. Ziegler, Combinatorial stratification of complex arrangements, Journal 
Amer. Math. Soc, 5 (1992), pp. 105-149. 

P. V. M. Blagojevic and A. S. Dimitrijevic Blagojevic, Using equivariant obstruction theory 
in combinatorial geometry, Topology and its Applications, 154 (2007), pp. 2635-2655. 

P. V. M. Blagojevic, W. LiicK, and G. M. Ziegler, Equivariant topology of configuration 
spaces. Preprint in preparation, February 2012. 

M. E. Chisholm, k-regular mappings of 2" -dimensional euclidean space, Proc. Amer. Math. Soc, 
74 (1979), pp. 187-190. 

F. R. Cohen and D. Handel, k-regular embeddings of the plane, Proc. Amer. Math. Soc, 72 
(1978), pp. 201-204. 

G. E. Cooke and R. L. Finney, Homology of Cell Complexes, Mathematical Notes, Princeton 
University Press, Princeton, NJ, 1967. 

C. DE CONCINI and M. Salvetti, Cohomology of Coxeter groups and Artin groups. Math. Research 
Letters, 7 (2000), pp. 213-232. 

P. Deligne, Les immeubles des groupes de tresses generalises, Inventiones Math., 17 (1972), pp. 273- 
302. 



16 



[19] L. C. Evans, Partial differential equations and Monge-Kantorovich mass transfer, in Current De- 
velopments in Mathematics, Boston, MA, 1999, Int. Press, pp. 65-126. 

R. Fox AND L. Neuwirth, The braid groups, Math. Scandinavica, 10 (1962), pp. 119-126. 
D. B. FuKS, Cohomologies of the braid groups mod 2, Fmictional Anal. AppL, 24 (1970), pp. 143- 
151. 

I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, Resultants, and 
Multidimensional Determinants, Birkhauser, Boston, 1994. 

C. GiUSTi AND D. Sinha, Fox-Neuwirth cell structures and the cohomology of the symmetric group. 



Preprint, October 2011, 18 pages, http : //arxiv . org/abs/1110 . 4137 



M. GORESKY AND R. D. MacPherson, Stratified Morse Theory, vol. 14 of Ergebnisse Series, 
Springer Verlag, 1988. 

A. Hubard and B. Aronov, Convex equipartitions of volume and surface area. Preprint, October 
2010, 9 pages; version 3, September 2011, 17 pages; http : //arxiv . org/abs/1010 .4611] 

H. Joris, C. Oestreicher, and J. Steinig, The greatest common divisor of certain sets of 
binomial coefficients, J. Number Theory, 21 (1985), pp. 101-119. 

L. V. Kantorovich, a new method of solving some classes of extremal problems, Doklady Akad. 
Sci. USSR, 28 (1940), pp. 211-214. 

G. Kaplan and D. Levy, GCD of truncated rows in Pascal's triangle, INTEGERS: Electronic J. 
Comb. Number Theory, 4 (2004), p. #A14. http : //www . emis . de/ j ournals/INTEGERS/papers/| 
|el4/el4.p"df] 



R. N. Karasev, Equipartition of several measures. Preprint, November 2010, 6 pages; version 6, 
August 2011, 10 pages; http://arxiv.org/abs/1011.4762 

H. Minkowski, Allgemeine Lehrsdtze iiber konvexe Polyeder, Nachr. Ges. Wiss. Gottingen, (1897), 
p. 198-219. Reprinted in Gesammelte Abhandlungen II (Leipzig and Berlin, 1911) 103-121. 

, Volumen und Oberfldche, Math. Annalen, 57 (1903), p. 447-495. Reprinted in Gesammelte 

Abhandlungen II (Leipzig and Berlin, 1911) 230-276. 

J. R. Munkres, Elements of Algebraic Topology, Addison- Wesley, Menlo Park, CA, 1984. 



R. Nandakumar, "Fair" partitions. Blog entry, |http : //nandacumar . blog spot . de/2006/09/ 
[cutting- shapes .html, September 28, 2006. 

R. Nandakumar and N. Ramana Rao, 'Fair' partitions of polygons: An introduction. Preprint, 
December 2008, 28 pages; version 6, November 2010, 7 pages; http://arxiv.org/abs/0812.224l] 
Proc. Indian Academy of Sciences - Mathematical Sciences, to appear. 

B. Ram, Common factors of ; (m- = 1, 2, . . . n — 1), J. Indian Math. Club (Madras), 1 
(1909), pp. 39-43. 

M. Salvetti, Topology of the complement of real hyperplanes in , Inventiones Math., 88 (1987), 
pp. 603-618. 

D. Siersma and M. van Manen, Power diagrams and applications. Preprint, 23 pages, August 
2005; http : //arxiv . org/abs/math/0508037, 

C. SOULE, Secant varieties and successive minima, J. Algebraic Geometry, 13 (2004), pp. 323-341. 
T. TOM DiECK, Transformation Groups, vol. 8 of Studies in Mathematics, Walter de Gruyter, Berlin, 
1987. 

V. A. Vassiliev, Braid group cohomologies and algorithm complexity. Functional Analysis AppL, 
22 (1988), pp. 182-190. 

, Complements of Discriminants of Smooth Maps: Topology and Applications, vol. 98 of Trans- 
lations of Math. Monographs, American Math. Soc,, Providence, RI, 1992. 

C. ViLLANi, Topics in Optimal Transportation, vol. 58 of Graduate Studies in Math., Amer. Math. 
Soc, 2003. 

G. M. ZiEGLER, Lectures on Polytopes, vol. 152 of Graduate Texts in Math., Springer- Verlag, New 
York, 1995. Revised edition, 1998; seventh updated printing 2007. 



17