Boundary effects in some stochastic geometric models

Workshop on Stein’s Method and Networks

Xiaochuan Yang

joint work with

Frankie Higgs and Mathew Penrose (University of Bath)

Full coverage threshold

\[R_{n,k} = \inf\{ r: \mathcal X(B(x,r))\ge k, \ \forall x\in A \}\]

  • \[ L_{n} \le R_{n,2} \]
  • \[ L_{n,k} \le R_{n,k+1}\]

Connectivity threshold

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}\]

Result

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\).

  • general \(k = k(n)\)
  • binomial process
  • non-uniform
  • Penrose, PTRF’22, book
  • Penrose, Y, Higgs, ’23

Finite convex polytope

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}\]

  • \(\hat H_0(x)=x, \hat H_\infty(x)=1\) (chg scale to \(k(n)\) when \(\beta=\infty\))
  • \(\Phi^*(A)\): faces of \(A\), including \(A^o\) viewed as \(d\)-dim face
  • \(D(\phi)\) is the dimension of the face \(\phi\)
  • \(f_\phi = \inf_{x\in\phi} f(x)\) where \(f\) is density
  • \(\rho_\phi = |B(o,1)\cap \kappa_\phi|\) angular volume of face \(\phi\)

Proof: granulation

Want to show some threshold \(\sim r_n\)

  • draw grid of spacing \(\varepsilon r_n\)
  • random point “activates” closest grid point
  • count relevant grid patterns

let’s implement this twice, 1 for torus, 2 for metric space

\(n L_n^d \ge c\log n\): torus

  • assume \(\{L_n \le r_n\}\) happens with \(n r_n^d = c\log n\)
  • at each \(\varepsilon_1 r_n\) lattice point, EITHER non-activated OR at least two points within \((1+2\sqrt{d}\varepsilon_1)r_n\) \[\mathbb P[ . \cup ..] = 1 - \mathbb P[ \{.\}^c | \{..\}^c]\mathbb P[\{..\}^c] \le 1 - \eta \mathbb P[\{..\}^c]\]
  • keeps lattices distant \(3r_n\) from each other, by independence \[ \mathbb (1- ...)^{c_1 r_n^{-d}} = O(\exp(- n^{1-\theta_d c}))\to 0\] provided \(c < 1/\theta_d\)

\(n L_n^d \ge c\log n\): metric space

  • a portion of \(A\) is \(r\)-packed with packing number \(\Omega(r^{-b})\)
  • \(\mu(B(x,r))\le a r^d\) for every \(x\) in that portion

\[ \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\)

  • the ultimate lower bound is the max of these \((b/d)/a\) for all kinds of portions

\(n M_n^d \le c\log n\): torus

suppose \(\{M_n > r_n\}\) with \(n r_n^d = c\log n\), then \(\sharp\) clusters \(\ge 2\), so one of the following happens

  • \(\exists\) isolated point
  • \(\exists\) non-isolated small clusters, \(0<diam \le K r_n\)
  • \(\exists\) two big clusters, \(diam > K r_n\)

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\).

\(n M_n^d \le c\log n\): metric space

  • a portion of \(A\) is covered by \(O(r^{-b})\) balls with radius \(r\) and \(\mu(B(x,r))\ge a r^d\) for each \(x\) in that portion
  • \[\mathbb P[\exists iso \mbox{ in portion}]\le O(r_n^{-b}) \exp(- n a r_n^d) = n^{b/d - ac}\to 0\] provided \(c>(b/d)/a\).
  • union bound: \(c > \max (b/d)/a\) over all portions
  • small and big clusters are more complicated, draw

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

Isolated points and AB coverage

Given \(\mathcal X, \mathcal Y\) sampled from \(A\) \[ T = \inf\{r: \mathcal X(B(y,r))\ge 1, \forall y\in \mathcal Y \}\]

  • lower bound of \(R_n\), the minimal matching threshold, and connectivity threshold of BRGG
  • related to AB-percolation, Iyer-Yogeshwaren

\(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\]

Papers

  • Largest nearest-neighbour link and connectivity threshold in a polytopal random sample Journal of Applied and Computational Topology
  • Covering one point process with another submitted

code:

https://github.com/frankiehiggs/connectivity-in-polytopes

https://github.com/frankiehiggs/CovXY

package:

https://github.com/xiaochuany/geography

Thanks