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.

  • $\begingroup$ The way you state it, $|X|$ is the answer. For example, the distance between any two distinct points could be $\alpha +1$. $\endgroup$ – Bill Johnson Mar 15 '12 at 21:31
  • $\begingroup$ I am not sure I agree. The sets $A$ have to be of a fixed size $k$. $\endgroup$ – Ankur Mar 15 '12 at 21:40
  • $\begingroup$ Oh, sorry. I misread the problem. For the example I mentioned, the max is zero. For some $X$, the max is $\lfloor|X|/k\rfloor$; for example, make the diameter of $X$ less than $\alpha$. So it is not clear what you are looking for. Do you want examples where the max is an arbitrary integer between $0$ and $$\lfloor|X|/k\rfloor$$? Such examples are also easy to construct. $\endgroup$ – Bill Johnson Mar 15 '12 at 22:26
  • $\begingroup$ I have added a clarification that the values of $\alpha$ and $k$ are not degenerate. I was hoping for upper bounds on the max in terms of the given parameters. If you make the diameter too large or too small, the bound would of course degenerate to something obvious. $\endgroup$ – Ankur Mar 15 '12 at 22:48

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$.

  • $\begingroup$ I am not sure how the bound on $B_n(Y,k)$ can be translated to a bound on $A(Y,\alpha,k)$; but the use the doubling diameter has given me some directions to think along. Thanks. $\endgroup$ – Ankur Mar 17 '12 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.