# Does there exist a class of graphs with $O(n^2)$ maximal cliques which can be realized as the 1-skeleton of a Vietoris-Rips complex in $\mathbb R^2$?

Let $$\mathfrak G$$ be a class of graphs with quadratically many maximal cliques in the size of the vertex set. In other words, if $$G=(V,E)\in \mathfrak G$$ with $$|V|=n$$, the graph $$G$$ contains $$O(n^2)$$ maximal cliques.

Can $$G$$ be realized as the $$1$$-skeleton of a Vietoris-Rips complex $$Rips(X)_r$$ for some finite $$X\subset \mathbb R^2$$ (with the $$L_2$$ metric) at some scale parameter $$r \geq 0$$?

Recall that the Vietoris Rips complex on a finite set $$X$$ in a metric space at a scale parameter $$r$$ is the maximal simplicial complex defined by saying that a subset $$S\subset X$$ of $$k$$ points in $$X$$ is a $$(k+1)$$-simplex whenever $$\text{diam} (S)\leq r$$.

The Rips complex is completely determined by its $$1$$-skeleton, making it a clique complex.

I know that any planar or $$1$$-planar graph has only $$O(n)$$ maximal cliques, so therefore $$\mathfrak G$$ must not be contained in these classes, though it could potentially be $$k$$-planar for $$k\geq 2$$.

I've calculated numerous simple examples in $$\mathbb R^2$$ and I can't get quadratically many maximal cliques.

It seems that the geometry of $$\mathbb R^2$$ restricts this, but I'm not completely sure how to prove it rigorously.

Remark (edit): In full generality this question could be stated for classes of graphs having $$O(n^\ell)$$ maximal cliques for $$\ell\geq 2$$, but it seemed like asking when $$\ell=2$$ would be the simplest case to show.

• Could you explain in more detail how the class of graphs $\mathfrak{G}$ is defined? It seems to me that a class of graphs is defined if for each particular graph we can tell whether it belongs to this class or not. In this regard, it seems that the function of $O(n^2)$ must be completely concrete. Commented Jan 18, 2023 at 7:09

Since the Vietoris-Rips complex depends on the pairwise distances, this is equivalent to realizing the graph as a Vietoris-Rips complex at scale parameter $$r=1$$.
Proof. We illustrate this by the following example. Assume $$n=2 p$$. Draw a circle of diameter $$1+\epsilon$$, where $$0<\epsilon<<1$$. Place the $$2 p$$ nodes uniformly on the edge of the circle and label them clockwise from 1 to $$2 p$$. If $$\epsilon$$ is small enough, we have edges from any vertex $$i$$ to all other vertices except the diametrically opposite vertex $$(i+p)$$ mod $$2 p$$. Thus we have constructed a complete p-partite graph with its vertex set being a pair of diametrically opposite nodes i.e. $$\{i, i+p\}, i=1, \ldots p$$. The selection of one vertex from each of $$p$$ sets will form a maximal clique. Clearly we have a total of $$2^p=2^{n / 2}$$ maximal cliques. $$\Box$$