# DPS Clustering: New Results
## 4 Results: Third Stage of DPS
### FirstPart: The Theory of \(d\)-Clusters
#### 4.2.1 The Notation  
\(d(x)\) is a numerical sequence of distances \(d_{i}(x)=d\Big{(}X_{i-1}(x),\overline{X_{i-1}(x)}\Big{)}\):  
\[d(x)=\{d_{1}(x),\ldots,d_{|X|-1}(x)\} \tag{15}\]  
**Definition 7**. : _Let us call an eigen \(d\)-cluster \(C=C_{k}(x)\), \(1\leq k\leq|X|-2\) with center (origin) in \(x\) the eigen segment \(X_{k}(x)\) of the enumeration \(X(x)\), for which \(\max_{i=1}^{k}d_{i}(x)<d_{k+1}(x)\):_  
\[C=C_{k}(x)\Leftrightarrow \begin{array}{c}\text{eigen}\\ d\text{-cluster}\end{array} \Leftrightarrow(C=C_{k}(x))\wedge\Big{(}\max_{i= 1}^{k}d_{i}(x)<d_{k+1}(x)\Big{)} \tag{16}\]  
**Statement 3**. : _The cluster \(C_{k}(x)\) is independent of the choice of origin within itself:_  
\[C_{k}(x)=C_{k}(y)\ \forall y\in C_{k}(x)\diagup x\]  
In other words, in the case of \(d\)-clustering, there is a set-theoretic equality \(X_{k}(x)=X_{k}(y)\) that is, for any \(y\in C_{k}(x)\), the first \(k+1\) terms in the enumeration \(X(y)\) will lie in \(C_{k}(x)\). Proof. : Induction on the number \(i\) of steps \(y_{i-1}\Rightarrow y_{i}\), \(i=1\leq i\leq k\) in the enumeration \(X(y)\). Let \(y=x_{j}\), \(j=1,\ldots,k\). * \(i=1\). We have to show that \(y_{1}\in C_{k}(x)\). By virtue of \(y\in C_{k}(x)\), we have \[d\Big{(}y,\overline{C_{k}(x)}\Big{)}\geq d\Big{(}C_{k}(x),\overline{C_{k}(x)} \Big{)}=d_{k+1}(x).\] The element \(y=x_{j}\) in \(C_{k}(x)=X_{k}(x)\) has two neighbors \(x_{j-1}\) and \(x_{j+1}\), if \(1\leq j<k\), and one neighbor \(x_{k-1}\), if \(j=k\) and \(y=x_{k}\). To any of the neighbors, the distance from \(y\) will be less than \(d_{k+1}(x)\), so the next element after \(y=y_{0}\) in the sequence \(X(y)\) necessarily lies \(C_{k}(x)\). * Let the assumption that the first \(i\) steps of \(y_{i}\), \(i\leq k-1\) in the sequence \(X(y)\) lie in \(C_{k}(x)\) be satisfied. Let us show that the element \(y_{i+1}\) will also lie in \(C_{k}(x)\). Under our assumptions \(X_{i}(y)\subset C_{k}(x)\), therefore \[d(X_{i}(y),\overline{C_{k}(x)})>d(C_{k}(x),\overline{C_{k}(x)})=d_{k+1}(x).\] Assume \(y_{m}=x_{s(m)}\), \(m=0,\ldots,i\). If \(s_{0}<\cdots<s_{i}\) is the correct ordering of array \(s(m)|_{0}^{i}\), then two cases are possible: 1 st: the array \(s_{p}|_{0}^{i}\) has no gaps, that is, it is an eigensegment in \([0,k]\). In this case, \(C_{k}(x)\) necessarily contains either an element \(x_{s_{0}-1}\), or an element \(x_{s_{i}+1}\), whose distance from \(X_{i}(y)\) is nontrivial and less than \(d_{k+1}(x)\). Hence, the term \(y_{i+1}\) in the sequence \(X(y)\) necessarily lies in \(C_{k}(x)\): 2 nd:\(s_{p}|_{0}^{i}\) array has gaps. Let \(p^{*}\) be the first number for which \(s_{p^{*}+1}-s_{p^{*}}>1\). In this case, in the array \(s_{p}|_{0}^{i}\), it has no number \(s_{p^{*}}+1\) and in the set \(X_{i}(y)\) of an element \(x_{s_{p^{*}}+1}\), whose distance from \(x_{s_{p^{*}}}\) will be less than \(d_{k+1}(x)\). Hence, in this case too, the term \(y_{i+1}\) in the sequence \(X(y)\) lies in \(C_{k}(x)\). **Consequence 1**. : _Eigen \(d\)-clusters behave like non-Archimedean balls: either one contains the other or they do not intersect. In particular, two \(d\)-clusters of the same order either coincide or do not intersect._  
Proof. : Let \(C=C_{k}(x)\), \(\bar{C}=C_{\bar{k}}(\bar{x})\) and \(y\in C\cap\bar{C}\). According to Statement 3, \(C=X_{k}(y)\), \(\bar{C}=X_{\bar{k}}(y)\). If \(k\leq\bar{k}\), then \(C\subseteq\bar{C}\). The \(d\)-clusters of \(C_{k}(x)\) are eigennopoint subsets in \(X\). Let us remove this restriction on \(k\) in Definition 7 using the notion of a connectivity exponent, which develops and continues the topic of finite connectivity Section 2.2.1. **Definition 8**. : _1. Connectivity index \(r(A)\) of a subset \(A\Leftrightarrow\) minimum \(r\) for which \(A\) is \(r\)-connected:_  
\[r(A)=\min\{r:A\ r\text{-connected}\}.\]  
_2. The isolation index \(e(A)\) of a subset \(A\Leftrightarrow\) the distance to its complement \(\bar{A}\):_  
\[e(A)=d(A,\bar{A}).\]  
**Statement 4**. : \[r(X_{k}(x))=\max_{i=1}^{k}d_{i}(x)\]  
Proof. : 1.