One popular problem in applied probability deals with the coverage problem: place randomly $n$ disks of radii $r$ in a domain $Y$ (say, spherical caps on a sphere); what is the probability that their union covers the whole domain $Y$?
A great deal is known about this problem which can be formulated as follows:
Let $\cov_Y(n,r)\subset X^n$ be the collection of the centers of the disks such that their union covers $Y$.
What is its measure (with respect to some probability measure $\mu^n$ on $X^n$)?
Here we are interested not in the measure of the space $\cov_Y(n,r)$, but in its topology.
In slightly higher generality, let \(X, Y\) be topological spaces, and $R\subset X\times Y$ be an open subset of their product, a relation.
For $n\in\Nat$, we will define the space of $R$-coverings of $Y$ a collection $\bx$ of $n$ distinguishable points in $X$, $\bx=\{x_1,\ldots,x_n\}\subset $ such that for any $y\in Y$, there exists $x_k, 1\leq k\leq n$ for which $(x_k,y)\in R$.
In other words, the union of the slices $R_{x_k}, k=1,\ldots, n$ covers all of $Y$.
In this note we will be primarily concerned with the situation where $X=Y$ is a compact metric space, and the relation is given by $R=\{(x,y): d(x,y)\leq r\}$ for some $r>0$.
Definition An \((n,r)\)-covering as a collection of \(n\) distinguishable points in \(X\) such that the union of metric \(r\)-balls centered at these points contains all of \(X\). \[ \cov_X(n,r):=\{(x_1,\ldots,x_n)\in X^n|\cup_k B(x_k,r)=X\}\subset X^n \]
Sometimes one refers to such finite collections as $r$-net, or finite $r$-approximation of $X$ in the Gromov-Hausdorff metric.
Let's take $X$ to be an interval (which we can assume to be $[0,1]$).
Let \(l\) be the smallest number of the open metric balls (i.e., the intervals of length \(2r\)) required to cover \(I\), - i.e. \[ l=\lfloor 1/2r \rfloor+1. \]
We define the slack as \(k=n-l\).
Two coverings of an interval of slack $5$.
Consider some examples for \(n=3\).
If the slack is zero (but the covering space is non-empty), the space of coverings consists of six components: the left-to-right order of the covering segments cannot be changed without breaking coverage. Each of the components is contractible.
Here, $r=.23$
If the slack is one, the space is homeomorphic to the solid torus.
Here, $r=.36$
For general $r$, the topology of the space of coverings of an interval is given by the following
Theorem
The space of coverings $\cov_I(n,r)$ is homotopy equivalent to the $k$-skeleton of the permutahedron $P_n$, with $k=n-\lceil 1/2r\rceil$ being the slack: \[ \cov_I(n,r)\equiv \skel_k(P_n). \]
Here \(P_n\) is the order \(n\) permutahedron
Permutahedron is a convex polytope defined as the convex hull of the permutation orbit of a generic point $(a_1,\ldots, a_n)$, \[P_n=\mathtt{conv}\{(a_{\sigma_1},\ldots,a_{\sigma_n}),\sigma\in S_n\},\]
while \(\skel_k\) stands for \(k\)-skeleton, the union of all faces of the polyhedron of the dimensions \(k\) or less.
The vertices of $P_n$ correspond to the linear orderings on the set $\nset=\{1,2,\ldots,n\}$. The edges between these vertices correspond to transpositions of the neighboring elements in the linear order.
Each face of the permutahedron corresponds to a composition, i.e., a partition of \(\nset\) into an ordered sequence of disjoint blocks, considered as sets (unordered within each block). The compositions are naturally ordered (by the order-preserving refinements).
Each permutation can be considered as a composition into the blocks of size one. For a collection of linear orders, the (unique) minimal composition which can be refined to each of these orders corresponds to the minimal face of the permutahedron containing all the vertices corresponding to the permutations.
Conversely, for any composition the set of permutations obtained from it by various refinements into the linear order of singletons, forms the set of the faces on the boundary of the face corresponding to that composition.
In other words, we have
Proposition
The partially ordered set of the compositions of \(\nset\) is isomorphic to the lattice of the facets of the permutahedron \(P_n\). The dimension of the facet corresponding to the composition with $k$ blocks is $n-k$.
The $k$-skeleton of the permutahedron \(P_n\) is homotopy equivalent to the nerve of the sublattice of the compositions with at least $(n-k)$ blocks.
Topology of Permutahedra
Proposition
The \(k\)-skeleton of \(P_n\) is homotopy equivalent to a wedge of
\(k\)-spheres.
To find the homotopy type of the space of coverings of an interval it is enough to compute its Euler characteristics, \(\chi(\skel_k(P_n))\).
The exponential generating function for Euler characteristics of the skeleta of codimention \(k\) in \(P_n\) is \[ \sum_n \chi(\skel_k(P_n))\frac{z^n}{n!}= e^z-1-\sum_{l=0}^k(1-e^{-z})^{l+1}. \]
Examples
Codimension 1 \[ e^z-1-(1-e^{-z})=\sum_{n\geq 2} (1+(-1)^{n-2})\frac{z^n}{n!}: \] as expected, we recover the exponential generating function of Euler characteristics of $(n-2)$-dimensional spheres.
Codimension 2 \[ e^z-1-(1-e^{-z})-(1-e^{-z})^2=\sum_{n\geq 3}(1+(-1)^{n-3}(3-2^n))\frac{z^n}{n!}. \] In other words, the \((n-3)\)-skeleton of \(P_n\) is homotopy equivalent to a wedge of \(2^n-3\) spheres \(\sphere^{n-3}\), for \(n\geq 3\).
There is a different way to look at the covering spaces \(\cov_I(n, r)\), in some sense dual to the permutahedron model.
Assume that $\forts$ is a finite set (the points of which are referred to as forts).
Definitions
For fixed $\nset, \forts$, one can associate to the partial order on the details defined above its nerve (the simplicial complex whose simplices are chains in the poset) which we will denote as $\Delta(\nset,\forts)$.
Example For $|\forts|=2, n=3$, the partial order is shown on Figure, and its nerve has the homotopy type of a circle.
It turns out that the nerve $\Delta(\nset,\forts)$ of the posets of details is homotopy equivalent to an appropriate skeleton of a permutahedron:
Proposition For any $n,\forts$, \(\Delta(n,\forts)\sim \skel_{n-|\forts|}(P_n). \)
We return now to the space of coverings of the interval, $\cov_I(n,r)$.
Define as forts $\forts$ the arithmetic progression with \(l\) terms, starting at \(0\) and ending at \(1\): \[ \forts =\{f_1=0, f_2=1/(l-1),\ldots,f_{l-1}=(l-2)/(l-1), f_l=1\}\subset I, \]
As the distances between the forts are \(1/(l-1)>2r\), no interval of length \(2r\) can contain more than one fort.
The subset of standard positions is an arithmetic progression of size $l$ such that $l$ intervals of length $2r$ with centers at the standard positions $\cent$ cover $I$: \[\cent=\{c_1\lt \cdots\lt c_l\}\subset I\]
For a detail $\dl$, call any configuration $\xx$ $\dl$-standard if $x_k$ is in the $\dl(k)$-th standard position for any $k\in\dom(\dl)$.
The collection of $\dl$-standard configurations is a closed contractible (indeed, homeomorphic to $I^{n-l}$) subset of $\cov_I(r,n)$.
Definition
For a detail $\dl$ we define the subset of $\dl$-admissible configurations in $\cov_I(n,r)$ as
\[
U_{\dl}:=\{\xx\in\cov_I(n,r):|f_{\dl(k)}-x_k|\lt r\},
\]
i.e., the collection of coverings such that the $k$-th interval contains
$\dl(k)$-th fort.
Any $\dl$-standard configuration is in $\dl$-admissible.
If a detail $\dl_1$ dominates the detail $\dl_2$, their admissible subsets satisfy $U_{\dl_2}\subset U_{\dl_1}$.
More generally, the lattice structure on the details maps contravariantly into the lattice of $\dl$-admissible sets:
Lemma The intersection of admissible sets over a family $D$ of details is the admissible set $U_{\dl^*}$, where $\dl^*$ is the join of details in $D$: \[ \bigcap_{\dl\in D} U_\dl=U_{\dl^*}, \dl^*=\bigvee_{\dl\in D} \dl. \]
We are now in the situation known in the applied homotopy theory as an arrangement: a lattice of the subsets of a space is given such that their union is the whole space, and each of the embeddings in the lattice is a cofibration.
Recall now one of the standard results:
Proposition
If all subspaces in the poset of the subsets covering a space are contractible, then the ambient space is homotopy equivalent to the nerve of the poset.
Example For lattice of composition $I=(I_1|I_2|\ldots|I_l), l\leq k$ with $\nset=\amalg_j I_j$, the lattice of sets \[V_I:=\{\xx \ | \ x_m\lt x_{m'} \mbox{ if } m\in I_j, m'\in I_{j+1}\}\] is homotopy equivalent to $\skel_k(P_n)$.
The admissible sets are contractible:
Lemma
For every detail $\dl$, the set of $\dl$-central configurations is a deformation retract of $U_{\dl}$. In particular, every $U_\dl$ is contractible.
The proof is by sweeps:
This immediately produces a proof of
Proposition For any $n,\forts$, \[ \Delta(n,\forts)\sim \skel_{n-|\forts|}(P_n). \]
In fact, the same reasonings can be used in a general setting: assume that $X$ is a compact metric space.
Proposition
If $\forts\subset X$ is a finite subset of forts which are $2r$-separated, then
for any detail $\dl$ the subspace $U_\dl\subset \cov_X(r,n)$ of $\dl$-admissible configurations is well-defined, the space of $r$ coverings $\cov_X(r,n)$ is covered by the sets $U_\dl, \dl\in\dls$, and the lattice of details maps contravariantly to the lattice of the sets $U_\dl$.
In particular, if all $U_\dl$ are contractible, $\cov_X(r,n)$ is homotopy equivalent to the corresponding skeleta of the permutahedra.
A historical remark: the link of the admissible sets $U_\dl$ to the standard sets (where all the points $x_k, k\in\dom(\dl)$ are in the standard positions) was suggested by Hang Wan in his 2013 thesis. He studied specifically the unions of the sets with all standard positions occupied, and established that their homotopy types are independent of the set of standard positions.
Those spaces were rediscovered recently by D. Kozlov under the name of Stirling complexes.
We can generalize the theorem on the covering spaces of intervals to higher dimensions.
One situation where this is feasible is the problem of covering of a product of intervals by a collection of unit cubes.
Consider $X=\prod_{j=1}^d I_j$.
Let $l_j=\lfloor |I_j|/2r\rfloor+1$ is the minimal number of $2r$ 1D-balls needed to cover the interval $I_j$.
Then $l:=\prod l_j$ is the minimal number of $r$-balls in $l_0$ metric on $\Real^d$ needed to cover $X$. Define the slack as usual, $k=n-l$.
Theorem The space of $r$-coverings is homotopy equivalent to $k$-skeleton of $P_n$: \[ \cov_X(n,r)\sim \skel_k(P_n). \]
Theorem The space of $r$-coverings is homotopy equivalent to $k$-skeleton of $P_n$: \[ \cov_X(n,r)\sim \skel_k(P_n). \]
The proof is still by sweeps: one defines the forts, details and standard positions as in the univariate case. The key observation is that the sets $U_\dl, \dl\in \dls$ are still contractible.
What about other spaces of coverings? They seem to be much harder to study, not unlike the spaces of configuration of the hard disks in a bounded domain in $\Real^d, d\geq 2$.
Coverings through relations form a broad class of interesting examples, - wide open area.