Random Flag Complex (Pointcloud to Simplicial)

A random graph $G(n, p)$ denotes a distribution of possible graphs with $n$ vertices where each edge appear with probability $p$. These graphs are also called Erdos-Renyi graphs and their properties are analysed as $n \rightarrow \infty$. Then, a property of $G$ denoted $Q(G)$ is said to happen with high probability (w.h.p) if the probability of $Q(G)$ approaches $1$ as $n$ approaches $\infty$. For example, Let $\epsilon > 0$ be fixed, one can say that $G$ is connected w.h.p according to Erdos-Renyi 2 if

$$ p \geq \frac{(1+\epsilon) \log n}{n} $$

More recently, the properties of random topological structures has been studied in relation the the homological properties that arise out of these. Here we implement a Random Flag Complex. A Flag Complex is another name for the clique complex in the literature. A Flag Complex $\mathcal{X}(H)$ of a graph $H$ is then a clique lifting of $H$. Conversely, we say that a Flag Complex a Clique Complex and the Vietoris-Rips Complex are homeomorphic.

A Random Flag Complex $\mathcal{X}(n, p)$ is the Flag Complex of a random graph $G(n,p)$. Since a random graph consists of sampling the space of all possible graphs that can be formed by $n$ vertices with each edge having probability $p$, then the clique lifting of that graph is denoted $\mathcal{X}(n, p)$.

In [1] the author shows how the $k$-th homology group varies with $p$ in relation to $k$. This technique then provides a way to generate simplicial complexes from point clouds with desired homological properties given the setting of the parameter $p$ which in this implementation can also be regulated with a constant $\alpha$ such that $p=n^{-\alpha}$

---

[1] Kahle, M. (2014). Topology of random simplicial complexes: a survey. AMS Contemp. Math, 620, 201-222. [2] ERDdS, P., & R&wi, A. (1959). On random graphs I. Publ. math. debrecen, 6(290-297), 18.

---

From https://github.com/pyt-team/challenge-icml-2024/pull/50