1
$\begingroup$

Question: Let $(X, d)$ be a metric space such that there is a positive $a$ and $n$ open balls $B(x_1, a),\ldots, B(x_n, a)$ such that together these balls cover $X$.

Find an upper bound $M$ for the diameter of $X$. Find "the smallest" upper bound $M$ for the diameter of $X$ in the following sense: the formula for $M$ is valid in all cases, and there is a metric space $X$ such that $\operatorname{diam} (X) = M$.

Thoughts: I find the question a little hard to parse. I think it's asking what is the biggest diameter that this can have, so my answer then would be $\sup M = an$.

Thinking about the real number line, if there are $n$ # of balls, the two furthest points from each other would be $a\cdot n$ length from each other. Still trying to figure out what the rest of the questions asks...

  • 0
    Thank you for your input! I think I don't quite understand that... the $max d(x_j,x_k)$ would be $a(n-2) + (a/2) + (a/2) = a(n-1)$ but $2a + a(n-1) = a(n+1)$ which doesn't intuitively make sense to me. Am I thinking about this incorrectly? If you take a closed, bounded interval of R, and line up the balls to cover that set you get that the distance between two points could be at most $a\times n$. I can't picture a bigger distance than that right now.2011-10-09
  • 1
    Suppose $X$ has $n$ points, with any two points being a fixed distance $d$ apart. Then $X$ has diameter $d$, but can be covered by $n$ open balls with radius as small as we like. So there's no function of $n$ and $a$ which will work as an upper bound here.2011-10-09
  • 0
    I've been assuming that "a" is a fixed radius but I think it is too ambiguously written to know either way. Thanks for the input, I think I need further direction to understand how to think about this problem.2011-10-09
  • 1
    The radius $a$ is fixed. The question is not at all ambiguous: it’s asking for the smallest number (as a function of $a$ and $n$ that is **guaranteed** to be at least as large as the diameter of $X$. Then, once you have that, you’re to find a specific example of $n$ balls of radius $a$ covering a space whose diameter really is that big; this will show that no smaller number would have met the guarantee.2011-10-09
  • 0
    If $X$ is not connected, then there is no upper bound from the information given.2011-10-09
  • 0
    @robjohn: Yes, there is: Davide gave it.2011-10-09
  • 0
    @Chris: You’re misreading the question. You’re *given* the radius $a$ and the number of balls (and presumably the distances between centres) and asked what upper bound that imposes on the diamater. There’s no requirement that it be a particularly *good* upper bound.2011-10-09
  • 0
    @Brian: okay, I was thinking the OP wanted a formula not involving the $\{x_i\}$; but yes, Davide's answer is correct. If $X$ is connected then the the diameter is $\le 2an$.2011-10-09
  • 0
    @Brian: yes, I understand that. My point stands: no upper bound which is a function of $n$ and $a$ can work. In particular, the OP's bound $an$ does not work.2011-10-09
  • 0
    Either there is a mistake in the problem statement (the hypothesis "connected" is missing) or the bound must depend on the $x_i$. Here's an example: consider any collection of $n$ real numbers: $x_1\leq x_2 \leq \dots \leq x_n$ and consider $X$ to be the union of open intervals $(x_i-a,x_i+a)$ with the standard metric. Then the diameter of $X$ is $x_n-x_1+2a$ which can be made arbitrarily large.2011-10-09

1 Answers 1