Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\left\{\mathbf{p}_1,\dots, \mathbf{p}_k\right\}$ be a set of points in $n$-dimensional Euclidean space, and let the second moment of these points be defined as:

$ U=\sum \limits_{i=1}^{k} ||\mathbf{p}_i -\bar{\mathbf{p}}||^2, $

where $\bar{\mathbf{p}}$ is their centroid.

Let two points $i$ and $j$ be connected if $||\mathbf{p}_i - \mathbf{p}_j||\leq \lambda$.

Then, under the constraint that the points are to form a connected graph, what is the configuration that maximizes their second moment?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Notice that this is the same as maximizing $\sum_{i<j} |p_i-p_j|^2$. Also by rescaling assume that $\lambda =1$. Since your graph is connected there is a spanning tree whose vertices are the $p_i$'s. Let $\text{d}(i,j)$ denote the graph theoretic distance between $p_i$ and $p_j$ along this tree. From the triangle inequality $\sum_{i<j} |p_i-p_j|^2 \le \sum_{i<j} \text{d}(i,j)^2$. It is a nice combinatorial exercise to show that this last quantity is maximized when the tree is a path. Therefore your second moment is maximized when the points are all on a line so that $|p_1-p_2|=|p_2-p_3|=\cdots=|p_{k-1}-p_k|=1$.

share|improve this answer
    
Great answer. I suspected that it should be like this, intuitively, but I could not prove it. I'm very happy to do the exercise you mention. However, I'm not a professional mathematician, and know very little about graph theory, so I would be very grateful if you could give me some hints about how to approach it (such as any results/tools I should use). Thanks again. –  mga Aug 31 '13 at 2:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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