{
  "id": "1802.08224",
  "version": "v1",
  "published": "2018-02-22T18:23:52.000Z",
  "updated": "2018-02-22T18:23:52.000Z",
  "title": "Thresholds for vanishing of `Isolated' faces in random Čech and Vietoris-Rips complexes",
  "authors": [
    "Srikanth K. Iyer",
    "D. Yogeshwaran"
  ],
  "comment": "29 pages, 1 figure",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study combinatorial connectivity for two models of random geometric complexes. These two models - \\v{C}ech and Vietoris-Rips complexes - are built on a homogeneous Poisson point process of intensity $n$ on a $d$-dimensional torus using balls of radius $r_n$. In the former, the $k$-simplices/faces are formed by subsets of $(k+1)$ Poisson points such that the balls of radius $r_n$ centred at these points have a mutual interesection and in the latter, we require only a pairwise intersection of the balls. Given a (simplicial) complex (i.e., a collection of $k$-simplices for all $k \\geq 1$), we can connect $k$-simplices via $(k+1)$-simplices (`up-connectivity') or via $(k-1)$-simplices (`down-connectivity). Our interest is to understand these two combinatorial notions of connectivity for the random \\v{C}ech and Vietoris-Rips complexes asymptically as $n \\to \\infty$. In particular, we analyse in detail the threshold radius for vanishing of isolated $k$-faces for up and down connectivity of both types of random geometric complexes. Though it is expected that the threshold radius $r_n = \\Theta((\\frac{\\log n}{n})^{1/d})$ in coarse scale, our results give tighter bounds on the constants in the logarithmic scale as well as shed light on the possible second-order correction factors. Further, they also reveal interesting differences between the phase transition in the \\v{C}ech and Vietoris-Rips cases. The analysis is interesting due to the non-monotonicity of the number of isolated $k$-faces (as a function of the radius) and leads one to consider `monotonic' vanishing of isolated $k$-faces. The latter coincides with the vanishing threshold mentioned above at a coarse scale (i.e., $\\log n$ scale) but differs in the $\\log \\log n$ scale for the \\v{C}ech complex with $k = 1$ in the up-connected case.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-02-22T18:23:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60D05",
      "05E45",
      "60B99",
      "05C80"
    ],
    "keywords": [
      "vietoris-rips complexes",
      "random geometric complexes",
      "coarse scale",
      "threshold radius",
      "second-order correction factors"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}