# Modularity of very dense graphs

Colin McDiarmid, Fiona Skerman

###### Abstract

It is known that complete graphs and complete bipartite graphs have modularity
zero. We show that the least number of edges we may delete from the complete
graph $K_{n}$ to obtain a graph with non-zero modularity is $\lfloor
n/2\rfloor+1$. Similarly we determine the least number of edges we may delete
from or add to a complete bipartite graph to reach non-zero modularity.

We also analyse the modularity of very dense random graphs, and in particular
we find that there is a transition to modularity zero when the average degree
of the complementary graph drops below 1.

##  1 Introduction

The modularity $q^{*}(G)$ of a graph $G$ was introduced by Newman and Girvan
in 2004 [17], to give a measure of how well $G$ can be divided into
‘communities’, and now is at the heart of the most popular algorithms used to
cluster real data [7]. See Section 1.1 below for precise definitions and
further discussion.

We are interested here in the modularity of very dense graphs, complete
bipartite graphs, and very dense random graphs. We saw in [13] that for
suitable random graphs $R_{n}$, if the average degree of $R_{n}$ tends to
$\infty$ as $n\to\infty$ then $q^{*}(R_{n})\to 0$ in probability – details are
given below. But when is $q^{*}(R_{n})>0$ whp and when is it actually 0 whp? A
key step in understanding this is deterministic.

It is known [3] and easy to see that complete graphs have modularity 0.
(Complete multipartite graphs also have modularity 0, see [11, 2].) Graphs
which are close to a complete graph in that there are very few missing edges
also have modularity 0. We give the precise threshold in Theorem 1.1 below.

Each graph $G$ with at most 3 vertices has modularity $q^{*}(G)=0$. (By
convention a graph $G$ with no edges has $q^{*}(G)=0$.) The 4-vertex path has
modularity $\frac{1}{6}$, and the 4-vertex graph consisting of two disjoint
edges has modularity $\frac{1}{2}$; and indeed for each $n\geq 4$ there is an
$n$-vertex graph $G$ with $q^{*}(G)>0$. Given an integer $n\geq 4$, let $f(n)$
be the least number of edges missing from any $n$-vertex graph $G$ with
$q^{*}(G)>0$.

######  Theorem 1.1.

For each $n\geq 4$ we have $f(n)=\lfloor n/2\rfloor+1$.

This corrects [20], which in the notation here says that $f(n)\geq n-2$. Given
a graph $H$, let $\delta^{-}(H)$ be the least number of edges we can delete to
obtain a subgraph $H^{\prime}$ with $q^{*}(H^{\prime})>0$. If there is no
subgraph $H^{\prime}$ with $q^{*}(H^{\prime})>0$ we set
$\delta^{-}(H)=\infty$. (The only graph with $m\geq 4$ edges with this
property is the $m$-edge star $K_{1,m}$. This can be seen by noting that
$\delta^{-}(H)$ is finite as soon as $H$ contains two disjoint edges.) Thus
Theorem 1.1 says that $\delta^{-}(K_{n})=\lfloor n/2\rfloor+1$ for $n\geq 4$,
so large complete graphs have modularity 0 ‘robustly’.

We noted above that any complete multipartite graph $H$ has modularity 0, but
here there is no robustness. We focus on complete bipartite graphs, where we
can tell the complete story reasonably quickly: we find that, except for a few
small examples, it is enough to add or remove a single edge to obtain a graph
with positive modularity. (See Section 2.4 for some corresponding partial
results for complete multipartite graphs.)

To state the results let us define natural counterparts to $\delta^{-}$: given
a graph $H$, let $\delta^{+}(H)$ be the least number of edges we can _add_
(between already existing vertices) to obtain a graph $H^{\prime}$ with
$q^{*}(H^{\prime})>0$ (where $\delta^{+}(H)=\infty$ if there is no such graph
$H^{\prime}$). Likewise let $\delta(H)$ be the minimum number of edits, either
adding or removing edges, to obtain a graph $H^{\prime}$ with positive
modularity (where $\delta(H)=\infty$ if there is no such graph $H^{\prime}$,
that is if $v(H)\leq 3$).

######  Theorem 1.2.

Let $G=K_{s,t}$ be a complete bipartite graph with $s\leq t$.

(a) If $s=1$ then $\delta^{-}(G)=\infty$, and if $s\geq 2$ then
$\delta^{-}(G)=1$.

(b) If $s=1$ and $t\geq 4$, or if $s\geq 2$ and $t\geq 3$, then
$\delta^{+}(G)=1$. In the other cases (namely when $(s,t)=(1,1),(1,2),(1,3)$
or $(2,2)$), we have $\delta^{+}(G)=\infty$.

(c) If $s=1$ and $t\geq 4$, or if $s\geq 2$, then $\delta(G)=1$. If
$(s,t)=(1,1)$ or $(1,2)$ then $\delta(G)=\infty$, and in the remaining case
$(s,t)=(1,3)$ we have $\delta(G)=2$.

Theorems 1.1 and 1.2 suggest that complete graphs $K_{n}$ may be the
‘furthest’ from graphs with positive modularity.

######  Question 1.3.

Is it true that, for each graph $H$ with $n\geq 4$ vertices we have
$\delta(H)\leq\delta(K_{n})$?

One may note the following from Theorem 1.1 and its proof. Let $n\geq 4$ and
let $G$ be any graph obtained from $K_{n}$ by deleting the edges of a
bipartite graph with $k\leq n/2$ edges: then $\delta(G)=\delta^{-}(G)=\lfloor
n/2\rfloor+1-k$.

Now consider random graphs. The modularity of random graphs $G_{n,p}$ and
$G_{n,m}$ (see Section 1.1 below for definitions) is quite fully analysed in
[13], except for the very dense case. By Theorem 1.3 of [13], when $p=p(n)$
satisfies $p\geq 1/n$ and $p$ is bounded away from 1, we have
$q^{*}(G_{n,p})=\Theta((np)^{-1/2})$ whp; and by Theorem 4.1 of the same
paper, when $1/n\leq p\leq 1-c_{0}/n$ for a suitable (large) constant $c_{0}$
we have $q^{*}(G_{n,p})=\Omega(\sqrt{\frac{1-p}{np}})$ whp. We focus here on
the very dense case, when $p=1-\Theta(1/n)$. Note that in this case
$\sqrt{\frac{1-p}{np}}=\Theta(1/n)$. It follows easily from Theorem 1.1 that
when $1-p$ is very small (say $1-p\leq(1-\varepsilon)/n$) then whp
$q^{*}(G_{n,p})=0$. We shall see that when $1-p$ is just a little larger (say
$1-p=(1+\varepsilon)/n$) we have whp $q^{*}(G_{n,p})=\Theta(1/n)$.

######  Theorem 1.4.

(a) If $p=p(n)$ satisfies $p\geq 1-1/n+\omega(n)/n^{3/2}$ (where
$\omega(n)\to\infty$ as $n\to\infty$) then $q^{*}(G_{n,p})=0$ whp.

(b) Given $1<c_{1}<c_{2}$, there exist $0<\alpha<\beta$ such that, if $p$
satisfies $1-c_{2}/n\leq p\leq 1-c_{1}/n$ then $\alpha/n\leq
q^{*}(G_{n,p})\leq\beta/n$ whp.

Part (b) of Theorem 1.4 allows us to extend the range of $p$ in Theorem 4.1 of
[13] up to nearly $1-1/n$ (and part (a) shows that we cannot go much further).
Using Theorem 4.1 of [13] for the lower parts of the range we obtain the
following result.

######  Theorem 1.5.

Given $\varepsilon>0$ there exists $\alpha>0$ such that if $p=p(n)$ satisfies
$1/n\leq p\leq 1-(1+\varepsilon)/n$ then
$q^{*}(G_{n,p})\geq\alpha\sqrt{\frac{1-p}{np}}$ whp.

Now consider the random $m$-edge graph $G_{n,m}$. It follows immediately from
Theorem 1.1 that $q^{*}(G_{n,m})=0$ when $m\geq\binom{n}{2}-n/2$. Thus the
natural corresponding $G_{n,m}$ version of Theorem 1.4 omits part (a).

######  Theorem 1.6.

Given $1<c_{1}<c_{2}$, there exist $0<\alpha<\beta$ such that, if $m=m(n)$
satisfies $\binom{n}{2}-c_{2}\,n/2\leq m\leq\binom{n}{2}-c_{1}\,n/2\,$ then
$\,\alpha/n\leq q^{*}(G_{n,m})\leq\beta/n$ whp.

###  1.1 Definitions and preliminaries

Given a non-empty graph $G$ (with at least one edge), we give a modularity
score to each vertex partition (or ‘clustering’) : the modularity $q^{*}(G)$
(sometimes called the ‘maximum modularity’) of $G$ is defined to be the
maximum of these scores over all vertex partitions. For a set $A$ of vertices,
let the _volume_ ${\rm vol}(A)$ or ${\rm vol}_{G}(A)$ be the sum over the
vertices $v$ in $A$ of the degree $d_{v}$, also let $e(A)$ or $e_{G}(A)$
denote the number of edges within $A$, and for $B$ disjoint from $A$ let
$e(A,B)$ or $e_{G}(A,B)$ denote the number of edges between $A$ and $B$.

######  Definition 1.1 (Newman & Girvan [17], see also Newman [16]).

Let $G$ be a graph with $m\geq 1$ edges. For a partition ${\mathcal{A}}$ of
the vertices of $G$, the modularity score of ${\mathcal{A}}$ on $G$ is

$q_{\mathcal{A}}(G)=\frac{1}{2m}\sum_{A\in{\mathcal{A}}}\sum_{u,v\in
A}\left({\mathbf{1}}_{uv\in
E}-\frac{d_{u}d_{v}}{2m}\right)=\frac{1}{m}\sum_{A\in{\mathcal{A}}}e(A)-\frac{1}{4m^{2}}\sum_{A\in{\mathcal{A}}}{\rm
vol}(A)^{2};$

and the modularity of $G$ is
$q^{*}(G)=\max_{\mathcal{A}}q_{{\mathcal{A}}}(G)$, where the maximum is over
all vertex partitions ${\mathcal{A}}$ of $G$.

Isolated vertices are irrelevant. We need to give empty graphs (with no edges)
some modularity value: conventionally we set $q^{*}(G)=0$ for each such graph
$G$, and we set $q_{\mathcal{A}}(G)=0$ for every partition ${\mathcal{A}}$ on
$V(G)$. The second equation for $q_{{\mathcal{A}}}(G)$ expresses modularity as
the difference of two terms, the _edge contribution_ or _coverage_
$q^{E}_{\mathcal{A}}(G)=\tfrac{1}{m}\sum_{A}e(A)$, and the _degree tax_
$q^{D}_{\mathcal{A}}(G)=\tfrac{1}{4m^{2}}\sum_{A}{\rm vol}(A)^{2}$. Since
$q^{E}_{{\mathcal{A}}}(G)\leq 1$ and $q^{D}_{{\mathcal{A}}}(G)>0$, we have
$q_{{\mathcal{A}}}(G)<1$ for any graph $G$. Also, the trivial partition
${\mathcal{A}}_{0}$ with all vertices in one part has
$q^{E}_{{\mathcal{A}}_{0}}(G)=q^{D}_{{\mathcal{A}}_{0}}(G)=1$, so
$q_{{\mathcal{A}}_{0}}(G)=0$. Thus we have

$0\leq q^{*}(G)<1.$

Suppose that we pick uniformly at random a multigraph (where multiple edges
and loops are allowed) with degree sequence $(d_{1},\ldots,d_{n})$ where
$\sum_{v}d_{v}=2m$. Then the expected number of edges between distinct
vertices $u$ and $v$ is $d_{u}d_{v}/(2m-1)$. This is the original rationale
for the definition: whilst rewarding the partition for capturing edges within
the parts, we should penalise by (approximately) the expected number of such
edges.

_Random graphs_

Let $n$ be a positive integer. Given $0\leq p\leq 1$, the (binomial) random
graph $G_{n,p}$ has vertex set $[n]:=\\{1,\ldots,n\\}$ and the $\binom{n}{2}$
possible edges appear independently with probability $p$. Given an integer $m$
with $0\leq m\leq\binom{n}{2}$, the (Erdős-Rényi) random graph $G_{n,m}$ is
sampled uniformly from the $m$-edge graphs on vertex set $[n]$. These two
random graphs are closely related when $m\approx\binom{n}{2}p$, see for
example [6, 10].

For a sequence of events $A_{n}$ we say that $A_{n}$ holds _with high
probability (whp)_ if ${\mathbb{P}}(A_{n})\to 1$ as $n\to\infty$. For a
sequence of random variables $X_{n}$ and a real number $a$, we write
$X_{n}\overset{p}{\rightarrow}a$ if $X_{n}$ converges in probability to $a$ as
$n\to\infty$ (that is, if for each $\varepsilon>0$ we have
$|X_{n}-a|<\varepsilon$ whp). For $x=x(n)$ and $y=y(n)$ we write $x\sim y$ to
indicate that $\,x=(1+o(1))y\,$ as $n\to\infty$.

_More on modularity_

Let $G=(V,E)$ be a nonempty graph, and let $\nu={\rm vol}(G)$. For $U\subseteq
V$, let $p_{G}(U)=2e(U)\nu-{\rm vol}(U)^{2}$. If ${\mathcal{A}}$ is a
partition of $V(G)$, then
$q_{{\mathcal{A}}}(G)=\nu^{-2}\sum_{A\in{\mathcal{A}}}p_{G}(A)$. Since ${\rm
vol}(U)=2e(U)+e(U,\bar{U})$ (where $\bar{U}$ denotes $V\backslash U$), we have

$\displaystyle p_{G}(U)$ $\displaystyle=$ $\displaystyle 2e(U)\nu-{\rm
vol}(U)^{2}=({\rm vol}(U)-e(U,\bar{U}))\nu-{\rm vol}(U)(\nu-{\rm
vol}(\bar{U}))$ $\displaystyle=$ $\displaystyle-e(U,\bar{U})\nu+{\rm
vol}(U){\rm vol}(\bar{U}).$

Thus we may also write $p_{G}(U)$ as ${\rm vol}(U){\rm
vol}(\bar{U})-e(U,\bar{U})\nu$; and this expression for $p_{G}(U)$ is
symmetric in $U$ and $\bar{U}$, so $p_{G}(U)=p_{G}(\bar{U})$. Now, if
${\mathcal{A}}$ is a bipartition with parts $U$ and $\bar{U}$, then

$q_{{\mathcal{A}}}(G)=\nu^{-2}(p_{G}(U)+p_{G}(\bar{U}))=2\nu^{-2}p_{G}(U).$

Thus there is a bipartition ${\mathcal{A}}$ with $q_{{\mathcal{A}}}(G)>0$ iff
there is a set $U$ of vertices with $p_{G}(U)>0$, iff $q^{*}(G)>0$. We have
thus shown the following result which we record as a lemma.

######  Lemma 1.7.

Let $G$ be a graph with at least one edge. Then the following are equivalent :
(i) $q^{*}(G)=0$, (ii) $q_{\mathcal{A}}(G)\leq 0$ for each bipartition
${\mathcal{A}}$ of $V(G)$, and (iii) $p_{G}(U)\leq 0$ for each $U\subset
V(G)$.

Here, we recall the very nice result of Dinh and Thai [5], that for any $k$
there is a partition ${\mathcal{A}}$ with at most $k$ parts such that
$q_{\mathcal{A}}(G)\geq q^{*}(G)\,(1-1/k)$. Note that this implies the
equivalence of (i) and (ii) in the lemma (that is, $q^{*}(G)>0$ if and only if
there is a bipartition ${\mathcal{A}}$ with $q_{\mathcal{A}}(G)>0$).

_Robustness_

We shall use the following ‘robustness’ lemma from [13]. Since we set
$q^{*}(G)=0$ if $G$ has no edges, we can rephrase the lemma there as the
following.

######  Lemma 1.8.

If $G=(V,E)$ is a graph, $E_{0}$ is a non-empty subset of $E$, and
$G^{\prime}=(V,E\setminus E_{0})$, then

$|q^{*}(G)-q^{*}(G^{\prime})|<2\,|E_{0}|/|E|.$

_Previous results on extreme modularity values and modularity of random
graphs_

As discussed above the following graphs are known to have zero modularity:
complete graphs [3] and complete multipartite graphs [11, 2]. There are some
general lower bounds which can show strictly positive modularity : if we let
$\bar{d}$ denote the average degree of a graph, then connected graphs with
maximum degree $o(n)$ have modularity at least $2/\bar{d}-o(1)$ [18], and both
preferential attachment graphs [18] and deterministic graphs with mild
assumptions on the degree sequence [1] have modularity
$\Omega(\bar{d}^{-1/2})$.

At the other extreme, which graphs have modularity near 1? De Montgolfier,
Soto and Viennot [15] define a sequence of graphs to be maximally modular if
their modularity values tend to 1 as their number $m$ of edges tends to
infinity. The following are known to be maximally modular: trees with maximum
degree $o(m)$, graphs of bounded genus with maximum degree $o(m)$ [8], graphs
where treewidth times maximum degree is $o(m)$ [12], lattices [15, 19], whp
random graphs $G_{n,p}$ and $G_{n,m}$ with average degree at most $1+o(1)$
[13], whp random hyperbolic graphs [4] and whp spatial preferential attachment
graphs [18].

See also table in [13] for a summary of known modularity values; and note that
since then improved bounds for random regular graphs were obtained in [9] – in
particular the modularity of random cubic graphs was shown to lie in the
interval $[0.667,0.79]$ whp. Lastly, it is known that for any $n$-vertex base
graph $G$, letting $G_{p}$ be graph obtained by keeping each edge with
probability $p$ then $q^{*}(G_{p})\rightarrow q^{*}(G)$ in probability if
$e(G)p/n\rightarrow\infty$ as $n\to\infty$ [14].

##  2 Deterministic proofs and results

In this section we first prove Theorem 1.1 on $f(n)=\delta^{-}(K_{n})$. Then,
after a couple of preliminary lemmas, we determine $\delta^{-}(G)$ for all
complete bipartite graphs $G$ and then $\delta^{+}(G)$ and $\delta(G)$ for all
complete bipartite graphs $G$. Finally we give a couple of examples and
briefly consider multipartite graphs. (Recall that
$\delta^{+},\delta^{-},\delta$ are the minimum numbers of edges that may be
added, removed or edited to obtain a graph with positive modularity - see the
introduction for definitions.)

###  2.1 Nearly complete graphs: proof of Theorem 1.1

We first give a straightforward proof of the upper bound on
$f(n)\,(=\delta^{-}(K_{n})=\delta(K_{n})$) for $n\geq 4$.

We construct a graph $G$ on $n$ vertices with a bipartition
${\mathcal{A}}=(A,B)$ where $|A|=\lceil n/2\rceil$ and $|B|=\lfloor
n/2\rfloor$, as follows. Start with all edges present, let $F$ be the set of
edges between the parts, and let $k=\lfloor n/2\rfloor+1$. Note that if $n$ is
even then $|F|=n^{2}/4\geq n\geq k$, and if $n$ is odd then
$|F|=(n^{2}-1)/4\geq n-1/4\geq k$. Form $G$ by deleting any $k$ edges from
$F$, so $G$ has $m=\binom{n}{2}-k$ edges. We shall show that
$q_{\mathcal{A}}(G)>0$, considering separately the cases when $n$ is even,
odd.

Suppose first that $n$ is even, so $k=n/2+1$ and $m=\frac{1}{2}(n^{2}-2n-2)$.
Since $|A|=|B|$ and all edges are between $A$ and $B$ we have ${\rm
vol}(A)={\rm vol}(B)$ and thus $q^{D}_{{\mathcal{A}}}(G)=1/2$. Also

$q^{E}_{{\mathcal{A}}}(G)=\frac{2\binom{n/2}{2}}{m}=\frac{n(n-2)}{2(n^{2}-2n-2)}=\frac{1}{2}+\frac{1}{n^{2}-2n-2}.$

Hence $q_{\mathcal{A}}(G)>0$, as required.

Now suppose that $n$ is odd, so $k=(n+1)/2$ and $m=\frac{1}{2}(n^{2}-2n-1)$.
Then

$\displaystyle q^{E}_{{\mathcal{A}}}(G)$ $\displaystyle=$
$\displaystyle\frac{\binom{\lceil n/2\rceil}{2}+\binom{\lfloor
n/2\rfloor}{2}}{m}\;\;=\;\;\frac{(n\\!+\\!1)(n\\!-\\!1)+(n\\!-\\!1)(n\\!-\\!3)}{8m}\,,$

and we may check that the numerator is $4m+4$ so

$\displaystyle q^{E}_{{\mathcal{A}}}(G)\;\;\>=\;\;\frac{1}{2}+\frac{1}{2m}\,.$

Also ${\rm vol}(A)=\frac{1}{2}(n+1)(n-1)-k=\frac{1}{2}(n^{2}-n-2)$ and ${\rm
vol}(B)=\frac{1}{2}(n-1)^{2}-k=\frac{1}{2}(n^{2}-3n)$, so

$\displaystyle q^{D}_{{\mathcal{A}}}(G)$ $\displaystyle=$
$\displaystyle\frac{1}{4}\,\frac{(n^{2}-n-2)^{2}+(n^{2}-3n)^{2}}{4m^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{4}\,\frac{8m^{2}+4m+4}{4m^{2}}\;\;=\;\;\frac{1}{2}+\frac{m+1}{4m^{2}}\,.$

We have $q_{\mathcal{A}}(G)>0$ so long as
$q^{E}_{\mathcal{A}}(G)>q^{D}_{\mathcal{A}}(G)$, which by the above is
equivalent to $m>1$. But $n>3$ so $m=\frac{1}{2}(n^{2}-2n-1)>1$, and this
completes the proof of the upper bound.

Now let us prove the lower bound. We must show that if $n\geq 4$ and we form
$G$ by removing $x\leq n/2$ edges from $K_{n}$ then $q^{*}(G)=0$. Let us note
first one useful inequality. Let $G$ be a graph on vertex set $V$, let $U$ be
a proper subset of $V$, and form $G^{\prime}$ by ‘moving’ an edge currently
between $U$ and $\bar{U}$ to the location of a missing edge within $U$ or
$\bar{U}$. Then

$p_{G^{\prime}}(U)>p_{G}(U).$ (2.1)

(This is similar to the ‘local rewiring’ result of [20] [Lemma 1].) To prove
(2.1), note first that we may assume the edge is moved into $U$ (since
$p(U)=p(\bar{U})$). Now $e_{G^{\prime}}(U)-e_{G}(U)=1$ and

${\rm vol}_{G^{\prime}}(U)^{2}-{\rm vol}_{G}(U)^{2}=({\rm
vol}_{G}(U)+1)^{2}-{\rm vol}_{G}(U)^{2}=2{\rm vol}_{G}(U)+1,$

so

$\displaystyle p_{G^{\prime}}(U)-p_{G}(U)$ $\displaystyle=$ $\displaystyle
2{\rm vol}(G)(e_{G^{\prime}}(U)-e_{G}(U))-\left({\rm
vol}_{G^{\prime}}(U)^{2}-{\rm vol}_{G}(U)^{2}\right)$ $\displaystyle=$
$\displaystyle 2{\rm vol}(G)-2{\rm vol}_{G}(U)-1\;\geq\;1$

since ${\rm vol}_{G}(U)\leq{\rm vol}(G)-1$. This completes the proof of (2.1).

Now suppose that the graph $H$ on $V=[n]$ and $U\subset V$ are such that
$p_{H}(U)$ maximises the value $p_{G}(W)$ over all graphs $G$ on $V$ with at
most $n/2$ edges missing and all nonempty $W\subset V$. Since the number of
edges missing is at most $n/2<n-1$ there are edges of $H$ in $(U,\bar{U})$.
Hence by inequality (2.1), no edges within $U$ or within $\bar{U}$ are
missing.

Suppose that $|U|=j$ (where $1\leq j\leq n-1$) and $x$ edges are missing from
$H$. Then

$\displaystyle p_{H}(U)$ $\displaystyle=$ $\displaystyle{\rm vol}_{H}(U){\rm
vol}_{H}(\bar{U})-e_{H}(U,\bar{U}){\rm vol}(H)$ $\displaystyle=$
$\displaystyle(j(n-1)-x)((n-j)(n-1)-x)-(j(n-j)-x)(n(n-1)-2x)$ $\displaystyle=$
$\displaystyle-j(n-j)(n-1)+2xj(n-j)-x^{2}$ $\displaystyle=$ $\displaystyle
j(n-j)(2x-(n-1))-x^{2}.$

Hence $p_{H}(U)<0$ if $x\leq(n-1)/2$. Suppose that $x=n/2$. Then
$p_{H}(U)=j(n-j)-(n/2)^{2}$, so $p_{H}(U)<0$ if $j\neq n/2$, and $p_{H}(U)=0$
if $j=n/2$. This completes the proof of Theorem 1.1.

###  2.2 Local graph modifications

We shall use the following lemma in the proof of part (a) of Theorem 1.2. Note
that in the lemma below an edge between the parts is removed, whilst in (2.1)
an edge from between the parts is moved to within the parts.

######  Lemma 2.1.

Let $G$ be a graph and let ${\mathcal{A}}=\\{A,\bar{A}\\}$ be a bipartition
with non-negative modularity score for $G$ such that $e_{G}(A,\bar{A})\geq 1$.
Then for $G^{\prime}$ obtained by removing an edge between the parts we have
$q_{\mathcal{A}}(G^{\prime})>q_{\mathcal{A}}(G)$.

###### Proof.

Let $G$ have $m$ edges, and note that $m\geq 2$. The difference in the edge
contributions

$\displaystyle q^{E}_{\mathcal{A}}(G^{\prime})-q^{E}_{\mathcal{A}}(G)$
$\displaystyle=$
$\displaystyle\frac{1}{(m-1)m}\big{(}e_{G}(A)+e_{G}(\bar{A})\big{)}.$

Let $q={\rm vol}_{G}(A)-m=m-{\rm vol}_{G}(\bar{A})$. Since
$e_{G}(A,\bar{A})\geq 1$ each part has volume at least one and so
$1\leq|q|\leq m-1$. The difference in degree taxes is

$q^{D}_{\mathcal{A}}(G)-q^{D}_{\mathcal{A}}(G^{\prime})=\frac{(m\\!+\\!q)^{2}\\!+\\!(m\\!-\\!q)^{2}}{4m^{2}}-\frac{(m\\!+\\!q\\!-\\!1)^{2}+(m\\!-\\!q\\!-\\!1)^{2}}{4(m\\!-\\!1)^{2}}=\frac{m^{2}\\!+\\!q^{2}}{2m^{2}}-\frac{m^{2}\\!+\\!q^{2}\\!-\\!2m\\!+\\!1}{2(m\\!-\\!1)^{2}},$

which simplifies to $-q^{2}(2m-1)/(2(m-1)^{2}m^{2})$, and thus we have

$\displaystyle q_{\mathcal{A}}(G^{\prime})-q_{\mathcal{A}}(G)$
$\displaystyle=$
$\displaystyle\frac{1}{2(m-1)^{2}m^{2}}\bigg{(}2(m-1)m(e_{G}(A)+e_{G}(\bar{A}))-q^{2}(2m-1)\bigg{)}\,.$

But now $q_{\mathcal{A}}(G)\geq 0$ which implies
$2m(e_{G}(A)+e_{G}(\bar{A}))=2m^{2}q^{E}_{\mathcal{A}}(G)\geq
2m^{2}q^{D}_{\mathcal{A}}(G)=m^{2}+q^{2}$ and hence

$\displaystyle q_{\mathcal{A}}(G^{\prime})-q_{\mathcal{A}}(G)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2(m-1)^{2}m^{2}}\bigg{(}(m-1)(m^{2}+q^{2})-q^{2}(2m-1)\bigg{)}$
$\displaystyle=$
$\displaystyle\frac{1}{2(m-1)^{2}m^{2}}\bigg{(}m^{3}-m^{2}-q^{2}m\bigg{)}\,.$

Recalling that $1\leq|q|\leq m-1$, we have $m^{3}-m^{2}-q^{2}m\geq
m^{3}-m^{2}-m(m-1)^{2}=m^{2}-m$. Thus

$\displaystyle q_{\mathcal{A}}(G^{\prime})-q_{\mathcal{A}}(G)$
$\displaystyle\geq$ $\displaystyle\frac{1}{2(m-1)m}>0\,,$

as required. ∎

Given an $n$-vertex graph $G$, by adding $(\binom{n}{2}-\frac{n}{2}-e(G))^{+}$
edges we may form a graph $G_{0}$ with at most $\frac{n}{2}$ edges missing,
and then $q^{*}(G_{0})=0$ since $f(n)>n/2$ by Theorem 1.1. Hence, by Lemma 1.8
(the robustness lemma), we have the following result, which extends the bound
from Theorem 1.1 that $f(n)>n/2$. The notation $x^{+}$ means $\max\\{x,0\\}$.

######  Lemma 2.2.

For each $n\geq 2$ and each nonempty $n$-vertex graph $G$

$q^{*}(G)\leq\frac{2(\binom{n}{2}-\frac{n}{2}-e(G))^{+}}{e(G)}.$

We will use Lemma 2.2 to prove the upper bound in Theorem 1.4.

###  2.3 Nearly complete bipartite graphs: proof of Theorem 1.2

We commented earlier that any complete multipartite graph $G$ satisfies
$q^{*}(G)=0$, but there is no robustness result for complete multipartite
graphs corresponding to Theorem 1.1. In this section we prove the three parts
of Theorem 1.2 on $\delta^{-}(G)$, $\delta^{+}(G)$ and $\delta(G)$ for
complete bipartite graphs $G$, in Lemmas 2.3, 2.4 and 2.5. In Section 2.4 we
briefly consider complete multipartite graphs.

We start with $\delta^{-}$, and see in Lemma 2.3 that $\delta^{-}(G)=1$ for
all complete bipartite graphs $G$, with the exception of stars.

######  Lemma 2.3 (part (a) of Theorem 1.2).

Let $G=K_{s,t}$ be a complete bipartite graph with $s\leq t$. If $s=1$ then
$\delta^{-}(G)=\infty$; and if $s\geq 2$ then $\delta^{-}(G)=1$.

###### Proof.

Suppose first that $s=1$, so $G$ is the star $K_{1,t}$. As we delete edges we
get stars $K_{1,t^{\prime}}$ for $t^{\prime}<t$ (together with isolated
vertices) and eventually an empty graph. All these graphs have modularity zero
and hence $\delta^{-}(K_{1,t})=\infty$.

From now on let $s\geq 2$. We have seen that $q^{*}(K_{s,t})=0$, so we must
show that removing an edge from $K_{s,t}$ yields a graph with positive
modularity value. (Recall by Lemma 1.7 that $q^{*}(G)>0$ iff there is a
bipartition ${\mathcal{A}}$ with $q_{\mathcal{A}}(G)>0$, and hence
$q^{*}(K_{s,t})=0$ follows also from the claim on line (2.2) below.)

There are two cases. We first consider the case that $s$ and $t$ have a common
factor and show that in this case there is a bipartition
$\mathcal{A}=\\{A,\bar{A}\\}$ with $q_{\mathcal{A}}(K_{s,t})=0$ and
$e(A,\bar{A})\geq 1$. Thus by Lemma 2.1, for $K_{s,t}^{-}$ the graph obtained
from $K_{s,t}$ by removing an edge between parts $A$ and $\bar{A}$ we have
$q_{\mathcal{A}}(K_{s,t}^{-})>0$. After that we consider the case when $s$ and
$t$ are coprime which is only a little more complicated.

Before splitting into cases we give an expression for the modularity score of
$K_{s,t}$ for bipartitions which will be useful for both cases. Write $S$, $T$
for the two parts of the bipartite graph of sizes $s$, $t$ respectively, and
let $\sigma=|A\cap S|/s$ and $\tau=|A\cap T|/t$ be the proportions of the
vertex set $A$ in each of the bipartite parts. We _claim_ that for
${\mathcal{A}}=\\{A,\bar{A}\\}$

$q_{{\mathcal{A}}}(K_{s,t})=-\tfrac{1}{2}(\sigma-\tau)^{2}.$ (2.2)

_Proof of Claim._ The proof is by direct calculation. Note that

$e(A)=|A\cap S|\,|A\cap T|=\sigma\tau st,$

similarly, $e(\bar{A})=(1-\sigma)(1-\tau)st$, and thus

$q^{E}_{{\mathcal{A}}}(K_{s,t})=\sigma\tau+(1-\sigma)(1-\tau)=1-(\sigma+\tau)+2\sigma\tau.$
(2.3)

Also each vertex in part $S$ (resp. $T$) has degree $t$ (resp. $s$) and so

${\rm vol}(A)=|A\cap S|t+|A\cap T|s=(\sigma+\tau)st\,,$

which together with the corresponding expression for ${\rm vol}(\bar{A})$
yields

$q^{D}_{{\mathcal{A}}}(K_{s,t})=(\tfrac{1}{2}(\sigma+\tau))^{2}+(1-\tfrac{1}{2}(\sigma+\tau))^{2}=1-(\sigma+\tau)+\tfrac{1}{2}(\sigma+\tau)^{2}.$

Thus we have

$q_{{\mathcal{A}}}(K_{s,t})=2\sigma\tau-\tfrac{1}{2}(\sigma+\tau)^{2}=-\tfrac{1}{2}(\sigma-\tau)^{2}$

which completes the proof of the claim.

Case 1: $s$ and $t$ have a common factor.
Recall that by Lemma 2.1 it is sufficient to find a bipartition
${\mathcal{A}}=(A,\bar{A})$ such that $e(A,\bar{A})\geq 1$ and
$q_{\mathcal{A}}(K_{s,t})=0$. Let $\ell>1$ be a common factor of $s$ and $t$.
Then take $A$ to have $|S|/\ell$ vertices from $S$ and $|T|/\ell$ vertices
from $T$. Clearly $e(A,\bar{A})\geq 1$; and since $\sigma=|A\cap
S|/s=1/\ell=|A\cap T|/t=\tau$, by the claim on line (2.2) we have
$q_{\mathcal{A}}(K_{s,t})=0$ and we are done.

Case 2: $s$ and $t$ are co-prime.
The following relation between graphs $G$, $G^{-}$ and the modularities will
be useful. Let $\mathcal{A}=\\{A,\bar{A}\\}$ be a vertex bipartition of $G$
such that $e(A,\bar{A})\geq 1$ and let $G^{-}$ be any graph formed from $G$ by
removing an edge between the parts $A$ and $\bar{A}$. Then

$e(G^{-})^{2}q_{\mathcal{A}}(G^{-})=e(G)^{2}q_{\mathcal{A}}(G)-e(G)q^{E}_{\mathcal{A}}(G)+e(G)-1/2.$
(2.4)

To see this note that because the removed edge is between parts in
$\mathcal{A}$,
$e(G^{-})q_{\mathcal{A}}^{E}(G^{-})=e(G)q_{\mathcal{A}}^{E}(G)$. Similarly one
may check that
$e(G^{-})^{2}q_{\mathcal{A}}^{D}(G^{-})=e(G)^{2}q_{\mathcal{A}}^{D}(G)-e(G)+1/2$
and that these together give (2.4).

Applied to our graph $G=K_{s,t}$ and $G^{-}=K_{s,t}^{-}$ obtained by removing
an edge from between parts $A$ and $\bar{A}$, we have

$(st-1)^{2}q_{\mathcal{A}}(K_{s,t}^{-})=s^{2}t^{2}\cdot
q_{\mathcal{A}}(K_{s,t})-st\cdot(q^{E}_{\mathcal{A}}(K_{s,t})-1)-1/2.$ (2.5)

Note from (2.3)

$q^{E}_{{\mathcal{A}}}(K_{s,t})-1=-(\sigma+\tau)+2\sigma\tau=-(\sigma-\tau)^{2}-\sigma(1-\sigma)-\tau(1-\tau).$

Hence, substituting this and the expression for the modularity score in (2.2)
we have

$(st-1)^{2}q_{\mathcal{A}}(K_{s,t}^{-})=-st(\sigma-\tau)^{2}(\tfrac{1}{2}st-1)+st\big{(}\sigma(1-\sigma)+\tau(1-\tau)\big{)}-1/2.$
(2.6)

Observe that since $s$ and $t$ are co-prime the linear diophantine equation
$at-bs=1$ has solutions $(a,b)$ with $a$ and $b$ integers. Note also that if
$(a,b)$ is a solution then $(a+s,b+t)$ is also a solution. Hence there is a
solution $(a^{\prime},b^{\prime})$ with $1\leq a^{\prime}\leq s-1$ (we cannot
have $a^{\prime}=0$). Thus $b^{\prime}s=a^{\prime}t-1$ satisfies $t-1\leq
b^{\prime}s\leq(s-1)t-1$, and so $1\leq b^{\prime}\leq t-1$.

Our construction is to take $A$ with $a^{\prime}$ vertices in $S$ and
$b^{\prime}$ vertices in $T$ then

$|\sigma-\tau|=\left|\frac{|A\cap S|}{s}-\frac{|A\cap
T|}{t}\right|=\bigg{|}\frac{a^{\prime}}{s}-\frac{b^{\prime}}{t}\bigg{|}=\frac{1}{st}.$
(2.7)

Since $1\leq a^{\prime}\leq s-1$, $\sigma$ satisfies $1/s\leq\sigma\leq 1-1/s$
and hence $\sigma(1-\sigma)\geq 1/s^{2}$. Similarly $\tau(1-\tau)\geq
1/t^{2}$.

Hence by (2.6), substituting $|\sigma-\tau|=1/(st)$, $\sigma(1-\sigma)\geq
1/s^{2}$ and $\tau(1-\tau)\geq 1/t^{2}$ we get

$(st-1)^{2}q_{\mathcal{A}}(K_{s,t}^{-})\geq\frac{1}{st}+\frac{t}{s}+\frac{s}{t}-1>0$
(2.8)

and we are done. ∎

######  Lemma 2.4 (part (b) of Theorem 1.2).

Let $G$ be a complete bipartite graph $K_{s,t}$ with $s\leq t$. If $s=1$ and
$t\geq 4$, or if $s\geq 2$ and $t\geq 3$, then $\delta^{+}(G)=1$. In the other
cases (namely when $(s,t)=(1,1),(1,2),(1,3)$ or $(2,2)$), we have
$\delta^{+}(G)=\infty$.

###### Proof.

Let $s=1$ and form $G^{+}$ by adding an edge to the star $K_{1,t}$. If $t$ is
1 or 2 then $q^{*}(G^{+})=0$ since $G^{+}$ has at most 3 vertices. If $t=3$
then $G^{+}$ is $K_{4}$ less 2 edges, so $q^{*}(G^{+})=0$ by Theorem 1.1. But
for all $t\geq 4$

$q^{*}(G^{+})>0\,.$ (2.9)

To see this, suppose that the added edge $e$ is $\\{a,b\\}$, and let
${\mathcal{A}}$ be the partition of the vertex set $V$ into $\\{a,b\\}$ and
$V\setminus\\{a,b\\}$. Then

$q_{\mathcal{A}}^{E}(G^{+})=\frac{t-1}{t+1}$

and

$q_{\mathcal{A}}^{D}(G^{+})=\frac{4^{2}+(2t-2)^{2}}{4(t+1)^{2}}=\frac{4+(t-1)^{2}}{(t+1)^{2}}\,.$

Thus

$(t+1)^{2}q_{\mathcal{A}}(G^{+})=(t^{2}-1)-4-(t^{2}-2t+1)=2t-6\,:$

so $q_{\mathcal{A}}(G^{+})>0$ for $t\geq 4$. This completes the proof of
(2.9), and thus of the case $s=1$.

Suppose now that $s\geq 2$. Note first that if $s=t=2$ (so $G$ is $K_{2,2}$)
then at most 2 edges are missing from $K_{4}$, and thus $\delta^{+}(G)=\infty$
by Theorem 1.1. Now assume also that $t\geq 3$. It remains to show that
$\delta^{+}(G)=1$.

The following relation between graphs $G$, $G^{+}$ and the modularity scores
will be useful. Let $\mathcal{A}=\\{A,\bar{A}\\}$ be a vertex bipartition of
$G$ such that $e(A)<|A|(|A|-1)/2$ and let $G^{+}$ be any graph formed from $G$
by adding an edge within the part $A$. Since the extra edge is added inside a
part in $\mathcal{A}$,
$e(G^{+})q_{\mathcal{A}}^{E}(G^{+})=e(G)q_{\mathcal{A}}^{E}(G)+1$. For the
degree tax we may calculate

$e(G^{+})^{2}q_{\mathcal{A}}^{D}(G^{+})=\tfrac{1}{4}({\rm
vol}_{G}(A)+2)^{2}+\tfrac{1}{4}{\rm
vol}_{G}(\bar{A})^{2}=e(G)^{2}q_{\mathcal{A}}^{D}(G)+{\rm vol}_{G}(A)+1\,.$

Thus we get an expression similar to (2.4),

$\displaystyle e(G^{+})^{2}q_{\mathcal{A}}(G^{+})$ $\displaystyle=$
$\displaystyle
e(G^{+})^{2}q^{E}_{\mathcal{A}}(G^{+})-e(G^{+})^{2}q^{D}_{\mathcal{A}}(G^{+})$
(2.10) $\displaystyle=$
$\displaystyle(e(G)+1)(e(G)q^{E}_{\mathcal{A}}(G)+1)-e(G)^{2}q_{\mathcal{A}}^{D}(G)-{\rm
vol}_{G}(A)-1$ $\displaystyle=$ $\displaystyle
e(G)^{2}q_{\mathcal{A}}(G)+e(G)+e(G)q^{E}_{\mathcal{A}}(G)-{\rm vol}_{G}(A).$

Note that making the following substitutions for total edges :
$e(G)=e_{G}(A)+e_{G}(A,\bar{A})+e_{G}(\bar{A})$, for internal edges :
$\;e(G)q^{E}_{\mathcal{A}}(G)=e_{G}(A)+e_{G}(\bar{A})$ and for volume of $A$ :
${\rm vol}_{G}(A)=2e_{G}(A)+e_{G}(A,\bar{A})$ we get

$e(G^{+})^{2}q_{{\mathcal{A}}}(G^{+})=e(G)^{2}q_{{\mathcal{A}}}(G)+2e_{G}(\bar{A}).$
(2.11)

Case 1: $s$ and $t$ have a common factor.
Let $\ell>1$ be a common factor of $s$ and $t$. Take $\bar{A}$ to be the part
with $|S|/\ell$ vertices from $S$ and $|T|/\ell$ vertices from $T$ (we want to
add an edge within the vertex set $A$, so we take $|A|\geq|\bar{A}|$). Then
$|A\cap T|\geq 2$ since $t\geq 3$, and thus we may add an edge within part $A$
\- call this new graph $K_{s,t}^{+}$.

Similarly to in the proof of Lemma 2.3, $\sigma=|A\cap S|/s=1-1/\ell=|A\cap
T|/t=\tau$ and we have $q_{{\mathcal{A}}}(K_{s,t})=0$ for the bipartition
${\mathcal{A}}=\\{A,\bar{A}\\}$. Thus by (2.11)

$e(K_{s,t}^{+})^{2}q_{{\mathcal{A}}}(K_{s,t}^{+})=2e_{K_{s,t}}(\bar{A}).$

But now, since $\bar{A}$ has non-empty intersection with both $S$ and with $T$
we have $e_{K_{s,t}}(\bar{A})\geq 1$ and thus
$q_{{\mathcal{A}}}(K_{s,t}^{+})>0$ as required.

Case 2: $s$ and $t$ are co-prime.
As in the proof of Lemma 2.3 we may assume that $a^{\prime}t-b^{\prime}s=1$
has a solution with $1\leq a^{\prime}\leq s-1$ and $1\leq b^{\prime}\leq t-1$
positive integers. Now, if either $a^{\prime}>1$ or $b^{\prime}>1$ then take
$A$ with $a^{\prime}$ vertices in $S$ and $b^{\prime}$ vertices in $T$,
otherwise take $A$ to be the complement of that, i.e. with $s-a^{\prime}$
vertices in $S$ and $t-b^{\prime}$ vertices in $T$. Let $\sigma=|A\cap S|/s$
and $\tau=|A\cap T|/t$. In either case, as in (2.7),

$|\sigma-\tau|=1/(st).$ (2.12)

Notice also by our choice of $A$ that the set $A$ intersects either $S$ or $T$
in at least two vertices, and hence we have a place to add an edge within the
set $A$, again we call the resulting graph $K_{s,t}^{+}$.

Now by (2.11) for bipartition ${\mathcal{A}}=\\{A,\bar{A}\\}$

$e(K_{s,t}^{+})^{2}q_{{\mathcal{A}}}(K_{s,t}^{+})=e(K_{s,t})^{2}q_{{\mathcal{A}}}(K_{s,t})+e_{K_{s,t}}(\bar{A})=-\tfrac{1}{2}+e_{K_{s,t}}(\bar{A})$

where the second equality follows because by the claim in (2.2)
$q_{{\mathcal{A}}}(K_{s,t})=-\frac{1}{2}(\sigma-\tau)^{2}$, by (2.12) and
because the total number of edges is $e(K_{s,t})=st$. Again, by construction
$\bar{A}$ has non-empty intersection both with $S$ and with $T$ and hence
$e_{K_{s,t}}(\bar{A})\geq 1$, and $q_{{\mathcal{A}}}(K_{s,t}^{+})>0$ as
required. ∎

The above results show that for a complete bipartite graph $G$, always
$\delta^{-}(G)$ and $\delta^{+}(G)$ are 1 or $\infty$: that is not quite the
case for $\delta(G)$.

######  Lemma 2.5 (part (c) of Theorem 1.2).

Let $G$ be a complete bipartite graph $K_{s,t}$ with $s\leq t$. If $s=1$ and
$t\geq 4$, or if $s\geq 2$, then $\delta(G)=1$. If $(s,t)=(1,1)$ or $(1,2)$
then $\delta(G)=\infty$, and in the remaining case $(s,t)=(1,3)$ we have
$\delta(G)=2$.

###### Proof.

If $s=1$ and $t\geq 4$, or if $s\geq 2$, then
$1\leq\delta(G)\leq\delta^{+}(G)=1$ by Lemma 2.4; and if $s+t\leq 3$ then
$\delta(G)=\infty$. This leaves only the case $(s,t)=(1,3)$. When $G=K_{1,3}$
we saw that $\delta^{-}(G)=\delta^{+}(G)=\infty$, and so $\delta(G)\geq 2$.
But if $H$ is the 4-vertex path then $q^{*}(H)=\frac{1}{6}>0$, and so
$\delta(G)=2$. ∎

###  2.4 Nearly complete multipartite graphs - a partial story

We start this section by showing that complete multipartite graphs $G$ whose
part sizes have a non-trivial common divisor have $\delta^{-}(G)=1$ – though
some such graphs $G$ have $\delta^{+}(G)=\infty$, see Example 2.7. Finally we
give an example of a complete tripartite graph $G$ with $\delta^{+}(G)=2$, see
Example 2.8. We do not aim here to give a complete story but rather give a few
partial results and examples which indicate that for complete multipartite
graphs the results will be a little more involved than for complete bipartite
graphs.

######  Proposition 2.6.

Let $G=K_{s_{1},\ldots,s_{k}}$ be a complete multipartite graph where $k\geq
2$; and let $\ell|s_{i}$ for each $i$ for some integer $\ell\geq 2$. Then
$\delta^{-}(G)=1$.

###### Proof.

First note that by [2, 20] $q^{*}(G)=0$, so it remains to show that we can
remove an edge from $G$ and obtain a graph with positive modularity. By Lemma
2.1 it suffices to construct a bipartition ${\mathcal{A}}=\\{A,\bar{A}\\}$ of
$G$ with $e_{G}(A,\bar{A})\geq 1$ and $q_{\mathcal{A}}(G)\geq 0$.

Denote the parts of the complete multipartite graph by $S_{1},\ldots,S_{k}$.
Construct vertex set $A$ by including $|S_{i}|/\ell$ vertices from $S_{i}$ for
each $i$. We will show that the bipartition ${\mathcal{A}}=\\{A,\bar{A}\\}$
has the properties required. It is clear that $e_{G}(A,\bar{A})\geq 1$ so it
remains only to show $q_{\mathcal{A}}(G)\geq 0$; we show below that
$q_{\mathcal{A}}(G)=0$.

First note that

$e(A)=\sum_{i<j}\frac{|S_{i}|}{\ell}\frac{|S_{j}|}{\ell}=\frac{1}{\ell^{2}}e(G);$

that is, part $A$ contains a $1/\ell^{2}$ proportion of the edges of $G$.
Similarly, part $\bar{A}$ contains a $(\ell-1)^{2}/\ell^{2}$ proportion of the
edges; and thus $q_{\mathcal{A}}^{E}(G)=(1+(\ell-1)^{2})/\ell^{2}$. Also, part
$A$ has a $1/\ell$ proportion of the volume of the graph, and part $\bar{A}$
has a $(\ell-1)/\ell$ proportion; and so
$q^{D}_{\mathcal{A}}(G)=q^{E}_{\mathcal{A}}(G)$. Hence we have
$q_{\mathcal{A}}(G)=0$, which completes the proof. ∎

######  Example 2.7.

Let $G$ be a complete multipartite graph $K_{2,\ldots,2}$ or
$K_{2,\ldots,2,1,\ldots,1}$, with each partite set of size 2 or 1. We shall
see $\delta^{+}(G)=\infty$. First note that $q^{*}(G)=0$. Note also that if
$G$ has $j>0$ partite sets of size $2$ and $k\geq 0$ partite sets of size $1$
then adding $\ell<j$ edges yields a complete multipartite graph with $j-\ell$
partite sets of size $2$ and $k+2\ell$ partite sets of size $1$, and adding
$\ell=j$ edges yields a complete graph. However, all complete multipartite
graphs and complete graphs have modularity zero. Thus adding any number of
edges to $G$ yields a zero modularity graph, and so $\delta^{+}(G)=0$ as
claimed.

######  Example 2.8.

Let $G$ be the complete tripartite graph $K_{1,3,3}$. We shall see that
$\delta^{+}(G)=2$ and $\delta(G)=\delta^{-}(G)=1$.

Note that $q^{*}(G)=0$ and thus $\delta^{+}(G),\delta^{-}(G)\geq 1$.

We first show that $\delta^{+}(G)\geq 2$ and then that $\delta^{+}(G)=2$. All
graphs obtained by adding a single edge to $G$ are isomorphic: denote this
16-edge graph by $G^{+}$. Observe that $G^{+}$ is the complete graph $K_{7}$
less a disjoint triangle and two-edge path: a total of five missing edges. By
Lemma 1.7, to show that $q^{*}(G^{+})=0$ it is enough to consider an arbitrary
bipartition ${\mathcal{A}}=\\{A,\bar{A}\\}$ for $G^{+}$, and show that
$q_{\mathcal{A}}(G^{+})\leq 0$. Without loss of generality,
$|A|\leq|\bar{A}|$. Note that for every graph $H$ and every bipartition
$\mathcal{B}$ with a part of size 1, we have $q_{\mathcal{B}}(H)\leq 0$. Thus
we may assume that $|A|\geq 2$, so $|A|$ is 2 or 3.

Of the five edges missing in $G^{+}$ at most four can be between the parts $A$
and $\bar{A}$, and thus $e_{G^{+}}(A,\bar{A})\geq|A||\bar{A}|-4$. Firstly, if
$|A|=3$ and $|\bar{A}|=4$ then $e_{G^{+}}(A,\bar{A})\geq|A||\bar{A}|-4=8$.
Hence $q_{\mathcal{A}}^{E}(G^{+})\leq 8/16=1/2$, and since the degree tax of
any bipartition is always at least $1/2$, in this case
$q_{\mathcal{A}}(G^{+})\leq 0$.

To show that $\delta^{+}(G)\geq 2$, it remains to check the case $|A|=2$ and
$|\bar{A}|=5$, when $e_{G^{+}}(A,\bar{A})\geq 6$. If $e_{G^{+}}(A,\bar{A})\geq
8$ then as in the case $|A|=3$ above we have $q_{\mathcal{A}}(G^{+})\leq 0$.
If $e_{G^{+}}(A,\bar{A})=7$ then ${\rm
vol}_{G^{+}}(A)=2e_{G^{+}}(A)+e_{G^{+}}(A,\bar{A})\leq 2+7=9$. The degree tax
is minimised by having volumes as equal as possible, so
$q^{D}_{\mathcal{A}}(G^{+})\geq(9^{2}+23^{2})/32^{2}$. But
$q^{E}_{\mathcal{A}}(G^{+})=1-7/16=9/16$ so $q_{\mathcal{A}}(G^{+})\leq
9/16-305/512<0$. Finally, suppose that $e_{G^{+}}(A,\bar{A})=6$. Then arguing
as before we see that ${\rm vol}_{G^{+}}(A)\leq 2+6=8$, so
$q^{D}_{\mathcal{A}}(G^{+})\geq(8^{2}+24^{2})/32^{2}=5/8$. But
$q^{E}_{\mathcal{A}}(G^{+})=1-6/16=5/8$, and so $q_{\mathcal{A}}(G^{+})=0$.

We have now seen that $\delta^{+}(G)\geq 2$. To show that $\delta^{+}(G)=2$,
let $G^{++}$ be the 17 edge graph obtained from $K_{1,3,3}$ by adding two
disjoint edges. Note that $G^{++}$ is the complete graph less two disjoint
two-edge paths. Let ${\mathcal{A}}$ be a bipartition with part sizes $3$ and
$4$ such that all four missing edges are between the parts, so
$e_{G^{++}}(A,\bar{A})=8$. Then $q^{E}_{\mathcal{A}}(G^{++})=9/17$ and the
degree tax is $q^{D}_{\mathcal{A}}(G^{++})=(14^{2}+20^{2})/34^{2}$ which gives
$q_{\mathcal{A}}(G^{++})>0$ and thus $\delta^{+}(G)=2$.

Finally, we show that $\delta^{-}(G)=1$ and thus $\delta(G)=1$. Form $G^{-}$
from $G$ by deleting an edge, $uv$ say, between the partite sets of size 3.
Then let $A=\\{u,w\\}$ where $w\neq v$ is in the same partite set as $v$. Note
that the 7 ‘missing’ edges in $G^{-}$ form two $K_{3}$’s joined by an edge,
and 5 of these ‘missing’ edges are between $A$ and $\bar{A}$. Thus for the
bipartition ${\mathcal{A}}=\\{A,\bar{A}\\}$ we have
$q^{E}_{\mathcal{A}}(G^{-})=1-5/14=9/14$. For the degree tax of
${\mathcal{A}}$, note that $d_{u}=3$ and $d_{w}=4$ so ${\rm vol}(A)=7$, ${\rm
vol}(\bar{A})=21$ and thus
$q^{D}_{{\mathcal{A}}}(G^{-})=(7^{2}+21^{2})/28^{2}=(1^{2}+3^{2})/4^{2}=5/8$.
Hence $q_{\mathcal{A}}(G^{-})=9/14-5/8=1/56>0$, and so we have
$\delta^{-}(G)=1$ as required.

##  3 Proofs for results on random graphs

Most of this section is taken up with proving Theorem 1.4. After that we
quickly prove Theorems 1.5 and 1.6.

###  3.1 Proof of Theorem 1.4

Part (a). This part follows easily from Theorem 1.1. Let $p=p(n)$ satisfy
$p\geq 1-1/n+\omega(n)\,n^{-3/2}$. The number of edges missing in $G_{n,p}$ is
at most $X$, where $X\sim{\rm Bin}(\binom{n}{2},1/n-\omega\,n^{-3/2})$. Now
${\mathbb{E}}[X]\leq n/2-\omega\sqrt{n}/2$, and ${\rm var}(X)\leq n/2$. Thus,
by Chebyshev’s inequality,

${\mathbb{P}}(X\geq
n/2)\leq{\mathbb{P}}(|X-{\mathbb{E}}[X]|\geq\omega\sqrt{n}/2)\leq\frac{n/2}{\omega^{2}n/4}=o(1).$

Hence $q^{*}(G_{n,p})=0$ whp by Theorem 1.1. This completes the proof of
Theorem 1.4 (a).

Part (b). In order to prove part (b) of Theorem 1.4 we start with three
deterministic lemmas, Lemmas 3.1 and 3.3 which we will apply to the
complementary graph, together with Lemma 3.2 which will be used to prove Lemma
3.3. We shall need here only the case $k=2$ of Lemma 3.1.

######  Lemma 3.1.

Let $k\geq 2$ be fixed, and let the $n$-vertex graph $G$ satisfy
$e(G)=o(n^{3/2})$. Let ${\mathcal{A}}=(A_{1},\ldots,A_{k})$ be a partition of
$V(G)$ such that $\max_{i}|A_{i}|\leq n/k\,+o(\sqrt{n})$. Then for the
complementary graph $\bar{G}$ we have
$q_{{\mathcal{A}}}^{D}(\bar{G})=\frac{1}{k}+o(1/n)$.

###### Proof.

For each $i$

${\rm
vol}_{\bar{G}}(A_{i})\leq(\frac{n}{k}+o(\sqrt{n}))(n-1)=\frac{2}{k}\binom{n}{2}+o(n^{3/2})=\frac{2}{k}e(\bar{G})+x$

where $x=\frac{2}{k}e(G)+o(n^{3/2})=o(n^{3/2})$. Hence, by the convexity of
$f(x)=x^{2}$,

$\displaystyle\sum_{i=1}^{k}{\rm vol}_{\bar{G}}(A_{i})^{2}$
$\displaystyle\leq$
$\displaystyle(k-1)(\frac{2}{k}e(\bar{G})+x)^{2}+(\frac{2}{k}e(\bar{G})-(k-1)x)^{2}$
$\displaystyle=$
$\displaystyle\frac{4}{k}e(\bar{G})^{2}+k(k-1)x^{2}\;=\;\frac{4}{k}e(\bar{G})^{2}+o(n^{3}),$

and so $q_{{\mathcal{A}}}^{D}(\bar{G})\leq\frac{1}{k}+o(n^{-1})$. Also
$q_{{\mathcal{A}}}^{D}(\bar{G})\geq\frac{1}{k}$ since ${\mathcal{A}}$ has $k$
parts, which completes the proof. ∎

######  Lemma 3.2.

Let $F$ be an $n$-vertex forest with maximum degree at most $d$, and let
$\rho\geq 1/n$. Then we can find a set of less than $d/\rho$ edges such that
deleting these edges yields a forest in which each component tree has at most
$\rho n$ vertices.

###### Proof.

Let $x$ be the total number of vertices in components with more than $\rho n$
vertices. Thus $x\leq n$, and we may assume that $x>0$. Let the tree $T$ be a
component with more than $\rho n$ vertices. Pick a leaf $r$ in $T$, and start
following a path from $r$ until we first reach a vertex $v$ such that, for
each new edge $e$ incident to $v$ (that is, not including the edge along which
we arrived at $v$ if $v$ is not $r$), the component of $T-e$ not containing
$v$ has at most $\rho n$ vertices. Remove from $T$ all the edges incident with
$v$. This removes at most $d$ edges, and decreases $x$ by more than $\rho n$.
We need to repeat this less than $1/\rho$ times, and so we delete in total
less than $d/\rho$ edges. ∎

Let $G$ be a graph with $n$ vertices and $m$ edges. The _excess_ of $G$ is
$m-n$. The _core_ of $G$ is the graph obtained by repeatedly deleting leaves,
and (if it is non-empty) it is the unique maximal subgraph of $G$ with minimum
degree at least 2. We call a bipartition ${\mathcal{A}}=(A,B)$ _balanced_ when
$||A|-|B||\leq 1$.

######  Lemma 3.3.

Let $G$ be an $n$-vertex graph with maximum degree at most $d$, let $\rho\geq
1/n$, and let $G$ have at least $\rho n-1$ isolated vertices; and suppose that
the core of $G$ has excess at most $s$, and has at most $j$ components. Then
there is a balanced bipartition $(A,B)$ of $V(G)$ such that
$e(G)-e(A,B)<s+j+d/\rho$.

###### Proof.

By removing at most $s+j$ edges from $G$ we may reduce it to a forest $F$. By
Lemma 3.2, by removing less than $d/\rho$ further edges we may form a forest
$F^{\prime}$ where each (tree) component has at most $\rho n$ vertices. We may
find a proper 2-colouring $(A^{\prime},B^{\prime})$ of $F^{\prime}$ less its
isolated vertices such that $||A^{\prime}|-|B^{\prime}||\leq\rho n-1$. Now by
adding the isolated vertices we can form a proper 2-colouring $(A,B)$ of
$F^{\prime}$ such that $||A|-|B||\leq 1$. To complete the proof note that
$e(A,B)\geq e(F^{\prime})>e(G)-(s+j+d/\rho)$. ∎

Now consider the random graph $G\sim G_{n,c/n}$. (We shall be interested in
the complementary graph $\overline{G}$.) For each $c\in[1,\infty)$ there is a
unique $x=x(c)\in(0,1]$ such that $xe^{-x}=ce^{-c}$. Here we are following
Frieze and Karonski [6]. The function $x(c)$ is continuous and strictly
decreasing on $[1,\infty)$.

######  Lemma 3.4 (Lemma 2.16 of [6]).

Let $c>1$ and let $x=x(c)$. Then whp the core of $G_{n,c/n}$ has
$(1-x)(1-x/c)n+o(n)$ vertices and $(1-x/c)^{2}cn/2+o(n)$ edges.

We now use the above lemmas to prove the lower bound in Theorem 1.4 (b) in the
special case when the complementary graph is $G_{n,c/n}$ with $c$ small
(precisely, when $1<c\leq 2$).

######  Lemma 3.5.

Let $1<c\leq 2$, and let $G\sim G_{n,c/n}$. Then there exists $\delta>0$ such
that whp there is a balanced bipartition ${\mathcal{A}}=(A,B)$ of $V(G)$ with
$q_{{\mathcal{A}}}(\overline{G})\geq\delta/n+o(1/n)$.

###### Proof.

Let $x=x(c)$ as above. We shall see that we may take

$\delta=\tfrac{1}{2c}((c-1)(2-c)+2(x-1)^{2}).$ (3.1)

It is easy to handle the degree tax for any balanced bipartition
${\mathcal{A}}$. Since $e(G)=cn/2+o(n)=o(n^{3/2})$ whp, by Lemma 3.1 we have
$q_{{\mathcal{A}}}^{D}(\bar{G})=\tfrac{1}{2}+o(1/n)$ whp. We need to work to
find ${\mathcal{A}}$ with sufficiently high edge-contribution
$q_{{\mathcal{A}}}^{E}(\bar{G})$.

By Lemma 3.4, the core of $G$ whp has $(1-x)(1-x/c)n+o(n)$ vertices and
$(1-x/c)^{2}cn/2+o(n)$ edges. So whp the excess of the core is

$\displaystyle(1-\tfrac{x}{c})^{2}cn/2-(1-x)(1-\tfrac{x}{c})n+o(n)$
$\displaystyle=$
$\displaystyle(1-\tfrac{x}{c})(\tfrac{c}{2}-\tfrac{x}{2}-(1-x))n+o(n)$
$\displaystyle=$ $\displaystyle\tfrac{1}{2}(1-\tfrac{x}{c})(c+x-2)n+o(n).$

(It is easy to check that $c+x>2$.) Also, whp the maximum degree in $G$ is
$O(\log n/\log\log n)$, there is exactly one complex component (with more than
one cycle), there are $o(n)$ (actually many fewer) unicyclic components, and
there are $\Omega(n)$ isolated vertices [6]. Thus, by Lemma 3.3, whp there is
a balanced bipartition $(A,B)$ of $V(G)$ such that

$e(G)-e_{G}(A,B)\leq\tfrac{1}{2}(1-\tfrac{x}{c})(c+x-2)n+o(n).$

But $e(G)=\tfrac{1}{2}cn+o(n)$ whp, so whp

$\displaystyle e_{G}(A,B)$ $\displaystyle\geq$
$\displaystyle\tfrac{1}{2}cn-\tfrac{1}{2}(1-\tfrac{x}{c})(c+x-2)n+o(n)$
$\displaystyle=$
$\displaystyle\tfrac{n}{2}(c-(c+x-2-x-\tfrac{x^{2}}{c}+\tfrac{2x}{c}))+o(n)$
$\displaystyle=$ $\displaystyle(1-\tfrac{x(2-x)}{2c})\,n+o(n).$

Since $|A||B|\leq n^{2}/4$, we may see that

$\displaystyle q_{{\mathcal{A}}}^{E}(\overline{G})$ $\displaystyle\geq$
$\displaystyle 1-\frac{\frac{n^{2}}{4}-e_{G}(A,B)}{e(\overline{G})}$
$\displaystyle=$ $\displaystyle
1-\frac{\frac{1}{2}e(\overline{G})+(\frac{n^{2}}{4}-\frac{1}{2}e(\overline{G})-e_{G}(A,B))}{e(\overline{G})}$
$\displaystyle=$
$\displaystyle\tfrac{1}{2}-\frac{\frac{n^{2}}{4}-\frac{1}{2}\binom{n}{2}-(e_{G}(A,B)-\frac{1}{2}e(G))}{e(\overline{G})}$
$\displaystyle=$
$\displaystyle\tfrac{1}{2}+\frac{e_{G}(A,B)-\frac{1}{2}e(G)-\frac{1}{4}n}{e(\overline{G})}.$

But by the above, whp

$e_{G}(A,B)-\tfrac{1}{2}e(G)-\tfrac{1}{4}n\geq\delta n/2+o(n)$

where

$\delta=2-\tfrac{x(2-x)}{c}-\tfrac{1}{2}(1+c)=\tfrac{3}{2}-\tfrac{x(2-x)}{c}-\tfrac{1}{2}c.$

Thus
$q_{{\mathcal{A}}}^{E}(\overline{G})\geq\frac{1}{2}+\tfrac{(\delta/2)n}{e(\overline{G})}+o(1/n)$.
Hence, recalling that
$q_{{\mathcal{A}}}^{D}(\overline{G})=\frac{1}{2}+o(1/n)$, we have

$q_{{\mathcal{A}}}(\overline{G})\geq\tfrac{(\delta/2)n}{e(\overline{G})}+o(1/n)=\tfrac{\delta}{n}+o(1/n)\mbox{
whp}.$

We may rewrite $\delta$ as

$\delta=\tfrac{1}{2c}(3c-2x(2-x)-c^{2})=\tfrac{1}{2c}((c-1)(2-c)+2(x-1)^{2})$

as in (3.1), so clearly $\delta>0$ since $1<c\leq 2$; and this completes the
proof. ∎

Observe from (3.1) that if $c_{1}=1+\varepsilon$ with $\varepsilon$ small,
then $\delta=\varepsilon/2+O(\varepsilon^{2})$ as $\varepsilon\to 0$.

The next lemma uses Lemma 3.5 and completes the proof of the lower bound in
part (b) of Theorem 1.4. Given a graph $G$ and $0\leq p\leq 1$, let $G_{p}$
denote the random subgraph of $G$ obtained by considering each edge
independently and keeping it with probability $p$ (and otherwise deleting it).
Thus the binomial random graph $G_{n,p}$ could be written as $(K_{n})_{p}$,
where $K_{n}$ is the $n$-vertex complete graph.

######  Lemma 3.6.

Let $c>1$ and let $\delta>0$ be as in (3.1). Let the probability $p=p(n)$
satisfy $p\to 1$ as $n\to\infty$ and $p\leq 1-c/n$ for $n$ sufficiently large.
Then $q^{*}(G_{n,p})\geq\delta/n+o(1/n)$ whp.

###### Proof.

We may assume that $1<c<2$. Consider large $n$. Let $\rho=\rho(n)=p/(1-c/n)$.
We may form $G_{n,p}$ from $K_{n}$ in two steps. First delete edges
independently with probability $c/n$ to give $G_{n,1-c/n}$, and then delete
edges independently with probabilty $\rho$. By Lemma 3.5 there is a balanced
bipartition ${\mathcal{A}}$ of $[n]$ such that whp
$q_{{\mathcal{A}}}(G_{n,1-c/n})\geq\delta/n+o(1/n)$. Note that also
$e(G_{n,1-c/n})\geq\binom{n}{2}-cn$ whp.

Let $H$ be a graph on $[n]$ with $e(H)\geq\binom{n}{2}-cn$, and suppose that
${\mathcal{A}}$ is a balanced bipartition of $[n]$ with
$q_{{\mathcal{A}}}(H)\geq\delta/n+o(1/n)$. It suffices to show that the random
subgraph $H_{\rho}$ of $H$ must satisfy
$q_{{\mathcal{A}}}(H_{\rho})\geq\delta/n+o(1/n)$ whp. Note that $\rho\to 1$ as
$n\to\infty$: let $\omega=\omega(n)\to\infty$ as $n\to\infty$ sufficiently
slowly that $\omega\,(1-\rho)^{1/2}\to 0$.

Consider $e(H_{\rho})$, which has the binomial distribution ${\rm
Bin}(e(H),\rho)$. By Chebyshev’s inequality

${\mathbb{P}}\left(|e(H_{\rho})-e(H)\rho|\geq
x(e(H)\rho(1-\rho))^{1/2}\right)\leq x^{-2}.$

Thus whp

$\displaystyle e(H_{\rho})$ $\displaystyle=$ $\displaystyle
e(H)\rho+O(\omega\,(e(H)\rho(1-\rho))^{1/2})$ $\displaystyle=$ $\displaystyle
e(H)\rho\,(1+O((\omega\,((1-\rho)/e(H))^{1/2})$ $\displaystyle=$
$\displaystyle e(H)\rho\,(1+O(\omega\,(1-\rho)^{1/2}/n)),$

and so

$e(H_{\rho})=e(H)\rho\,(1+o(1/n))\;\;\mbox{ whp}.$ (3.2)

For a graph $H^{\prime}$ on $[n]$ let $e^{\rm int}(H^{\prime})=e^{\rm
int}_{\mathcal{A}}(H^{\prime})$ denote the number of internal edges within the
parts of ${\mathcal{A}}$. Then, since $e^{\rm int}(H)=\Theta(n^{2})$, much as
above we have

$e^{\rm int}(H_{\rho})=e^{\rm int}(H)\rho\,(1+o(1/n))\;\;\mbox{ whp}.$

Hence

$q_{{\mathcal{A}}}^{E}(H_{\rho})=\frac{e^{\rm
int}(H_{\rho})}{e(H_{\rho})}=q_{{\mathcal{A}}}^{E}(H)(1+o(1/n))=q_{{\mathcal{A}}}^{E}(H)+o(1/n)\;\mbox{
whp}.$ (3.3)

The degree tax is only a little more complicated. Let the parts of
${\mathcal{A}}$ be $A$ and $B$, and let $X={\rm vol}_{H_{\rho}}(A)$. Suppose
that $H$ has $i$ edges within $A$ and $j$ edges between $A$ and $B$, so ${\rm
vol}_{H}(A)=2i+j$. Then $X$ has variance

${\rm var}(X)=(4i+j)\rho(1-\rho)\leq 2{\rm vol}_{H}(A)\rho(1-\rho).$

Hence, by Chebyshev’s inequality as before, whp

$\displaystyle X$ $\displaystyle=$ $\displaystyle{\rm
vol}_{H}(A)\rho+O(\omega({\rm vol}_{H}(A)\rho(1-\rho))^{1/2})$
$\displaystyle=$ $\displaystyle{\rm
vol}_{H}(A)\rho\,(1+O((\omega((1-\rho)/{\rm vol}_{H}(A))^{1/2})$
$\displaystyle=$ $\displaystyle{\rm
vol}_{H}(A)\rho\,(1+O(\omega(1-\rho)^{1/2}/n)),$

since ${\rm vol}_{H}(A)=\Theta(n^{2})$. Thus ${\rm vol}_{H_{\rho}}(A)={\rm
vol}_{H}(A)\rho\,(1+o(1/n))$ whp; and similarly ${\rm vol}_{H_{\rho}}(B)={\rm
vol}_{H}(B)\rho\,(1+o(1/n))$ whp. Hence, using also (3.2), whp

$\displaystyle q_{{\mathcal{A}}}^{D}(H_{\rho})$ $\displaystyle=$
$\displaystyle({\rm vol}_{H_{\rho}}(A)^{2}+{\rm vol}_{H_{\rho}}(B)^{2})/{\rm
vol}(H_{\rho})^{2}$ $\displaystyle=$ $\displaystyle
q_{{\mathcal{A}}}^{D}(H)(1+o(1/n))\;=\;q_{{\mathcal{A}}}^{D}(H)+o(1/n).$

But now, using also (3.3), whp

$\displaystyle q_{{\mathcal{A}}}(H_{\rho})$ $\displaystyle=$ $\displaystyle
q_{{\mathcal{A}}}^{E}(H_{\rho})-q_{{\mathcal{A}}}^{D}(H_{\rho})\;=\;q_{{\mathcal{A}}}^{E}(H)-q_{{\mathcal{A}}}^{D}(H)+o(1/n)$
$\displaystyle=$ $\displaystyle
q_{\mathcal{A}}(H)+o(1/n)\;\geq\;\delta/n+o(1/n)$

which completes the proof. ∎

It remains in this subsection to prove the upper bound in Theorem 1.4 (b). Let
$c>0$ and let $p\geq 1-c/n$. Then whp
$e(G_{n,p})\geq\binom{n}{2}-(c+o(1))n/2$, and so
$\binom{n}{2}-n/2-e(G_{n,p})\leq(c-1+o(1))\,n/2$. Hence by Lemma 2.2

$q^{*}(G_{n,p})\leq\frac{(c-1+o(1))\,n}{e(G_{n,p})}\leq
2\,c/n\;\;\;\mbox{whp}.$

Thus we may set $\beta=2c$ to complete the proof.

###  3.2 Proof of Theorem 1.5

By Theorem 4.1 of [13] there exist $\alpha_{1}>0$ and $c_{0}$ such that if
$p=p(n)$ satisfies $1/n\leq p\leq 1-c_{0}/n$ then
$q^{*}(G_{n,p})\geq\alpha_{1}\sqrt{\frac{1-p}{np}}$ whp. We shall choose
$0<\alpha\leq\alpha_{1}$, so we need not consider this range of $p$ further.

Now let $\varepsilon>0$, and let $p$ satisfy $1-c_{0}/n\leq p\leq
1-1/n-\varepsilon/n$. Then

$\sqrt{\tfrac{1-p}{np}}\leq\sqrt{\tfrac{c_{0}/n}{n(1-c_{0}/n)}}=(\sqrt{c_{0}}+o(1/n))/n.$

By Theorem 1.4 there exists $\alpha_{2}>0$ such that
$q^{*}(G_{n,p})\geq\alpha_{2}/n$ whp. Let $\alpha>0$ satisfy
$\alpha\leq\alpha_{1}$ and $\alpha<\alpha_{2}/\sqrt{c_{0}}$. Then
$\alpha_{2}/n\geq\alpha\sqrt{\frac{1-p}{np}}$ for $n$ sufficiently large, so
$q^{*}(G_{n,p})\geq\alpha\sqrt{\frac{1-p}{np}}$ whp, as required.

###  3.3 Proof of Theorem 1.6

We shall use the following lemma, which is essentially Lemma A.2 in the
appendix to the arXiv version of [13], where it is proved using a simple
coupling argument.

######  Lemma 3.7.

Let $m=m(n)\to\infty$ as $n\to\infty$ and let $p=m/\binom{n}{2}$. Suppose that
$q^{*}(G_{n,p})\in(a_{n},b_{n})$ whp. Then for any $\varepsilon>0$,
$q^{*}(G_{n,m})\in(a_{n}-\varepsilon/\sqrt{m},b_{n}+\varepsilon/\sqrt{m})$
whp.

Let $1<c_{1}<c_{2}$. Let $m=m(n)$ satisfy $\binom{n}{2}-c_{2}\,n/2\leq
m\leq\binom{n}{2}-c_{1}\,n/2$. Then $p=m/\binom{n}{2}$ satisfies
$1-c_{2}/(n-1)\leq p\leq 1-c_{1}/(n-1)$, and so $1-(c_{2}+1)/n\leq p\leq
1-c_{1}/n$ for $n$ sufficiently large. Hence by Theorem 1.4 there exist
$0<\alpha<\beta$ (depending only on $c_{1}$ and $c_{2}+1$) such that
$\alpha/n\leq q^{*}(G_{n,p})\leq\beta/n$ whp. Hence by Lemma 3.7 with
$\varepsilon=\alpha/4$,

$q^{*}(G_{n,m})\in\big{(}\frac{\alpha}{n}-\frac{\alpha}{4\sqrt{m}},\frac{\beta}{n}+\frac{\alpha}{4\sqrt{m}}\big{)}\;\;\;\mbox{
whp}.$

But for $n$ sufficiently large $\sqrt{m}\geq n/2$ and so
$\alpha/4\sqrt{m}\leq\alpha/2n$; and thus

$q^{*}(G_{n,m})\in\big{(}\frac{\alpha/2}{n},\frac{\beta+\alpha/2}{n}\big{)}\;\;\;\mbox{
whp}.$

This completes the proof of Theorem 1.6.

##  4 Concluding remarks

We considered graphs with modularity zero, with starting point the complete
graphs and complete bipartite graphs. For each such complete graph, we found
the least number of edges which we may add to or delete from or edit to obtain
a graph with non-zero modularity.

We also considered the modularity of very dense random graphs, and in
particular we found that there is a transition to modularity zero when the
average degree of the complementary graph drops below 1.

Complete multipartite graphs also have modularity zero but corresponding
questions for them are still open - see Section 2.4. It is also open, see
Question 1.3, whether complete graphs are the furthest (in edit distance) from
graphs with positive modularity.

## References

  * [1] V. Agdur, N. Kamčev, and F. Skerman.  Universal lower bound for community structure of sparse graphs.  arXiv preprint arXiv:2307.07271, 2023.
  * [2] M. Bolla, B. Bullins, S. Chaturapruek, S. Chen, and K. Friedl.  Spectral properties of modularity matrices.  Linear Algebra and Its Applications, 473:359–376, 2015.
  * [3] U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner.  On modularity clustering.  Knowledge and Data Engineering, IEEE Transactions on, 20(2):172–188, 2008.
  * [4] J. Chellig, N. Fountoulakis, and F. Skerman.  The modularity of random graphs on the hyperbolic plane.  Journal of Complex Networks, 10(1):cnab051, 2022.
  * [5] T. N. Dinh and M. T. Thai.  Finding community structure with performance guarantees in scale-free networks.  In Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on, pages 888–891. IEEE, 2011.
  * [6] A. Frieze and M. Karoński.  Introduction to random graphs.  Cambridge University Press, 2015.
  * [7] A. Lancichinetti and S. Fortunato.  Limits of modularity maximization in community detection.  Physical Review E, 84(6):066122, 2011.
  * [8] M. Lasoń and M. Sulkowska.  Modularity of minor-free graphs.  Journal of Graph Theory, 102(4):728–736, 2023.
  * [9] L. Lichev and D. Mitsche.  On the modularity of 3-regular random graphs and random graphs with given degree sequences.  Random Structures & Algorithms, 61(4), 2022.
  * [10] T. Łuczak.  On the equivalence of two basic models of random graph.  In Proceedings of Random graphs, volume 87, pages 151–159, 1990\.
  * [11] S. Majstorovic and D. Stevanovic.  A note on graphs whose largest eigenvalues of the modularity matrix equals zero.  Electronic Journal of Linear Algebra, 27(1):256, 2014.
  * [12] C. McDiarmid and F. Skerman.  Modularity of regular and treelike graphs.  Journal of Complex Networks, 6(4), 2018.
  * [13] C. McDiarmid and F. Skerman.  Modularity of Erdős-Rényi random graphs.  Random Structures & Algorithms, 57(1):211–243, 2020.
  * [14] C. McDiarmid and F. Skerman.  Modularity and edge sampling.  arXiv preprint arXiv:2112.13190, 2021.
  * [15] F. de Montgolfier, M. Soto, and L. Viennot.  Asymptotic modularity of some graph classes.  In Algorithms and Computation, pages 435–444. Springer, 2011.
  * [16] M. E. J. Newman.  Networks: An Introduction.  Oxford University Press, 2010.
  * [17] M. E. J. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Physical Review E, 69(2):026113, 2004.
  * [18] L. O. Prokhorenkova, P. Prałat, and A. Raigorodskii.  Modularity in several random graph models.  Electronic Notes in Discrete Mathematics, 61:947–953, 2017.
  * [19] F. Skerman.  Modularity of Networks.  PhD thesis, University of Oxford, 2016.
  * [20] S. Trajanovski, H. Wang, and P. Van Mieghem.  Maximum modular graphs.  The European Physical Journal B-Condensed Matter and Complex Systems, 85(7):1–14, 2012.