# A generalization of Geroch’s conjecture

Simon Brendle  Department of Mathematics
Columbia University
New York, NY, 10027<EMAIL_ADDRESS>,  Sven Hirsch  Department of
Mathematics
Duke University
Durham, NC, 27708<EMAIL_ADDRESS>and  Florian Johne  Department of
Mathematics
Columbia University
New York, NY, 10027<EMAIL_ADDRESS>
###### Abstract.

The Theorem of Bonnet–Myers implies that manifolds with topology
$M^{n-1}\times\mathbb{S}^{1}$ do not admit a metric of positive Ricci
curvature, while the resolution of Geroch’s conjecture implies that the torus
$\mathbb{T}^{n}$ does not admit a metric of positive scalar curvature. In this
work we introduce a new notion of curvature interpolating between Ricci and
scalar curvature (so called $m$-intermediate curvature), and use stable
weighted slicings to show that for $n\leq 7$ and $1\leq m\leq n-1$ the
manifolds $N^{n}=M^{n-m}\times\mathbb{T}^{m}$ do not admit a metric of
positive $m$-intermediate curvature.

##  1\. Introduction

Closed manifolds with positive Ricci curvature have finite fundamental group
due to the Theorem of Bonnet–Myers, in particular manifolds of topological
type $N^{n}=M^{n-1}\times\mathbb{S}^{1}$ do not admit a metric of positive
Ricci curvature. A different proof (at least in dimension $n\leq 7$) can be
obtained by minimizing area in a homology class and using the stability
inequality with test function $f=1$.

On the other hand, a conjecture of Geroch asks whether the torus
$\mathbb{T}^{n}$ does admit a metric of positive scalar curvature. This
conjecture was resolved by R. Schoen und S.-T. Yau for $3\leq n\leq 7$ by
using minimal hypersurfaces [10], and by M. Gromov and H.-B. Lawson by using
spinors for all dimensions [6]. The non-existence result for metrics of
positive scalar curvature was extended to closed $n$-dimensional aspherical
manifolds for $n\in\\{4,5\\}$ independently by O. Chodosh and C. Li [2] and by
M. Gromov [5]. For a more detailed overview on topological obstructions to
positive scalar curvature we refer to the recent survey by O. Chodosh and C.
Li [3].

The above obstruction for positive Ricci curvature and positive scalar
curvature raise the following question: What kind of curvature obstructions
can be found for manifolds of topological type
$N^{n}=M^{n-m}\times\mathbb{T}^{m}$? This is an interesting question even for
the case $N^{4}=\mathbb{S}^{2}\times\mathbb{T}^{2}$.

To investigate this question we define a family of curvature conditions (for
$1\leq m\leq n-1$) reducing to Ricci curvature for $m=1$ and to scalar
curvature for $m=n-1$ as follows:

######  Definition 1.1 (Positive $m$-intermediate curvature).

Suppose $(N^{n},g)$ is a Riemannian manifold. For given orthonormal vectors
$\\{e_{1},\dots,e_{m}\\}$ at the point $p\in N$ extend them to an orthonormal
basis $\\{e_{1},\dots,e_{n}\\}$ of $T_{p}M$. The $m$-intermediate curvature
$\mathcal{C}_{m}$ of the orthornormal vectors $\\{e_{1},\dots,e_{m}\\}$ is
defined by

$\mathcal{C}_{m}(e_{1},\dots,e_{m}):=\sum_{p=1}^{m}\sum_{q=p+1}^{n}\operatorname{Rm}_{N}(e_{p},e_{q},e_{p},e_{q}).$

We say that $(N^{n},g)$ has positive $m$-intermediate curvature at $p\in N$,
if we have $\mathcal{C}_{m}(e_{1},\dots,e_{m})>0$ for any choice of
orthornormal vectors $\\{e_{1},\dots,e_{m}\\}$. Moreover, we say that the
manifold $(N^{n},g)$ has positive $m$-intermediate curvature, if it has
positive $m$-intermediate curvature for all $p\in M$.

The product manifold $N^{n}=\mathbb{S}^{n-m}\times\mathbb{T}^{m}$ (with $1\leq
m\leq n-2$) with the standard metric on both factors has positive
$(m+1)$-intermediate curvature, and nonnegative $m$-intermediate curvature.

We observe that the condition of positive $m$-intermediate curvature defines a
non-empty, open, $O(n)$-invariant convex cone in the space of algebraic
curvature tensors for $1\leq m\leq n-1$. Moreover, under the conditions $2\leq
m\leq n-1$ and $n+2-m\leq k\leq n$ the curvature tensor of
$\mathbb{S}^{k-1}\times\mathbb{R}^{n-k+1}$ is contained in this open cone. The
general surgery result due to S. Hoelzel [7, Theorem A] then implies that
positive $m$-intermediate curvature is preserved under surgeries of
codimension at least $n+2-m$.

######  Remark 1.2 (Connection to other notions of curvature).

(i) The quantity $\mathcal{C}_{m}(e_{1},\dots,e_{m})$ is a sum of sectional
curvatures of planes containing at least one of the vectors
$e_{1},\ldots,e_{m}$. In particular, positive $m$-intermediate curvature is a
weaker condition than positive sectional curvature.

(ii) A manifold with positive $m$-intermediate curvature has positive scalar
curvature. Indeed, the sum $\sum_{1\leq p_{1}<\dots<p_{m}\leq
n}\mathcal{C}_{m}(e_{p_{1}},\dots,e_{p_{m}})$ is equal to the scalar
curvature, up to a factor.

(iii) There is a connection to the notion of $(m,n)$-intermediate scalar
curvature introduced (as $m$-curvature) into the literature by M.-L. Labbi [9]
and also studied by M. Burkemper, C. Searle and M. Walsh [1]. More precisely,
the $(m,n)$-intermediate scalar curvature defined by

$\displaystyle
s_{m,n}(e_{1},\dots,e_{m})=\sum_{p=m+1}^{n}\sum_{q=m+1}^{n}\operatorname{Rm}(e_{p},e_{q},e_{p},e_{q})$

satisfies the relation

$\displaystyle
s_{m,n}(e_{1},\dots,e_{m})+2\,\mathcal{C}_{m}(e_{1},\dots,e_{m})=\operatorname{R}.$

In particular, $\mathcal{C}_{m}(e_{1},\dots,e_{m})$ depends only on the span
of $\\{e_{1},\dots,e_{m}\\}$, hence the $m$-intermediate curvature
$\mathcal{C}_{m}$ can be regarded as a scalar function on the Grassmannian.

(iv) For $m=n-1$, we obtain $s_{n-1,n}(e_{1},\ldots,e_{n-1})=0$ and
$2\,\mathcal{C}_{n-1}(e_{1},\ldots,e_{n-1})=\operatorname{R}$. Hence, the
intermediate curvature reduces to the scalar curvature in this case.

The case $m=2$ (also called bi-Ricci curvature) was studied by Y. Shen and R.
Ye in [12, 13]. They proved diameter estimates for stable minimal submanifolds
in manifolds of positive bi-Ricci curvature and an estimate on the homology
radius.

Our first main theorem concerns obstructions for the existence of metrics of
positive $m$-intermediate curvature. To that end, we consider a notion of
stable weighted slicing. Our definition closely resembles the notion of
minimal $k$-slicings by R. Schoen and S.-T. Yau [11].

######  Definition 1.3 (Stable weighted slicing of order $m$).

Suppose $1\leq m\leq n-1$ and let $(N^{n},g)$ be an orientable Riemannian
manifold of dimension $\dim N=n$. A stable weighted slicing of order $m$
consists of a collection of orientable and smooth submanifolds $\Sigma_{k}$,
$0\leq k\leq m$, and a collection of positive functions $\rho_{k}\in
C^{\infty}(\Sigma_{k})$ satisfying the following conditions:

  * •

$\Sigma_{0}=N$ and $\rho_{0}=1$.

  * •

For each $1\leq k\leq m$, $\Sigma_{k}$ is an embedded two-sided hypersurface
in $\Sigma_{k-1}$. Moreover, $\Sigma_{k}$ is a stable critical point of the
$\rho_{k-1}$-weighted area

$\mathcal{H}^{n-k}_{\rho_{k-1}}(\Sigma)=\int_{\Sigma}\rho_{k-1}\,d\mu$

in the class of hypersurfaces $\Sigma\subset\Sigma_{k-1}$.

  * •

For each $1\leq k\leq m$, the function
$\frac{\rho_{k}}{\rho_{k-1}|_{\Sigma_{k}}}\in C^{\infty}(\Sigma_{k})$ is a
first eigenfunction of the stability operator associated with the
$\rho_{k-1}$-weighted area.

Observe that we use the first eigenfunction of the Jacobi operator of weighted
area, while in [11, p. 7] a perturbed version of the weighted stability
operator (denoted by $Q_{k}$) is used.

It is a classical theorem that manifolds with positive Ricci curvature do not
admit stable minimal hypersurfaces. Our first theorem shows that manifolds
with $m$-intermediate curvature do not allow stable weighted slicings of order
$m$.

######  Theorem 1.4 ($m$-intermediate curvature and stable weighted slicings).

Assume that $1\leq m\leq n-1$ and $n(m-2)\leq m^{2}-2$. Suppose $(N^{n},g)$ is
a closed and orientable Riemannian manifold with positive $m$-intermediate
curvature. Then $N$ does not admit a stable weighted slicing

$\Sigma_{m}\subset\dots\subset\Sigma_{1}\subset\Sigma_{0}=N^{n}$

of order $m$.

The inequality $n(m-2)\leq m^{2}-2$ is automatically satisfied for $m=1$
(Ricci curvature), $m=2$ (bi-Ricci curvature), $m=n-2$, and $m=n-1$ (scalar
curvature). Moreover, the inequality $n(m-2)\leq m^{2}-2$ holds for all $n\leq
7$ and all $1\leq m\leq n-1$. Surprisingly, in dimension $n\geq 8$, the
inequality $n(m-2)\leq m^{2}-2$ fails for $m=3$ (tri-Ricci curvature) and
$m=4$ (tetra-Ricci curvature).

The second step, which essentially is given in work of R. Schoen and S.-T. Yau
[10], gives a topological condition for the existence of a stable weighted
slicing:

######  Theorem 1.5 (Existence of stable weighted slicings).

Assume $n\leq 7$ and $1\leq m\leq n-1$. Let $N^{n}$ be a closed and orientable
manifold of dimension $n$, and suppose that there exists a closed and
orientable manifold $M^{n-m}$ and a map $F:N^{n}\rightarrow
M^{n-m}\times\mathbb{T}^{m}$ with non-zero degree. Then for each Riemannian
metric $g$ on $N^{n}$ there exists a stable weighted slicing

$\Sigma_{m}\subset\Sigma_{m-1}\subset\dots\subset\Sigma_{1}\subset\Sigma_{0}=N^{n}$

of order $m$. In conjunction with Theorem 1.4 we deduce that the manifold $N$
does not admit a metric with positive $m$-intermediate curvature.

The dimensional restriction allows us to invoke the regularity theory for
hypersurfaces minimizing a weighted area. As a consequence of the above
theorem we observe the following corollary:

######  Corollary 1.6 (Nonexistence of metrics of positive $m$-intermediate
curvature).

The product manifolds $N^{n}=M^{n-m}\times\mathbb{T}^{m}$ do not admit a
metric of positive $m$-intermediate curvature for $n\leq 7$ and $1\leq m\leq
n-1$.

In particular, the manifold $\mathbb{S}^{2}\times\mathbb{T}^{2}$ does not
admit a metric of positive bi-Ricci curvature.

In Section 2 we introduce our notation and recall the first and second
variation formula for weighted area. In Section 3, we describe the proof of
Theorem 1.4. Afterwards, in Section 4, we give the proof of Theorem 1.5 and
establish existence of stable weighted slicings under topological assumptions.

Acknowledgements: The first author was supported by the National Science
Foundation under grant DMS-2103573 and by the Simons Foundation. The second
author would like to thank Hubert Bray and Yiyue Zhang for their interest in
this work, and he acknowledges the hospitality of Columbia University, where
this project was initiated.

##  2\. The first and second variation of weighted area

For a Riemannian manifold $(N^{n},g)$ we consider its Levi-Civita connection
$D$ and its Riemann curvature tensor $\operatorname{Rm}_{N}$ given by the
formula

$\operatorname{Rm}_{N}(X,Y,Z,W)=-g(D_{X}D_{Y}Z-D_{Y}D_{X}Z-D_{[X,Y]}Z,W)$

for vector fields $X,Y,Z,W\in\Gamma(TN)$.
Consider a two-sided embedded submanifold $\Sigma^{n-1}$. We denote its
induced Levi-Civita connection by $D_{\Sigma}$, its unit normal vector field
by $\nu\in\Gamma(N\Sigma)$, its scalar-valued second fundamental form by
$h_{\Sigma}$ and its mean curvature (the trace of the scalar-valued second
fundamental form over $\Sigma$) by $H_{\Sigma}$. The gradient of a smooth
function on $N$ or $\Sigma$ is denoted by $D_{N}f$ or $D_{\Sigma}f$.

Our arguments employ the first and second variation formula of a suitably
weighted area: Consider a Riemannian manifold $(N^{n},g)$, a smooth positive
function $\rho:N\rightarrow\mathbb{R}$, and an embedded two-sided closed
manifold $\Sigma\subset N^{n}$. For a given smooth function $f\in
C^{\infty}(\Sigma)$ we consider a variation
$F:(-\epsilon,\epsilon)\times\Sigma\rightarrow N$ with $F(0,x)=x$ and
$\left.\frac{\partial}{\partial s}F(s,x)\right|_{s=0}=f(x)\,\nu(x)$. In the
following, we denote the map $F(s,\cdot)$ by $F_{s}$. Moreover, we denote by
$\Sigma_{s}$ the image of $F_{s}$ and by $\nu_{s}$ the unit normal vector
field to $F_{s}$.

By precomposing the maps $F_{s}$ with suitable tangential diffeomorphisms, we
can arrange that the variation is normal in the sense that

$\frac{\partial}{\partial s}F_{s}=f_{s}\,\nu_{s},$

where $f_{s}$ is a smooth function on $\Sigma_{s}$.

We consider the weighted area defined by

$\mathcal{H}^{n-1}_{\rho}(\Sigma):=\int_{\Sigma}\rho\,d\mu.$

We recall the classical formulae for the first and second variation of
weighted area:

######  Proposition 2.1 (First variation of weighted area).

The first variation of weighted area is given by

$\displaystyle\left.\frac{d}{ds}\mathcal{H}^{n-1}_{\rho}(\Sigma_{s})\right|_{s=0}=\int_{\Sigma}\rho
f\left(H_{\Sigma}+\langle D_{N}\log\rho,\nu\rangle\right)\,d\mu.$

###### Proof.

This is a consequence of the first variation formula for area, and the chain
rule. ∎

######  Corollary 2.2.

Suppose $\Sigma$ is a critical point of weighted area. Then we have

$H_{\Sigma}=-\langle D_{N}\log\rho,\nu\rangle.$

For a constant weight we recover the minimal surface equation $H_{\Sigma}=0$.

######  Proposition 2.3 (Second variation formula on critical points).

If $\Sigma$ is a critical point of the weighted area functional, then the
second variation of weighted area is given by

$\displaystyle\left.\frac{d^{2}}{ds^{2}}\mathcal{H}^{n-1}_{\rho}(\Sigma_{s})\right|_{s=0}$
$\displaystyle=$
$\displaystyle\int_{\Sigma}\rho\left(-f\Delta_{\Sigma}f-\left(|h_{\Sigma}|^{2}+\operatorname{Ric}_{N}(\nu,\nu)\right)f^{2}+f^{2}(D_{N}^{2}\log\rho)(\nu,\nu)-f\langle
D_{\Sigma}\log\rho,D_{\Sigma}f\rangle\right)\,d\mu.$

###### Proof.

We use normal variations for our computation, and hence the first derivative
is given by

$\frac{d}{ds}\int_{\Sigma_{s}}\rho\,d\mu_{s}=\int_{\Sigma_{s}}\rho
f_{s}\left(H_{\Sigma_{s}}+\langle
D_{N}\log\rho,\nu_{s}\rangle\right)\,d\mu_{s}.$

We now differentiate both sides of this equation with respect to $s$, and
evaluate the result at $s=0$. By the variation formulas for hypersurfaces,
compare for example with [8], the first order change in the mean curvature is
given by

$\left.\frac{\partial}{\partial
s}H_{\Sigma_{s}}\right|_{s=0}=-\Delta_{\Sigma}f-\left(|h_{\Sigma}|^{2}+\operatorname{Ric}_{N}(\nu,\nu)\right)f,$

whereas the first order change in the normal vector field is given by

$\left.D_{s}\nu_{s}\right|_{s=0}=-D_{\Sigma}f.$

This implies

$\displaystyle\left.\frac{\partial}{\partial s}\left(H_{\Sigma_{s}}+\langle
D_{N}\log\rho,\nu_{s}\rangle\right)\right|_{s=0}$
$\displaystyle=-\Delta_{\Sigma}f-\left(|h_{\Sigma}|^{2}+\operatorname{Ric}_{N}(\nu,\nu)\right)f+(D_{N}^{2}\log\rho)(\nu,\nu)f-\langle
D_{\Sigma}\log\rho,D_{\Sigma}f\rangle,$

hence

$\displaystyle\left.\frac{d^{2}}{ds^{2}}\mathcal{H}^{n-1}_{\rho}(\Sigma_{s})\right|_{s=0}$
$\displaystyle=$ $\displaystyle\int_{\Sigma}\rho
f\left(-\Delta_{\Sigma}f-\left(|h_{\Sigma}|^{2}+\operatorname{Ric}_{N}(\nu,\nu)\right)f+(D_{N}^{2}\log\rho)(\nu,\nu)f-\langle
D_{\Sigma}\log\rho,D_{\Sigma}f\rangle\right)\,d\mu.$

∎

For a constant weight we recover the usual second variation formula for
minimal hypersurfaces:

$\displaystyle\left.\frac{d^{2}}{ds^{2}}\mathcal{H}^{n-1}(\Sigma_{s})\right|_{s=0}=$
$\displaystyle\int_{\Sigma}\left(-f\Delta_{\Sigma}f-\left(|h_{\Sigma}|^{2}+\operatorname{Ric}_{N}(\nu,\nu)\right)f^{2}\right)\,d\mu.$

##  3\. Properties of stable weighted slicings

Let $(N^{n},g)$ be a closed and orientable Riemannian manifold of dimension
$\dim N=n$. Throughout this section, we assume that we are given a stable
weighted slicing of order $m$. Our goal is to show that the metric $g$ cannot
have positive $m$-intermediate curvature.

By the first variation formula for weighted area, Corollary 2.2, the mean
curvature $H_{\Sigma_{k}}$ of the slice $\Sigma_{k}$ in the manifold
$\Sigma_{k-1}$ satisfies for $1\leq k\leq m$ the relation

$H_{\Sigma_{k}}=-\langle D_{\Sigma_{k-1}}\log\rho_{k-1},\nu_{k}\rangle.$

By the second variation formula for weighted area (compare Proposition 2.3) we
obtain for $1\leq k\leq m$ the inequality

$\displaystyle 0\leq$
$\displaystyle\int_{\Sigma_{k}}\rho_{k-1}\left(-\psi\Delta_{\Sigma_{k}}\psi-\psi\langle
D_{\Sigma_{k}}\log\rho_{k-1},D_{\Sigma_{k}}\psi\rangle\right)\,d\mu$
$\displaystyle-\int_{\Sigma_{k}}\rho_{k-1}\left(|h_{\Sigma_{k}}|^{2}+\operatorname{Ric}_{\Sigma_{k-1}}(\nu_{k},\nu_{k})-(D_{\Sigma_{k-1}}^{2}\log\rho_{k-1})(\nu_{k},\nu_{k})\right)\psi^{2}\,d\mu$

for all $\psi\in C^{\infty}(\Sigma_{k})$. By Definition 1.3 we may write
$\rho_{k}=\rho_{k-1}\,v_{k}$, where $v_{k}>0$ is the first eigenfunction of
the stability operator for the weighted area functional. The function $v_{k}$
satisfies

$\displaystyle\lambda_{k}v_{k}=$
$\displaystyle-\Delta_{\Sigma_{k}}v_{k}-\langle
D_{\Sigma_{k}}\log\rho_{k-1},D_{\Sigma_{k}}v_{k}\rangle-\left(|h_{\Sigma_{k}}|^{2}+\operatorname{Ric}_{\Sigma_{k-1}}(\nu_{k},\nu_{k})\right)v_{k}$
$\displaystyle+(D_{\Sigma_{k-1}}^{2}\log\rho_{k-1})(\nu_{k},\nu_{k})v_{k},$

where $\lambda_{k}\geq 0$ denotes the first eigenvalue of the stability
operator.

By setting $w_{k}=\log v_{k}$ we record the following equation:

(1) $\displaystyle\lambda_{k}=$
$\displaystyle-\Delta_{\Sigma_{k}}w_{k}-\langle
D_{\Sigma_{k}}\log\rho_{k-1},D_{\Sigma_{k}}w_{k}\rangle-\left(|h_{\Sigma_{k}}|^{2}+\operatorname{Ric}_{\Sigma_{k-1}}(\nu_{k},\nu_{k})\right)$
$\displaystyle+(D_{\Sigma_{k-1}}^{2}\log\rho_{k-1})(\nu_{k},\nu_{k})-|D_{\Sigma_{k}}w_{k}|^{2}.$

We next record two lemmata connecting the second derivatives on consecutive
slices.

######  Lemma 3.1 (First slicing identity).

We have for $1\leq k\leq m$ the identiy

$\displaystyle\Delta_{\Sigma_{k}}\log\rho_{k-1}+(D_{\Sigma_{k-1}}^{2}\log\rho_{k-1})(\nu_{k},\nu_{k})=\Delta_{\Sigma_{k-1}}\log\rho_{k-1}+H_{\Sigma_{k}}^{2}.$

###### Proof.

The above formula follows by applying the formula relating the Laplace
operator on a submanifold to the Laplace operator on the ambient space

$\displaystyle\Delta_{\Sigma_{k}}f+(D_{\Sigma_{k-1}}^{2}f)(\nu_{k},\nu_{k})=\Delta_{\Sigma_{k-1}}f-H_{\Sigma_{k}}\langle
D_{\Sigma_{k-1}}f,\nu_{k}\rangle.$

to the function $f=\log\rho_{k-1}$. The gradient term on the right-hand side
is rewritten by using the first variation formula for weighted area

$H_{\Sigma_{k}}=-\langle D_{\Sigma_{k-1}}\log\rho_{k-1},\nu_{k}\rangle.$

from Corollary 2.2. ∎

######  Lemma 3.2 (Second slicing identity).

We have for $1\leq k\leq m-1$ the identity

$\displaystyle\Delta_{\Sigma_{k}}\log\rho_{k}=$
$\displaystyle\Delta_{\Sigma_{k}}\log\rho_{k-1}+(D_{\Sigma_{k-1}}^{2}\log\rho_{k-1})(\nu_{k},\nu_{k})$
$\displaystyle-\left(\lambda_{k}+|h_{\Sigma_{k}}|^{2}+\operatorname{Ric}_{\Sigma_{k-1}}(\nu_{k},\nu_{k})+\langle
D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}w_{k}\rangle\right).$

###### Proof.

This follows from the identity $\log\rho_{k}=w_{k}+\log\rho_{k-1}$ together
with the equation (1). ∎

######  Lemma 3.3 (Stability inequality on the bottom slice).

On the bottom slice $\Sigma_{m}$ we have the inequality

$\displaystyle\int_{\Sigma_{m}}\rho_{m-1}^{-1}\left(\Delta_{\Sigma_{m-1}}\log\rho_{m-1}+H_{\Sigma_{m}}^{2}\right)d\mu\geq\int_{\Sigma_{m}}\rho_{m-1}^{-1}\left(|h_{\Sigma_{m}}|^{2}+\operatorname{Ric}_{\Sigma_{m-1}}(\nu_{m},\nu_{m})\right)\,d\mu.$

###### Proof.

By the second variation of weighted area (compare Proposition 2.3) the
stability inequality on the bottom slice $\Sigma_{m}$ gives

$\displaystyle 0\leq$
$\displaystyle\int_{\Sigma_{m}}\rho_{m-1}\left(-\psi\Delta_{\Sigma_{m}}\psi-\psi\langle
D_{\Sigma_{m}}\log\rho_{m-1},D_{\Sigma_{m}}\psi\rangle\right)\,d\mu$
$\displaystyle-\int_{\Sigma_{m}}\rho_{m-1}\left(|h_{\Sigma_{m}}|^{2}+\operatorname{Ric}_{\Sigma_{m-1}}(\nu_{m},\nu_{m})-(D_{\Sigma_{m-1}}^{2}\log\rho_{m-1})(\nu_{m},\nu_{m})\right)\psi^{2}\,d\mu$

for all $\psi\in C^{\infty}(\Sigma_{m})$. Since the weight $\rho_{m-1}$ is
positive, we may use the direction $\psi=\rho_{m-1}^{-1}$ in the stability
inequality, and observe

$\displaystyle-\Delta_{\Sigma_{m}}\psi$
$\displaystyle=-\Delta_{\Sigma_{m}}\,\rho_{m-1}^{-1}=\rho_{m-1}^{-1}\Delta_{\Sigma_{m}}\log\rho_{m-1}-\rho_{m-1}^{-3}|D_{\Sigma_{m}}\rho_{m-1}|^{2},$
$\displaystyle-\langle D_{\Sigma_{m}}\log\rho_{m-1},D_{\Sigma_{m}}\psi\rangle$
$\displaystyle=-\langle
D_{\Sigma_{m}}\log\rho_{m-1},D_{\Sigma_{m}}\rho_{m-1}^{-1}\rangle=\rho_{m-1}^{-3}|D_{\Sigma_{m}}\rho_{m-1}|^{2}.$

The gradient terms in the previous formulae cancel, and we obtain by
rearrangement

$\displaystyle\int_{\Sigma_{m}}\rho_{m-1}^{-1}\left(\Delta_{\Sigma_{m}}\log\rho_{m-1}+(D_{\Sigma_{m-1}}^{2}\log\rho_{m-1})(\nu_{m},\nu_{m})\right)d\mu$
$\displaystyle\geq$
$\displaystyle\int_{\Sigma_{m}}\rho_{m-1}^{-1}\left(|h_{\Sigma_{m}}|^{2}+\operatorname{Ric}_{\Sigma_{m-1}}(\nu_{m},\nu_{m})\right)\,d\mu.$

Finally, we use the first slicing equality from Lemma 3.1 to replace

$\Delta_{\Sigma_{m}}\log\rho_{m-1}+(D_{\Sigma_{m-1}}^{2}\log\rho_{m-1})(\nu_{m},\nu_{m})=\Delta_{\Sigma_{m-1}}\log\rho_{m-1}+H_{\Sigma_{m}}^{2}.$

∎

######  Lemma 3.4 (Main inequality).

We have the inequality

$\displaystyle\int_{\Sigma_{m}}\rho_{m-1}^{-1}\left(\Lambda+\mathcal{R}+\mathcal{E}+\mathcal{G}\right)\,d\mu\leq
0,$

where the eigenvalue term $\Lambda$, the intrinsic curvature term
$\mathcal{R}$, the extrinsic curvature term $\mathcal{E}$, and the gradient
term $\mathcal{G}$ are given by

$\displaystyle\Lambda$
$\displaystyle=\sum_{k=1}^{m-1}\lambda_{k},\;\mathcal{R}=\sum_{k=1}^{m}\operatorname{Ric}_{\Sigma_{k-1}}(\nu_{k},\nu_{k}),\;\mathcal{G}=\sum_{k=1}^{m-1}\langle
D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}w_{k}\rangle,$
$\displaystyle\;\text{and}\;\;\mathcal{E}$
$\displaystyle=\sum_{k=1}^{m}|h_{\Sigma_{k}}|^{2}-\sum_{k=2}^{m}H_{\Sigma_{k}}^{2}.$

###### Proof.

If we substitute the first slicing equality, Lemma 3.1, into the second
slicing equality, Lemma 3.2, we obtain for $1\leq k\leq m-1$ the identity

$\displaystyle\Delta_{\Sigma_{k}}\log\rho_{k}=\Delta_{\Sigma_{k-1}}\log\rho_{k-1}+H_{\Sigma_{k}}^{2}$
$\displaystyle-\left(\lambda_{k}+|h_{\Sigma_{k}}|^{2}+\operatorname{Ric}_{\Sigma_{k-1}}(\nu_{k},\nu_{k})+\langle
D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}w_{k}\rangle\right).$

Summation of the above formula over $k$ from $1$ to $m-1$ yields

$\displaystyle\Delta_{\Sigma_{m-1}}\log\rho_{m-1}=$
$\displaystyle\Delta_{\Sigma_{0}}\log\rho_{0}+\sum_{k=1}^{m-1}H_{\Sigma_{k}}^{2}$
$\displaystyle-\sum_{k=1}^{m-1}\left(\lambda_{k}+|h_{\Sigma_{k}}|^{2}+\operatorname{Ric}_{\Sigma_{k-1}}(\nu_{k},\nu_{k})+\langle
D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}w_{k}\rangle\right).$

We plug this equation into the stability inequality, Lemma 3.3. Moreover, we
observe that the weight $\rho_{0}$ is constant, the mean curvature of the top
slice $H_{\Sigma_{1}}$ vanishes, and that the stability inequality contains
the mean curvature term $H_{\Sigma_{m}}^{2}$ the extrinsic curvature term
$|h_{\Sigma_{m}}|^{2}$ and the curvature term
$\operatorname{Ric}_{\Sigma_{m-1}}(\nu_{m},\nu_{m})$. Then the lemma follows
by grouping the terms suitably. ∎

We consider two examples to illustrate the structure of the curvature terms:

######  Example 3.5 (Positive Ricci curvature and $m=1$).

In the case $m=1$ we have the slicing $\Sigma_{1}\subset\Sigma_{0}=N^{n}$ and
we recover the classic result on the instability of minimal hypersurfaces in
positive Ricci curvature $\operatorname{Ric}>0$. Indeed, we have
$\Lambda=\mathcal{G}=0$, $\mathcal{E}=|h_{\Sigma_{1}}|^{2}$, and
$\mathcal{R}=\operatorname{Ric}_{N}(\nu_{1},\nu_{1})$. Thus
$\mathcal{R}+\mathcal{E}>0$. Combined with the existence theory for stable
weighted slicings from Section 4 this implies the non-existence of metrics of
positive Ricci curvature on manifolds with topology
$N^{n}=M^{n-1}\times\mathbb{S}^{1}$ in dimension $\dim N\leq 7$.

######  Example 3.6 (Positive bi-Ricci curvature and $m=2$).

In the case $m=2$ we have the slicing
$\Sigma_{2}\subset\Sigma_{1}\subset\Sigma_{0}=N^{n}$. We moreover observe
$\Lambda=\lambda_{1}\geq 0$, $\mathcal{G}=|D_{\Sigma_{1}}w_{1}|^{2}\geq
H_{\Sigma_{2}}^{2}$, and the curvature terms $\mathcal{E}$ and $\mathcal{R}$
are given by

$\displaystyle\mathcal{E}=|h_{\Sigma_{1}}|^{2}+|h_{\Sigma_{2}}|^{2}-H_{\Sigma_{2}}^{2},$
and
$\displaystyle\mathcal{R}=\operatorname{Ric}_{N}(\nu_{1},\nu_{1})+\operatorname{Ric}_{N}(\nu_{2},\nu_{2})-\operatorname{Rm}_{N}(\nu_{1},\nu_{2},\nu_{1},\nu_{2})-(h_{\Sigma_{1}}^{2})(\nu_{1},\nu_{1}).$

Thus if we assume positive bi-Ricci curvature we have
$\Lambda+\mathcal{R}+\mathcal{E}+\mathcal{G}>0$. This shows a non-existence
result for stable weighted slicings of order two. Combined with the existence
theory for stable weighted slicings from Section 4 this implies that a
manifold with topology $N^{n}=M^{n-2}\times\mathbb{T}^{2}$ (with $n\leq 7$)
does not admit a metric of positive bi-Ricci curvature.

The eigenvalue term $\Lambda$ is non-negative, since it is the sum of the non-
negative eigenvalues. We will estimate the other terms below.

The first step is to estimate the gradient terms:

######  Lemma 3.7 (Estimate of gradient terms).

We have the estimate

$\displaystyle\mathcal{G}\geq\sum_{k=2}^{m}\left(\frac{1}{2}+\frac{1}{2(k-1)}\right)H_{\Sigma_{k}}^{2}.$

###### Proof.

We define for $k\geq 1$ the nonnegative real numbers $\alpha_{k}$ by

$\alpha_{k}=\frac{k-1}{2k}.$

By direct computation one verifies the identity

$\displaystyle 1-\alpha_{k-1}=\frac{1}{4\alpha_{k}}$

for $k\geq 2$. Using the identity $H_{\Sigma_{k+1}}=-\langle
D_{\Sigma_{k}}\log\rho_{k},\nu_{k+1}\rangle$, we obtain

$\displaystyle\langle D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}w_{k}\rangle$
$\displaystyle=$ $\displaystyle\langle
D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}(\log\rho_{k}-\log\rho_{k-1})\rangle$
$\displaystyle=$
$\displaystyle(1-\alpha_{k})|D_{\Sigma_{k}}\log\rho_{k}|^{2}-\frac{1}{4\alpha_{k}}|D_{\Sigma_{k}}\log\rho_{k-1}|^{2}$
$\displaystyle+\alpha_{k}\,\left|D_{\Sigma_{k}}\log\rho_{k}-\frac{1}{2\alpha_{k}}D_{\Sigma_{k}}\log\rho_{k-1}\right|^{2}$
$\displaystyle=$
$\displaystyle(1-\alpha_{k})\,H_{\Sigma_{k+1}}^{2}+(1-\alpha_{k})\,|D_{\Sigma_{k+1}}\log\rho_{k}|^{2}-(1-\alpha_{k-1})\,|D_{\Sigma_{k}}\log\rho_{k-1}|^{2}$
$\displaystyle+\alpha_{k}\,\left|D_{\Sigma_{k}}\log\rho_{k}-\frac{1}{2\alpha_{k}}D_{\Sigma_{k}}\log\rho_{k-1}\right|^{2}$

for $2\leq k\leq m-1$. Summation over $k$ from $2$ to $m-1$ yields the formula

$\sum_{k=2}^{m-1}\langle
D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}w_{k}\rangle\geq\sum_{k=2}^{m-1}(1-\alpha_{k})\,H_{\Sigma_{k+1}}^{2}+(1-\alpha_{m-1})\,|D_{\Sigma_{m}}\log\rho_{m-1}|^{2}-|D_{\Sigma_{2}}\log\rho_{1}|^{2}.$

Moreover, the identity $H_{\Sigma_{2}}=-\langle
D_{\Sigma_{1}}\log\rho_{1},\nu_{2}\rangle$ implies

$\langle
D_{\Sigma_{1}}\log\rho_{1},D_{\Sigma_{1}}w_{1}\rangle=|D_{\Sigma_{1}}\log\rho_{1}|^{2}=H_{\Sigma_{2}}^{2}+|D_{\Sigma_{2}}\log\rho_{1}|^{2}.$

Adding the two inequalities gives

$\sum_{k=1}^{m-1}\langle
D_{\Sigma_{k}}\log\rho_{k},D_{\Sigma_{k}}w_{k}\rangle\geq\sum_{k=1}^{m-1}(1-\alpha_{k})\,H_{\Sigma_{k+1}}^{2}+(1-\alpha_{m-1})\,|D_{\Sigma_{m}}\log\rho_{m-1}|^{2}.$

∎

In the next step we rewrite the intrinsic curvature terms with the help of the
Gauss equations:

######  Lemma 3.8 (Iterated Gauss equations).

The curvature term $\mathcal{R}$ is given by

$\displaystyle\mathcal{R}=\mathcal{C}_{m}(e_{1},\dots,e_{m})+\sum_{k=1}^{m-1}\sum_{p=k+1}^{m}\sum_{q=p+1}^{n}\left(h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{p}}(e_{q},e_{q})-h_{\Sigma_{k}}(e_{p},e_{q})^{2}\right),$

where $\mathcal{C}_{m}$ denotes the $m$-intermediate curvature of the
Riemannian manifold $(N^{n},g)$.

###### Proof.

Fix a point $x\in\Sigma_{m}$ and consider an orthornomal basis
$\\{e_{1},\dots,e_{n}\\}$ of $T_{x}N$ with $e_{j}=\nu_{j}$ for $1\leq j\leq m$
as above. We observe by the definition of the Ricci curvature on the slice
$\Sigma_{k-1}$, and by the Gauss equations the formula

$\displaystyle\operatorname{Ric}_{\Sigma_{p-1}}(\nu_{p},\nu_{p})$
$\displaystyle=\operatorname{Ric}_{\Sigma_{p-1}}(e_{p},e_{p})=\sum_{q=p+1}^{n}\operatorname{Rm}_{\Sigma_{p-1}}(e_{p},e_{q},e_{p},e_{q})$
$\displaystyle=\sum_{q=p+1}^{n}\operatorname{Rm}_{N}(e_{p},e_{q},e_{p},e_{q})+\sum_{q=p+1}^{n}\sum_{k=1}^{p-1}\left(h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{k}}(e_{q},e_{q})-h_{\Sigma_{k}}(e_{p},e_{q})^{2}\right).$

Summation over $p$ from $1$ to $m$ then implies

$\displaystyle\mathcal{R}$
$\displaystyle=\sum_{p=1}^{m}\operatorname{Ric}_{\Sigma_{p-1}}(\nu_{p},\nu_{p})$
$\displaystyle=\sum_{p=1}^{m}\sum_{q=p+1}^{n}\operatorname{Rm}_{N}(e_{p},e_{q},e_{p},e_{q})+\sum_{p=1}^{m}\sum_{q=p+1}^{n}\sum_{k=1}^{p-1}\left(h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{k}}(e_{q},e_{q})-h_{\Sigma_{k}}(e_{p},e_{q})^{2}\right)$
$\displaystyle=\mathcal{C}_{m}(e_{1},\dots,e_{m})+\sum_{p=1}^{m}\sum_{q=p+1}^{n}\sum_{k=1}^{p-1}\left(h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{k}}(e_{q},e_{q})-h_{\Sigma_{k}}(e_{p},e_{q})^{2}\right).$

If we interchange the order of summation, the assertion follows. ∎

######  Remark 3.9 (Observation on full slicing).

In the special case $m=n-1$ the curvature term $\mathcal{R}$ can be rewritten
as

$\displaystyle\mathcal{R}$
$\displaystyle=\mathcal{C}_{n-1}(e_{1},\dots,e_{n-1})+\sum_{k=1}^{n-2}\sum_{p=k+1}^{n-1}\sum_{q=p+1}^{n}\left(h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{p}}(e_{q},e_{q})-h_{\Sigma_{k}}(e_{p},e_{q})^{2}\right)$
$\displaystyle=\frac{1}{2}\operatorname{R}_{N}+\frac{1}{2}\sum_{k=1}^{n-2}\left(H_{\Sigma_{k}}^{2}-|h_{\Sigma_{k}}|^{2}\right).$

(cf. Remark 1.2 (iv)). Note that the mean curvature of the top slice
$\Sigma_{1}$ vanishes, and that $H_{\Sigma_{n-1}}^{2}=|h_{\Sigma_{n-1}}|^{2}$
since $\Sigma_{n-1}$ is one-dimensional. Therefore, for $m=n-1$ we obtain

$\displaystyle\mathcal{R}+\mathcal{E}+\mathcal{G}$
$\displaystyle=\frac{1}{2}\operatorname{R}_{N}+\frac{1}{2}\sum_{k=1}^{n-1}|h_{\Sigma_{k}}|^{2}-\frac{1}{2}\sum_{k=1}^{n-1}H_{\Sigma_{k}}^{2}+\mathcal{G}$
$\displaystyle\geq\frac{1}{2}\operatorname{R}_{N}+\frac{1}{2}\sum_{k=1}^{n-1}|h_{\Sigma_{k}}|^{2}+\sum_{k=2}^{n-1}\frac{1}{2(k-1)}H_{\Sigma_{k}}^{2}.$

In the last step we have used the estimate for the gradient terms
$\mathcal{G}$ from Lemma 3.7. Hence, we recover a similar result as in the
computation of R. Schoen and S.-T. Yau [11].

In the next step we need to analyze the contributions coming from the
extrinsic curvature. We fix $m\in\\{2,\dots,n-1\\}$, and we define for $1\leq
k\leq m$ the extrinsic curvature terms $\mathcal{V}_{k}$:

$\displaystyle\mathcal{V}_{1}=$
$\displaystyle|h_{\Sigma_{1}}|^{2}+\sum_{p=2}^{m}\sum_{q=p+1}^{n}\left(h_{\Sigma_{1}}(e_{p},e_{p})h_{\Sigma_{1}}(e_{q},e_{q})-h_{\Sigma_{1}}(e_{p},e_{q})^{2}\right),$
$\displaystyle\mathcal{V}_{k}=$
$\displaystyle|h_{\Sigma_{k}}|^{2}-\left(\frac{1}{2}-\frac{1}{2(k-1)}\right)H_{\Sigma_{k}}^{2}$
$\displaystyle+\sum_{p=k+1}^{m}\sum_{q=p+1}^{n}\left(h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{k}}(e_{q},e_{q})-h_{\Sigma_{k}}(e_{p},e_{q})^{2}\right)\;\text{for}\;2\leq
k\leq m-1,$ $\displaystyle\mathcal{V}_{m}=$
$\displaystyle|h_{\Sigma_{m}}|^{2}-\left(\frac{1}{2}-\frac{1}{2(m-1)}\right)H_{\Sigma_{m}}^{2}.$

By combining Lemma 3.7, with Lemma 3.8, and the above expressions
$\mathcal{V}_{k}$ for the extrinsic curvature terms, we obtain:

######  Lemma 3.10.

For $2\leq m\leq n-1$ we have the pointwise estimate

$\displaystyle\mathcal{R}+\mathcal{E}+\mathcal{G}\geq\mathcal{C}_{m}(e_{1},\dots,e_{m})+\sum_{k=1}^{m}\mathcal{V}_{k}.$

In the following lemmata we estimate the extrinsic curvature terms
$\mathcal{V}_{k}$. The estimate for $\mathcal{V}_{m}$ follows from the trace
estimate for symmetric two-tensors. The estimate for $\mathcal{V}_{1}$ uses
minimality of the top slice $\Sigma_{1}$. The estimate for $\mathcal{V}_{k}$
with $2\leq k\leq m-1$ is the most involved.

######  Lemma 3.11 (Extrinsic curvature terms on top slice).

For $2\leq m\leq n-1$ we have the estimate

$\displaystyle\mathcal{V}_{1}\geq\frac{m^{2}-2-n(m-2)}{2(n-m)(m-1)}\left(\sum_{p=2}^{m}h_{\Sigma_{1}}(e_{p},e_{p})\right)^{2}.$

###### Proof.

To estimate the term $\mathcal{V}_{1}$, we begin by discarding the off-
diagonal terms of the second fundamental form $h_{\Sigma_{1}}$:

$\displaystyle\mathcal{V}_{1}=$
$\displaystyle|h_{\Sigma_{1}}|^{2}+\sum_{p=2}^{m}\sum_{q=p+1}^{n}\left(h_{\Sigma_{1}}(e_{p},e_{p})h_{\Sigma_{1}}(e_{q},e_{q})-h_{\Sigma_{1}}(e_{p},e_{q})^{2}\right)$
$\displaystyle\geq$
$\displaystyle\sum_{p=2}^{n}h_{\Sigma_{1}}(e_{p},e_{p})^{2}+\sum_{p=2}^{m}\sum_{q=p+1}^{n}h_{\Sigma_{1}}(e_{p},e_{p})h_{\Sigma_{1}}(e_{q},e_{q}).$

The terms on the right hand side can be rewritten as follows:

$\mathcal{V}_{1}\geq\frac{1}{2}\sum_{p=2}^{m}h_{\Sigma_{1}}(e_{p},e_{p})^{2}+\sum_{q=m+1}^{n}h_{\Sigma_{1}}(e_{q},e_{q})^{2}+\sum_{p=2}^{m}h_{\Sigma_{1}}(e_{p},e_{p})\,H_{\Sigma_{1}}-\frac{1}{2}\left(\sum_{p=2}^{m}h_{\Sigma_{1}}(e_{p},e_{p})\right)^{2}.$

Recall that $H_{\Sigma_{1}}=0$. By the Cauchy–Schwarz inequality,

$\sum_{p=2}^{m}h_{\Sigma_{1}}(e_{p},e_{p})^{2}\geq\frac{1}{m-1}\left(\sum_{p=2}^{m}h_{\Sigma_{1}}(e_{p},e_{p})\right)^{2}$

and

$\sum_{q=m+1}^{n}h_{\Sigma_{1}}(e_{q},e_{q})^{2}\geq\frac{1}{n-m}\left(\sum_{q=m+1}^{n}h_{\Sigma_{1}}(e_{q},e_{q})\right)^{2}=\frac{1}{n-m}\left(\sum_{p=2}^{m}h_{\Sigma_{1}}(e_{p},e_{p})\right)^{2},$

where in the last step we have used the fact that $H_{\Sigma_{1}}=0$. Putting
these facts together, the assertion follows. ∎

######  Lemma 3.12 (Extrinsic curvature terms on intermediate slices).

For $2\leq m\leq n-1$ and $2\leq k\leq m-1$ we have the estimate

$\displaystyle\mathcal{V}_{k}\geq\frac{m^{2}-2-n(m-2)}{2(m-1)(n-m)}\left(\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})\right)^{2}.$

###### Proof.

To estimate the term $\mathcal{V}_{k}$, we start by discarding the off-
diagonal terms:

$\displaystyle\mathcal{V}_{k}=$
$\displaystyle|h_{\Sigma_{k}}|^{2}-\left(\frac{1}{2}-\frac{1}{2(k-1)}\right)H_{\Sigma_{k}}^{2}+\sum_{p=k+1}^{m}\sum_{q=p+1}^{n}\left(h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{k}}(e_{q},e_{q})-h_{\Sigma_{k}}(e_{p},e_{q})^{2}\right)$
$\displaystyle\geq$
$\displaystyle\sum_{p=k+1}^{n}h_{\Sigma_{k}}(e_{p},e_{p})^{2}-\left(\frac{1}{2}-\frac{1}{2(k-1)}\right)H_{\Sigma_{k}}^{2}+\sum_{p=k+1}^{m}\sum_{q=p+1}^{n}h_{\Sigma_{k}}(e_{p},e_{p})h_{\Sigma_{k}}(e_{q},e_{q}).$

The terms on the right hand side can be rewritten as follows:

$\displaystyle\mathcal{V}_{k}\geq$
$\displaystyle\frac{1}{2}\sum_{p=k+1}^{m}h_{\Sigma_{k}}(e_{p},e_{p})^{2}+\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})^{2}$
$\displaystyle+\frac{1}{2(k-1)}\left(\sum_{p=k+1}^{m}h_{\Sigma_{k}}(e_{p},e_{p})\right)^{2}-\left(\frac{1}{2}-\frac{1}{2(k-1)}\right)\left(\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})\right)^{2}$
$\displaystyle+\frac{1}{k-1}\left(\sum_{p=k+1}^{m}h_{\Sigma_{k}}(e_{p},e_{p})\right)\left(\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})\right).$

The Cauchy–Schwarz inequality gives

$\sum_{p=k+1}^{m}h_{\Sigma_{k}}(e_{p},e_{p})^{2}\geq\frac{1}{m-k}\left(\sum_{p=k+1}^{m}h_{\Sigma_{k}}(e_{p},e_{p})\right)^{2}$

and

$\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})^{2}\geq\frac{1}{n-m}\left(\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})\right)^{2}.$

Moreover, Young’s inequality implies

$\displaystyle\left(\sum_{p=k+1}^{m}h_{\Sigma_{k}}(e_{p},e_{p})\right)\left(\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})\right)\geq$
$\displaystyle-\frac{m-1}{2(m-k)}\left(\sum_{p=k+1}^{m}h_{\Sigma_{k}}(e_{p},e_{p})\right)^{2}$
$\displaystyle-\frac{m-k}{2(m-1)}\left(\sum_{q=m+1}^{n}h_{\Sigma_{k}}(e_{q},e_{q})\right)^{2}.$

Putting these facts together, the assertion follows. ∎

######  Lemma 3.13 (Extrinsic curvature terms on bottom slice).

For $2\leq m\leq n-1$ we have the estimate

(2)
$\mathcal{V}_{m}\geq\frac{m^{2}-2-n(m-2)}{2(n-m)(m-1)}\,H_{\Sigma_{m}}^{2}.$

###### Proof.

We observe by the the trace estimate for symmetric two-tensors the inequality

$\displaystyle\mathcal{V}_{m}$
$\displaystyle=|h_{\Sigma_{m}}|^{2}-\left(\frac{1}{2}-\frac{1}{2(m-1)}\right)H_{\Sigma_{m}}^{2}\geq\left(\frac{1}{n-m}-\left(\frac{1}{2}-\frac{1}{2(m-1)}\right)\right)H_{\Sigma_{m}}^{2}$
$\displaystyle=\frac{m^{2}-2-n(m-2)}{2(n-m)(m-1)}\,H_{\Sigma_{m}}^{2}.$

∎

With the above observations we prove our first theorem:

###### Proof of Theorem 1.4.

Assume that $1\leq m\leq n-1$ and $n(m-2)\leq m^{2}-2$. Suppose that
$(N^{n},g)$ is a closed and orientable Riemannian manifold which admits a
stable weighted slicing

$\Sigma_{m}\subset\Sigma_{m-1}\subset\dots\subset\Sigma_{1}\subset\Sigma_{0}=N^{n}.$

If $m=1$, the stability inequality implies that $(N^{n},g)$ cannot have
positive Ricci curvature. Hence, it remains to consider the case when $2\leq
m\leq n-1$ and $n(m-2)\leq m^{2}-2$. In this case, it follows from Lemma 3.11,
Lemma 3.12, and Lemma 2 that $\mathcal{V}_{k}\geq 0$ for all $1\leq k\leq m$.
Using Lemma 3.10, we obtain the pointwise inequality

$\displaystyle\mathcal{R}+\mathcal{E}+\mathcal{G}\geq\mathcal{C}_{m}(e_{1},\dots,e_{m}).$

If $\mathcal{C}_{m}(e_{1},\dots,e_{m})$ is strictly positive, this contradicts
our main inequality, Lemma 3.4. Therefore, the Riemannian manifold $(N^{n},g)$
cannot have positive $m$-intermediate curvature. ∎

##  4\. Existence of stable weighted slicings

In this section we prove existence of stable weighted slicings of order $m$.
The argument uses the mapping degree and is essentially contained in Theorem
4.5 of [11]. Alternatively, one could also use an argument based on homology,
compare with Theorem 4.6 in [11].

###### Proof of Theorem 1.5.

Suppose $N^{n}$ and $M^{n-m}$ are closed and orientable manifolds, and suppose
$F:N^{n}\rightarrow\mathbb{T}^{m}\times M^{n-m}$ is a map of degree $d\neq 0$.
The projection of $F$ onto the factors yields maps $f_{0}:N\rightarrow M$ and
maps $f_{1},\dots,f_{m}:N\rightarrow\mathbb{S}^{1}$. Let $\Theta$ be a top-
dimensional form of the manifold $M$ normalized such that $\int_{M}\Theta=1$,
and let $\theta$ be a one-form on the circle $\mathbb{S}^{1}$ with
$\int_{\mathbb{S}^{1}}\theta=1$. We define the pull-back forms
$\Omega:=f_{0}^{*}\,\Theta$ and $\omega_{j}:=f_{j}^{*}\,\theta$. By the
normalization condition we deduce that
$\int_{N}\omega_{1}\wedge\dots\wedge\omega_{m}\wedge\Omega=d$.

We claim that one can construct closed and orientable slices $\Sigma_{k}$ and
weights $\rho_{k}$ such that
$\int_{\Sigma_{k}}\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega=d$. We
prove the claim by induction. The base case $k=0$ holds by the previous
observation and by setting $\Sigma_{0}:=N$ and $\rho_{0}:=1$. For the
induction step we suppose that we have constructed the slice $\Sigma_{k-1}$
and the weight $\rho_{k-1}$, such that
$\int_{\Sigma_{k-1}}\omega_{k}\wedge\dots\wedge\omega_{m}\wedge\Omega=d$.

We define a class $\mathcal{A}_{k}$ by

$\displaystyle\mathcal{A}_{k}=\left\\{\Sigma\;\text{is
an}\;(n-k)-\text{integer rectifiable current in
}\Sigma_{k}\;\text{with}\;\int_{\Sigma}\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega=d\right\\}.$

The first step is to show that the class $\mathcal{A}_{k}$ is non-empty. To
prove this, let us fix a regular value $p_{k}\in\mathbb{S}^{1}$ of the map
$f_{k}|_{\Sigma_{k-1}}:\Sigma_{k-1}\rightarrow\mathbb{S}^{1}$. The existence
of a regular value follows from Sard’s Theorem.

On the complement $\mathbb{S}^{1}\backslash\\{p_{k}\\}$ the one-form $\theta$
is exact. In other words, there exists a smooth function
$\psi_{k}:\mathbb{S}^{1}\backslash\\{p_{k}\\}\rightarrow\mathbb{R}$, such that
$d\psi_{k}=\theta$. Moreover, due to the normalization condition
$\int_{\mathbb{S}^{1}}\theta=1$, the function $\psi_{k}$ jumps by $1$ at
$p_{k}$.

We next consider the pre-image
$\tilde{\Sigma}_{k}=\\{x\in\Sigma_{k-1}:f_{k}(x)=p_{k}\\}$. Since
$p_{k}\in\mathbb{S}^{1}$ is a regular value of the map
$f_{k}|_{\Sigma_{k-1}}:\Sigma_{k-1}\rightarrow\mathbb{S}^{1}$, it follows that
$\tilde{\Sigma}_{k}$ is a closed and orientable submanifold of $\Sigma_{k-1}$.
We define a function
$\varphi_{k}:\Sigma_{k-1}\backslash\tilde{\Sigma}_{k}\rightarrow\mathbb{R}$ by
setting $\varphi_{k}:=\psi_{k}\circ f_{k}$. Since the pull-back commutes with
the differential, we deduce
$d\varphi_{k}=f_{k}^{*}\,(d\psi_{k})=f_{k}^{*}\,\theta=\omega_{k}$ on
$\Sigma_{k-1}\backslash\tilde{\Sigma}_{k}$.

The above observation (and the closedness of the forms
$\omega_{k},\dots,\omega_{m},\Omega$) implies

(3)
$\omega_{k}\wedge\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega=d(\varphi_{k}\,\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega).$

We first consider the case when $\tilde{\Sigma}_{k}$ is empty. Integrating the
identity (3) over $\Sigma_{k-1}$ gives

$\displaystyle
d=\int_{\Sigma_{k-1}}\omega_{k}\wedge\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega=\int_{\Sigma_{k-1}}d(\varphi_{k}\,\omega_{k+1}\wedge\cdots\wedge\omega_{m}\wedge\Omega)=0.$

This is a contradiction.

It remains to consider the case when $\tilde{\Sigma}_{k}$ is non-empty. In
this case $\tilde{\Sigma}_{k}$ is a smooth, orientable and embedded
hypersurface in $\Sigma_{k-1}$. We integrate identity (3) over
$\Sigma_{k-1}\setminus\tilde{\Sigma}_{k}$. By Stokes theorem, the integral of
the right hand side yields two boundary integrals over $\tilde{\Sigma}_{k}$.
Since the function $\varphi_{k}$ jumps by $1$ along $\tilde{\Sigma}_{k}$, we
obtain

$\displaystyle
d=\int_{\Sigma_{k-1}\setminus\tilde{\Sigma}_{k}}\omega_{k}\wedge\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega$
$\displaystyle=\int_{\Sigma_{k-1}\setminus\tilde{\Sigma}_{k}}d(\varphi_{k}\,\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega)$
$\displaystyle=\pm\int_{\tilde{\Sigma}_{k}}\omega_{k+1}\wedge\dots\wedge\omega_{m}\wedge\Omega,$

where the sign depends on the choice of orientation of $\tilde{\Sigma}_{k}$.
Therefore, we can make a choice of orientation so that $\tilde{\Sigma}_{k}$
belongs to the class $\mathcal{A}_{k}$. In particular, the class
$\mathcal{A}_{k}$ is non-empty.

We consider the variational problem

$\displaystyle\sigma_{k}=\inf\left\\{\mathbb{M}_{\rho_{k-1},n-k}(\Sigma):\Sigma\in\mathcal{A}_{k}\right\\},$

where $\mathbb{M}_{\rho_{k-1},n-k}$ denotes the $\rho_{k-1}$-weighted mass
functional on $(n-k)$-integer rectifiable currents. By the compactness theory
for integer rectifiable currents, compare for example Theorem 7.5.3 in [14],
we deduce that there exists an $(n-k)$-integer rectifiable current
$\Sigma_{k+1}$ with mass $\mathbb{M}_{\rho_{k-1},n-k}(\Sigma_{k})=\sigma_{k}$.

By the regularity theory for integer rectifiable currents, compare for example
Theorem 7.5.8 in [14] or the survey [4], and the dimension bound $n\leq 7$ we
deduce that $\Sigma_{k}$ is a smooth and orientable (and hence two-sided)
hypersurface. Moreover, the smooth surface $\Sigma_{k}$ is stable with respect
to variations of the weighted area, and therefore we can find a positive first
eigenfunction $v_{k}$ of the weighted stability operator. Defining the weight
$\rho_{k}$ by the formula $\rho_{k}=\rho_{k-1}\cdot v_{k}$ completes the
induction step. ∎

## References

  * [1] M. Burkemper, C. Searle and M. Walsh, Positive $(p,n)$-intermediate scalar curvature and cobordism, arxiv:2110.12069
  * [2] O. Chodosh and C. Li, Generalized soap bubbles and the topology of manifolds with positive scalar curvature, arxiv:2008.11888
  * [3] O. Chodosh and C. Li, Recent results concerning topological obstructions to positive scalar curvature, Perspectives in Scalar Curvature, World Scientific Publishing Company vol. 2 (2022)
  * [4] C. De Lellis, The regularity theory for the area functional (in geometric measure theory), International Congress of Mathematicians, 2022
  * [5] M. Gromov, No metrics with positive scalar curvatures on aspherical 5-manifolds, arxiv:2009.05332
  * [6] M. Gromov and H. B. Lawson, Positive scalar curvature and the Dirac operator on complete Riemannian manifolds, Inst. Hautes Etudes Sci. Publ. Math. (1983), no. 58, 83–196 (1984)
  * [7] S. Hoelzel, Surgery stable curvature conditions, Math. Ann., 365 (2016), no. 1-2, 13–47.
  * [8] G. Huisken and A. Polden, Geometric evolution equations for hypersurfaces, Calculus of variations and geometric evolution problems (1999): 45-84
  * [9] M.-L. Labbi, Stability of the $p$-curvature positivity under surgeries and manifolds with positive Einstein tensor, Ann. Global Anal. Geom. 15 (1997), 299–312
  * [10] R. Schoen and S.-T. Yau, On the structure of manifolds with positive scalar curvature, Manuscr. Math. 28 (1979), 159–183
  * [11] R. Schoen and S.-T. Yau, Positive Scalar Curvature and Minimal Hypersurface Singularities, arXiv:1704.05490
  * [12] Y. Shen and R. Ye, On stable minimal surfaces in manifolds of positive bi-Ricci curvatures, Duke Math. J. 85 (1996), 109–116
  * [13] Y. Shen and R. Ye, On the geometry and topology of manifolds of positive bi-Ricci curvature, arXiv preprint dg-ga/9708014 (1997)
  * [14] L. Simon, Lectures on geometric measure theory, The Australian National University, Mathematical Sciences Institute, Centre for Mathematics & its Applications, 1983


2024

# INVESTIGATION OF TRIANGLE COUNTS IN GRAPHS EVOLVED BY UNIFORM CLUSTERING
ATTACHMENT

###### Abstract

The clustering attachment model introduced in the paper Bagrow and Brockmann
(2013) may be used as an evolution tool of random networks. We propose a new
clustering attachment model which can be considered as the limit of the former
clustering attachment model as model parameter $\alpha$ tends to zero. We
focus on the study of a total triangle count that is considered in the
literature as an important characteristic of the network clustering. It is
proved that total triangle count tends to infinity a.s. for the proposed
model. Our simulation study is used for the modeling of sequences of triangle
counts. It is based on the interpretation of the clustering attachment as a
generalized Pólya-Eggenberger urn model that is introduced here at first time.
Keywords: clustering attachment, preferential attachment, random graph,
evolution, urn model.

##  1 Introduction

In this paper we discuss an evolution model of undirected random graphs by the
clustering attachment (CA) rule introduced in [1]. The attachment of a newly
appending node to existing nodes by the CA typically lowers its clustering
coefficient, in contrast to the well-known preferential attachment (PA) that
executes so called ’rich-get-richer’ models. This leads to numerous new
phenomena like a community formation around new nodes, bursts of a modularity
and light-tailed distributions of node degrees [1]. The idea of the CA is that
existing nodes are drawn not towards hubs, but towards densely connected
groups that is usual for social human behaviour.

We propose a new clustering attachment model which can be considered as the
limit of the former clustering attachment model in [1] as model parameter
$\alpha$ tends to zero. The latter model This model boils down to the
sequential selection of existing nodes by a new node with equal probability.
The following example of such an attachment can be given. An individual comes
to an unfamiliar community (for a new job) and chooses someone to be friends
at random, with equal probability. This can happen to every beginner. If a
newcomer joined an existing node, this does not mean that another new node
will join it in the future. On the contrary, the chances of joining decrease
as there are more and more nodes to choose from.

A triangle of connected nodes is the most studied subgraph that can be
considered as a basic community. It seems, it was introduced first in [2]. The
triangle count relates to calculation of the clustering coefficient. The
latter is an important representation of a clustering structure in random
graphs since it expresses the fraction of connected neighbors of a node. The
limiting behavior of the number of triangles attracts the attention of many
researchers, see [3], [4], [5] among others. Our objective is to find a limit
behaviour of the total triangle counts in the evolving CA graph. Remarkable is
that the triangle counts were investigated for the PA evolution model. Here,
we deal with the CA setting that is a novelty.

Let $G_{n}=\left(V_{n},E_{n}\right)$, $n=1,2,\dots$ denote the sequence of
random graphs in which $n$ may be interpreted as the discrete time since
graphs are generated during the evolution. Here, $V_{n}$ is the set of nodes
and $E_{n}$ is the set of edges. Here and further, we apply notations used in
[6]. Let $\\#A$ denote the cardinality (the number of elements) of arbitrary
finite set $A$. The graph $G_{n}$ consists of $\\#V_{1}+n-1$ nodes and
$\\#E_{1}+m(n-1)$ edges, i.e., for any $n\in\mathbb{N}$,

$\\#V_{n}=\\#V_{1}+n-1,\quad\\#E_{n}=\\#E_{1}+m(n-1),$

where natural $m\geq 2$ is a parameter of the clustering attachment model.

Before providing postulates that describe how new edges and nodes are formed,
let us recall that the clustering coefficient of node $i\in V_{n}$ is defined
as

$\displaystyle c_{i,n}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}0,&\hbox{$D_{i,n}=0$ or
$D_{i,n}=1$,}\\\
2\Delta_{i,n}/\left(D_{i,n}\left(D_{i,n}-1\right)\right),&\hbox{$D_{i,n}\geq
2$,}\end{array}\right.$

where $D_{i,n}$ and $\Delta_{i,n}$ are the degree and number of triangles of
node $i$, respectively. Let us define more general definition of the CA model.

######  Definition 1.1.

The graph $G_{n+1}$ is obtained from $G_{n}$ according to the rule, which
consists of two parts:

(i) the deterministic part: a new node $\\#V_{1}+n\in V_{n+1}\setminus V_{n}$
is appended to $G_{n}$;

(ii) the probabilistic part: each node $i\in V_{n}$ is equipped with the
weight

(2) $p_{i,n}=\frac{f\left(c_{i,n}\right)+\epsilon}{\sum_{j\in
V_{n}}\left(f\left(c_{j,n}\right)+\epsilon\right)},$

where the attachment function $f:[0,1]\to[0,\infty)$ is deterministic, non-
decreasing, while $\epsilon\geq 0$ is another parameter of the CA model.
Choose the existing nodes $i_{1},\dots i_{m}\in V_{n}$ by a successive
sampling and connect each of them with the newly appended node $\\#V_{1}+n$.

By replacing $c_{i,n}$ by $D_{i,n}$ in (2), we turn to the definition of the
PA model, see, e.g., pg. 5 in [7]. For the CA model introduced in [1], weights
(2) were constructed by the attachment function

(3) $f(x)=x^{\alpha},\ \alpha>0.$

Further we will assume, in addition, that $f(x)$ in (2) satisfies conditions

(4) $f(0)=0,\quad f(x)>0,\ 0<x\leq 1.$

Assumptions regarding the initial graph $G_{1}$ depend on the parameter
$\epsilon$. If $\epsilon>0$ holds, then it is enough to assume that

(5) $\\#V_{1}\geq m.$

If $\epsilon=0$, then the assumption stronger than (5) is required. Namely, we
assume that

(6) $\\#\tilde{V}_{1}\geq m,$

where the sequence of sets $\tilde{V}_{1},\tilde{V}_{2},\dots$ is defined as
follows: $\tilde{V}_{n}=\\{i\in V_{n}:\ f\left(c_{i,n}\right)>0\\}$, $n\geq
1$. Under assumption (4) the sequence $\tilde{V}_{1},\tilde{V}_{2},\dots$ is
non-decreasing in the sense that ${\tilde{V}}_{n}\subseteq{\tilde{V}}_{n+1}$
for each $n\in\mathbb{N}$. Thus, from (6) it follows $\\#\tilde{V}_{n}\geq m$
for each $n\in\mathbb{N}$. The last inequality ensures that for any
$n\in\mathbb{N}$ there is at least one collection of nodes
$i_{1},\dots,i_{m}\in V_{n}$ that can be chosen by the successive sampling
with a positive probability.

The CA model has a Markov property in the sense that the obtaining $G_{n+1}$
once $G_{n}$ is known does not require a prior knowledge of earlier graphs
$G_{1},G_{2},\dots,G_{n-1}$.

The paper is organized as follows. The main result is given in section 2.
Section 3 contains a survey of known results. In Section 4 we discuss the
successive sampling for the CA model considered in Theorem 2.1. The proves of
Theorem 2.1, corrolary 2.3 and lemms required for the proof of the theorem are
given in Section 5. Section 6 contains results of a simulation study to
demonstrate a growth of the total triangle counts. Section 7 contains a
gratitude. Conclusions are presented in Section 8.

##  2 Main result

The number of triangles in the graph $G_{n}$ is expressed in terms of the
number of triangles of nodes

$\Delta_{n}=\frac{1}{3}\sum_{i\in{\tilde{V}}_{n}}\Delta_{i,n}.$

Let us consider the CA model with parameters $\epsilon=0$, $m=2$ and the
attachment function

(7) $f(x)=\left\\{\begin{array}[]{ll}0,&\hbox{$x=0$,}\\\
1,&\hbox{$x>0$.}\end{array}\right.$

A sequence of functions $f_{n}=x^{1/n}$, $n=1,2,\dots$ converges to $f(x)$ in
(7) point-wise. This allows us to call such CA model as a limit model (as
$\alpha\downarrow 0$) of the CA model with parameters $\epsilon=0$, $m=2$ and
the attachment function (3).

######  Theorem 2.1.

Let $G_{n}$, $n=1,2,\dots$ be a sequence of graphs generated by the CA model
with parameters $\epsilon=0$, $m=2$ and the attachment function given in (7).
Assume that the initial graph $(V_{1},E_{1})$ is finite and satisfies
condition (6). Then, as $n\to\infty$,

(8) $\Delta_{n}\to\infty,\qquad n\to\infty\qquad\ {\mbox{a}.s.}$

As it will be shown in Section 4, the nodes of the sequence
${\tilde{V}}_{1},{\tilde{V}}_{2},\dots$ play a key role in the evolution of
the CA model.

######  Corollary 2.2.

Under the assumptions of Theorem 2.1, we get $\\#{\tilde{V}}_{n}\to\infty$ as
$n\to\infty$ a.s..

Let the sequence of the sets ${\tilde{E}}_{1},{\tilde{E}}_{2},\dots$ be such
that for any $n\geq 1$, $\left({\tilde{V}}_{n},{\tilde{E}}_{n}\right)$ is a
complete graph. In other words, ${\tilde{E}}_{n}$ denotes the set of all
possible edges between nodes in ${\tilde{V}}_{n}$. Some edges in
${\tilde{E}}_{n}$ may not exist in the graph $G_{n}$. The next corollary
contains a lower bound of the expectation $E\Delta_{n}$.

######  Corollary 2.3.

Under the assumptions of Theorem 2.1, it holds

(9) $E\Delta_{n}-\Delta_{1}>\frac{\\#\left({\tilde{E}}_{1}\cap
E_{1}\right)}{3\\#{\tilde{E}}_{1}}\ln(n-1),\quad n\geq 2.$

##  3 Related works

Let us firstly review the literature dealing with the CA model. The CA rule
was studied in [1] as a pioneer paper. The term ’clustering’ with regard to
social networks was used in [8] for the time evolution in scientific
collaboration networks where the average clustering coefficient is high. In
contrast to the PA which is intensively studied in the literature due to its
application in real-world networks like Internet, the study of the CA seems to
be did not get noticeable development.

In [1], the CA model with parameters $\epsilon\geq 0$, $m=2$ and the
attachment function (3) is considered using heuristics and Monte-Carlo
simulations. The main conclusions of [1] are the following: (i) the model
parameters $\epsilon$, $m$ and $\alpha$ impact on bursts of the modularity
time series built during evolution with a significant role of $\alpha$ (see,
e.g., [9], [10] for definitions of the modularity); (ii) fluctuations of the
modularity for $\alpha>0$ are far larger than observed for $\alpha=0$; (iii)
the consecutive growth and decay of the modularity values reflect to the
arising of dense communities or visa versa, and in general, the evolution of
the communities; (iv) the average clustering coefficient increases
significantly as $\alpha$ increases. In [11], the impact of $\alpha$ on the
modularity sequence is investigated for the same model as in [1], but with an
uniform node deletion at each evolution step. Based on Monte-Carlo
simulations, a weak clustering of the modularity and a weak heaviness of node
degree distribution tails were observed in [11] as $\alpha>0$. Strong
consecutive bursts of the modularity and light tail of the node degree
distribution were recognised in [11] for the case $\alpha=0$.

Our paper is devoted to the limit theorem for the total triangle count in the
graph. Theorem 2.1 is the first theoretical result for the CA model. Let us
recall the corresponding results for the PA model and several other models.
The PA model was first introduced in [12], see also [13]. In [14] the expected
number of triangles is proved to be of rate $\ln^{3}(n)$ for the original
Albert-Barabási model (that is the PA model with $\epsilon=0$, $m=2$ and the
attachment function $f(x)=x$). The PA model with $\epsilon>0$, $m\geq 2$ and
$f(x)=x$ was studied in [15]. In [15] it is observed that the expected number
of triangles is of order $\ln(n)$. In [16] (see also references therein) and
[5] results regarding the number of triangles for a broad class of PA models
can be found.

Let $\tau$ denote the exponent of a power-law distribution which, as a rule,
approximates well the node degree distribution in real-world networks. The
relation

(10) $\frac{\Delta_{n}}{n^{3(3-\tau)/2}}\ {\buildrel\rm p\over{\to}}\ C,\quad
n\to\infty$

holds for several random graph models. Here, ${\buildrel\rm p\over{\to}}$
denotes the convergence in probability and the constant $C>0$ depends on
parameters of a concrete model. In particular, in [17] it was shown that (10)
holds for the inhomogeneous random graphs. If $\tau<7/3$, the total number of
triangles satisfies (10) for a geometric inhomogeneous random graph, while the
normalization in (10) must be replaced by $n$ if $\tau>7/3$ holds, see [18].
In [19], it is obtained that (10) holds for uniform random graphs and the
erased configuration model.

The convergence with rate $O\left(n^{-1/2}\right)$ in total variation between
the distribution of triangle counts and a Poisson distribution in generalized
random graphs with random vertex weights introduced in [20] is proved in [4].

##  4 Consecutive uniform sampling of nodes

Let $G_{n}$ be an observed graph. Our objective here is to show that the sets
$\tilde{E}_{n}$ and $\tilde{E}_{n}\cap E_{n}$ are enough to know for the
evolution by the CA. By combining (2) and (7) we get the equivalent definition
of ${\tilde{V}}_{n}$: $\tilde{V}_{n}=\\{i\in V_{n}:\ \Delta_{i,n}>0\\}$. By
substituting $\epsilon=0$, $m=2$ and (7) into (2) we obtain that attachment
weights $p_{i,n}$, $i\in V_{n}$ are uniformly distributed at $\tilde{V}_{n}$:

(11) $p_{i,n}=\left\\{\begin{array}[]{ll}0,&\hbox{$i\in
V_{n}\setminus{\tilde{V}}_{n}$,}\\\
1/\\#{\tilde{V}}_{n},&\hbox{$i\in{\tilde{V}}_{n}$.}\end{array}\right.$

By (11) it follows that an appended node $\\#V_{1}+n$ can be attached with
positive probability only to existing nodes $\\{i\in V_{n}$:
$\Delta_{i,n}>0\\}$ involved into at least one triangle.

Let the sequence of sets $\mathcal{E}_{1},\mathcal{E}_{2},\dots$ be such that
for any $n\geq 1$, the pair $\left(V_{n},\mathcal{E}_{n}\right)$ is a complete
graph.

Let $W_{n}$ denote a pair of nodes $\\{i_{1},i_{2}\\}$ from $V_{n}$, chosen by
applying the successive sampling (or random sampling without return). The
successive sampling begins by selecting node $i_{1}$ from $V_{n}$ with
probability (11). The probabilities of remaining $\\#V_{n}-1$ nodes are then
re-normalized as follows: $p_{i,n}/(1-p_{i_{1},n})$. The process is repeated
by selecting the node $i_{2}$. It does not matter for the evolution by the CA
model which node is chosen first in the pair. Thus, further we will assume
that $W_{n}$ is a two-dimensional random vector with values in
$\mathcal{E}_{n}$.

######  Proposition 4.1.

Random vector $W_{n}$ is uniformly distributed on ${\tilde{E}}_{n}$.

######  Proof 4.2.

Let $\\{i,j\\}\in{\tilde{E}}_{n}$. Let us consider for each node
$i\in{\tilde{V}}_{n}$ the random event
$A_{n,i}\equiv\\{\mbox{node}\leavevmode\nobreak\ i\leavevmode\nobreak\
\mbox{is \leavevmode\nobreak\ chosen}\\}$. By the law of a total probability,

(12) $\displaystyle P\left(W_{n}=\\{i,j\\}\right)$ $\displaystyle=$
$\displaystyle P(A_{n,j}|A_{n,i})P(A_{n,i})+P(A_{n,i}|A_{n,j})P(A_{n,j})$
$\displaystyle=$
$\displaystyle\frac{2}{\\#{\tilde{V}}_{n}\left(\\#{\tilde{V}}_{n}-1\right)}=\frac{1}{\\#{\tilde{E}}_{n}}.$

By (12), we obtain

$P\left(W_{n}\in{\tilde{E}}_{n}\right)=\sum_{\\{i_{1},i_{2}\\}\in{\tilde{E}}_{n}}P\left(W_{n}=\\{i_{1},i_{2}\\}\right)=1.$

This implies
$P\left(W_{n}\in\mathcal{E}_{n}\setminus{\tilde{E}}_{n}\right)=0$, and
consequently, $P\left(W_{n}=\\{i,j\\}\right)=0$ for any pair of nodes
$\\{i,j\\}\in\mathcal{E}_{n}\setminus{\tilde{E}}_{n}$.

From Prop. 4.1 it follows that the attachment rule (ii) with function (7) and
parameters $\epsilon=0$, $m=2$ does not give preferences to a pair of nodes
with relatively large clustering coefficients. This means an absence of the
rich-get-richer effect in the CA model under consideration.

The equality $P\left(W_{n}=\\{i,j\\}\right)=0$, $i,j\in
V_{n}\setminus{\tilde{V}}_{n}$ means that nodes from the set
$V_{n}\setminus{\tilde{V}}_{n}$ do not take part in forming the graph
$G_{n+1}$ since newly appending nodes do not attach to such nodes. The
possibility to decompose the set $V_{n}$ into subsets of active nodes
${\tilde{V}}_{n}$ and inactive ones $V_{n}\setminus{\tilde{V}}_{n}$ turns to
the mind that the CA model can be used to generate various two-classes
communities. We refer [1] for more possible applications of CA model.

######  Example 4.3.

Fig. 1 illustrates classes mentioned above of one realization of the CA random
graph $(V_{n},E_{n})$ with $n=5000$ and $n=10000$ when the initial graph
$G_{1}$ is a quadrilateral with all diagonals except one:

$V_{1}=\\{1,2,3,4\\},\quad
E_{1}=\\{\\{1,2\\},\\{1,3\\},\\{1,4\\},\\{2,3\\},\\{3,4\\}\\}.$

Figure 1: The CA random graph $(V_{n},E_{n})$ with $n=5000$ (left) and
$n=10000$ (right): nodes from ${\tilde{V}}_{n}$ are shown in black, edges from
${\tilde{E}}_{n}\cap E_{n}$ are in dark grey and the rest of graph is in light
grey.

##  5 Proofs

###  5.1 Auxiliary lemmas

Here and throughout, we assume that set of edges $E_{n}$, $n\geq 1$ is
presented as a set of unordered pairs of nodes. For any $n\geq 1$ we divide
the set ${\tilde{E}}_{n}$ into two subsets: ${\tilde{E}}_{n}\cap E_{n}$ and
${\tilde{E}}_{n}\setminus\left({\tilde{E}}_{n}\cap E_{n}\right)$. The set
${\tilde{E}}_{n}\cap E_{n}$ contains the unordered pairs of nodes which are
connected by edges in graph $G_{n}$. Put $B_{n}=\\{W_{n}\in{\tilde{E}}_{n}\cap
E_{n}\\}$, $n\geq 1$ denotes a random event that a pair of nodes $W_{n}$
chosen by the uniform sampling is connected by an edge from $E_{n}$.

Let $B^{c}$ denote the opposite event to the random event $B$. Let
$n,k\in\mathbb{N}$, and $\ell\in\mathbb{N}\cup\\{0\\}$ are such that $n\geq
2$, $1\leq k<n$, $0\leq\ell\leq n-k$. Let $\left(B_{k}\cap\dots\cap
B_{n-1}\right)_{\ell}$ denote the union of $(n-k)!/(\ell!(n-k-\ell)!)$ non-
intersecting random events such that $\ell$ events $B_{j}$ are replaced by
their opposites in the intersection $B_{k}\cap\dots\cap B_{n-1}$. If a random
event $\left(B_{k}\cap\dots\cap B_{n-1}\right)_{\ell}$ occurs, then $\ell$
pairs of nodes among $W_{k},\dots,W_{n-1}$ are disconnected, while the rest
$n-k-\ell$ pairs are connected. For example, if $k=1$, $n=4$, then we have

$\displaystyle\ell=0:\quad(B_{1}\cap B_{2}\cap B_{3})_{0}$ $\displaystyle=$
$\displaystyle B_{1}\cap B_{2}\cap B_{3},$
$\displaystyle\ell=1:\quad(B_{1}\cap B_{2}\cap B_{3})_{1}$ $\displaystyle=$
$\displaystyle(B_{1}\cap B_{2}\cap B_{3}^{c})\cup(B_{1}\cap B_{2}^{c}\cap
B_{3})\cup(B_{1}^{c}\cap B_{2}\cap B_{3}),$
$\displaystyle\ell=2:\quad(B_{1}\cap B_{2}\cap B_{3})_{2}$ $\displaystyle=$
$\displaystyle(B_{1}\cap B_{2}^{c}\cap B_{3}^{c})\cup(B_{1}^{c}\cap B_{2}\cap
B_{3}^{c})\cup(B_{1}^{c}\cap B_{2}^{c}\cap B_{3}),$
$\displaystyle\ell=3:\quad(B_{1}\cap B_{2}\cap B_{3})_{3}$ $\displaystyle=$
$\displaystyle B_{1}^{c}\cap B_{2}^{c}\cap B_{3}^{c}.$

By Prop. 4.1,

(13) $P\left(B_{n}\right)=\sum_{\\{i_{1},i_{2}\\}\in{\tilde{E}}_{n}\cap
E_{n}}\frac{1}{\\#{\tilde{E}}_{n}}=\frac{\\#\left({\tilde{E}}_{n}\cap
E_{n}\right)}{\\#{\tilde{E}}_{n}}.$

Let $n\geq k-1$ and $k\geq 1$. If the random event $\left(B_{k}\cap\dots\cap
B_{n-1}\right)_{\ell}$ has occurred, then

$\displaystyle\\#\left({\tilde{E}}_{n}\cap E_{n}\right)$ $\displaystyle=$
$\displaystyle\\#\left({\tilde{E}}_{k}\cap E_{k}\right)+2(n-\ell-k),$
$\displaystyle\\#{\tilde{E}}_{n}$ $\displaystyle=$
$\displaystyle\\#{\tilde{E}}_{k}+(n-\ell-k)\\#{\tilde{V}}_{k}+(1/2)(n-\ell-k)(n-\ell-k-1).$

Thus, by (13) we get

$\displaystyle P\left(B_{n}|\left(B_{k}\cap\dots\cap
B_{n-1}\right)_{\ell}\right)$ $\displaystyle=$ $\displaystyle
p_{n-\ell}\left(G_{k}\right),$

where

(14) $p_{n}\left(G_{k}\right)=\frac{\\#\left({\tilde{E}}_{k}\cap
E_{k}\right)+2(n-k)}{\\#{\tilde{E}}_{k}+(n-k)\\#{\tilde{V}}_{k}+(1/2)(n-k)(n-k-1)}.$

Let us prove several inequalities which will be used in the proof of Theorem
2.1.

######  Lemma 5.1.

Let assumptions of Theorem 2.1 hold. For any natural numbers $k\leq n$,

(15) $\displaystyle p_{n}\left(G_{k}\right)$ $\displaystyle>$ $\displaystyle
0,$ (16) $\displaystyle p_{n}\left(G_{k}\right)$ $\displaystyle>$
$\displaystyle p_{n+1}\left(G_{k}\right).$

######  Proof 5.2.

Assumption (6) implies ${\tilde{E}}_{k}\not=\emptyset$ and
${\tilde{E}}_{k}\cap E_{k}\not=\emptyset$ for any natural $k$. Now (15)
follows from (14).

Next, using (14), the inequality (16) boils down to the following

$\\#{\tilde{V}}_{k}\left\\{\\#\left({\tilde{E}}_{k}\cap E_{k}\
\right)-\\#{\tilde{V}}_{k}+1\right\\}+(n-k)\\#\left({\tilde{E}}_{k}\cap E_{k}\
\right)+(n-k)(n-k+1)>0.$

Thus, it is enough to show that for any initial graph satisfying (6),

(17) $\\#\left({\tilde{E}}_{k}\cap E_{k}\ \right)>\\#{\tilde{V}}_{k}-1$

holds. Let us use the mathematical induction to prove (17). We consider the
graph $\left({\tilde{V}}_{1},{\tilde{E}}_{1}\cap E_{1}\right)$. A minimum
number of edges in ${\tilde{E}}_{1}\cap E_{1}$ depends on
$\\#{\tilde{V}}_{1}$. If $\\#{\tilde{V}}_{1}=3$ holds, then the graph, which
has a minimum number of edges is triangle for which
$\\#\left({\tilde{E}}_{1}\cap E_{1}\ \right)=3$. Thus, the inequality (17)
holds for $k=1$ in this case. If $\\#{\tilde{V}}_{1}>3$ holds, then the graph,
which has a minimum number of edges consists of $\\#{\tilde{V}}_{1}-2$
triangles with the same one side (see, Example 4.3 for the case
$\\#{\tilde{V}}_{1}=4$). For such graphs it holds
$\\#\left({\tilde{E}}_{1}\cap E_{1}\right)=\\#{\tilde{V}}_{1}+1$. This yields
that inequality (17) with $k=1$ and $\\#{\tilde{V}}_{1}>3$ holds again.

Next, let us make the induction hypothesis that (17) holds. We have to show
that (17) holds when $k$ is replaced by $k+1$. If the random event $B_{k}$
occurs, then $\\#\left({\tilde{E}}_{k+1}\cap E_{k+1}\
\right)=\\#\left({\tilde{E}}_{k}\cap E_{k}\ \right)+2$ and
$\\#{\tilde{V}}_{k+1}=\\#{\tilde{V}}_{k}+1$ follow. By (17) we get

$\\#\left({\tilde{E}}_{k+1}\cap E_{k+1}\
\right)-\\#{\tilde{V}}_{k+1}+1=\left\\{\\#\left({\tilde{E}}_{k}\cap E_{k}\
\right)-\\#{\tilde{V}}_{k}+1\right\\}+1>0.$

The case when $B_{k}$ does not occur can be considered similarly.

######  Lemma 5.3.

Under assumptions of Theorem 2.1, we have

(18) $P\left(B_{n}\right)>P\left(B_{n}|B_{1}\cap\dots\cap B_{n-1}\right),\quad
n=2,3,\dots$

######  Proof 5.4.

By the law of total probability,

$\displaystyle\\!\\!\\!\\!\\!P(B_{n})$ $\displaystyle=$
$\displaystyle\sum_{\ell=0}^{n-1}P\left(B_{n}|\left(B_{1}\cap\dots\cap
B_{n-1}\right)_{\ell}\right)P\left(\left(B_{1}\cap\dots\cap
B_{n-1}\right)_{\ell}\right).$

From Lemma 5.1 it follows that for any $1\leq\ell\leq n-1$,

$P\left(B_{n}|B_{1}\cap B_{2}\cap\dots\cap
B_{n-1}\right)<P\left(B_{n}|\left(B_{1}\cap B_{2}\cap\dots\cap
B_{n-1}\right)_{\ell}\right).$

This implies $P(B_{n})>P\left(B_{n}|B_{1}\cap\dots\cap
B_{n-1}\right)\sum_{\ell=0}^{n-1}P\left(\left(B_{1}\cap\dots\cap
B_{n-1}\right)_{\ell}\right).$ The statement (18) follows since the last sum
is equal to $1$.

The proof of the theorem 2.1 is a verification of the conditions of the Borel-
Cantelli lemma below.

######  Lemma 5.5.

([21], p.79) Let random events $C_{1},C_{2},\dots$ be defined on one
probability space that satisfy the correlation condition: for any natural $u$
and $v$, such that $u\not=v$, random events $C_{u}$ and $C_{v}$ are negative
correlated or uncorrelated. If $\sum_{n=1}^{\infty}P(C_{n})=\infty$, then
$P\\{C_{n}\leavevmode\nobreak\ \mbox{i.m.}\\}=1.$111Through
$\\{C_{n}\leavevmode\nobreak\ \mbox{i.m.}\\}$ denotes an event consisting in
the fact that infinitely many events will occur from $C_{1},C_{2},...$ [22].

######  Lemma 5.6.

Let assumptions of Theorem 2.1 hold. Then random events $B_{1},B_{2},\dots$
satisfy the correlation condition, i.e.,

(19) $P\left(B_{u}\cap B_{v}\right)\leq
P\left(B_{u}\right)P\left(B_{v}\right).$

######  Proof 5.7.

If $\min\\{u,v\\}=1$, then the supposition (6) leads to
$0<\\#\left({\tilde{E}}_{1}\cap
E_{1}\right)\leq\\#\left({\tilde{E}}_{1}\right)$, see, the proof of lemma 5.1.
Thus from (13) follows that $P(B_{1})>0$. If $\min\\{u,v\\}>1$, then combining
(15) and (18), we obtain
$P\left(B_{\min\\{u,v\\}}\right)>p_{\min\\{u,v\\}}(G_{1})>0$. It is proved
that $P\left(B_{\min\\{u,v\\}}\right)>0$ for any natural numbers $u$ and $v$.
Appplying definition of total probability one can rewrite the correlation
condition as follows:

(20)
$P\left(B_{\max\\{u,v\\}}\right)-P\left(B_{\max\\{u,v\\}}|B_{\min\\{u,v\\}}\right)\geq
0.$

It is enough to derive that the inequality (20) is fulfilled for
$\max\\{u,v\\}=n+k$ and $\min\\{u,v\\}=n$, where $n$ and $k$ are any natural
numbers.

If $k=1$, then applying the formula of total probability with (16), we get

$P(B_{n+1})-P(B_{n+1}|B_{n})=\left(1-p_{1}(G_{n})\right)\left(p_{1}(G_{n})-p_{2}(G_{n})\right)\geq
0.$

Here, the equality is valid for $\\#\left({\tilde{E}}_{n}\cap
E_{n}\right)=\\#\left({\tilde{E}}_{n}\right)$.

Let now $k\geq 2$. We state that

(21) $\displaystyle P\left(B_{n+k}\right)$ $\displaystyle=$ $\displaystyle
J+\sum_{\ell=0}^{k-1}p_{n+k-\ell-1}(G_{n})P\left(B_{n}^{c}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right),$ (22) $\displaystyle
P\left(B_{n+k}|B_{n}\right)$ $\displaystyle=$ $\displaystyle
J+\sum_{\ell=0}^{k-1}p_{n+k-\ell}(G_{n})P\left(B_{n}^{c}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right),$

where

$J=\sum_{\ell=0}^{k-1}p_{n+k-\ell}(G_{n})P\left(B_{n}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right).$

From (21), (22) it follows immediately that the difference
$P\left(B_{n+k}\right)-P\left(B_{n+k}|B_{n}\right)$ is equal to

$\displaystyle\sum_{\ell=0}^{k-1}\left\\{p_{n+k-\ell-1}(G_{n})-p_{n+k-\ell}(G_{n})\right\\}P\left(B_{n}^{c}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right)$
$\displaystyle=\sum_{\ell=0}^{k-1}\left\\{p_{n+k-\ell-1}(G_{n})-p_{n+k-\ell}(G_{n})\right\\}\left\\{1-p_{n-\ell}(G_{n})\right\\}P\left(\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right).$

By (15), (16) it follows that the latter sum is positive.

Let us prove (21). Applying the formula of total probability we obtain

$\displaystyle P\left(B_{n+k}\right)$ $\displaystyle=$ $\displaystyle
P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{0}\right)P\left(\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{0}\right)$
$\displaystyle+\sum_{\ell=1}^{k-1}P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right)P\left(\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right)$
$\displaystyle+P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{k}\right)P\left(\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{k}\right)$

Using the identity

$\displaystyle\left(B_{n}\cap\dots\cap B_{n+k-1}\right)_{\ell}$
$\displaystyle=$ $\displaystyle\left\\{B_{n}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right\\}\cup$
$\displaystyle\cup\left\\{B_{n}^{c}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell-1}\right\\},$

we have

$\displaystyle P\left(B_{n+k}\right)$ $\displaystyle=$
$\displaystyle\bigg{\\{}P\left(B_{n+k}|B_{n}\cap\dots\cap
B_{n+k-1}\right)P\left(B_{n}\cap\dots\cap B_{n+k-1}\right)$
$\displaystyle+\sum_{\ell=1}^{k-1}P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right)P\left(B_{n}\cap\left(B_{n+1}\dots\cap
B_{n+k-1}\right)_{\ell}\right)\bigg{\\}}$
$\displaystyle+\sum_{\ell=1}^{k-1}P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right)P\left(B_{n}^{c}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell-1}\right)$
$\displaystyle+P\left(B_{n+k}|B_{n}^{c}\cap\dots\cap
B_{n+k-1}^{c}\right)P\left(B_{n}^{c}\cap\dots\cap B_{n+k-1}^{c}\right).$

Applying (14), we get that the sum in curly brackets is equal to $J$. By
replacing the summation variable with $s=\ell-1$, we obtain

$\displaystyle\sum_{\ell=1}^{k-1}P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right)P\left(B_{n}^{c}\cap\left(B_{n+1}\dots\cap
B_{n+k-1}\right)_{\ell-1}\right)$
$\displaystyle=\sum_{s=0}^{k-2}P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{s+1}\right)P\left(B_{n}^{c}\cap\left(B_{n+1}\dots\cap
B_{n+k-1}\right)_{s}\right)$
$\displaystyle=\sum_{s=0}^{k-1}P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{s+1}\right)P\left(B_{n}^{c}\cap\left(B_{n+1}\dots\cap
B_{n+k-1}\right)_{s}\right)$
$\displaystyle-P\left(B_{n+k}|\left(B_{n}\cap\dots\cap
B_{n+k-1}\right)_{k}\right)P\left(B_{n}^{c}\cap\left(B_{n+1}\dots\cap
B_{n+k-1}\right)_{k-1}\right).$

Using (14) once more, we will get the proof (21).

The identity (22) can be checked in a similar way. To this end, it is enough
to apply the formula of total probability and the identity

$\displaystyle\left(B_{n+1}\cap\dots\cap B_{n+k-1}\right)_{\ell}$
$\displaystyle=$ $\displaystyle\left\\{B_{n}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right\\}\cup$
$\displaystyle\cup\left\\{B_{n}^{c}\cap\left(B_{n+1}\cap\dots\cap
B_{n+k-1}\right)_{\ell}\right\\}.$

###  5.2 Proof of Theorem 2.1

######  Proof 5.8.

The difference of the total number of triangles in graphs $G_{n}$ and $G_{1}$
as well as the difference of the number of nodes involved in triangles can be
expressed through indicators of random events $B_{j}$ by

(23) $\displaystyle\Delta_{n}-\Delta_{1}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n-1}I\left\\{B_{j}\right\\},$ (24)
$\displaystyle\\#{\tilde{V}}_{n}-\\#{\tilde{V}}_{1}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n-1}I\left\\{B_{j}\right\\},\quad n\geq 2,$

where $I\left\\{\cdot\right\\}$ denotes the indicator of the event. By (23),
(24) it follows that the counting of the total number of triangles
$\Delta_{n}$ is a linear function of the cardinality of the set
${\tilde{V}}_{n}$:

(25)
$\Delta_{n}=\\#{\tilde{V}}_{n}+\left(\Delta_{1}-\\#{\tilde{V}}_{1}\right),\quad
n\geq 2.$

In view of (23), the statement (8) follows from

$\sum_{j=1}^{n-1}I\left\\{B(j)\right\\}\to\infty\quad{\rm
a.s.}\qquad\mbox{as}\qquad\ n\to\infty,$

that equivalently implies that

$\displaystyle P\left(B_{n}\ {\rm occurs\ infinitely\ many\ times}\
n\right)=1.$

Let us prove that the sequence $B_{1},B_{2},\dots$ satisfies the conditions of
Borell-Cantelli lemma (see, lemma 5.5). One of them is verified in the lemma
5.6. It is enough to prove that

(26) $\sum_{n=1}^{\infty}P\left(B_{n}\right)=\infty.$

Due to lemmas 5.1, 5.3,

$\sum_{n=1}^{\infty}P\left(B_{n}\right)>\sum_{n=3}^{\infty}p_{n}(G_{1}).$

Note that by (14), it follows

(27) $p_{n}(G_{1})>\frac{\\#\left({\tilde{E}}_{1}\cap
E_{1}\right)+2(n-1)}{n\\#{\tilde{E}}_{1}+(1/2)(n-1)(n-2)}.$

Using inequality $\\#\left({\tilde{E}}_{1}\cap
E_{1}\right)\leq\\#{\tilde{E}}_{1}$, one can prove that the right-hand side of
(27) exceeds $\\#\left({\tilde{E}}_{1}\cap
E_{1}\right)/\left(\left(3\\#{\tilde{E}}_{1}\right)(n-2)\right)$ for $n\geq
3$. Hence, it holds

$\sum_{n=1}^{\infty}P\left(B_{n}\right)>\frac{\\#\left({\tilde{E}}_{1}\cap
E_{1}\right)}{3\\#{\tilde{E}}_{1}}\lim_{N\to\infty}H_{N},$

where $H_{N}=\sum_{n=1}^{N}1/n$. The relation (26) follows by applying the
inequality $H_{N}>\ln(N)$ and the relation $\lim_{N\to\infty}\ln(N)=\infty$.

It remains to prove corollaries 2.2, 2.3. The statement of the corollary 2.2
follows from (8) and (25).

To prove the corollary 2.3, we note that from (23) the inequality follows

$E\left(\Delta_{n}\right)-\Delta_{1}=\sum_{j=1}^{n-1}P(B_{j})>\sum_{j=3}^{n+1}p_{j}(G_{1}),\quad
n\geq 2.$

It follows from the proof of the relation (26) that the last sum is greater
than $\left(\\#\left({\tilde{E}}_{1}\cap
E_{1}\right)/\left(3\\#{\tilde{E}}_{1}\right)\right)\ln(n-1)$. This completes
the proof of the inequality (9).

##  6 Monte-Carlo simulation

Let us consider modeling the sequence $\Delta_{n}$, $n\geq 1$. To investigate
the growth of the sample mean $\Delta_{n}$ modeling a sequence of graphs
$G_{n}$, $n\geq 1$ is not required. It is enough to simulate a sequence of
sets ${\tilde{E}}_{n}$, $n\geq 1$.

Let us interpret pairs of nodes from ${\tilde{E}}_{n}$ in terms of a
generalized Pólya-Eggenberger urn model. We use the fact that for each $n\geq
1$, the set ${\tilde{E}}_{n}$ is divided into two subsets:
${\tilde{E}}_{n}\cap E_{n}$ and
${\tilde{E}}_{n}\setminus\left({\tilde{E}}_{n}\cap E_{n}\right)$, see section
6. Each pair of nodes from ${\tilde{E}}_{n}\cap E_{n}$ is interpreted as a
white ball, while a pair of nodes belonging to the set
${\tilde{E}}_{n}\setminus\left({\tilde{E}}_{n}\cap E_{n}\right)$ is
interpreted as a black ball. Hence, an urn (or in other words, the set
${\tilde{E}}_{n}$) contains $\\#\left({\tilde{E}}_{n}\cap E_{n}\right)$ white
balls and $\\#\left({\tilde{E}}_{n}\setminus\left({\tilde{E}}_{n}\cap
E_{n}\right)\right)$ black ones.
At every time step $n\geq 1$, we draw a ball uniformly (with return) at random
from the urn (see, proposition 4.1). The color of the ball is inspected and
the urn is replenished according to the following rule. If a white ball is
drawn, then we put into the urn two white balls and
$\left(1/2)\left(1+\sqrt{1+8\\#{\tilde{E}}_{n}}\right)-2\right)$ black balls.
We recall that cardinalities $\\#{\tilde{V}}_{n}$ and $\\#{\tilde{E}}_{n}$ are
related as
$\\#{\tilde{V}}_{n}\left(\\#{\tilde{V}}_{n}-1\right)=2\\#{\tilde{E}}_{n}$
(see, (12)), and that is why $\\#{\tilde{V}}_{n}+1$ ball is added to the urn.
If we have chosen a black ball, the content of the urn is not changed.

Note that the number of added black and/or white balls is fixed in classical
Pólya-Eggenberger urn model (see, e.g., [21], pg. 437) while the number of
added black balls depends on $\\#{\tilde{E}}_{n}$ in our case. For more
generalizations of the Pólya-Eggenberger urn model we refer to [23] and
references therein.

Keeping in mind that pairs of nodes from ${\tilde{E}}_{n}$ are uniformly
distributed (see Prop. 4.1), we provide quite simple algorithm to simulate the
sequence $\Delta_{n}$, $n\geq 1$.

[.]

The initial step. Using an initial graph $G_{1}$, calculate $\Delta_{1}$,
$\\#{\tilde{V}}_{1}$, $\\#\left({\tilde{E}}_{1}\cap E_{1}\right)$ and
$\\#\left({\tilde{E}}_{1}\setminus\left({\tilde{E}}_{1}\cap
E_{1}\right)\right)$.

The evolutionary step. For any $n\geq 1$, simulate a variate of random
variable $\xi_{n}$, which has the uniform discrete distribution at the
interval of natural numbers $[1,\dots,\\#{\tilde{E}}_{n}]$. If
$\xi_{n}>\\#\left({\tilde{E}}_{n}\cap E_{n}\right)$, then

$\displaystyle\\#\left({\tilde{E}}_{n+1}\cap E_{n+1}\right)$ $\displaystyle=$
$\displaystyle\\#\left({\tilde{E}}_{n}\cap E_{n}\right),$
$\displaystyle\\#\left({\tilde{E}}_{n+1}\setminus\left({\tilde{E}}_{n+1}\cap
E_{n+1}\right)\right)$ $\displaystyle=$
$\displaystyle\\#\left({\tilde{E}}_{n}\setminus\left({\tilde{E}}_{n}\cap
E_{n}\right)\right).$

If $\xi_{n}\leq\\#\left({\tilde{E}}_{n}\cap E_{n}\right)$, then

$\displaystyle\\#\left({\tilde{E}}_{n+1}\cap E_{n+1}\right)$ $\displaystyle=$
$\displaystyle\\#\left({\tilde{E}}_{n}\cap E_{n}\right)+2,$
$\displaystyle\\#\left({\tilde{E}}_{n+1}\setminus\left({\tilde{E}}_{n+1}\cap
E_{n+1}\right)\right)$ $\displaystyle=$
$\displaystyle\\#{\tilde{E}}_{n+1}-\\#\left({\tilde{E}}_{n+1}\cap
E_{n+1}\right),$

where

$\\#{\tilde{E}}_{n+1}:=\\#\left({\tilde{E}}_{n}\cap
E_{n}\right)+\\#\left({\tilde{E}}_{n}\setminus\left({\tilde{E}}_{n}\cap
E_{n}\right)\right)+(1/2)\left(1+\sqrt{1+8\\#{\tilde{E}}_{n+1}}\right).$

In both cases, we get

$\Delta_{n+1}=\Delta_{1}-\\#{\tilde{V}}_{1}+(1/2)\left(1+\sqrt{1+8\\#{\tilde{E}}_{n+1}}\right).$

Let us recall that we need to store only four quantities during the
realization of the proposed algorithm: $\Delta_{1}$, $\\#{\tilde{V}}_{1}$,
$\\#\left({\tilde{E}}_{n}\cap E_{n}\right)$ and
$\\#\left({\tilde{E}}_{n}\setminus\left({\tilde{E}}_{n}\cap
E_{n}\right)\right)$.

For each initial graph $G_{1}$ $100$ independent sequences
$\Delta_{1}^{(j)},\dots,\Delta_{N}^{(j)}$ of the length $N=10^{6}$ are
simulated. The upper index $(j)$ denotes the number of sequence.
The following complete graphs are selected as the initial ones: 1) triangle
$G_{1,1}$; 2) complete graph $G_{1,2}$ with the number of vertices $17$; 3)
complete graph $G_{1,3}$ with the number of vertices $51$.

The sequence of sample means of triangle counts $\Delta_{n}^{(j)}$, $1\leq
n\leq N$ is calculted by formula

${\bar{\Delta}}_{n}(G_{1,\ell})=\frac{1}{100}\sum_{j=1}^{100}\Delta_{n}^{(j)},\quad\ell\in\\{1,2,3\\}$

for each initial graph $G_{1,\ell}$. The plots
$\left\\{\left(n,{\bar{\Delta}}_{n}(G_{1,\ell})-\Delta_{1}(G_{1,\ell})\right),\
1\leq n\leq N\right\\}$, where $\ell\in\\{1,2,3\\}$ and $N=10^{6}$ are shown
in Fig.2.

Figure 2: Plots
$\left\\{\left(n,{\bar{\Delta}}_{n}(G_{1,\ell})-\Delta_{1}(G_{1,\ell})\right),\
0\leq n\leq 10^{6}\right\\}$ where plots with $\ell\in\\{1,2,3\\}$ are shown
in black, grey and light grey collors, respectively.

The least squares method is used to fit the discrete data

$\left\\{\left(n,{\bar{\Delta}}_{n}(G_{1,\ell})-\Delta_{1}(G_{1,\ell})\right),\
2\cdot 10^{5}\leq n\leq N\right\\},$
$\left\\{\left(n,{\bar{\Delta}}_{n}(G_{1,\ell})-\Delta_{1}(G_{1,\ell})\right),\
5\cdot 10^{5}\leq n\leq N\right\\}$

by the function $\varphi(n)=c_{1}+c_{2}n^{c_{3}}$. Estimates of $c_{1}$,
$c_{2}$ and $c_{3}$ are presented in Table 1.

The range of $n$: $[2\cdot 10^{5},10^{6}]$
---
Initial graph | ${\hat{c}}_{1}$ | ${\hat{c}}_{2}$ | ${\hat{c}}_{3}$
$G_{0,1}$ | 1 | 2.827 | 0.499
$G_{0,2}$ | 680 | 3.179 | 0.492
$G_{0,3}$ | 20825 | 6.564 | 0.447

The range of $n$: $[5\cdot 10^{5},10^{6}]$
---
Initial graph | ${\hat{c}}_{1}$ | ${\hat{c}}_{2}$ | ${\hat{c}}_{3}$
$G_{0,1}$ | 1 | 2.831 | 0.499
$G_{0,2}$ | 680 | 3.234 | 0.491
$G_{0,3}$ | 20825 | 6.133 | 0.452

Table 1:  Estimates of $c_{1}$, $c_{2}$ and $c_{3}$.

The findings of our simulation are the following.

  1. 1.

Simulation results shown in Fig. 2 are approximately similar to the
theoretical ones. Indeed, $E\Delta_{n}$ and empirical mean
${\bar{\Delta}}_{n}$ grow together with $n$, see corollary 2.3 and fig. 2.

  2. 2.

${\bar{\Delta}}_{n}$ grows as $C\sqrt{n}$, where $2\cdot 10^{5}\leq n\leq
10^{6}$, see Tab. 1. This simulation result does not contradict to Corollary
2.3. It should be noted that from this simulation result it does not follow
that ${\bar{\Delta}}_{n}$ has the same (or close) growth rate as $n>10^{6}$.

  3. 3.

When modeling the number of triangles $\Delta_{n}$ at $n>10^{6}$, difficulties
arose due to the limited computer memory.

  4. 4.

The plots of $\left(n,{\bar{\Delta}}_{n}(G_{1,1})-\Delta_{1}(G_{1,1})\right)$
and $\left(n,{\bar{\Delta}}_{n}(G_{1,2})-\Delta_{1}(G_{1,2})\right)$ are in
the close correspondence, while the plot
$\left(n,{\bar{\Delta}}_{n}(G_{1,3})-\Delta_{1}(G_{1,3})\right)$ has a shift
along the vertical axis relative to the other two graphs at $0\leq n\leq
10^{6}$, which is most likely due to the size of the graph $G_{1,3}$. It can
be assumed that the influence of a relatively large initial graph should be
eliminated with a large $n$.

##  7 Gratitude

The authors express their gratitude to M.S. Ryzhov for the computer
simulation.

##  8 Conclusions

Motivated by [7], where rather wide definition of the PA models is given, we
provide the new definition of the CA model. By means of the latter one can
simulate the evolution of many random systems and networks where newly
appending nodes are drawn likely not towards hubs, but towards densely
connected groups.

The properties of our CA model in which new nodes connect to existing nodes
with equal probabilities are investigated. The new CA model can be qualified
as a limit (as the parameter of the attachment function $\alpha\downarrow 0$)
of the CA model proposed in [1]. We proved that the total number of triangles
$\Delta_{n}$ tends to infinity almost surely as evolution step $n\to\infty$
without additional assumptions on the choice of the initial graph from which
the CA begins. To prove this result, it is proved that there is a negative
correlation or uncorrelation of random events, consisting in the fact that
pairs of existing nodes selected by new nodes at different time moments are
connected by an edge, or in other words, that a new triangle is formed as a
result of appending a new node. It is also shown that as the evolution step
increases, the probability of obtaining a new triangle decreases, which can
lead to stabilization of the growth in the number of triangles. The corollary
2.3 shows that the growth rate of the average number of triangles
$E\Delta_{n}$ is higher than the logarithmic one with increasing number of
evolution steps. These results are of independent interest.

Our simulation results do not contradict to the theoretical results.
Specification of the upper and lower bounds for $E\Delta_{n}$ is the purpose
of our further research.

## References

## References

  * [1] Bagrow J. P., Brockmann D. Natural Emergence of Clusters and Bursts in Network Evolution // Physical review X. 2013. No. 3. P. 021016.
  * [2] Newman M. E. J. Random Graphs with Clustering // Physical Review Letters. 2009. No. 103. Issue 5. P. 058701.
  * [3] Qun Liu, Zhishan Dong Limit laws for the number of triangles in the generalized random graphs with random node weights // Statistics and Probability Letters. 2020. No. 161. P. 108733.
  * [4] Bobkov S.G., Danshina M.A., Ulyanov V. V. Rate of Convergence to the Poisson Law of the Numbers of Cycles in the Generalized Random Graphs // In Operator Theory and Harmonic Analysis. Springer Proceedings in Mathematics and Statistics, vol. 358. Karapetyants, A.N., Pavlov, I.V., Shiryaev, A.N., Eds. Springer: Cham, 2021. P. 109–133.
  * [5] Garavaglia A. and C. Stegehuis, Subgraphs in preferential attachment models, Advances in Applied Probability, 51, 898-926, 2019.
  * [6] Van der Hofstad R. Random Graphs and Complex Networks. Cambridge: Cambridge University Press, 2017. Vol. 1.
  * [7] Wang T., Resnick S.I. Consistency of Hill estimators in a linear preferential attachment model // Extremes. 2019. No. 22. P. 1–28.
  * [8] Newman M. E. J. Clustering and preferential attachment in growing networks // Phys. Rev. E. 2001. No. 64, P. 025102(R).
  * [9] Newman M. E. J. The Structure and Function of Complex Networks // SIAM Review. 2003. No. 45. Issue 2. P. 167–256.
  * [10] Arenas A., Fernandez A., Gomez S. Analysis of the structure of complex networks at different resolution levels // New Journal of Physics. 2008. No. 10. P. 053039.
  * [11] Markovich N.M., Ryzhov M.S. Clusters of Exceedances for Evolving Random Graphs // In: Vishnevskiy, V.M., Samouylov, K.E., Kozyrev, D.V. (eds) Distributed Computer and Communication Networks: Control, Computation, Communications. DCCN 2022. Lecture Notes in Computer Science. 2022. vol 13766. P. 67–74.
  * [12] Barabási A.-L., Albert R. Statistical mechanics of complex networks // Rev. Modern Phys. 1999. No. 74. P. 47–97.
  * [13] Albert R., Barabási A.-L. Emergence of scaling in random networks // Science. 2002. No. 286. P. 509–512.
  * [14] Bollobás B., Riordan O.M. Mathematical Results on Scale-Free Random Graphs. Weinheim: Wiley-WCH. 2002.
  * [15] Eggemann N., NobleS. D. The clustering coefficient of a scale-free random graph // Discrete Appl. Math. 2011. No. 159. P. 953–965.
  * [16] Prokhorenkova L. O. General results on preferential attachment and clustering coefficient. Optimization Lett. 11, 279–298, 2017.
  * [17] Stegehuis C., van der Hofstad R., van Leeuwaarden J. S. Variational principle for scale-free network motifs // Scientific reports. 2019. No. 9, Issue 1.
  * [18] Michielan R., Stegehuis C. Cliques in geometric inhomogeneous random graphs // Journal of Complex Networks. 2022. No. 10. P. cnac002.
  * [19] Gao P., van der Hofstad R., Southwell A., Stegehuis C. Counting triangles in power-law uniform random graphs // Electronic journal of combinatorics. 2020. No. 27. Issue 3. P. 1–28.
  * [20] Britton T., Deijfen M., Martin-Löf A. Generating simple random graphs with prescribed degree distribution // J. Stat. Phys. 2006. No. 124. P. 1377–1397.
  * [21] Fristedt B., Gray L. A Modern Approach to Probability Theory. Boston: Birkhäuser, 1997.
  * [22] Shiryaev A.N. Probability. Berlin Heidelberg: Springer, 1995.
  * [23] Chen M.-R., Kuba M. On generalized Pólya urn models // J. Appl. Probab. 2013. No. 50. P. 1169–1186.