This question is inspired by a recent talk by [Matt Kahle](http://matthewkahle.org/) on random geometric complexes. 


Some simple notation: let $\mathcal{B} \subset \mathbb{R}^d$ be the unit ball in $d$-dimensional Euclidean space with the usual norm $\|\cdot\|$ and let $\mathcal{B}^k$ denote the $k$-fold product of this ball with itself for any positive integer $k$. For each $n \in \mathbb{N}$, define $K\_n \subset \mathcal{B}^n$ as follows:


$$ K\_n = \lbrace(p\_1,\ldots,p\_n) \in \mathcal{B}^n \text{ so that } \|p\_i - p\_j\| < 1 \text{ for all } 1 \leq i,j \leq n\rbrace.$$


Thus, $K\_n$ consists of those $n$-tuples of points in the unit ball whose diameter is bounded above by $1$. I would like to know what fraction of $\mathcal{B}^n$ lies in $K\_n$ asymptotically as $n$ increases. More precisely, let $\mu$ be the usual $d$-dimensional Lebesgue measure, and define 
$$\chi(n) = \frac{\mu(K\_n)}{\mu(\mathcal{B})^n}.$$



> 
> How does $\chi(n)$ behave for fixed dimension $d$ as $n \to \infty$?
> 
> 
> 


While an answer to this specific question would be great, I would be much more interested in some insight regarding *how* one should tackle such problems. The Calculus approach of setting up some integral fails horribly -- at least, I should confess that I tried $n = 2 = d$ and got hopelessly stuck with what appears to be an elliptic integral of the murderous kind -- so I expect that there is no closed formula for $\chi(n)$. But surely someone has worked out asymptotic envelopes for such a basic quantity!



What fraction of n-point sets in the unit ball have diameter smaller than 1?
I am certainly not the best person to answer this question, as I do not have much insight to share regarding how to approach this kind of problems. My only (fairly obvious) suggestion is to *estimate* the relevant quantities in any way possible. In this process, it can be very helpful to reduce the calculations to lower dimensions, and the Fubini theorem will be our friend here.$\newcommand{\norm}[1]{\lVert #1 \rVert}$$\newcommand{\abs}[1]{\lvert #1 \rvert}$$\newcommand{\suchthat}{\ : \ }$$\newcommand{\set}[1]{\left\lbrace #1 \right\rbrace}$$\newcommand{\NN}{\mathbb{N}}$$\newcommand{\RR}{\mathbb{R}}$$\newcommand{\ball}[2][0]{{B\_{#2}(#1)}}$$\newcommand{\unitball}{\ball{1}}$$\newcommand{\dd}{\:\mathrm{d}}$$\newcommand{\label}[1]{\rlap{\qquad\qquad \text{#1}}}$


For this problem, my single intuition is that when one of the points $p\_i$ drifts away from the centre of the unit ball, then every other point $p\_j$ for $j\neq i$ cannot access a certain portion of the unit ball which sits close to $-p\_i \: /\norm{p\_i}$. By adding sufficiently many points, this should make the ratio $\chi(n)$ go to zero as $n$ goes to infinity. I will try to make this intuition precise in the remainder of this answer.




---


**Notation and preliminaries**


Fix the dimension $d$ of the ambient Euclidean space. Let $\norm{\cdot}$ denote the Euclidean norm on $\RR^d$, and $\ball[x]{r} = \set{ p\in\RR^d \suchthat \norm{p - x} \lt r }$ the open ball in $\RR^d$ with radius $r$ and centre $x$. Further, let $\mu$ be the Lebesgue measure on $\RR^d$, and $\mu\_n = \mu^{\times n}$ the product measure on $\bigl(\RR^d \bigr)^{\times n}$ (i.e. Lebesgue measure on $\RR^{d n}$).


As in the statement of the question, $K\_n$ will denote the following subset of $\unitball^{\times n}$:
$$ K\_n = \set{ (p\_1, \ldots, p\_n) \in \unitball^{\times n} \suchthat \forall\_{i,j} \ \norm{p\_i - p\_j} \lt 1 } $$
We shall prove that
$$ \chi(n) = \frac{\mu\_n(K\_n)}{\mu\_n \bigl( \unitball^{\times n} \bigr)} = \frac{\mu\_n(K\_n)}{\mu\bigl(\unitball\bigr)^n} $$
converges to $0$ as $n\to\infty$. In fact, I will give (fairly coarse) upper and lower bounds for $\chi(n)$. Nevertheless, I am sure one can give much stricter bounds for $\chi(n)$ and perhaps even describe its asymptotic behaviour.




---


**Upper bound for $\chi(n)$**


Fix a positive integer $n$. Define
$$ X\_n = \set{ (p\_1, \ldots, p\_n)\in K\_n \suchthat \forall\_i \ \norm{p\_i} \lt 1/2 } $$
(the choice of the number $1/2$ here is mostly arbitrary) and $Y\_n = K\_n\setminus X\_n$ to be the complement of $X\_n$ in $K\_n$. The set $X\_n$ is contained in $\ball{1/2}^{\times n}$ and thus
$$ \mu\_n(X\_n) \leq \mu\_n\bigl(\ball{1/2}^{\times n}\bigr) = \mu\bigl(\ball{1/2}\bigr)^n $$
Now define for each $i\in\set{1, \ldots, n}$ the set
$$ Z\_{n,i} = \set{ (p\_1, \ldots, p\_n)\in K\_n \suchthat \norm{p\_i} \geq 1/2 } $$
It is easy to check that
$$ Y\_n = \bigcup\_{i=1}^n Z\_{n,i} $$
Moreover, by permuting the first and $i$-th points (which gives a measure preserving self-bijection of $K\_n$), we see that $\mu\_n(Z\_{n,i}) = \mu\_n(Z\_{n,1})$ for all $i\in\set{1, \ldots, n}$. It follows that
$$ \mu\_n(Y\_n) \leq n \cdot \mu\_n(Z\_{n,1}) $$
and therefore
$$ \mu\_n(K\_n) = \mu\_n(X\_n) + \mu\_n(Y\_n) \leq \mu\bigl(\ball{1/2}\bigr)^n + n\cdot \mu\_n(Z\_{n,1}) \label{(A)} $$


Now we perform a crude estimation of the volume of $Z\_{n,1}$. The Fubini theorem entails
$$ \mu\_n(Z\_{n,1}) = \int\_{\unitball\setminus\ball{1/2}} \mu\_{n-1}(P\_x) \dd \mu(x) $$
where $P\_x \subset K\_{n-1}$ is the following cross-section of $Z\_{n,1}$, for each $x\in\unitball\setminus\ball{1/2}$:
$$ P\_x = \set{ (p\_1, \ldots, p\_{n-1}) \in \bigl(\RR^d \bigr)^{\times (n-1)} \suchthat (x, p\_1, \ldots, p\_{n-1}) \in K\_n } $$


**Lemma:** For each $x\in\unitball\setminus\ball{1/2}$, the inequality $\mu\_{n-1}(P\_x) \leq \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1}$ holds.


I will present a proof of the lemma at the end of this answer. We now apply the estimate in the lemma to the preceding integral expression for $\mu\_n(Z\_{n,1})$ to obtain:
$$ \mu(Z\_{n,1}) \leq \mu\bigl( \unitball \bigr) \cdot \mu\bigl( \unitball\cap\ball[1/2,0,\ldots,0]{1} \bigr)^{n-1} $$
Putting this together with estimate (A):
$$ \mu\_n(K\_n) \leq \mu\bigl(\ball{1/2}\bigr)^n + n\cdot \mu\bigl( \unitball \bigr) \cdot \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1} $$
and further using the fact that $\ball{1/2} \subset \unitball\cap\ball[1/2,0,\ldots,0]{1}$, we simplify
$$ \mu\_n(K\_n) \leq (n+1) \cdot \mu\bigl( \unitball \bigr) \cdot \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1} $$
Consequently, we obtain an upper bound for $\chi(n)$:



> 
> $$ \chi(n) \leq (n+1) \left( \frac{\mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)}{\mu\bigl(\unitball\bigr)} \right)^{n-1} = (n+1) \rho^{n-1} $$
> 
> 
> 


where $0 \lt \rho \lt 1$. Note that $\rho$ depends only on $d$. In particular, $\chi(n)$ converges to zero as $n\to\infty$.




---


**Lower bound for $\chi(n)$**


It is very easy to give a crude lower bound for $\chi(n)$. Simply observe that $X\_n \subset K\_n$, and that $X\_n = \ball{1/2}^{\times n}$ (here we *do* require the choice of $1/2$ in the definition of $X\_n$). Therefore,
$$ \mu\_n(K\_n) \geq \mu\_n(X\_n) = \mu\bigl(\ball{1/2}\bigr)^n $$
and so



> 
> $$ \chi(n) \geq \left( \frac{\mu\bigl(\ball{1/2}\bigr)}{\mu\bigl(\ball{1}\bigr)} \right)^n = 2^{-dn} $$
> 
> 
> 




---


**Proof of the lemma**


We make use of the rotational symmetry of $Z\_{n,1}$. Choose a rotation on $\RR^d$ which takes the point $x$ to the point $(\norm{x},0,\ldots,0)$ on the first axis. Applying that rotation componentwise gives a measure preserving bijection between $P\_x$ and $P\_{(\norm{x},0,\ldots,0)}$, and we see that
$$ \mu\_{n-1}(P\_x) = \mu\_{n-1}\bigl( P\_{(\norm{x},0,\ldots,0)} \bigr) \label{(1)} $$


On the other hand, it is straightforward to check that
$$ P\_x = \set{ (p\_1, \ldots, p\_{n-1}) \in K\_{n-1} \suchthat \forall\_i \ \norm{p\_i - x} \lt 1 } $$
and it follows that
$$ P\_x \subset \bigl(\unitball\cap\ball[x]{1}\bigr)^{\times (n-1)} \label{(2)} $$


*Claim*: For $0\leq s\leq t$, the following inclusion holds:
$$ \unitball\cap\ball[t,0,\ldots,0]{1} \subset \unitball\cap\ball[s,0,\ldots,0]{1} \label{(3)} $$


*Proof of claim:*


* For $a\in\RR$, we have $\abs{a-s} \leq \max\set{ \abs{a-t}, \abs{a} }$: either $a \lt s$ which implies $\abs{a-s} \leq \abs{a-t}$, or $a\geq s$ which implies $\abs{a-s}\leq \abs{a}$.
* Thus, for any $y\in\RR^d$ we have $\abs{y\_1-s} \leq \max\set{ \abs{y\_1-t}, \abs{y\_1} }$ which by a simple calculation implies $\norm{y-(s,0,\ldots,0)} \leq \max\set{ \norm{y-(t,0,\ldots,0)}, \norm{y} }$.


*End of proof.*


The inclusions (2) and (3) prove
$$ P\_{(t,0,\ldots,0)} \subset \bigl(\unitball\cap\ball[t,0,\ldots,0]{1}\bigr)^{\times (n-1)} \subset \bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{\times (n-1)} $$
for $1/2 \leq t \lt 1$. Using (1), we conclude that for each $x\in\unitball\setminus\ball{1/2}$
$$ \mu\_{n-1}(P\_x) = \mu\_{n-1}\bigl( P\_{(\norm{x},0,\ldots,0)} \bigr) \leq \mu\_{n-1}\Bigl(\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{\times (n-1)}\Bigr) $$
and so $\mu\_{n-1}(P\_x) \leq \mu\bigl(\unitball\cap\ball[1/2,0,\ldots,0]{1}\bigr)^{n-1}$ as desired.


