disjoint subsets of a finite metric space of fixed size and fixed diameter

Question

I have encountered this question as a part of some other research. The problem appears to be a combinatorial problem. But my knowledge of results in combinatorics and discrete math is quite thin. I was hoping someone here may know the answer.

Let $X$ be a finite set $(X,d)$ be a discrete metric space. Form subsets $A$ of a given size $k$ by drawing elements from $X$ with the restriction that for any $x,y \in A$, the distance $d(x,y) \leq \alpha$, where $\alpha$ is a given. Assume that the values of $\alpha$ and $k$ are not degenerate: assume there do exist sets $A$ with diameter $\alpha$ and size $k$ each so that their union is $X$. Also assume $\alpha$ is smaller than the diameter of $X$. What then is the maximum number of disjoint sets $A$ with this diameter and size? Or are there bounds in terms of $|X|,k,d,\alpha$?

Clearly, if I remove the restriction of the distance and allow arbitrary sets $A$, the answer is trivial $=\lfloor|X|/k\rfloor$. The distance restriction makes it harder.

I would be happy if someone can at least point me to an suitable body results which could be useful in this problem.

Answer 1

A metric space is called doubling with doubling constant $D=D(X)$ provided for every $r>0$, every closed ball of radius $2r$ can be covered by at most $D$ balls of radius $r$. Finite dimensional normed spaces are doubling; infinite dimensional normed spaces are never doubling.

Given a finite metric space $X$, $\alpha>0$, and a positive integer $k$, let $A(X,\alpha,k)$ be the largest integer $m$ s.t. $X$ contains $m$ disjoint subsets each of cardinality $k$ s.t. for any two points $x$, $y$ in any the same subset, $d(x,y)\le \alpha$. Given a metric space $Y$ and positive integers $n$ and $k$, let $B_n(Y,k)$ be the minimum of $A(X,\alpha,k)$ taken over all $n$-element subsets $X$ of $Y$ of diameter at most one.

Observation: If $Y$ is doubling with diameter at most one, then for every $0<\alpha<1$ and every $k$, $B_n(Y,k)/n\to 1/k$ as $n\to \infty$. Indeed, it is enough to check this for $\alpha$ of the form $2^{-m}$. Cover $Y$ by $D(Y)^m$ balls of radius $2^{-m}$. If none of these balls contains at least $k$ elements of a subset $Z$ of $Y$, then the cardinality of $Z$ is at most $(k-1)D^m$. Consequently, for every $n$, $n-kB_n(Y,k)\le (k-1)D^m$.