Workshop on Stein’s Method and Networks
joint work with
Frankie Higgs and Mathew Penrose (University of Bath)
Given a point cloud \(\mathcal X\) in a metric space, the LNNL tells us how far the most isolated point is from the others
\(L_n = \inf\{r: \mathcal X(B(x,r))\ge 2, \ \forall x\in\mathcal X \}\)
similarly \(L_{n,k}\)
\[R_{n,k} = \inf\{ r: \mathcal X(B(x,r))\ge k, \ \forall x\in A \}\]
A graph is \(k\)-connected, denoted \(\mathcal K_k\), if the removal of \(k-1\) vertices does not disconnect the graph.
\[M_{n,k} = \inf\{r: G(\mathcal X,r) \in \mathcal K_k \}\]
x-x x-x
\[L_{n,k} \le M_{n,k}\]
Let \(\mathcal X = \mathcal P_n\). Under conditions on \(A\), we have the strong law \[ \frac{n L_{n}^d}{\log n} \sim \frac{n M_{n}^d}{\log n} \sim \frac{n R_{n}^d}{\log n}\sim c\] where \(c\) depends on the geometry of \(A\).
Let \(k=k(n)\sim \beta \log(n)\) with \(\beta \in [0,\infty]\). Then
\[ c = \max_{\phi\in\Phi^*(A)} \frac{\hat H_\beta(D(\phi)/d)}{f_\phi \rho_\phi}\]
Want to show some threshold \(\sim r_n\)
let’s implement this twice, 1 for torus, 2 for metric space
\[ \mathbb (1- \eta (n ar^d) e^{- n ar^d} )^{c_1 r_n^{-b}} = O(\exp(- n^{b/d - ac}))\to 0\] provided \(c< (b/d)/a\)
suppose \(\{M_n > r_n\}\) with \(n r_n^d = c\log n\), then \(\sharp\) clusters \(\ge 2\), so one of the following happens
Implement granulation for each of the above cases. e.g. \(\mathbb P[\exists iso] \le r_n^{-d} \exp( - c\theta_d \log n )= n^{1- c\theta_d}\to 0\) provided \(c> 1/\theta_d\).
we need \(A\) has a doubling measure (not necessarily \(\mu\)), connected and unicoherent, balls are connected, and the removal of a ball does not create a big second component
provided that \(A\) has matching covering and packing exponent and one can estimate volume of balls (\(G_r\setminus G\)) optimally (up to epsilon), all three thresholds are asymptotically the same
Given \(\mathcal X, \mathcal Y\) sampled from \(A\) \[ T = \inf\{r: \mathcal X(B(y,r))\ge 1, \forall y\in \mathcal Y \}\]
\(n\mathbb E[|{x\in A: \mathcal P_n(B(x,r))=0}|] = \int_A \mathbb \exp(- n \theta_d r^d) ndx = \mathbb E[\sharp iso]\)
\[\mathcal Y(\mbox{uncovered}_{r_n}) \to Po(.) \mbox{ for some } r_n \Rightarrow T_n \overset{d}\to (2 compt) Gumbel\]
code:
https://github.com/frankiehiggs/connectivity-in-polytopes
https://github.com/frankiehiggs/CovXY
package: