Clustering in Euclidean space

Question

Let $P_1,\cdots,P_m$ be points in $\mathbb{R}^n$ such that the distance between any $P_i,P_j$ is less than 1.

Let $p_{i,j}$ be a probability distribution on pairs of these points, that is for $1\leq i,j\leq m$, $p_{i,j}\geq 0$ and $\sum_{i,j} p_{i,j}=1$.

Let $\epsilon>0$ be such that $$\sum_{d(P_i,P_j)>\epsilon} p_{i,j}<\epsilon.$$

Is there a way to choose $\epsilon'$ and $\delta$ and cluster these points into groups satisfying these three conditions?

1. $\epsilon'$ and $\delta$ only depend on $\epsilon$, not on $n,m$. As $\epsilon$ goes to 0, $\epsilon'$ and $\delta$ go to 0 also.

2. Any two points in the same group have distance less than $\epsilon'$.

3. The total probability of pairs of points from different groups is less than $\delta$.

Answer 1

$\let\eps\epsilon$1. There is no such way independent of $n$.

Indeed, assume that for some suitable small $\eps$ there exist $\eps'<1/10$ and $\delta<1/2$. For $n=1/\eps^2$ let your set of points be $\{0,\eps\}^n$, and distribute $p_{i,j}$ uniformly over the edges of the cube. We claim that no desired clustering is possible.

Indeed, consider any cluster; wlog, it contains $0$. Now we compare the number of edges inside it with the number of edges from it to the outside; we claim that the ratio of these two numbers is at most, say, $1/10$. Notice that the weight (i.e. the number of coordinates equal to $\eps$) of each point in the cluster is at most $n/100$.

Let us reconstruct our cluster starting from $0$ and adding the points one by one in non-decreasing order of weights. Each time we add a point, we remove at most $n/100$ edges going outside (the ones from the new point to the previously added), add at most $n/100$ edges inside (the same ones), and add at least, say, $98n/100$ edges going outside (the ones from the new point to the points with greater weights). Thus at each step the estimate is confirmed.

Therefore, the total number of edges inside the clusters is not greater than $1/5$ times the number of other edges, and we failed to clusterize the points in a required manner.

2. On the other hand, if we fix the dimension $n$, then the claim holds, even if the diameter 1 condition is omitted. Indeed, one may choose randomly the orthonormal base and dissect the whole space by hyperplanes into cubes of side $\eps'/\sqrt{n}$ (the offsets are also chosen uniformly random). The clusters will be the sets in one cube.

Indeed, each segment of length $\leq\eps$ will be crossed by a hyperplane of fixed direction with probability of order $\eps/\eps'$ (sorry, I omit the computations right now), so at average the sum of $p_{i,j}$ over the small crossed segments $P_iP_j$ will be small (if we choose an appropriate $\eps'/\eps$).