MIN-TYPE MORSE THEORY FOR CONFIGURATION SPACES OF HARD SPHERES  YULIY BARYSHNIKOV, PETER BUBENIK, AND MATTHEW KAHLE  We dedicate this paper to the memory of Boris Lubachevsky.  Abstract.   In this paper we study configuration spaces of hard spheres in a bounded region.   We develop a general Morse-theoretic framework and show that mechanically balanced configurations play the role of critical points. As an application, we find the precise threshold radius for a configuration space to be homotopy equivalent to the configuration space of points.  1.   Introduction  Configuration spaces of   n   points in   R d   are well studied [4]. In this article we are interested in a natural generalization, configuration spaces of non-overlapping balls in a bounded region in   R d . Besides their intrinsic mathematical interest, the study of these spaces is mo- tivated by physical considerations.   For example, in statistical mechanics “hard spheres” (or in two dimensions “hard disks”) are among the most well-studied models of matter. Computer simulations suggest a solid-liquid phase transition for hard spheres [17], but this is not well understood mathematically. A number of papers in statistical mechanics have explored the hypothesis that underpinning phase transitions are changes in the topology of the underlying con- figuration space or equipotential submanifolds [24, 16, 1, 9]. Franzosi, Pettini, and Spinelli show that under fairly general conditions (smooth, finite-range, confining potentials), the Helmholtz free energy cannot pass through a phase transition unless there is a change in the topology of the underlying configuration space [11, 10]. This theorem unfortunately does not apply to configuration spaces of hard spheres, since the potential function is not smooth — but the Morse-theoretic methods developed here may be a step in the direction of extending it to include hard spheres. Several other papers have investigated configuration spaces as models of motion planning for robots [8, 13]. For example, Farber’s “topological complexity” can be thought of as measuring the difficulty of designing an algorithm for navigating the space. As Deeley recently pointed out when he studied “thick particles” on metric graphs, the assumption that robots are points is not physically realistic, and giving the points thickness wildly complicates the topology of the underlying configuration space [6]. Let   B   be a bounded region in   R d . Define   Conf ( n, r ) to be the configuration space of   n   non-overlapping balls of radius   r   in   B .   We are especially interested here in understanding when the topology changes if   n   is fixed and   r   is varying . First we consider the extreme cases. For   r   sufficiently small, one expects that   Conf ( n, r ) is  The third author thanks IAS and NSA Grant # H98230-10-1-0227.  1  arXiv:1108.3061v2 [math.AT] 29 Aug 2011
2   YULIY BARYSHNIKOV, PETER BUBENIK, AND MATTHEW KAHLE  homotopy equivalent to the configuration space   Conf ( n ) of   n   distinct points in   B  — for a survey of configuration spaces of points see Cohen [4]. On the other hand for   r   sufficiently large,   Conf ( n, r ) is empty.   Indeed finding the smallest such   r   is the sphere packing problem in a bounded region — see for example Graham et al. [15, 2, 18, 19] and Melissen [22, 21]. In this note we develop a Morse-theoretic framework which provides a necessary condition for the topology to change — mechanical balanced configurations play the role of critical points (and submanifolds). As an illustration of the method, we find the precise threshold radius below which   Conf ( n, r ) is homotopy equivalent to  Conf ( n ). 2.   Tautological Morse function  Fix   n , and define   Conf ( n ) to be the set of ordered   n -tuples of distinct points in a bounded domain   B ⊂   R d :  Conf ( n ) =   { ~ x   = ( x 1 , . . . , x n )   |   x i   ∈ B , x i   6   =   x j   for   i   6   =   j } .  As an open subset of   R dn ,   Conf ( n ) has the structure of a smooth manifold. Let  τ   :   Conf ( n )   →   R   be defined by (1)   τ   ( ~ x ) := min  (   1 2 min  i 6   = j   d ( x i , x j   ) ,   min  i   min  p ∈ ∂ B   d ( x i , p )  )  ,  where   ∂ B   denotes the boundary of   B .   We call   τ   the tautological function.   Then by definition the configuration space of   n   balls of radius   r   in   B   is given by  Conf ( n, r ) =   τ   − 1 [ r,   ∞ ) .  This observation suggests using a “Morse”-type theory of   τ   to study the topology of   Conf ( n, r ) and especially how the topology changes as   r   varies.   One obvious trouble on that route is the fact that   τ   typically is not smooth, so that we need a general framework which allows us to work with non-smooth functions. In the next section we will discuss the properties of   min -type functions, that is functions on a manifold   M   given as the minimum of a parametric family of real valued functions  τ   ( x ) := min  p   f   ( p, x ) , x   ∈   M, p   ∈   P,  where   P   is a compact parameter space, and   f   is continuously differentiable in   x  for every fixed   p   ∈   P   .   We note that the function given by (1) falls within this category, if one considers as   P   the disjoint union of the discrete set corresponding to pairs ( i, j ) ,   1   ≤   i < j   ≤   n   and of   n   copies of the boundary, formed by the pairs ( i, p ) ,   1   ≤   i   ≤   n, p   ∈   ∂ B . It should be remarked that the Morse-type theory of the   min   (or even   min-max ) type functions has appeared in the literature (compare [20, 3, 12]), but in a much more restrictive context (with essentially finite parameter space). 3.   Min-type Morse theory  Let us start with some notation and definitions. For a manifold   M   and function   f   :   M   →   R , let   M   c   denote the superlevel set at  c , i.e.   M   c   =   f   − 1 [ c,   ∞ ).
MIN-TYPE MORSE THEORY FOR CONFIGURATION SPACES OF HARD SPHERES   3  We say that a function   h   : ( s, t )   →   R , is   increasing with speed at least   v >   0 if  h ( t ′ )   −   h ( s ′ )   ≥   v ( t ′   −   s ′ ) for any   s ′   < t ′   in the interval ( s, t ). We note that such a function does not have to be even continuous. We record for later use the following (immediate) result:  Lemma 3.1.   Let   f   :   M   ×   R   →   R   be a continuous proper function, (strictly) increasing along each fiber   { x } ×   R . Then the fiber-wise inverse   φ   : ( x, c )   7   →   inf( t   :  f   ( x, t ) =   c )   is continuous on   M   ×   [ c 1 , c 2 ]   for any interval   [ c 1 , c 2 ]   which belongs to the ranges of all the functions   f x ( · ) :=   f   ( x,   · ) . Proof.   As   f   is proper, then the   t -projection of the preimage of a compact interval [ c 1 , c 2 ] is compact as well. Further, if a sequence ( x i , c i ) converges to ( x ∗ , c ∗ ), yet  t i   :=   φ ( x i , c i ) fails to converge to   t ∗   :=   φ ( x ∗ , c ∗ ), we can, using the boundedness of the sequence ( t i ), choose a subsequence such that along it   t j   →   t   6   =   t ∗ .   By continuity, lim   f   ( x j   , t j   ) =   f   ( x ∗ , t ) (as   x j   converge to   x ∗ ). The fact that   f   ( x j   , t j   ) =  c j   implies that   f   ( x ∗ , t ) equals   c ∗ , which by the continuity of   f   also equals   f   ( x ∗ , t ∗ ). This contradicts the assumption that   f   increases fiber-wise.     For a smooth vector field   V   on   M   we will denote the time   t   shift along the trajectories of   V   as   S V t   .   We will say that the function   f   increases along the tra- jectories of   V   with non-zero speed , if for some common   v >   0, and for all   x   ∈   M   ,  h x   :   t   7   →   f   ( S V t   x ) increases with speed at least   v .  Lemma 3.2.   Let   M   be a smooth manifold and   f   :   M   →   R   a continuous function, such that   M   a   is compact.   Suppose that   M   admits a smooth vector field   V   non- vanishing on   f   − 1 [ a, b ] , and such that   f   is increasing along the trajectories of   V   on the set   f   − 1 [ a, b ]   with non-zero speed. Then   M   b   is a deformation retract of   M   a .  Lemma 3.2 can be seen as a generalization of Theorem 3.1 in [23] for non-smooth functions   f   . We remark here that one can drop here the non-zero speed condition, requiring only that   f   is increasing along the trajectories of   V   , but we do not need this strengthened form in this paper.  Proof.   For   x   ∈   M   a   set a partially defined function on   M   a   × R   by   g ( x, t ) :=   f   ( S V t   x ). The non-zero speed condition implies that [ a, b ] is in the range of   g ( x,   · ) for any  x   ∈   f   − 1 ([ a, b ]), and together with the compactness of   M   a   implies that   g   is proper. Hence, by Lemma 3.1,  ̃ φ ( x, c ) = inf( t   :   f   ( S V t   x )   ≥   c ) is well defined and continuous, as well as   φ ( x, c ) = max(  ̃ φ ( x, c ) ,   0). As for any   c   ≤   f   ( x ),   φ ( x, c ) = 0,   φ   vanishes on  M   b   ×   [ a, b ]. Now define the homotopy  H   :   M   a   ×   [0 ,   1]   →   M   a  as  H   : ( x, τ   )   7   →   S V φ ( x, (1 − τ   ) a + τ b ) x.  Continuity of   φ   implies continuity of   H ; the facts that   H ( x,   0) =   id   M   a   ,   H ( x, τ   ) | M   b   =  id   M   b   for 0   ≤   τ   ≤   1 and   H ( x,   1)   ∈   M   b   are immediate.     3.1.   Regular values of   min -type functions.   Next we will use the fact that the tautological function   τ   is the minimum of a compact family of smooth functions. We want to establish conditions when a value   c   is   topologically regular , that is for which there exists some    >   0 such that   M   c +    is a deformation retract of   M   c −  . We give a general condition for topological regularity, as follows.
4   YULIY BARYSHNIKOV, PETER BUBENIK, AND MATTHEW KAHLE  Let   P   be a compact metric space,   M   a compact smooth manifold with boundary and  f   :   P   ×   M   →   R  a continuous function such that the   x -derivative of   f   (that is, the gradient of   f p , where   f p ( x ) =   f   ( p, x )) is continuous on   P   ×   M   .   We will be talking of   P   as the  parameter space . We denote by   τ   := min p ∈ P   f p   the   min -function of the family   f   .   The set   N   ⊂  P   ×   M   defined by  N   :=   { ( p, x ) :   f   ( p, x ) =   τ   ( x ) }  is compact, and the slices  N x   :=   { p   ∈   P   : ( p, x )   ∈   N   }  are   upper semi-continuous : for any   x   ∈   M   and any open neighborhood   U N x   ⊃   N x  there exists an open neighborhood   U x   3   x   such that for   x ′   ∈   U x ,   N x ′   ⊂   U N x . Next we show that if one can perturb each   x   to increase   τ   then we can do so globally with a minimum speed.  Lemma 3.3.   Assume that for any   x   ∈   M   , there exists a tangent vector   V x   ∈   T x M  such that   L V x   f p   >   0   for all   p   ∈   N x . Then  •   for some positive   v   there exists smooth vector   field   V   on   M   such that  L V   f p   ≥   v >   0   in some open vicinity of   N   , and  •   along the trajectories of   V   , the   min -function   τ   increases with speed at least  v . Proof.   For any   x   ∈   M   , we can extend the vector   V x   ∈   T x M   to a smooth vector field on   M   (which we still denote as   V x ), such that   L V x   f >   0 in some open vicinity  U N x   ×   U x   of   N x   × { x } . By compactness, there exists a finite collection of points  { x i }   in   M   such that the open sets   U i   :=   U N x i   × U x i   cover   N   (and the open sets   U x i  cover   M   ), and   v >   0 such that   L V i   f p   ≥   v   on   U i   (here   V i   :=   V x i   ). Using a partition of unity we arrive at the first conclusion. The second conclusion is immediate.     For   x   ∈   M   consider the intersection of the open half-spaces  H x ( p ) :=   { v   ∈   T x M   :   〈 df p | x , v 〉   >   0 }  over all   p   ∈   N x . This is an open convex cone  C o x   :=   ⋂  p ∈ N x  H x ( p ) in   T x M   . Upper semicontinuity of   N x   implies lower semicontinuity of   C o x ; for any   x   ∈   M  and any open set   V   ⊂   T M   intersecting   C o x , there exists an open neighborhood  U x   3   x   such that for   x ′   ∈   U x ,   C o x ′   intersects   V   . In particular, if   C o x   is non-empty, it remains such in a vicinity of   x . Combining Lemmata 3.2 and 3.3 we obtain the following  Corollary 3.4.   If the cones   C o x   are non-empty over the level set   τ   − 1 ( c ) , then   c   is topologically regular.  For general   min -type functions this is essentially the best possible condition for the regularity of the critical values.   If the functions   f p   are   quasi-convex , i.e. have convex lower excursion sets   { f p   ≤   c } , then Corollary 3.4 can be considerable
MIN-TYPE MORSE THEORY FOR CONFIGURATION SPACES OF HARD SPHERES   5  strengthened. Thus, one can show (we will do it in a follow-up paper) that a critical value is topologically regular, if for all points at the level set, the intersection of the   closed   half-spaces is a cone over a contractible base. This observation relies on stratified Morse theory due to Goresky and MacPherson[14], but is in a nutshell close to the elementary result used by Connelly in his work on the existence of continuous “unlocking” deformations of hard ball configurations, see [5]. Corollary 3.4 implies that unless the level set of the tautological function   τ   − 1 ( r ) contains a point   x   with   C o x   =   ∅ , the homotopy type of   Conf ( n, r ) is locally constant at   r . By Farkas’ lemma, the emptiness of the cone   C o x   implies that there exists a finite collection of points   p i   ∈   N x , i   = 1 , . . . , I   ≤   dim   M   + 1, and positive weights   w i   >   0 such that (2)   ∑  i  w i df p i   | x   = 0 .  4.   Critical points and stress graphs  In our hard spheres setting, the vanishing of the convex combination (2) has a clear geometric interpretation. For   ~ x   ∈   Conf ( n, r ), define a   stress graph   of   ~ x   to be a graph embedded in   R d   whose vertices are the points   x 1 , . . . , x n   and boundary points   y   ∈   ∂ B   where   d ( x i , y ) =   r  for some   i . The edges are the pairs   { x i , x j   }   where   d ( x i , x j   ) = 2 r   and   { x i , y }   where  d ( x i , y ) =   r .   Each edge   k   is assigned a positive weight   w k .   The points   x i   are referred to as   internal points   and the points   y   are referred to as   boundary points . We interpret this graph as a system of   mechanical stresses , with (repulsive) forces acting on the endpoints of a segment   k   equal to   w k   times the unit vector in the direction of   k .   Call the mechanical stresses acting on boundary points   boundary mechanical stresses .   Call a connected component   trivial   if it consists of a single point. Call   ~ x   trivial if Γ( ~ x ) has no edges. A stress graph is said to be   balanced   if it satisfies the following condition.  •   The mechanical stresses at each internal point sum to zero. 1  •   The boundary mechanical stresses on each connected component sum to zero. Say that the configuration is   ~ x   is   balanced   if it has a balanced stress graph. Call an internal point   isolated   if it is not in the boundary of any edges.   For each point   x i   call the intersection of the stress graph with the points on the sphere  d ( x i , x ) =   r   kissing points   of   x i . Call a kissing point that is also a boundary point a   boundary kissing point .  Lemma 4.1.   Assume that   ~ x   ∈   Conf ( n, r )   is balanced. Then  (1)   each non-isolated internal point is in the convex hull of its kissing points, and  (2)   each non-trivial connected component is contained in the convex hull of its boundary kissing points.  Now consider   ~ x   ∈   Conf ( n ) that is a critical point of   τ   with critical value   r . In (2), the parameters   p i   correspond either to the pairs of touching hard spheres,  d ( x a i   , x b i   ) = 2 r , or to the hard sphere   x c i   touching the boundary,   d ( x c i   , y i ) =   r ,  1 This result is similar to the necessary conditions for “locking”, see e.g. [5].
6   YULIY BARYSHNIKOV, PETER BUBENIK, AND MATTHEW KAHLE  at a point   y i   ∈   ∂ B . Let Γ( ~ x ) be the corresponding stress graph for   ~ x   with weights given by the coefficients   w i   in (2).  Theorem 4.2.   If   ~ x   ∈   Conf ( n )   is a critical point of   τ   with critical value   r , then   ~ x  is balanced and nontrivial as a point in   Conf ( n, r ) . Proof.   Consider   ~ x   ∈   Conf ( n, r ) and consider Γ( ~ x ).   From (2) it follows that the mechanical stresses at each internal point sum to zero. The sum of mechanical stresses in each connected component equals the sum of mechanical stresses on internal points and the sum of external mechanical stresses. From (2) and the first observation it follows that the boundary mechanical stresses on each connected component sum to zero. Finally, since the sum in (2) is nontrivial,   ~ x   is nontrivial.     5.   Hard spheres in a box  Consider now in more detail the case of hard spheres in a rectangular box with sides   L   :=   L 1   ≤   . . .   ≤   L d , given, for definitiveness sake, by  B   =   { 0   ≤   f m   ≤   L m , m   = 1 , . . . , d } .  (Here   { f m }   is the orthonormal coordinate system on   R d .) 5.1.   Initial interval.   We show that Theorem 4.2 implies a lower bound on the length of the initial interval of values of   r , where the homotopy type of   Conf ( n, r ) remains constant.  Theorem 5.1.   For the rectangular box   B , there are no critical values of   τ   in  (0 , L/ 2 n ) , and therefore,  Conf ( n, r )   '   Conf ( n )  for   r < L/ 2 n . Proof.   Assume that   ~ x   ∈   Conf ( n ) is a critical value for   τ   with critical value   r . Then by Theorem 4.2,   ~ x   is balanced and nontrivial.   A connected component of Γ( ~ x ) contains at most   n   internal points and thus has diameter at most 2 nr . Since   ~ x   is nontrivial, it has at least one nontrivial connected component.   It is contained in the convex hull of its boundary points, so it contains at least one boundary point. Since the boundary mechanical stresses of this connected component sum to zero, it must contain a pair of boundary points from opposing faces. Thus the diameter of this connected component is at least   L . Therefore   r   ≥   L/ 2 n .     We remark that the balanced stress graph of minimal diameter is not necessarily a segment, for non-rectangular boxes. For example, for the “concave triangle”, it is a cone over three points, see Figure 1. 5.2.   First perestroika.   A natural question is now to ask, whether there is a topol- ogy change as   nr   goes above the minimal length of the stress graph. We concentrate in the rest of the note on the case of the rectangular box with the shortest side of length   L , and will investigate, whether  i   :   Conf ( n, r ′ )   →   Conf ( n, r ) , r ′   =   L/ 2 n   +   , r   =   L/ 2 n   −     is a homotopy equivalence, for small enough    . We argue that it is not, by presenting explicit nontrivial ( dn   −   n   −   d )-cycles in ker( Hi )   ⊂   H dn − n − d ( Conf ( n, r ′ ) ,   Z ).
MIN-TYPE MORSE THEORY FOR CONFIGURATION SPACES OF HARD SPHERES   7  Figure 1.   Minimal length stress graph Indeed, let 0   <  < L/ 2 n ( n   −   1) (so that ( n   −   1) disks of radius   r ′   would fit within the box when arranged in a vertical column, and   n   would not), and consider the set   S    of   n -point configurations in   B   given by the conditions  •   x 1   fixed is at distance   r ′   from the center of the face   { f 1   = 0 } ,  • | x i +1   −   x i |   = 2 r ′   for   i   = 1 , . . . n   −   1, and  •   x n   is at distance   r ′   from the face   { f 1   =   L 1 } . In other words, we consider the configurations for which the   n   disks touch each other and the opposite horizontal faces, forming a chain, see Figure 2.  Figure 2.   A configuration in   S  . An immediate computation shows that   S    is diffeomorphic to a ( nd   −   n   −   d )- dimensional sphere. Orient it in some way, obtaining a class   s   ∈   H nd − n − d ( Conf ( n, r ′ )). Next we show that   s   is nontrivial by constructing a cohomology class with which it has a nontrivial pairing. Consider now the set Σ of configurations in   B n   given by  •   all points   x 1 , . . . , x n   have the same coordinates   f 3 , . . . , f d ;  •   all points   x 2 , . . . , x n   have the same coordinates   f 2 , . . . , f d ;
8   YULIY BARYSHNIKOV, PETER BUBENIK, AND MATTHEW KAHLE  •   the   f 1   coordinates of   x 2 , . . . , x n   satisfy  f 1 ( x 1 )   ≥   r ;   f 1 ( x i +1 )   −   f 1 ( x i )   ≥   2 r,   for   i   = 2 , . . . , n   −   1;   f 1 ( x n )   ≤   L   −   r,  and  •   f 2 ( x 1 )   ≤   f 2 ( x 2 ). In other words, the configuration consists of   n   −   1 vertically aligned nonover- lapping   r -disks constrained to have the same ( f 1 , f 2 )-plane (with the same   f 3 , . . . d  coordinates as the disk   x 1 ), see Figure 3. f 1 2 f  Figure 3.   A configuration in Σ. The conditions above are given by a finite collection of linear equalities and inequalities, and therefore define a convex polyhedron of dimension   d   +   n .   The boundary of this polyhedron is in   B n   −   Conf ( n, r ′ ), whence, upon orientation it defines a relative class   σ   ∈   H n + d ( B n ,   B n   −   Conf ( n, r ′ )). We notice that the space   B n   of   n -tuples of points in   B   can be embedded into the   nd -dimensional sphere   S nd   (consider a large ball containing   B n   and contract its boundary to a point).   By excision and the long exact sequence for a pair,  H n + d ( B n ,   B n   −   Conf ( n, r ′ ))   ∼ =   H n + d ( S nd , S nd   −   Conf ( n, r ′ ))   ∼ =   H n + d − 1 ( S nd   −  Conf ( n, r ′ )). By Alexander duality the class   σ   can be identified with a class (which we still denote by   σ ) in   H nd − n − d ( Conf ( n, r ′ )).  Lemma 5.2.   The pairing between the classes   s   and   σ   is non-trivial:   s   ·   σ   =   ± 1 . Proof.   Indeed, the manifolds   S    and Σ intersect transversally at a single point.     As one can observe, there exists a retraction of   S    to a point staying within  Conf ( n, r ), implying that the class   s   is in the kernel of   Hi .   Indeed, we first can reduce all the distances between by shrinking the differences between the adjacent chain centers so that  x i +1   −   x i   7   →   tr   −   (1   −   t ) r ′  r ′   ( x i +1   −   x i ) , t   = [0 ,   1];   i   = 1 , . . . , n   −   1 and   x 1   remains fixed (clearly, this homotopy keeps the configuration in   Conf ( n, r )). Then one can pull all the vectors ( x i +1   −   x i ) so that they point vertically upwards 2  (as not one was initially pointing downwards).  2 We think of   f 1   as height.
MIN-TYPE MORSE THEORY FOR CONFIGURATION SPACES OF HARD SPHERES   9  For each permutation   π   of indices 1 , . . . , n   one obtains different classes   s π   , and one can easily see that the pairing with the corresponding   n ! classes   σ π   is non- degenerate (because corresponding   S    and Σ’s are all geometrically distinct). Hence, the rank of the kernel of   Hi   is at least   n !. We notice that the sphericity of the set   S    does not depend on the fact that the stress graph is a chain. For the configuration on Figure 1, the corresponding set is diffeomorphic to a sphere as well: it is just the corollary of the first critical value coming from a   topologically Morse   critical point, compare [20]. 5.3.   Betti numbers.   We can also compute how the Betti numbers change across the first threshold.   Set   r ∗   =   L/ 2 n , and note that as the tautological function is semi-algebraic for semi-algebraic regions, its critical values are isolated.   As the only balanced stress graphs in the case of a rectangular domain are the chains spanning the shortest dimension, for some small      there are no other critical values in ( r ∗   −   , r ∗   +    ). It is well known [4] that the configuration space   Conf ( n ) of   n   (labeled) points in  R d   has Poincar ́ e polynomial  P   ( t ) :=   ∑  i ≥ 0  β i t i  =  n − 1 ∏  i =1  ( 1 +   it d − 1 )  = 1 +   · · ·   + ( n   −   1)! H n − 1 t ( n − 2)( d − 1)   + ( n   −   1)! t ( n − 1)( d − 1) ,  where  H n − 1   =  n − 1 ∑  i =1  1 /i.  This tells us the Betti numbers of   Conf ( n, r ∗   −    ), since we have already shown that   Conf ( n, r ∗   −    ) is homotopy equivalent to   Conf ( n ). We wish to compute the Betti numbers of   Conf ( n, r ∗   +    ). Let   N   = ( n − 1)( d − 1). As we shrink the disks across the critical value   r ∗   =   L/ 2 n , to the configuration space we attach   k n ! cells of dimension   N   , where   k   is the largest number such that   L k   =   L , whose boundaries are representatives for the homology classes   s   defined in Section 5.2. Each of these cells either increments   β N  or decrements   β N   − 1 . The first observation is that  β i [ Conf ( n, r ∗   +    )] =   β i [ Conf ( n, r ∗   −    )] for   i   ≤   N   −   2.   As (the proof to appear in a follow-up paper) one can show that  β i ( Conf ( n, r )) = 0 for   i   ≥   N   and   r > r ∗ , so in particular  β i [ Conf ( n, r ∗   +    )] = 0 for   i   ≥   N   .   Thus ( n   −   1)! of the   N   -cells increase   β N   .   This leaves only   β N   − 1   to compute. Every   N   -cell that does not contribute to   β N   decreases   β N   − 1 .   Since we know that   kn ! cells are added, ( n   −   1)! of them contributing to   β N   , we have  β N   − 1 [ Conf ( n, r ∗   +    )] =   β N   − 1 [ Conf ( n, r ∗   −    )] +   k n !   −   ( n   −   1)!   ,
10   YULIY BARYSHNIKOV, PETER BUBENIK, AND MATTHEW KAHLE  and since  β N   − 1 [ Conf ( n, r ∗   −    )] =  {   ( n   −   1)! H n − 1   :   d   = 2 0   :   d   ≥   3 ,  we have  β N   − 1 [ Conf ( n, r ∗   +    )] =  {   ( H n − 1   +   kn   −   1)( n   −   1)!   :   d   = 2 ( kn   −   1)( n   −   1)!   :   d   ≥   3 .  6.   Concluding remarks  In a future article we will discuss non-degeneracy of critical points, which is closely related to the question of making our necessary condition for a change in the topology sufficient. We also discuss defining and computing the index of critical points, and especially investigate more of the asymptotic properties of   Conf ( n, r ) as   n   → ∞ . In particular we obtain bounds on the rate of growth of Betti numbers. An important special case for which little seems known is: What is the threshold radius   r   =   r ( n ) for connectivity of   Conf ( n, r )? This is an important question phys- ically, since for example ergodicity of any Markov process hinges on connectivity of the state space. Diaconis, Lebeau, and Michel noted that   r   ≤   c/n   is sufficient to guarantee connectivity of   Conf ( n, r ) [7] and this is best possible for certain re- gions.   It would be interesting to know if connectivity of the configuration space ever extends into the thermodynamic limit, i.e. are there any bounding regions so that   Conf ( n, r ) is connected for   r   ≤   Cn − 1 /d   and some constant   C >   0?  Acknowledgments  We thank AIM and for hosting the workshop on, “Topological complexity of random sets” in August 2009, where we started discussing some of these problems. Y.B. was supported in part by the ONR grant 00014-11-1-0178. M.K. thanks IAS for hosting him this year and Robert MacPherson for several helpful conversations.  References  [1] Luca Angelani, Lapo Casetti, Marco Pettini, Giancarlo Ruocco, and Francesco Zamponi. Topology and phase transitions: From an exactly solvable model to a relation between topol- ogy and thermodynamics.   Phys. Rev. E , 71(3):036152, Mar 2005. [2] David W. Boll, Jerry Donovan, Ronald L. Graham, and Boris D. Lubachevsky. Improving dense packings of equal disks in a square.   Electron. J. Combin. , 7:Research Paper 46, 9 pp. (electronic), 2000. [3] L. N. Bryzgalova. The maximum functions of a family of functions that depend on parameters.  Funktsional. Anal. i Prilozhen. , 12(1):66–67, 1978. [4] Frederick R. Cohen. Introduction to configuration spaces and their applications. In   Braids , volume 19 of   Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. , pages 183–261. World Sci. Publ., Hackensack, NJ, 2010. [5] Robert Connelly. Rigidity of packings.   European J. Combin. , 29(8):1862–1871, 2008. [6] Kenneth Deeley. Configuration spaces of thick particles on a metric graph. submitted, 2011. [7] Persi Diaconis, Gilles Lebeau, and Laurent Michel. Geometric analysis for the Metropolis algorithm on Lipschitz domains. To appear in Invent. Math. [8] Michael Farber.   Invitation to topological robotics . Zurich Lectures in Advanced Mathematics. European Mathematical Society (EMS), Z ̈ urich, 2008. [9] Michael Farber and Viktor Fromm. Homology of planar telescopic linkages.   Algebr. Geom. Topol. , 10(2):1063–1087, 2010. [10] Roberto Franzosi and Marco Pettini. Topology and phase transitions II. Theorem on a nec- essary relation.   Nuclear Physics B , 782(3):219 – 240, 2007. [11] Roberto Franzosi, Marco Pettini, and Lionel Spinelli. Topology and phase transitions I. Pre- liminary results.   Nuclear Physics B , 782(3):189 – 218, 2007.
MIN-TYPE MORSE THEORY FOR CONFIGURATION SPACES OF HARD SPHERES   11  [12] V. Gershkovich and H. Rubinstein. Morse theory for Min-type functions.   Asian J. Math. , 1(4):696–715, 1997. [13] Robert Ghrist. Configuration spaces, braids, and robotics. In   Braids , volume 19 of   Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. , pages 263–304. World Sci. Publ., Hackensack, NJ, 2010. [14] Mark Goresky and Robert MacPherson.   Stratified Morse theory , volume 14 of   Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)] . Springer-Verlag, Berlin, 1988. [15] R. L. Graham and B. D. Lubachevsky. Repeated patterns of dense packings of equal disks in a square.   Electron. J. Combin. , 3(1):Research Paper 16, approx. 17 pp. (electronic), 1996. [16] Paolo Grinza and Alessandro Mossa. Topological origin of the phase transition in a model of DNA denaturation.   Phys. Rev. Lett. , 92(15):158102, Apr 2004. [17] Hartmut L ̈ owen. Fun with hard spheres. In   Statistical physics and spatial statistics (Wup- pertal, 1999) , volume 554 of   Lecture Notes in Phys. , pages 295–331. Springer, Berlin, 2000. [18] B. D. Lubachevsky and R. L. Graham. Curved hexagonal packings of equal disks in a circle.  Discrete Comput. Geom. , 18(2):179–194, 1997. [19] Boris D. Lubachevsky, Ron L. Graham, and Frank H. Stillinger. Patterns and structures in disk packings.   Period. Math. Hungar. , 34(1-2):123–142, 1997. 3rd Geometry Festival: an International Conference on Packings, Coverings and Tilings (Budapest, 1996). [20] V. I. Matov. Topological classification of the germs of functions of the maximum and minimax of families of functions in general position.   Uspekhi Mat. Nauk , 37(4(226)):167–168, 1982. [21] Hans Melissen. Densest packings of eleven congruent circles in a circle.   Geom. Dedicata , 50(1):15–25, 1994. [22] J. B. M. Melissen. Optimal packings of eleven equal circles in an equilateral triangle.   Acta Math. Hungar. , 65(4):389–393, 1994. [23] J. Milnor.   Morse theory . Based on lecture notes by M. Spivak and R. Wells. Annals of Mathematics Studies, No. 51. Princeton University Press, Princeton, N.J., 1963. [24] Ana C. Ribeiro Teixeira and Daniel A. Stariolo. Topological hypothesis on phase transitions: The simplest case.   Phys. Rev. E , 70(1):016113, Jul 2004.  Departments of Mathematics and ECE, UIUC, Urbana, IL  E-mail address :   ymb@uiuc.edu  Department of Mathematics, Cleveland State University  E-mail address :   p.bubenik@csuohio.edu  School of Mathematics, Institute for Advanced Study, Princeton NJ 08540  E-mail address :   mkahle@math.ias.edu