# Strong greedoid structure of $r$-removed $P$-orderings

Dmitrii Krachun11footnotemark: 1111Princeton University and Rozalina
Mirgalimova22footnotemark: 2222St. Petersburg State University

###### Abstract

Inspired by the notion of _$r$ -removed $P$-orderings_ introduced in the
setting of Dedekind domains by Bhargava [3] we study its generalization in the
framework of arbitrary (generalised) ultrametric spaces. We show that sets of
maximal ”$r$-removed perimeter” can be constructed by a greedy algorithm and
form a strong greedoid. This gives a simplified proof of several theorems in
[3] and also generalises the results of [5] which considered the case $r=0$
corresponding, in turn, to simple $P$-orderings of [2].

##  1 Introduction

Motivated by questions in polynomial function theory, Bhargava [2] introduced
the notion of _$P$ -orderings_ for a subset $X$ of a Dedekind domain $D$. The
construction is as follows. Given a prime ideal $P\subset D$, let $a_{0}$ be
an arbitrary element of $X$ and for $k=1,2,\dots$ choose $a_{k}\in X$ to
minimize

$\nu_{P}\left((a_{k}-a_{0})(a_{k}-a_{1})\dots(a_{k}-a_{k-1})\right),$

where $\nu_{P}$ denotes the $P$-adic valuation on $D$. One of the results of
[2] is the surprising fact that, despite the fact that typically the choice of
each $a_{k}$ is non-unique, the sequence of the resulting valuations does not
depend on the specific choice of $\\{a_{i}\\}$ but only on $X$ and $P$. Later,
to study basis of the ring of polynomials with integer-valued divided
differences, Bhargava [3] generalised this construction to _$r$ -removed
$P$-orderings_. For an $r$-removed $P$-ordering one again chooses a sequence
$\\{a_{i}\\}$ of elements from $X$ but now the first $r+1$ elements
$a_{0},\dots,a_{r}$ are chosen arbitrary and then each new element minimizes

$\min_{\begin{subarray}{c}A\subset\\{a_{0},\dots,a_{k-1}\\}\\\
|A|=k-r\end{subarray}}\sum_{a\in A}\nu_{P}(a_{k}-a).$

Again, one of the results of [3] is that the resulting sequences of exponents
does not depend on the choice of $\\{a_{i}\\}$.

Recently, Grinberg and Petrov [5] generalised the notion of $P$-orderings to
the context of _ultra triples_ , which is a certain extension of ultrametric
spaces, obtaining new proofs of several results of [2] and showing that all
(prefixes of) $P$-orderings form a strong greedoid. A natural question which
has been asked by Bhargava [1] is then

Do $r$-removed $P$-orderings also fit in the framework of [5]?

We resolve the question in the affirmative by showing that virtually all
theorems of [5] can be indeed generalised to cover the case of $r$-removed
$P$-orderings. This also gives a new proof of [3, Theorems 3, 4, 30], see
Corollary 1.1 and Remark 3.

Let us now introduce the objects we work with. An ultra triple $(E,w,d)$ is
given by a ground set $E$, an arbitrary _weight function_
$w:E\rightarrow\mathbb{R}$, and a _distance function_ $d:\\{(e,f)\in E\times
E\ |\ e\neq f\\}\rightarrow\mathbb{R}$ satisfying the ultrametric triangle
inequality $d(a,b)\leq\max\\{d(a,c),d(b,c)\\}$. Note that unlike in the case
of an ultrametric space we do not require distances to be non-negative.

We consider an _$r$ -removed distance_ from a point $v\in E$ to a finite
subset $C\subset E$ defined by

$\operatorname{dist}_{r}(v,C):=\begin{cases}\max\limits_{A\subset
C,\,|A|=|C|-r}\sum_{x\in A}d(v,x)&|C|>r;\\\ 0&|C|\leq r.\end{cases}$

In words, $\operatorname{dist}_{r}(v,C)$ is the maximum among sums of
distances from $v$ to the points of $C$ except for some $r$ of them. Given
this notion of a distance from a point to a set, we then consider _greedy
$r$-removed $m$-permutation_ of a finite subset $C\subset E$ to be an ordered
subset $(c_{0},\dots,c_{m-1})$ of $C$ which is defined greedily by choosing
elements $c_{0},c_{1},\dots$ one by one in such a way that for each
$n\in\\{0,1,\dots,m-1\\}$ the element $c_{n}$ maximizes

$w(c)+\operatorname{dist}_{r}(c,\\{c_{0},\dots,c_{n-1}\\})$

over all possible $c\in C\setminus\\{c_{0},\dots,c_{n-1}\\}$. A related
concept is that of an _$r$ -removed perimeter_ of a finite ordered set
$A=(a_{1},\dots a_{n})$ which is defined to be

$\operatorname{PER}_{r}(A):=\sum_{a\in
A}w(a)+\sum_{i=1}^{n}\operatorname{dist}_{r}(\\{a_{1},a_{2},\ldots,a_{i-1}\\},a_{i}).$

We prove that $r$-removed perimeter does not depend on a permutation of a
given set, see Lemma 1, allowing to naturally extend the notion of an
$r$-removed perimeter to finite (non-ordered) sets. Then, in Theorem 1 we show
that greedy $r$-removed $m$-permutation of a finite set $C$ has maximal
$r$-removed perimeter among all subsets of $C$ of size $m$, and as a corollary
we show that the sequence of numbers
$w(c_{j})+\operatorname{dist}_{r}(\\{c_{1},c_{2},\ldots,c_{j-1}\\},c_{j})$
does not depend on the choice of a greedy $r$-removed $m$-permutations. Then
in Theorem 3 we show that all sets of maximal $r$-removed perimeter form a
strong greedoid. At the end of the paper we also discuss some other notions of
perimeter that fit into our framework.

The rest of the paper is organised as follows. In Section 2 we formally define
the objects we study and introduce a device we call a _projection_ which is
later frequently used. Then, in Section 3 we prove that $r$-removed perimeter
of a set is well-defined and that construction of an greedy $r$-removed
$m$-permutation gives the maximal $r$-removed perimeter among all subsets of
size $m$. In Section 4 we prove that subsets of maximal $r$-removed perimeter
form a strong greedoid. Finally, Section 5 is devoted to the discussion of a
more general concept of a perimeter of a set, covered by our approach.

##  2 Basic definitions and constructions

We largely follow the notation used in [5], which we now briefly recall.
Throughout the paper, we consider a set $E$ as our ground set, and refer to
the elements of $E$ as points. For a non-negative integer $m$, an $m$-set
means a subset $A$ of $E$ with $|A|=m$, and an $m$-permutation means an
ordered set $A=(a_{1},\dots,a_{m})$ fromed by distinct elements of $E$.
Analogously, if $B\subseteq E$ is a subset and $m$ is a non-negative integer,
an $m$-subset of $B$ means an $m$-element subset of $B$ and an
$m$-permutations of $B$ means an ordered set $A$ formed by $m$ distinct
elements of $B$. The following definition already appeared in [5].

######  Definition 1.

An ultra triple is a triple $(E,w,d)$, where $E$ is a set,
$w:R\rightarrow\mathbb{R}$ is an arbitrary _weight function_ , and
$d:\\{(e,f)\in E\times E\ |\ e\neq f\\}\rightarrow\mathbb{R}$333One could also
extend the domain of $d$ to the whole of $E\times E$ by setting
$d(a,a):=-\infty$ for all $a\in E$. is a _distance function_ satisfying

  * •

$d(a,b)=d(b,a)$ for any two distinct $a,b\in E$.

  * •

$d(a,b)\leq\max\\{d(a,c),\,d(b,c)\\}\text{ for any three distinct }a,b,c\in
E.$

The inequality above is commonly known as the ultrametric triangle inequality;
but unlike the distance function of an ultrametric space, we allow $d$ to take
negative values.

The following are formal definitions of the objects already mentioned in the
introduction, namely, $r$-removed distance, $r$-removed perimeter, and an
$r$-removed $m$-permutation.

######  Definition 2.

Let $(E,w,d)$ be an ultra triple, $C\subseteq E$ be a finite non-empty subset,
and $v$ be any point in $E\setminus C$. We define
$\operatorname{dist}_{r}(C,v)$ to be the maximum among all possible sums of
distances from $v$ to some $|C|-r$ points of the set $C$. If $|C|\leq r$, we
set $\operatorname{dist}_{r}(C,v):=0$.

######  Definition 3.

Let $(E,w,d)$ be an ultra triple. For a permutation
$(a_{1},a_{2},\ldots,a_{k})$ of a finite subset $A\subseteq E$, we define its
$r$-removed perimeter by

$\operatorname{PER}_{r}((a_{1},a_{2},\ldots,a_{k})):=\sum_{a\in
A}w(a)+\sum_{i=1}^{k}\operatorname{dist}_{r}(\\{a_{1},a_{2},\ldots,a_{i-1}\\},a_{i}).$

######  Definition 4.

For an ultra triple $(E,w,d)$ let $C\subseteq E$ be a finite set, and $m$ be a
non-negative integer. A greedy $r$-removed $m$-permutation of $C$ is a list
$(c_{1},c_{2},\ldots,c_{m})$ of $m$ distinct elements of $C$ such that for
each $i\in\\{1,\ldots,m\\}$ and each $x\in
C\setminus\\{c_{1},c_{2},\ldots,c_{i-1}\\}$, we have

$\operatorname{PER}_{r}((c_{1},c_{2},\ldots,c_{i}))\geqslant\operatorname{PER}_{r}((c_{1},c_{2},\ldots,c_{i-1},x)).$
(1)

We now define a useful construction that we are going to use in the proofs, it
earlier implicitly appeared in [5]. We first recall the following definition
from [5].

######  Definition 5.

Let $(E,w,d)$ be an ultra triple, $A\subseteq E$ be a finite non-empty subset
and $c\in E$ be any point. We define a subset $\operatorname{proj}_{A}(c)$ of
$A$ as follows:

  * •

If $c\in A$, then $\operatorname{proj}_{A}(c):=\\{c\\}$;

  * •

If $c\notin A$, then $\operatorname{proj}_{A}(c)$ is the set of all $a\in A$
that minimize the distance $d(c,a)$.

Now we extend it in the following way

######  Definition 6.

Let $(E,w,d)$ be an ultra triple, $C=\\{c_{1},c_{2},\ldots,c_{k}\\}\subseteq
E$ be a finite ordered set and $A$ be any $n$-subset of $E$, where $n\geq k$.
We define $k$-permutation $(v_{1},v_{2},\ldots,v_{k})$ of $A$ recursively as
follows: $v_{i}$ is defined to be a projection of $c_{i}$ onto
$A\setminus\\{v_{1},v_{2},\ldots,v_{i-1}\\}$ for each $i=1,2,\ldots,k$. We
denote $(v_{1},v_{2},\ldots,v_{k})$ by $\operatorname{proj}(C\rightarrow A)$.
These projections $v_{i}$ may be non-unique, in which case we take arbitrary
element of the projection set.

There are three important observations about these constructions that we now
make. The first proposition already appeared in [5, Lemma 2.13] and we give
its short proof for completeness.

######  Proposition 1.

Let $(E,w,d)$ be an ultra triple and $A\subseteq E$ be a non-empty finite set.
Then for a point $c\in E$, its projection $b\in\operatorname{proj}_{A}(c)$ and
any $x\in A\setminus\\{b\\}$ we have $d(b,x)\leq d(c,x)$.

###### Proof.

If $c\in A$ then $b=c$ and we trivially have an equality. Otherwise, since
$x\in A$, by the definition of the projection we have $d(c,x)\geq d(c,b)$ and
so by the ultrametric triangle inequality we have

$d(b,x)\leq\max{\\{d(c,b),d(c,x)\\}}=d(c,x).$

∎

######  Proposition 2.

Let $(E,w,d)$ be an ultra triple, $C=(c_{1},c_{2},\ldots,c_{k})\subseteq E$ be
a finite ordered set and $A$ be a $n$-subset of $E$, with $n\geq k$. Denote
$\operatorname{proj}(C\rightarrow A)$ by $(v_{1},v_{2},\ldots,v_{k})$. Then
for each $j\in\\{1,2,\ldots,k\\}$ one has

$(A\setminus\\{v_{1},\ldots,v_{j}\\})\cap\\{c_{1},c_{2},\ldots,c_{j}\\}=\varnothing.$

###### Proof.

Arguing by contradiction we assume for some $i\leq j\leq k$ that $c_{i}\in
A\setminus\\{v_{1},\ldots,v_{j}\\}$. This implies that $c_{i}\in
A\setminus\\{v_{1},v_{2},\ldots,v_{i-1}\\}$. By definition this means that
$v_{i}:=\operatorname{proj}_{A\setminus\\{v_{1},v_{2},\ldots,v_{i-1}\\}}(c_{i})=c_{i}$.
Hence, $v_{i}=c_{i}\in A\setminus\\{v_{1},\ldots,v_{j}\\}$ which is
impossible. ∎

######  Proposition 3.

Let $(E,w,d)$ be an ultra triple, $C=(c_{1},c_{2},\ldots,c_{k})\subseteq E$ be
a finite ordered set and $A$ be a $n$-subset of $E$, with $n>k$. Then for each
$v\in A\setminus\operatorname{proj}(C\rightarrow A)$

$\operatorname{dist}_{r}(\operatorname{proj}(C\rightarrow
A),v)\leq\operatorname{dist}_{r}(C,v).$

###### Proof.

Denote $\operatorname{proj}(C\rightarrow A)$ by $(v_{1},v_{2},\ldots,v_{k})$.
The statement of the proposition would follow from the inequality
$d(v_{i},v)\leq d(c_{i},v)$ for each $i\in\\{1,2,\dots,k\\}$. But since $v\in
A\setminus\\{v_{1},v_{2},\ldots,v_{i-1}\\}$ this inequality is given by
Proposition 1 applied to the set $A\setminus\\{v_{1},v_{2},\ldots,v_{i-1}\\}$
and points $c_{i}$,
$v_{i}=\operatorname{proj}_{A\setminus\\{v_{1},v_{2},\ldots,v_{i-1}\\}}(c_{i})$
and $v$. ∎

##  3 Perimeter and greedy $r$-removed $m$-permutations

We first prove that any two permutations of a given set have the same
$r$-removed perimeter.

######  Lemma 1.

Any two permutations of a finite set $A\subseteq E$ have the same $r$-removed
perimeter.

###### Proof.

It suffices to prove the statement for pairs of permutations which differ by
one transposition. The general case is reduced to it by consecutive
transpositions.

Let us prove the statement for permutations
$(a_{1},\ldots,a_{t},a_{t+1},\ldots a_{k})$ and
$(a_{1},\ldots,a_{t-1},a_{t+1},a_{t},\ldots,a_{k})$. Denote by $C$ the set
$\\{a_{1},a_{2},\ldots a_{t-1}\\}$. Many summands from the definition of
$r$-removed perimeter coincide, all that remains to prove is

$\operatorname{dist}_{r}(C,a_{t})+\operatorname{dist}_{r}(C\cup\\{a_{t}\\},a_{t+1})=\operatorname{dist}_{r}(C,a_{t+1})+\operatorname{dist}_{r}(C\cup\\{a_{t+1}\\},a_{t}).$
(2)

If $t\leq r$, both sides are 0. Otherwise, we let $z=d(a_{t},a_{t+1})$,
$x_{j}=d(a_{t},a_{j})$ and $y_{j}=d(a_{t+1},a_{j})$, where $j=1,\ldots,t-1$.
In what follows we only consider triangles of the form $a_{t}a_{t+1}a_{j}$ for
some $j=1,2,\ldots,t-1$ and use ultrametric triangle inequality for them.

We colour triangles with two sides strictly greater than $z$ in red, in which
case $x_{j}=y_{j}$ by the ultrametric inequality. Triangles coloured in red
correspond to some largest distances from points $a_{t}$ and $a_{t+1}$ to the
set $C$ which coincide. In any other triangle we must have $x_{i}=z\geqslant
y_{i}$ or $y_{i}=z\geqslant x_{i}$.

If there are at least $t-r$ red triangles, then
$\operatorname{dist}_{r}(C,a_{t})=\operatorname{dist}_{r}(C,a_{t+1})$,
${\operatorname{dist}_{r}(C\cup\\{a_{t}\\},a_{t+1})=\operatorname{dist}_{r}(C\cup\\{a_{t+1}\\},a_{t})}$
and (2) is true.

If there are less than $t-r$ red triangles, then
$\operatorname{dist}_{r}(C\cup\\{a_{t}\\},a_{t+1})=\operatorname{dist}_{r}(C,a_{t+1})+z$
and
$\operatorname{dist}_{r}(C\cup\\{a_{t+1}\\},a_{t})=\operatorname{dist}_{r}(C,a_{t})+z$.
By substituting these expressions into (2), we again get an equality. ∎

In light of this lemma we have the following definition

######  Definition 7.

For a finite subset $A\subseteq E$, we define its $r$-removed perimeter
$\operatorname{PER}_{r}(A)$ to be the common $r$-removed perimeter of all
permutations of $A$.

######  Remark 1.

For the case $r=0$, the $r$-removed perimeter is the sum of the distances
between all unordered pairs of points plus the sum of the weight function of
all points. This case was considered in [5].

######  Theorem 1.

Let $(E,w,d)$ be an ultra triple and $C\subseteq E$ be a finite subset, and
$m$ and $r$ be non-negative integers. Let $(c_{1},c_{2},\ldots,c_{m})$ be any
greedy $r$-removed $m$-permutation of $C$. Then, for each
$k\in\\{0,1,...,m\\}$, the set $\\{c_{1},c_{2},\ldots,c_{k}\\}$ has maximum
$r$-removed perimeter among all $k$-subsets of $C$.

###### Proof.

Given a greedy $r$-removed $m$-permutation $(c_{1},c_{2},\ldots,c_{m})$, we
want to prove that for any $k$-subset $A\subseteq C$,
$\operatorname{PER}_{r}(A)\leq\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{k}\\})$.
We induct on $k$.

For $k=0$ both perimeters are 0, and so the inequality is trivially true. For
the induction step from $k-1$ to $k$, let
$(v_{1},v_{2},\ldots,v_{k}):=\operatorname{proj}(\\{c_{1},c_{2},\ldots,c_{k}\\}\rightarrow
A)$, which is an ordering of $A$. Then by Proposition 2,

$v_{k}\notin\\{c_{1},c_{2},\ldots,c_{k-1}\\}.$

By induction hypothesis we know that

$\operatorname{PER}_{r}(\\{v_{1},v_{2},\ldots,v_{k-1}\\})\leq\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{k-1}\\}),$

and so to complete the induction step it suffices to show that

$\operatorname{PER}_{r}(A)-\operatorname{PER}_{r}(\\{v_{1},v_{2},\ldots,v_{k-1}\\})\leq\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{k}\\})-\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{k-1}\\}),$

which, implicitly using Lemma 1, can be equivalently written as

$w\left(v_{k}\right)+\operatorname{dist}_{r}(\\{v_{1},v_{2},\ldots,v_{k-1}\\},v_{k})\leq
w\left(c_{k}\right)+\operatorname{dist}_{r}(\\{c_{1},c_{2},\ldots,c_{k-1}\\},c_{k}).$
(3)

We now turn to proving (3). Since $v_{k}\in
A\setminus\\{c_{1},c_{2},\ldots,c_{k-1}\\}\subseteq
C\setminus\\{c_{1},c_{2},\ldots,c_{k-1}\\}$ (recall that $A\subseteq C$), we
have
$\operatorname{PER}_{r}\\{c_{1},c_{2},\ldots,c_{k-1},v_{k}\\}\leq\operatorname{PER}_{r}\\{c_{1},c_{2},\ldots,c_{k}\\}$
by the definition of a greedy $r$-removed $m$-permutation. Subtracting
$\operatorname{PER}_{r}(\left\\{c_{1},c_{2},\ldots,c_{k-1}\right\\})$ from
both sides we arrive at

$w\left(v_{k}\right)+\operatorname{dist}_{r}(\\{c_{1},c_{2},\ldots,c_{k-1}\\},v_{k})\leq
w\left(c_{k}\right)+\operatorname{dist}_{r}(\\{c_{1},c_{2},\ldots,c_{k-1}\\},c_{k})$

And so to deduce (3) it remains to show that

$\operatorname{dist}_{r}(\\{v_{1},v_{2},\ldots,v_{k-1}\\},v_{k})\leq\operatorname{dist}_{r}(\\{c_{1},c_{2},\ldots,c_{k-1}\\},v_{k}).$

Which is nothing else but the statement of Proposition 3 for the point
$v=v_{k}$ and
$\\{v_{1},v_{2},\ldots,v_{k-1}\\}=\operatorname{proj}(\\{c_{1},c_{2},\ldots,c_{k-1}\\}\rightarrow
A)$. ∎

######  Remark 2.

It follows from the proof that if the equality

$\operatorname{PER}_{r}(\\{v_{1},v_{2},\ldots,v_{k}\\})=\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{k}\\})$

holds for
$(v_{1},v_{2},\ldots,v_{k}):=\operatorname{proj}(\\{c_{1},c_{2},\ldots,c_{k}\\}\rightarrow
A)$, then for each $j<k$ one also has an equality
$\operatorname{PER}_{r}(\\{v_{1},v_{2},\ldots,v_{j}\\})=\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{j}\\})$.

######  Corollary 1.1.

Let $C\subseteq E$ be a set, $m$ and $r$ be a non-negative integers,
$j\in\\{1,2,\ldots m\\}$. If $(c_{1},c_{2},\ldots,c_{m})$ is a greedy
$r$-removed $m$-permutation of $C$, then the number

$\displaystyle
w\left(c_{j}\right)+\operatorname{dist}_{r}(\\{c_{1},c_{2},\ldots,c_{j-1}\\},c_{j})$

does not depend on the choice of this greedy $r$-removed $m$-permutation but
only depends on $C,r$ and $j$.

###### Proof.

By Theorem 1, for each $k\leq m$ the set $\\{c_{1},c_{2},\ldots,c_{k}\\}$ has
maximum perimeter among all $k$-subsets of $C$, which implies that
$\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{k}\\})$ does not depend on
the choice of the greedy $r$-removed $m$-permutation of $C$. It remains to
note that

$\displaystyle
w(c_{j})+\operatorname{dist}_{r}(\\{c_{1},c_{2},\ldots,c_{j-1}\\},c_{j})=\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{j}\\})-\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{j-1}\\}).$

∎

######  Remark 3.

As a special case of this corollary we obtain the results of [3, Theorems 3,
4, 30]. Indeed, for a Dedekind domain $D$, a prime ideal $P\subset D$, and
$h\in\mathbb{Z}_{\geq 0}$, the distance function
$d_{P,h}(a,b):=-\max(h,\nu_{P}(a-b))$ satisfies the ultrametric triangle
inequality and so the result follows from Corollary 1.1 applied to an ultra
triple $(S,w\equiv 0,d_{P,h})$.

We now prove the converse of Theorem 1, namely, that any set of maximal
$r$-removed perimeter is a prefix of some greedy $r$-removed $m$-permutation.

######  Theorem 2.

Let $(E,w,d)$ be an ultra triple, $C\subseteq E$ be a finite set, and $m$ be a
non-negative integer such that $|C|\geqslant m$. For $k\in\\{0,1,\ldots,m\\}$
let $A$ be a $k$-subset of $C$ having maximum $r$-removed perimeter (among all
$k$-subsets of $C$). Then, there exists a greedy $r$-removed $m$-permutation
of $C$ for which $A$ is a prefix of this permutation.

###### Proof.

Choose an arbitrary greedy $r$-removed $m$-permutation
$(c_{1},c_{2},\ldots,c_{m})$ of $C$ by starting with any point and continuing
the sequence greedily choosing elements from the remaining points. By Theorem
1, the set $(c_{1},c_{2},\ldots,c_{k})$ has maximum perimeter among all
$k$-subsets of $C$. Hence,
$\operatorname{PER}_{r}(A)=\operatorname{PER}_{r}(\left\\{c_{1},c_{2},\ldots,c_{k}\right\\})$
since the set $A$ also has maximum $r$-removed perimeter among them.

Let
$(v_{1},v_{2},\ldots,v_{k}):=\operatorname{proj}(\\{c_{1},c_{2},\ldots,c_{k}\\}\rightarrow
A)$. What we want to prove is that there exists a greedy $r$-removed $m$
permutation of $C$ which starts from $(v_{1},v_{2},\dots,v_{k})$, which is
equivalent to checking that for each $p\leq k$ the point $v_{p}$ maximizes

$w(x)+\operatorname{dist}_{r}(\\{v_{1},\dots,v_{p-1}\\},x)$

over all $x\in C\setminus\\{v_{1},\dots,v_{p-1}\\}$.

As mentioned in Remark 2, the fact that
$\operatorname{PER}_{r}(\\{v_{1},v_{2},\ldots,v_{k}\\})=\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{k}\\})$
implies that for each $j\leq k$ we have
$\operatorname{PER}_{r}(\\{v_{1},v_{2},\ldots,v_{j}\\})=\operatorname{PER}_{r}(\\{c_{1},c_{2},\ldots,c_{j}\\})$.
In particular, this holds for $j=p$. Now, arguing by contradiction we assume
that there exists $x\in C\setminus\\{v_{1},\ldots,v_{p-1}\\}$ such that

$w(x)+\operatorname{dist}_{r}(\\{v_{1},\ldots,v_{p-1}\\},x)>w(v_{p})+\operatorname{dist}_{r}(\\{v_{1},\ldots,v_{p-1}\\},v_{p}).$

This would mean that

$\operatorname{PER}_{r}(\\{v_{1},\ldots,v_{p-1},x\\})>\operatorname{PER}_{r}(\\{v_{1},\ldots,v_{p-1},v_{p}\\})=\operatorname{PER}_{r}(\\{c_{1},\ldots,c_{p-1},c_{p}\\}),$

contradicting the fact that $\\{c_{1},\ldots,c_{p-1},c_{p}\\}$ has the largest
$r$-removed perimeter among all subsets of $C$ of size $p$. ∎

##  4 Strong greedoid of maximum perimeter sets

In [5] it was shown that sets maximizing the perimeter (i.e. $r$-removed
perimeter with $r=0$) form a strong greedoid. In this section we generalize
this statement to all $r\geq 0$. We start by recalling the relevant
definitions from the theory of greedoids.

######  Definition 8.

A collection $\mathcal{F}\subseteq 2^{E}$ of subsets of a finite set $E$ is
called a greedoid (on the ground set $E$) if it satisfies the following three
axioms:

  1. (i)

$\varnothing\in\mathcal{F}$.

  2. (ii)

If $A\in\mathcal{F}$ satisfies $|A|>0$, then there exists $a\in A$ such that
$A\setminus a\in\mathcal{F}$.

  3. (iii)

If $A,B\in\mathcal{F}$ satisfy $|A|=|B|+1$, then there exists $a\in A\setminus
B$ such that $B\cup a\in\mathcal{F}$.

A greedoid $\mathcal{F}$ on a ground set $E$ is called a strong greedoid (also
known as “Gauss greedoid”) if it additionally satisfies the following axiom:

  1. (iv)

If $A,B\in\mathcal{F}$ satisfy $|A|=|B|+1$, then there exists $a\in A\setminus
B$ such that $B\cup a\in\mathcal{F}$ and $A\setminus a\in\mathcal{F}$.

There are several equivalent definitions of a greedoid in the literature, ours
is taken from [6, Section IV.1]. Specifically, our axioms (i) and (iii) align
with conditions (1.4) and (1.6) in [6, Section IV.1], while axioms (i) and
(ii) establish $(E,\mathcal{F})$ as an accessible set system. The definition
of a strong greedoid can be found in [4].

Now we assume that the set $E$ is finite. The following theorem shows that
sets with maximal $r$-removed perimeter form a strong greedoid.

######  Theorem 3.

Let $(E,w,d)$ be an ultra triple on a finite ground set and $\mathcal{F}_{r}$
denote the collection of subsets $A\subseteq E$ that have maximum $r$-removed
perimeter among all $|A|$-sets:

$\mathcal{F}_{r}:=\\{A\subseteq E\ |\
\operatorname{PER}_{r}(A)\geq\operatorname{PER}_{r}(B)\text{ for all
}B\subseteq E\text{ satisfying }|B|=|A|\\}.$

Then $\mathcal{F}_{r}$ is a strong greedoid on the ground set $E$.

We start by proving the following lemma.

######  Lemma 2.

Let $A$ and $B$ be two subsets of $E$ such that $|A|=|B|+1$. Then, there
exists $u\in A\setminus B$ satisfying

$\operatorname{PER}_{r}(A\setminus u)+\operatorname{PER}_{r}(B\cup
u)\geq\operatorname{PER}_{r}(A)+\operatorname{PER}_{r}(B)$ (4)

###### Proof.

Let $k=|B|$ and so $|A|=k+1$. With a slight abuse of notation we denote by $B$
an arbitrary ordered set formed by elements of $B$, which we fix from now on.
Define $(v_{1},v_{2},\ldots,v_{k}):=\operatorname{proj}(B\rightarrow A)$ and
let $u$ be the unique element of $A\setminus\\{v_{1},v_{2},\ldots,v_{k}\\}$.
By Lemma 2 we have $u\notin B$. We now want to prove (4) for this choice of
$u$. Subtructing $\operatorname{PER}_{r}(A\setminus
u)+\operatorname{PER}_{r}(B)+w(u)$ from both sides we arrive at an equivalent
inequality

$\operatorname{dist}_{r}(B,u)\leq\operatorname{dist}_{r}(A\setminus u,u),$

which is simply the result of Proposition 3 applied to $u$ and $A\setminus
u=\operatorname{proj}(B\rightarrow A)$. ∎

###### Proof of Theorem 3.

First note that property (i) is trivial, and (iii) immediately follows from
(iv). Furthermore, since $E$ is finite, for any $s\leq|E|$ there exists
$B\in\mathcal{F}_{r}$ with $|B|=s$, and so by choosing arbitrary
$B\in\mathcal{F}_{r}$ with $|B|=|A|-1$ we can deduce (ii) from (iv).

To prove (iv) we use Lemma 2 to construct $u\in A\setminus B$ satisfying (4).
Since $A\in\mathcal{F}_{r}$ we must have $\operatorname{PER}_{r}(B\cup
u)\leq\operatorname{PER}_{r}(A)$. Similarly, $B\in\mathcal{F}_{r}$ implies
$\operatorname{PER}_{r}(A\setminus u)\leq\operatorname{PER}_{r}(B)$. Together
with (4) these two inequalities immediately imply that

$\operatorname{PER}_{r}(A\setminus
u)=\operatorname{PER}_{r}(B),\qquad\operatorname{PER}_{r}(B\cup
u)=\operatorname{PER}_{r}(A),$

which means that both $A\setminus u$ and $B\cup u$ are in $\mathcal{F}_{r}$.
This shows that $\mathcal{F}_{r}$ is a strong greedoid. ∎

##  5 Other perimeters

Instead of the $r$-removed distance $\operatorname{dist}_{r}(C,v)$ we could
start from some other notion of a distance from a point to a set, call it
$\operatorname{dist}(C,v)$, and define
$\operatorname{PER}(\\{a_{1},\dots,a_{n}\\})$ of an ordered set
$A:=(a_{1},\dots,a_{n})$ by setting $\operatorname{PER}(A):=\sum_{a\in
A}w(a)+\sum_{i=1}^{k}\operatorname{dist}(\\{a_{1},a_{2},\ldots,a_{i-1}\\},a_{i})$.
Tracking the proofs of Theorems 1, 2 and 3 we see that the only two properties
of the $\operatorname{dist}$ functions that we use are given by the following

######  Definition 9.

We say that a function $\operatorname{dist}$ satisfies property $\mathbf{S}$
if for any set $\left\\{c_{1},c_{2},\ldots,c_{n}\right\\}=:C\subseteq E$ and
$x,y\in E\setminus C$ one has

  1. (S1)

$\operatorname{dist}(C,x)+\operatorname{dist}(C\cup\\{x\\},y)=\operatorname{dist}(C,y)+\operatorname{dist}(C\cup\\{y\\},x)$;

  2. (S2)

If $d(c_{i},x)\leq d(c_{i},y)$ for each $i\in\\{1,2,\ldots,n\\}$, then

$\operatorname{dist}(\\{c_{1},c_{2},\ldots,c_{n}\\},x)\leq\operatorname{dist}(\\{c_{1},c_{2},\ldots,c_{n}\\},y).$

######  Remark 4.

Indeed, property $\mathbf{(S1)}$ is used in Lemma 1 to prove that the
perimeter of a set is well-defined, and is, in fact, equivalent to this lemma.
Property $\mathbf{(S2)}$ is used in the proofs of Theorems 1 and 2.

We now give a large family of distances satisfying property $\mathbf{S}$.

######  Lemma 3.

Let $(E,w,d)$ be an ultra triple and $f=(f_{n})_{n=1}^{\infty}$ be a sequence
of non-decreasing functions. For a set $\\{c_{1},\ldots,c_{n}\\}=C\subseteq E$
and $x\in E\setminus C$, let
$\operatorname{dist}_{f}(C,x):=\sum_{i=1}^{n}f_{i}(d_{i})$, where
$(d_{1},d_{2},\ldots,d_{n})$ is the ordered set of values
$d(c_{1},x),\ldots,d(c_{n},x)$ arranged in non-decreasing order. Then
$\operatorname{dist}_{f}$ satisfies property $\mathbf{S}$.

###### Proof.

We first check $\mathbf{(S1)}$. Since the property is linear in
$f=(f_{n})_{n=1}^{\infty}$, it suffices to check it for
$\operatorname{dist}_{f}$ with

$f_{j}:=\begin{cases}0&j\leq r;\\\ g&j>r.\end{cases}$

Where $g:\mathbb{R}\rightarrow\mathbb{R}$ is some fixed non-decreasing
function. Indeed, one easily sees that the linear span of these sequences
contains the whole cone of possible sequences of non-decreasing functions. But
for this specific choice of $f$, the distance $\operatorname{dist}_{f}$ is
nothing else but the $r$-removed distance for the ultra triple $(E,w,d_{g})$
where $d_{g}$ is given by $d_{g}(a,b):=g(d(a,b))$444One easily sees that
$d_{g}$ satisfies the ultemetric inequality for any non-decreasing $g$. and so
the equality (S1) is given by (2) from the proof of Lemma 1.

To check (S2) it suffices to note that if one $n$-tuple is point-wise smaller
than another, then the same remains true after each of the $n$-tuples is
sorted from the smallest value to the largest, and then use the fact that each
$f_{j}$ is non-decreasing. ∎

For sufficiently large spaces and under certain natural conditions on the
distance function $\operatorname{dist}$ from a point to a set we manage to
prove the reverse of Lemma 3. To avoid stating technical conditions we prove
the result for the space $(\mathbb{Z},w,-\nu_{p})$ in which distance between
points $a,b\in\mathbb{Z}$ is given by $-\nu_{p}(a-b)$, where $\nu_{p}$ stands
for the $p$-adic valuation and we further assume that $p>2$.

######  Lemma 4.

Consider an ultra triple $(\mathbb{Z},w,-\nu_{p})$ with arbitrary weight
function $w$ and $p>2$. Assume that the value of the distance function
$\operatorname{dist}(C,x)$ from a point $x$ to a set $C$ depends only on the
set of distances from $x$ to the points of $C$ and that $\operatorname{dist}$
satisfies property $\mathbf{S}$. Then
$\operatorname{dist}\equiv\operatorname{dist}_{f}$ for some sequence of non-
decreasing functions $f=(f_{n})_{n=1}^{\infty}$.

###### Proof.

By assumption there exists a sequence of symmetric functions
$g_{n}:\mathbb{Z}_{\leq 0}^{n}\rightarrow\mathbb{R}$ indexed by $n\geq 1$,
such that for any point $x$ and any set $\\{c_{1},\dots,c_{n}\\}$ not
containing $x$ we have

$\operatorname{dist}(x,\\{c_{1},\dots,c_{n}\\})=g_{n}(d(c_{1},x),\dots,d(c_{n},x)).$

We want to prove the existence of a sequence of non-decreasing functions
$(f_{n})_{n=1}^{\infty}$ such that for any non-positive integers $d_{1}\leq
d_{2}\leq\dots\leq d_{n}$

$g_{n}(d_{1},d_{2},\dots d_{n})=\sum_{j=1}^{n}f_{j}(d_{j}).$ (5)

We prove the existence of functions $f_{j}$ by induction on $j$, and for the
base case we set $f_{1}:=g_{1}$ which is non-decreasing by the second
condition of property $\mathbf{S}$.

Now assume that $f_{1},\dots,f_{m-1}$ are already defined in such a way that
(5) is satisfied for all $n<m$ and we want to define $f_{m}$. For each
$d\in\mathbb{Z}_{\leq 0}$ we set

$f_{m}(d):=g_{m}(d,d,\dots,d)-g_{m-1}(d,d,\dots,d),$

where we have $m$ arguments equal to $d$ in the first case and $m-1$ arguments
equal to $d$ in the second.

First, we check that (5) is satisfied for $n=m$. For this, given non-positive
integers $d_{1}\leq d_{2}\leq\dots\leq d_{n}$ we consider two points
$x,y\in\mathbb{Z}$ with $d(x,y)=d_{n}$ and a set of points
$C:=\\{c_{1},\dots,c_{n-1}\\}$ such that for each $j=1,\dots,n-1$ we have
$d_{j}:=d(c_{j},x)$ and $d(c_{j},y)=d_{n}$. The existence of such a set
follows from the property of $\mathbb{Z}$ with the $p$-adic distance (where
$p>2$) which guarantees that for any two points $a,b\in\mathbb{Z}$ and any
$\ell\leq d(a,b)$ there exists $c\in\mathbb{Z}$ such that $d(a,c)=\ell$ and
$d(b,c)=d(a,b)$. Using $\mathbf{(S1)}$ we write

$\displaystyle
g(d_{1},\dots,d_{n})=\operatorname{dist}(C\cup\\{y\\},x)=\operatorname{dist}(C,x)+\left(\operatorname{dist}(C\cup\\{x\\},y)-\operatorname{dist}(C,y)\right),$

and it remains to observe that the difference in parentheses is equal to
$f_{n}(d_{n})$ by the definition of $f_{n}$ and

$\operatorname{dist}(C,x)=\sum_{j=1}^{n-1}f_{j}(d_{j})$

by induction hypothesis.

Second, we show that $f_{m}$ is non-decreasing. Let
$\ell_{1},\ell_{2}\in\mathbb{Z}_{\leq 0}$ satisfy $\ell_{1}\leq\ell_{2}$. By
(5) we have

$f_{m}(\ell_{2})-f_{m}(\ell_{1})=g_{m}(\ell_{1},\dots,\ell_{1},\ell_{2})-g_{m}(\ell_{1},\dots,\ell_{1},\ell_{1})$

and so $f_{m}(\ell_{2})\geq f_{m}(\ell_{1})$ directly follows from
$\mathbf{(S2)}$. ∎

Acknowledgements: We would like to thank Fedor Petrov for his guidance in this
project.

## References

  * [1] M. Bhargava.  private communication, 2022.
  * [2] Manjul Bhargava.  $P$-orderings and polynomial functions on arbitrary subsets of Dedekind rings.  Journal für die reine und angewandte Mathematik, 490:101–128, 1997\.
  * [3] Manjul Bhargava.  On $p$-orderings, rings of integer-valued polynomials, and ultrametric analysis.  Journal of the American Mathematical Society, 22(4):963–993, 2009\.
  * [4] V. Bryant and I. Sharpe.  Gaussian, Strong and Transversal Greedoids.  European Journal of Combinatorics, 20(4):259–262, 1999.
  * [5] Darij Grinberg and Fedor Petrov.  A greedoid and a matroid inspired by Bhargava’s $p$-orderings.  The Electronic Journal of Combinatorics, 28(3), jul 2021.
  * [6] Bernhard Korte, Rainer Schrader, and László Lovász.  Greedoids, Algorithms and Combinatorics.  Springer, 1 edition, 1991.


Vladimir Goradzhanov, Igor Chilingaryan, Ivan Katkov, Kirill Grishin, Victoria
Toptun, Ivan Kuzmin, Mariia Demianenko 11institutetext: Sternberg Astronomical
Institute, M.V.Lomonosov Moscow State University,
22institutetext: Center for Astrophysics – Harvard and Smithsonian (USA),
33institutetext: Department of Physics, M.V. Lomonosov Moscow State
University,
44institutetext: New York University Abu Dhabi (UAE),
55institutetext: Center for Astro, Particle, and Planetary Physics, NYU AD
(UAE)
66institutetext: Moscow Institute of Physics and Technology (National Research
University),
77institutetext: HSE University

# Optical spectroscopic observations of intermediate-mass black holes and
their host galaxies: the $M_{BH}-\sigma_{*}$ relation.

Vladimir Goradzhanov 1133 Igor Chilingarian Ivan Katkov 1122114455 Kirill
Grishin 11 Victoria Toptun 1133 Ivan Kuzmin 1133 Mariia Demianenko 116677

###### Abstract

Intermediate-mass black holes (IMBHs; $M_{BH}<2*10^{5}M_{\odot}$) in galaxy
centers are cruciel for painting a coherent picture of the formation and
growth of supermassive black holes (SMBHs). Using Big Data analysis, we
identified 305 IMBH candidates for IMBH and 1623 candidates of ‘light-weight’
SMBHs ($2*10^{5}M_{odot}<M_{BH}<10^{6}M_{\odot}$). For 35 host galaxies from
this combined sample with the X-ray-confirmed active galactic nuclei (AGN) we
collected and analyzed optical spectroscopic observations. These data show
that bulge stellar velocity dispersions ($\sigma_{*}$) lie in the range of
24$\dots$118 km/s and do not follow the correlation with $M_{BH}$ established
by larger SMBHs indicating that in the $10^{5}-10^{6}M_{\odot}$ range the
accretion is the prevailing BH growth channel.

###### keywords:

cosmology: observations — early universe — galaxies: active — galaxies: nuclei
— galaxies: Seyfert — quasars: supermassive black holes

##  1 Introduction

Currently observed black holes are categorized by mass into three types:
stellar mass black holes ($4<M_{BH}<100M_{\odot}$), supermassive black holes
(SMBH; $M_{BH}>10^{5}M_{\odot}$), and intermediate mass black holes (IMBH;
$100<M_{BH}<10^{5}M_{\odot}$). The growth of central SMBHs and the way they
affect their host galaxies remains a highly controversial issue in modern
astrophysics. From theoretical perspectives, a black hole seed with a starting
mass of $50M_{\odot}$ cannot grow to a billion solar mass SMBH via accretion
in $\sim$1 Gyr (or $z>7$ corresponding to record holding high-redshift
quasars), because the accretion rate is limited by the Eddington luminosity
($L_{Edd}$). If this is indeed the main SMBH growth channel, then ‘undergrown’
seeds will form a population of IMBHs.

Here we adopt the limit $M_{\mathrm{BH}}<2\cdot 10^{5}M_{\odot}$ as the
threshold mass for what we call an IMBH, because it corresponds to +1$\sigma$
systematic uncertainty in virial mass estimate (Reines et al. 2013;
Chilingarian et al. 2018) from broad $H\alpha$.

Central massive black holes in both galaxies with active and inactive nuclei
follow rather tight correlations with the stellar velocity dispersion
$\sigma_{*}$ of the bulge and the total stellar mass of the bulge $M_{\rm
bulge}$ (Ferrarese & Merritt 2000; van den Bosch 2016), which is interpreted
as a co-evolution of the bulge and SMBH via galaxy mergers. At the same time,
SMBHs can gain mass via accretion (Volonteri 2012) at any moment during the
cosmic time. It is not yet fully known whether these relations hold for IMBH
because of observational difficulties and small samples of known IMBHs.

In 2018, the largest to-date sample of 305 IMBH candidates was identified by
Chilingarian et al. (2018) using data mining in the Reference Catalog of
Spectral Energy Distribution (Chilingarian et al. 2017) database of almost 1
million spectra of galaxies from the SDSS Survey (Abazajian et al. 2009). Some
of them were later observed with intermediate-resolution optical spectrographs
MagE (6.5-m Magellan telescope) and RSS (10-m Southern African Large
Telescope) to refine stellar velocity dispersions and improve $M_{BH}$
measurements. Here we report preliminary results of this project and also
present $\sigma_{*}$ measurements for a sample of ‘light-weight’ SMBHs
($<10^{6}M_{\odot}$) populating the bottom part of the $M_{BH}-\sigma_{*}$
relation.

##  2 Spectral data analysis

|
---|---
Figure 1: Left panels top to bottom: the original 2d emission spectrum of the
galaxy J110731.22+134712.9 in the $H\alpha$ region; the result of the fitting
of emission lines; fitting residuals; the reconstructed broad line profile.
Right panel: a 2D narrow-line profile of the $H\alpha$. Figure 2: The
$M_{BH}-\sigma_{*}$ relation featuring IMBHs and light-weight SMBHs. Only one
IMBH has a mass estimate based on masers (Zaw et al. 2020); the rest of the
data points are virial estimates from $H\alpha$. New data from MagE and SALT
are shown by green diamonds and red stars respectively.

We obtained 30 spectra for 26 ‘light-weight’ SMBHs using MagE and additional 9
spectra using RSS and reduced them with standard data processing pipelines. We
fitted the reduced spectra with the NBursts technique (Chilingarian et al.
2007b, a) to determine the stellar continuum and measure stellar velocity
dispersions as low as 20 km/s (Chilingarian & Grishin 2020). Then we
subtracted the best-fitting stellar population templates from the spectra and
applied a novel method of a two-dimensional nonparametric reconstruction of
the $H\alpha$ profile of emission spectra (see Fig. 1). The method yields a
non-parametric narrow-line profile featuring narrow lines from the AGN and a
position–velocity diagram for narrow lines originating from a star-forming
disk of its host galaxy. It also returns the parameters of the broad component
of $H\alpha$ and $H\beta$ formed in the broad-line region, as well as
corresponding fluxes. The broad $H\alpha$ flux and width are then used for the
virial $M_{BH}$ estimate using the calibration from Reines et al. (2013):
$M_{BH}=3.72\cdot
10^{6}(\mathrm{FWHM}_{H\alpha}/10^{3}\mathrm{km/s})^{2.06}\cdot(L_{H\alpha}/10^{42}\mathrm{erg/s})^{0.47}$.
We rejected 7 galaxies from the MagE sample where broad components were not
confidently detected. We also took into account slit losses assuming that the
broad H$\alpha$ component comes from a point source and knowing the slit
width.

##  3 The $M_{BH}-\sigma$ scaling relation

The $M_{BH}-\sigma_{buldge}$ relation constructed from the measured values of
$\sigma_{*}$ and $M_{BH}$ derived from MagE and SALT data is shown in Fig. 2.
We can make a preliminary conclusion that light-weight SMBHs and IMBHs do not
follow the relation established by more massive SMBHs and, hence, do not co-
evolve with bulges of their host galaxies. Such situation can arise if the
black hole mass growth in the low-mass regime is dominated by accretion rather
than mergers. This result might have serious implications on the detectability
of gravitational wave signals from merging IMBHs by the fortcoming LISA
mission. Acknowledgements. This project is supported by the RScF Grant
17-72-20119.

## References

  * Abazajian et al. (2009) Abazajian, K. N., Adelman-McCarthy, J. K., Agüeros, M. A., et al. 2009, ApJS, 182, 543
  * Chilingarian et al. (2007a) Chilingarian, I., Prugniel, P., Sil’chenko, O., & Koleva, M. 2007a, in IAU Symposium, Vol. 241, Stellar Populations as Building Blocks of Galaxies, ed. A. Vazdekis & R. R. Peletier (Cambridge, UK: Cambridge University Press), 175–176
  * Chilingarian & Grishin (2020) Chilingarian, I. V., & Grishin, K. A. 2020, PASP, 132, 064503
  * Chilingarian et al. (2018) Chilingarian, I. V., Katkov, I. Y., Zolotukhin, I. Y., et al. 2018, ApJ, 863, 1
  * Chilingarian et al. (2007b) Chilingarian, I. V., Prugniel, P., Sil’Chenko, O. K., & Afanasiev, V. L. 2007b, MNRAS, 376, 1033
  * Chilingarian et al. (2017) Chilingarian, I. V., Zolotukhin, I. Y., Katkov, I. Y., et al. 2017, ApJS, 228, 14
  * Ferrarese & Merritt (2000) Ferrarese, L., & Merritt, D. 2000, ApJ, 539, L9
  * Reines et al. (2013) Reines, A. E., Greene, J. E., & Geha, M. 2013, ApJ, 775, 116
  * van den Bosch (2016) van den Bosch, R. C. E. 2016, ApJ, 831, 134
  * Volonteri (2012) Volonteri, M. 2012, Science, 337, 544
  * Zaw et al. (2020) Zaw, I., Rosenthal, M. J., Katkov, I. Y., et al. 2020, The Astrophysical Journal, 897, 111.  https://doi.org/10.3847/1538-4357/ab9944


# Epidemic modelling requires knowledge of the social network

Samuel Johnson<EMAIL_ADDRESS>School of Mathematics, University of
Birmingham, Edgbaston B15 2TT, United Kingdom, and
The Alan Turing Institute, British Library, 96 Euston Rd, London NW1 2DB,
United Kingdom

###### Abstract

‘Compartmental models’ of epidemics are widely used to forecast the effects of
communicable diseases such as COVID-19 and to guide policy. Although it has
long been known that such processes take place on social networks, the
assumption of ‘random mixing’ is usually made, which ignores network
structure. However, ‘super-spreading events’have been found to be power-law
distributed, suggesting that the underlying networks may be scale free or at
least highly heterogeneous. The random-mixing assumption would then produce an
overestimation of the herd-immunity threshold for given $R_{0}$; and a (more
significant) overestimation of $R_{0}$ itself. These two errors compound each
other, and can lead to forecasts greatly overestimating the number of
infections. Moreover, if networks are heterogeneous and change in time,
multiple waves of infection can occur, which are not predicted by random
mixing. A simple SIR model simulated on both Erdős-Rényi and scale-free
networks shows that details of the network structure can be more important
than the intrinsic transmissibility of a disease. It is therefore crucial to
incorporate network information into standard models of epidemics.

††preprint: APS/123-QED

##  I Modelling epidemics

Throughout the recent COVID-19 pandemic, ‘compartmental models’, such as the
SIR or SEIR models, were widely used to forecast the likely number of
infections, hospitalisations and deaths from the disease under different
scenarios [1, 2, 3], particularly as a guide to making ‘non-pharmaceutical
interventions’ (NPIs) [4, 5]. However, doubts arose as to their predictive
power [6]. In the UK, for example, the large waves of infections expected to
occur in the absence of NPIs, in both the summer and winter of 2021, failed to
materialise 111See “SPI-M-O: Consensus Statement on COVID-19”, from 15
December 2021, for the advice given to the UK government before the expected
Omicron wave:
https://assets.publishing.service.gov.uk/government/uploads/system/uploads/attachment_data/file/1042204/S1439_SPI-
M-O_Consensus_Statement.pdf.

While these models can take account of many details of how the specific
disease spreads, they usually make the assumption of ‘random mixing’: that any
individual can infect any other [8]. However, people are in fact connected
according to a social network [9]. It has been known for decades that network
topology has important effects on spreading processes [10, 9, 11, 12, 8, 13,
14], but in practice it is difficult to gather data on this web of contacts.
Moreover, accounting for the network explicitly with agent-based modelling may
be computationally prohibitive at the scale of, say, a whole country. Hence,
random mixing – albeit with a degree of structure captured by the inclusion of
different groups of people – remains the standard assumption [15].

Social networks of various kinds have been found to be highly heterogeneous,
in that the degree, $k$, of vertices (i.e. the number of contacts of each
person) follows a distribution with a high variance [16, 17]. Scale-free
networks – in which this distribution is a power law, $p(k)\sim k^{-\alpha}$,
with $\alpha$ usually between 2 and 3 – are an extreme example of this. For
instance, a network of sexual contacts was observed to follow this rule with
$\alpha\simeq 2.4$ [18]. And while we don’t have detailed information on the
network of contacts underlying the spread of respiratory viruses, we do know
that, in the early stages of an epidemic, COVID-19 is driven largely by
‘super-spreading events’ (SSEs) [19], with one estimate suggesting that fewer
than $10\%$ of infectious individuals accounted for $80\%$ of infections [20].
The importance of SSEs was also shown in the case of SARS [21]. Moreover,
Fukui and Furukawa [22] found the distribution of these SSEs – that is, the
number of individuals infected on each occasion – followed power laws in the
cases of SARS, MERS and COVID-19. This suggests that the underlying networks
have highly heterogeneous degree distributions, which would be consistent with
other studies of social networks [16, 17, 18].

Figure 1:  Time series for the proportions of agents in the Infectious (panel
A) and Recovered (B) states, from the SIR model described in the main text, in
three scenarios: Erdős-Rényi (ER) random graphs and probability of infection
$\beta=0.48$ (dark blue circles); scale-free (SF) networks with exponent
$\alpha=2.5$ and $\beta=0.48$ (light blue triangles); and SF networks with
$\alpha=2.5$ and $\beta=0.12$ (red diamonds). Number of vertices $N=10^{4}$,
mean degree $\langle k\rangle=5$, averages over $100$ networks in each case,
bars represent one standard deviation. At time $t=0$ all agents are
Susceptible, except for 150 randomly chosen agents set to Infectious, for the
SF network with $\beta=0.12$; or 50 randomly chosen agents for the other two
cases (the discrepancy is to showcase the overlapping curves better). Lines
(splines) are a guide for the eye.

This letter uses an agent-based version of an SIR model to illustrate how the
random-mixing assumption can lead to very large errors in the total number of
people predicted to become infected, in a given epidemic ‘wave’, if the
network is scale free. This is not just because, for a given basic
reproduction number, $R_{0}$, the ‘herd immunity threshold’ (HIT) is generally
lower on a scale-free network; but, more significantly, because the initial
rapid growth in infections in the scale-free case can lead to an
overestimation of $R_{0}$. As we shall see, the combination of these two
effects can produce a random-mixing forecast of over $80\%$ of the population
becoming infected, when in fact only $20\%$ are affected before the epidemic
dies down naturally.

Conversely, once an epidemic has reached herd immunity, the random-mixing
assumption predicts that the population is safe from further waves unless
immunity wanes. However, if the networks are scale free and change in time,
multiple waves can occur even as individual immunity is maintained.

The COVID-19 pandemic involved multiple waves of infection in countries with
quite different levels of stringency in their NPIs. This seems more compatible
with a process taking place on time-varying, heterogeneous networks than with
the predictions of random-mixing models.

##  II The effect of the network

Consider a network in which each vertex represents an agent, and edges are
contacts which potentially allow for contagion of a transmissible disease. We
will compare here two different topologies: Erdős-Rényi (ER) networks, in
which the edges are placed entirely at random among the vertices [23]; and
scale-free (SF) networks. The latter are constructed by drawing desired
degrees from a distribution $p(k)\sim k^{-\alpha}$, and using the
‘configuration model’ to place the edges [9]. A ‘structural cut off’ is
imposed, such that $k<\sqrt{\langle k\rangle N}$, where $\langle k\rangle$ is
the mean degree and $N$ the number of vertices. For the parameters used here –
$\langle k\rangle=5$ and $N=10^{4}$ – the maximum degree in the SF case is
therefore 233. This is not unrealistically high for COVID-19 contact networks
since some SSEs saw over 100 people apparently infected by a single individual
within a few hours. In both cases we will consider undirected networks for
simplicity, although directionality has been found to have an important
influence on spreading processes [24]. The random-mixing assumption is a good
mean-field description of the Erdős-Rényi case. However, as discussed, the
scale-free network may be a better model for a real web of social contacts.

Figure 2:  Proportion of agents ever infected, $\rho$, against probability of
infection, $\beta$, for SF networks with $\alpha=2$ (dark blue circles) and
$\alpha=3$ (light blue triangles), and for ER random graphs (red diamonds)
(Panel A). Estimated value of basic reproduction number, $R_{0}^{e}$, from Eq.
(4) against $\beta$ on the same networks (B). Proportion infected, $\rho$,
against SF exponent $\alpha$ for infection probability $\beta=0.6$ (dark blue
circles), $\beta=0.3$ (light blue triangles) and $\beta=0.1$ (red diamonds)
(C). And $R_{0}^{e}$ against $\alpha$ for the same values of $\beta$ (D). All
agents are initially Susceptible except for 50 randomly chosen to be set to
Infectious. All other parameters as in Fig. 1.

The epidemic is described by the following model. Every agent $v_{i}$ has a
state $z_{i}(t)$ at discrete time $t$, which can take one of three values:
$S$, $I$ or $R$ (Susceptible, Infectious or Recovered). If there is an edge
from $v_{i}$ to $v_{j}$, and if $z_{i}(t)=I$ and $z_{j}(t)=S$, then with
probability $\beta$ we set $z_{j}(t+1)=I$ (i.e. $v_{j}$ is infected by
$v_{i}$). If $z_{i}(t)=I$, then $z_{i}(t+\tau)=R$, for all $\tau\geq 1$ (i.e.
every agent recovers after one time step, and thereafter cannot change state,
as though either immune or deceased). Agents are updated in parallel at every
time step.

This is a very simple version of an SIR model, with no allowance made for
heterogeneity in transmission times, infectiousness or other features, nor for
different categories of agents, such as asymptomatic individuals, children,
etc. Moreover, parallel updating is not always a good approximation for a
continuous-time process [25], which would be simulated more realistically with
a Gillespie algorithm [26]. The purpose of this model here is merely to
highlight how knowledge of the network is crucial even in the simplest of
settings.

Figure 3:  Proportion of agents ever infected, $\rho$, against estimated basic
reproduction number, $R_{0}^{e}$, from Eq. (4) for SF networks with exponent
$\alpha=2$ (dark blue circles) and $\alpha=3$ (light blue triangles), and for
ER random graphs (red diamonds). Different values for the same network
correspond to the different values of $\beta$ used in Fig. 2 A and B. All
other parameters as in Fig. 2.

Consider the situation where initially all agents are Susceptible except for
one randomly chosen agent, which is made Infectious at time $t=0$. If the mean
degree of the network is $\langle k\rangle$, at $t=1$ the expected number of
Infectious agents will be $\langle k\rangle\beta$, so the basic reproduction
number will be

$R_{0}=\langle k\rangle\beta.$ (1)

The expected mean degree of the newly Infectious agents, however, is not
$\langle k\rangle$, but $\langle k^{2}\rangle/\langle k\rangle$, where
$\langle k^{2}\rangle$ is the second moment of the degree distribution. (This
is an instance of the ‘friendship paradox’: your friends have more friends
than you [27]). So, taking into account that one of the contacts was the
originally Infectious vertex, the effective reproduction number, $R_{t}$, at
the next time step ($t=1$) is

$R_{1}=\left(\frac{\langle k^{2}\rangle}{\langle
k\rangle}-1\right)\beta=\left(\frac{\sigma^{2}}{\langle k\rangle}+\langle
k\rangle-1\right)\beta,$ (2)

where $\sigma^{2}$ is the variance of the degree distribution, $p(k)$. If the
network is an Erdős-Rényi random graph, this is a Poisson distribution, so
$\sigma^{2}=\langle k\rangle$ and $R_{1}=R_{0}$. However, if degrees are
distributed more heterogeneously, as in a scale-free network, then
$R_{1}>R_{0}$ [9]. In other words, the epidemic accelerates as it reaches more
highly connected vertices (hubs).

On the other hand, the epidemic plays the role of a targeted attack on the
network: by infecting the hubs early on, it removes edges more rapidly in a
more heterogeneous network than in a homogeneous one, with the result that in
the heterogeneous case fewer vertices may end up becoming Infectious before
the epidemic peters out. This is an instance of a more general effect whereby
if susceptibility and infectiousness are both heterogeneously distributed and
positively correlated in a population, the ‘herd immunity threshold’ (HIT)
(i.e. the proportion of infected people when $R_{t}$ drops below one) is lower
than we would expect from the standard equation HIT$=1-1/R_{0}$, which follows
from the assumption of random mixing [28].

Figure 1 shows averages over time series for the proportion of the agents
which are Infectious (panel A) or Recovered (B), for three different
scenarios. The dark blue circles correspond to Erdős-Rényi random graphs with
$\langle k\rangle=5$. The infection probability is $\beta=0.48$ so, according
to Eq. (1), $R_{0}=2.4$. Eventually about $88\%$ of agents become infected.
This is fairly close to the prediction of $81\%$ for COVID-19 infections in
the UK and the US made in March 2020 by the group led by Prof. Neil Ferguson
[4], despite the much greater sophistication of their model, for the case in
which no NPIs were introduced and based on an estimate of $R_{0}=2.4$.

The light blue triangles in Fig. 1 are for the same parameter values ($\langle
k\rangle=5$ and $\beta=0.48$) but now the networks are scale free, with an
exponent $\alpha=2.5$. The curve now grows significantly faster and peaks at a
higher value, yet also falls more quickly, going on eventually to infect a
slightly smaller proportion of the population ($72\%$) than in the ER case.

The red diamonds also correspond to SF networks with $\alpha=2.5$, but now
$\beta=0.12$. In this case, the curve initially follows a very similar
trajectory to the ER network with $\beta=0.48$; but it peaks earlier at a
lower value, and goes on to infect only $20\%$ of the population.

This example serves to illustrate how two different scenarios – high
transmissibility on a homogeneous network, and low transmissibility on a
heterogeneous one – can initially follow very similar epidemic curves, yet go
on to have markedly different outcomes.

##  III Mismeasuring $R_{0}$

In practice, it is not usually possible to obtain the value of $R_{0}$ from
contact tracing. Rather, scientists estimate this number from the rate at
which infections grow in the early stages of the epidemic, together with
assumptions about the incubation period and duration of infectiousness [4,
29]. For instance, if one assumes that each Infectious individual infects
$R_{0}$ others after a period $\tau$, and the number of Recovered is low
enough that one can assume exponential growth, then the number of Infectious
individuals at time $t$ is

$I(t)=I(0)R_{0}^{t/\tau}.$ (3)

Imagine a group of scientists living in a scale-free world who observed an
epidemic growing, in its early stages, as the red diamonds of Fig. 1. If they
assumed random mixing and estimated $R_{0}$ from Eq. (3), they would find that
$R_{0}\simeq 2.4$. Their model, even if quite sophisticated in other ways, may
well then predict that the epidemic would evolve similarly to the dark blue
circles. Moreover, if NPIs were then imposed, and the curve went on to peak
earlier than forecast and well before the expected HIT, it would be natural to
assume that $R_{t}$ had fallen below one thanks to the NPIs. Only when an
epidemic were allowed to spread without added NPIs would it become apparent
that the model’s predictions were significantly wrong.

Figure 2 (A) shows the proportion of the population who have been infected
after the wave has passed, $\rho=\lim_{t\rightarrow\infty}R(t)$, against
$\beta$ for SF networks with $\alpha=2$ and $3$, and for ER networks. At low
$\beta$, the epidemic reaches more agents on the SF networks, since the
process does not percolate on ER networks for $\beta\langle k\rangle<1$.
However, for larger $\beta$ the epidemic reaches more agents on more
homogeneous networks (i.e. the HIT is lower on SF networks [22]).

Figure 2 (B) shows the ‘estimated $R_{0}$’, or $R_{0}^{e}$. Using Eq. (3) and
bearing in mind that in this model $\tau=1$, this is defined as

$R_{0}^{e}=\max_{t}\frac{I(t+1)}{I(t)}.$ (4)

In other words, $R_{0}^{e}$ is akin to the value of $R_{0}$ that a group of
scientists might estimate from observations of the doubling time in the early
stages of the epidemic. For ER networks, which are equivalent to random
mixing, $R_{0}^{e}$ will be very close to $R_{0}$, as given by Eq. (1)
($R_{0}^{e}\simeq\langle k\rangle\beta$). However, we shall see that, for SF
networks, $R_{0}^{e}$ can be significantly higher than this value
($R_{0}^{e}>\langle k\rangle\beta$). Thus, estimates of the transmissibility
of a disease based on changes in the number of cases can be wrong if the
underlying social network is heterogeneous.

Fig. 2 (C) shows again the eventual proportion of infected agents, but against
$\alpha$ for SF networks, and different values of $\beta$. As $\alpha$
decreases, $\beta$ has less of an effect on the reach of the epidemic –
suggesting that the intrinsic transmissibility of a disease is less
significant if the network is highly heterogeneous.

Fig. 2 (D) shows $R_{0}^{e}$ against $\alpha$ for SF networks. The estimated
reproduction number is always greater the more heterogeneous the network, and
in the $\beta=0.1$ case the value of $\alpha$ can even determine whether
$R_{0}^{e}$ is greater or less than one.

Another way of viewing these results is to plot $\rho$ against $R_{0}^{e}$, as
in Fig. 3. On the ER networks, $\rho$ is very sensitive to $R_{0}^{e}$, as in
random-mixing models. But as degree heterogeneity increases, this sensitivity
decreases. For example, on the SF networks with $\alpha=2$, there is a range
for which a doubling in $R_{0}^{e}$ leads to barely a $20\%$ increase in the
proportion infected. Hence, if the network is highly heterogeneous, the
estimated $R_{0}$ is very sensitive to $\beta$, yet the number of people who
will become infected is not. In other words, it becomes more important to gain
knowledge about the network than about the intrinsic transmissibility of the
disease.

Figure 4:  Time series for proportions of agents in the Infectious (panels A
and C) and Recovered (B and D) states for ER random graphs (blue circles) and
SF networks with exponent $\alpha=2.2$ (red diamonds). At time $t=0$ all
agents are Susceptible, except for 50 randomly chosen agents set to
Infectious. At times $t=15$ and $t=30$, the networks are replaced with new
ones, randomly generated with the same network parameters; and 50 randomly
chosen Susceptible agents are set to Infectious. Panels A and B:
Transmissibility is constant at $\beta=0.4$ in the ER case and $\beta=0.1$ in
the SF case. Panels C and D: Transmissibility is increased at times $t=15$ and
$t=30$. In the ER case, $\beta=0.4$ until $t=15$, $\beta=0.6$ until $t=30$,
and $\beta=1$ thereafter. In the SF case, $\beta=0.1$ until $t=15$,
$\beta=0.2$ until $t=30$, and $\beta=0.4$ thereafter. All other parameters as
in Fig. 1.

##  IV Multiple waves

Once an epidemic has petered out naturally, it is often assumed that herd
immunity must have been achieved, and the population is no longer vulnerable
unless immunity wanes or transmissibility increases significantly. However,
when the HIT is low thanks to the heterogeneity of the social network, a large
pool of susceptible individuals may still remain even after a first ‘wave’ of
infection. As long as the structure of the network is unchanged, the
population will indeed have herd immunity. But if this structure is altered
the population may become vulnerable to subsequent waves of infection.

Figure 4 compares time series for ER and SF networks, as in Figure 1, but now
at times $t=15$ and $t=30$ the network structure is replaced with a new one,
and the epidemic is re-seeded by switching a small number of Susceptible
agents to Infected (all Recovered agents remain Recovered). Figures 4 A and B
show the proportions of Infectious and Recovered agents, respectively. Once
the epidemic has died down in the ER case, replacing the network with a new
version and re-seeding the epidemic has virtually no effect, since there are
insufficient remaining Susceptible agents for a new wave to occur. However, in
the SF case, a new wave is seen every time the network is changed - albeit
with each wave being smaller than the last. In panels A and B the
transmissibility is constant ($\beta=0.4$ and $0.1$ for the ER and SF
networks, respectively). Figures 4 C and D, however, show time series for
which, in addition to the network structure being changed, the
transmissibility is increased to $\beta=0.6$ (at $t=15$) and $\beta=1$ (at
$t=30$) for the ER networks; and to $\beta=0.2$ (at $t=15$) and $\beta=0.4$
(at $t=30$) for the SF networks. In the ER case there are still no more waves
of infection. However, in the SF case there are now subsequent waves of
increasing size.

In real life, should we expect the social networks behind epidemics to change?
Certain connections may be quite stable, such as those between work
colleagues, while others are transitory, say among people who happen to be
attending the same event. The COVID-19 pandemic involved several waves of
infection, something variously attributed to more infectious variants of the
virus, changing NPIs or waning immunity. However, Figure 4 shows that an
underlying network which is both heterogeneous and time varying is enough to
produce several waves, even when previous ones died down naturally.

##  V Conclusion

While we may not have detailed information on the web of contacts underlying a
process such as a COVID-19 epidemic, we know that social networks of various
kinds have been found to be highly heterogeneous [9], and that super-spreading
events for this and similar diseases appear to be power-law distributed [22].
A heterogeneous topology, such as a scale-free network, may therefore be a
better null model than the assumption of random mixing.

The epidemic model used here is very simple and devoid of any realistic
parameters. But there is no obvious reason to believe that the greater
sophistication of the compartmental models often used to guide public health
policy would annul the effects reported here. In any case, perhaps this could
be explored by implementing versions of such models on networks. Another
caveat is that in this model recovered agents can never again become infected.
In reality, we know that diseases such as COVID-19 can re-infect, either
because of waning immunity or new variants. Multiple waves of infection are
thus often attributed to changing levels of individual immunity. However, we
have seen that a changing network structure, if heterogeneous, can also lead
to multiple waves even when individual immunity is maintained.

If these results do carry over to more realistic scenarios, then it is crucial
to gather data on the networks of contacts on which epidemics play out, and to
adapt existing compartmental models either to correct for network topology, or
to take it into account explicitly. It may be the case that estimating
$\langle k^{2}\rangle/\langle k\rangle$ in a social network is in fact easier
than inferring the mean degree, since methods such as respondent-driven
sampling suffer from a bias towards more highly connected individuals [30].
Further research is also needed to elucidate to what extent social networks
change in time and how this affects epidemics [31].

In any case, the effects reported here suggest that: a) each ‘wave’ of a
disease such as COVID-19 may infect fewer people than we would otherwise
assume, even in the absence of NPIs, thanks to network heterogeneity; b) if
networks are heterogeneous and change in time, this can lead to multiple waves
of infection that would not be predicted by random-mixing models; and c) NPIs
focused on avoiding super-spreading events are likely to be particularly
efficacious at suppressing the epidemic.

Other network properties – such as efficiency [32], assortativity [33],
directionality [34] or spatial aspects [35] – may also be as relevant as
degree heterogeneity. A well-defined community structure, in particular, can
have an important effect [36]. Ultimately, epidemics are yet another example
of how the architecture of complex systems is fundamental to their dynamical
behaviour [11, 12, 22].

###### Acknowledgements.

I am grateful for support from the Alan Turing Institute under EPSRC Grant
EP/N510129/1.

## References

  * Abou-Ismail [2020] A. Abou-Ismail, Compartmental models of the COVID-19 pandemic for physicians and physician-scientists, SN comprehensive clinical medicine 2, 852 (2020).
  * Gnanvi  _et al._ [2021] J. E. Gnanvi, K. V. Salako, G. B. Kotanmi, and R. G. Kakaï, On the reliability of predictions on COVID-19 dynamics: a systematic and critical review of modelling techniques, Infectious Disease Modelling 6, 258 (2021).
  * McCabe  _et al._ [2021] R. McCabe, M. D. Kont, N. Schmit, C. Whittaker, A. Løchen, M. Baguelin, E. Knock, L. K. Whittles, J. Lees, N. F. Brazeau, _et al._ , Modelling intensive care unit capacity under different epidemiological scenarios of the COVID-19 pandemic in three Western European countries, International Journal of Epidemiology 50, 753 (2021).
  * Ferguson  _et al._ [2020] N. M. Ferguson, D. Laydon, G. Nedjati-Gilani, N. Imai, K. Ainslie, M. Baguelin, S. Bhatia, A. Boonyasiri, Z. Cucunubá, G. Cuomo-Dannenburg, _et al._ , Impact of non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand, (2020).
  * Vardavas  _et al._ [2021] R. Vardavas, P. N. de Lima, and L. Baker, Modeling COVID-19 nonpharmaceutical interventions: Exploring periodic NPI strategies, medRxiv (2021).
  * Ioannidis  _et al._ [2020] J. P. Ioannidis, S. Cripps, and M. A. Tanner, Forecasting for COVID-19 has failed, International Journal of Forecasting (2020).
  * Note [1] See “SPI-M-O: Consensus Statement on COVID-19”, from 15 December 2021, for the advice given to the UK government before the expected Omicron wave: https://assets.publishing.service.gov.uk/government/uploads/system/uploads/attachment_data/file/1042204/S1439_SPI-M-O_Consensus_Statement.pdf.
  * Keeling and Eames [2005] M. J. Keeling and K. T. Eames, Networks and epidemic models, Journal of the Royal Society Interface 2, 295 (2005).
  * Newman [2003] M. E. J. Newman, The structure and function of complex networks, SIAM Review 45, 167 (2003).
  * Moore and Newman [2000] C. Moore and M. E. Newman, Epidemics and percolation in small-world networks, Physical Review E 61, 5678 (2000).
  * Pastor-Satorras and Vespignani [2001] R. Pastor-Satorras and A. Vespignani, Epidemic spreading in scale-free networks, Physical Review Letters 86, 3200 (2001).
  * Newman [2002] M. E. Newman, Spread of epidemic disease on networks, Physical Review E 66, 016128 (2002).
  * Morita [2016] S. Morita, Six susceptible-infected-susceptible models on scale-free networks, Scientific Reports 6, 1 (2016).
  * Moore and Rogers [2020] S. Moore and T. Rogers, Predicting the speed of epidemics spreading in networks, Physical Review Letters 124, 068301 (2020).
  * Keeling  _et al._ [2020] M. J. Keeling, L. Dyson, G. Guyver-Fletcher, A. Holmes, M. G. Semple, I. Investigators, M. J. Tildesley, and E. M. Hill, Fitting to the uk COVID-19 outbreak, short-term forecasts and estimating the reproductive number, Statistical Methods in Medical Research , 09622802211070257 (2020).
  * Newman  _et al._ [2002] M. E. Newman, D. J. Watts, and S. H. Strogatz, Random graph models of social networks, Proceedings of the National Academy of Sciences 99, 2566 (2002).
  * Jackson and Rogers [2007] M. O. Jackson and B. W. Rogers, Meeting strangers and friends of friends: How random are social networks?, American Economic Review 97, 890 (2007).
  * Liljeros  _et al._ [2001] F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. Åberg, The web of human sexual contacts, Nature 411, 907 (2001).
  * Lewis [2021] D. Lewis, Superspreading drives the COVID pandemic-and could help to tame it., Nature , 544 (2021).
  * Endo  _et al._ [2020] A. Endo _et al._ , Estimating the overdispersion in COVID-19 transmission using outbreak sizes outside china, Wellcome open research 5 (2020).
  * Riley  _et al._ [2003] S. Riley, C. Fraser, C. A. Donnelly, A. C. Ghani, L. J. Abu-Raddad, A. J. Hedley, G. M. Leung, L.-M. Ho, T.-H. Lam, T. Q. Thach, _et al._ , Transmission dynamics of the etiological agent of SARS in Hong Kong: impact of public health interventions, Science 300, 1961 (2003).
  * Fukui and Furukawa [2020] M. Fukui and C. Furukawa, Power laws in superspreading events: Evidence from coronavirus outbreaks and implications for sir models, MedRxiv (2020).
  * Erdős and Rényi [1959] P. Erdős and A. Rényi, On random graphs. I, Publicationes Mathematicae 6, 290 (1959).
  * Klaise and Johnson [2016] J. Klaise and S. Johnson, From neurons to epidemics: How trophic coherence affects spreading processes, Chaos 26 (2016).
  * Fennell  _et al._ [2016] P. G. Fennell, S. Melnik, and J. P. Gleeson, Limitations of discrete-time approaches to continuous-time contagion dynamics, Physical Review E 94, 052125 (2016).
  * Cota and Ferreira [2017] W. Cota and S. C. Ferreira, Optimized Gillespie algorithms for the simulation of markovian epidemic processes on large and heterogeneous networks, Computer Physics Communications 219, 303 (2017).
  * Jackson [2019] M. O. Jackson, The friendship paradox and systematic biases in perceptions and social norms, Journal of Political Economy 127, 777 (2019).
  * Gomes  _et al._ [2022] M. G. M. Gomes, M. U. Ferreira, R. M. Corder, J. G. King, C. Souto-Maior, C. Penha-Gonçalves, G. Gonçalves, M. Chikina, W. Pegden, and R. Aguas, Individual variation in susceptibility or exposure to SARS-CoV-2 lowers the herd immunity threshold, Journal of theoretical biology 540, 111063 (2022).
  * Anderson  _et al._ [2020] R. Anderson, C. Donnelly, D. Hollingsworth, M. Keeling, C. Vegvari, R. Baggaley, and R. Maddren, Reproduction number (R) and growth rate (r) of the COVID-19 epidemic in the UK: methods of estimation, data sources, causes of heterogeneity, and use as a guide in policy formulation, The Royal Society 2020 (2020).
  * Mills  _et al._ [2014] H. L. Mills, S. Johnson, M. Hickman, N. S. Jones, and C. Colijn, Errors in reported degrees and respondent driven sampling: Implications for bias, Drug and alcohol dependence 142, 120 (2014).
  * Karsai  _et al._ [2014] M. Karsai, N. Perra, and A. Vespignani, Time varying networks and the weakness of strong ties, Scientific Reports 4, 1 (2014).
  * Latora and Marchiori [2001] V. Latora and M. Marchiori, Efficient behavior of small-world networks, Physical Review Letters 87, 198701 (2001).
  * Johnson  _et al._ [2010] S. Johnson, J. J. Torres, J. Marro, and M. A. Muñoz, Entropic origin of disassortativity in complex networks, Physical Review Letters 104, 108702 (2010).
  * Johnson [2020] S. Johnson, Digraphs are different: Why directionality matters in complex systems, Journal of Physics: Complexity 1, 015003 (2020).
  * Barthélemy [2011] M. Barthélemy, Spatial networks, Physics Reports 499, 1 (2011).
  * Lieberthal  _et al._ [2023] B. Lieberthal, A. Soliman, S. Wang, S. De Urioste-Stone, and A. M. Gardner, Epidemic spread on patch networks with community structure, Mathematical Biosciences 359, 108996 (2023).