$\displaystyle=(1-\varepsilon/10^{5})(1-6\varepsilon)(1-27\varepsilon)\max\\{|N_{G_{t_{v}}}(v)|,|N_{G_{t_{u}}}(u)|\\}$
$\displaystyle\geqslant(1-40\varepsilon)\max\\{|N_{G_{t_{v}}}(v)|,|N_{G_{t_{u}}}(u)|\\}$

where in the first inequality we use Eq. 3, the second inequality holds since
either $t^{\prime\prime}>t_{u}$ and we use (2) of Corollary 32 or
$t^{\prime\prime}=t_{u}$ and in that case
$|N_{G_{t^{\prime\prime}}}(u)\setminus N_{G_{t_{u}}}(u)|=0$, in the fourth
inequality we use the lower bound on $|N_{G_{t}}(v)\cap
N_{G_{t^{\prime\prime}}}(u)|$ that we proved in the current lemma, in the
fifth inequality we use 31, and the last inequality holds for $\varepsilon$
small enough.

Using what we just proved, i.e., $|N_{G_{t_{v}}}(v)\cap
N_{G_{t_{u}}}(u)|\geqslant(1-40\varepsilon)\max\\{|N_{G_{t_{v}}}(v)|,|N_{G_{t_{u}}}(u)|\\}$,
we now lower bound $|N_{\widetilde{G}_{t_{u}}}(u)\cap
N_{\widetilde{G}_{t_{v}}}(v)|$ using the same arguments as in the first case.

$\displaystyle|N_{\widetilde{G}_{t_{u}}}(u)\cap N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant|N_{G_{t_{u}}}(u)\cap
N_{G_{t_{v}}}(v)|-|N_{G_{t_{u}}}(u)\setminus
N_{\widetilde{G}_{t_{u}}}(u)|-|N_{G_{t_{v}}}(v)\setminus
N_{\widetilde{G}_{t_{v}}}(v)|$ $\displaystyle\geqslant|N_{G_{t_{u}}}(u)\cap
N_{G_{t_{v}}}(v)|-\varepsilon|N_{G_{t_{u}}}(u)|-\varepsilon|N_{G_{t_{v}}}(v)|$
$\displaystyle\geqslant|N_{G_{t_{u}}}(u)\cap
N_{G_{t_{v}}}(v)|-\varepsilon/(1-\varepsilon)|N_{\widetilde{G}_{t_{u}}}(u)|-\varepsilon/(1-\varepsilon)|N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant(1-40\varepsilon)\max\\{|N_{G_{t_{u}}}(u)|,|N_{G_{t_{v}}}(v)|\\}-\varepsilon/(1-\varepsilon)|N_{\widetilde{G}_{t_{u}}}(u)|-\varepsilon/(1-\varepsilon)|N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant(1-40\varepsilon)\max\\{|N_{G_{t_{u}}}(u)|,|N_{G_{t_{v}}}(v)|\\}-3\varepsilon|N_{\widetilde{G}_{t_{u}}}(u)|-3\varepsilon|N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant(1-40\varepsilon)(1-\varepsilon)\max\\{|N_{\widetilde{G}_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{v}}}(v)|\\}-3\varepsilon|N_{\widetilde{G}_{t_{u}}}(u)|-3\varepsilon|N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant(1-50\varepsilon)\max\\{|N_{\widetilde{G}_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{v}}}(v)|\\}$

And conclude the proof of the second case, in a similar manner to the first
case, that is, proving $N_{\widetilde{G}_{t}}(u)\approx
N_{\widetilde{G}_{t}}(v)$.

$\displaystyle|N_{\widetilde{G}_{t^{\prime}}}(u)\cap
N_{\widetilde{G}_{t^{\prime}}}(v)|$
$\displaystyle\geqslant|N_{\widetilde{G}_{t_{u}}}(u)\cap
N_{\widetilde{G}_{t_{v}}}(v)|-|N_{\widetilde{G}_{t^{\prime}}}(u)\setminus
N_{\widetilde{G}_{t_{u}}}(u)|-|N_{\widetilde{G}_{t^{\prime}}}(v)\setminus
N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant|N_{\widetilde{G}_{t_{u}}}(u)\cap
N_{\widetilde{G}_{t_{v}}}(v)|-12\varepsilon|N_{\widetilde{G}_{t_{u}}}(u)|-12\varepsilon|N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant(1-50\varepsilon)\max\\{|N_{\widetilde{G}_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{v}}}(v)|\\}-12\varepsilon|N_{\widetilde{G}_{t_{u}}}(u)|-12\varepsilon|N_{\widetilde{G}_{t_{v}}}(v)|$
$\displaystyle\geqslant(1-74\varepsilon)/(1+12\varepsilon)\max\\{|N_{\widetilde{G}_{t^{\prime}}}(u)|,|N_{\widetilde{G}_{t^{\prime}}}(v)|\\}$
$\displaystyle\geqslant(1-80\varepsilon)\max\\{|N_{\widetilde{G}_{t^{\prime}}}(u)|,|N_{\widetilde{G}_{t^{\prime}}}(v)|\\}$

Where in the second inequality we use (6) of Lemma 33, in the third inequality
we use the lower bound on $N_{\widetilde{G}_{t_{u}}}(u)\cap
N_{\widetilde{G}_{t_{v}}}(v)|$ that we proved in the current lemma, in the
fourth inequality we use (7) of Lemma 33 and the last inequality holds for
$\varepsilon$ small enough.

∎

######  Lemma 36.

$\mathcal{R}$ implies that $\forall u,v\in C_{\Phi}$:
$N_{\widetilde{G}_{t_{c}}}(u)\cap N_{\widetilde{G}_{t_{c}}}(v)\neq\emptyset$.

###### Proof.

The proof follows very similar arguments to the Cohen-Addad et al. ((2021))
that we repeat here for completeness. Let $d(x,y)$ be the distance of two
nodes $x,y$ in our sparse solution at time $t_{c}$. Suppose the lemma is not
true, then we have that $d(u,v)>2$. Towards a contradiction also assume $u,v$
to be the minimum distance nodes in $C_{\Phi}$ such that $d(u,v)>2$. Note that
for any edge in our sparse solution $\widetilde{G}_{t_{c}}$, one of its
endpoints is in $C_{\Phi}$. If $d(u,v)\geqslant 5$, let $P=\langle
u,u^{\prime},u^{\prime\prime},\ldots,v\rangle$ be the shortest $u$-$v$ path in
$\widetilde{G}_{t_{c}}$, thus either $u^{\prime}$ or $u^{\prime\prime}$ must
be in $C_{\Phi}$, contradicting the minimality assumption regarding the
distance between $u$ and $v$. If $d(u,v)\leqslant 4$, then either $d(u,v)=4$
or $d(u,v)=3$. We end up in a contradiction in both cases:

  1. 1.

If $d(u,v)=4$ then $\exists v^{\prime},w,u^{\prime}$ such that $v^{\prime}\in
N_{\widetilde{G}_{t_{c}}}(v)\cap N_{\widetilde{G}_{t_{c}}}(w)$, $w\in
C_{\Phi}$ and $u^{\prime}\in N_{\widetilde{G}_{t_{c}}}(w)\cap
N_{\widetilde{G}_{t_{c}}}(u)$.

  2. 2.

If $d(u,v)=3$ then $\exists w,u^{\prime}$ such that $w\in
N_{\widetilde{G}_{t_{c}}}(v)\cap N_{\widetilde{G}_{t_{c}}}(u^{\prime})$,
$u^{\prime}\in N_{\widetilde{G}_{t_{c}}}(w)\cap N_{\widetilde{G}_{t_{c}}}(u)$
and either $w$ or $u$ are in $C_{\Phi}$. Assume that $w\in C_{\Phi}$ (and the
case where $u^{\prime}\in C_{\Phi}$ is similar)

In both cases, from 35 we have:

$\displaystyle|N_{\widetilde{G}_{t_{c}}}(u)\cap N_{\widetilde{G}_{t_{c}}}(v)|$
$\displaystyle\geqslant|N_{\widetilde{G}_{t_{c}}}(w)|-|N_{\widetilde{G}_{t_{c}}}(w)\setminus
N_{\widetilde{G}_{t_{c}}}(u)|-|N_{\widetilde{G}_{t_{c}}}(w)\setminus
N_{\widetilde{G}_{t_{c}}}(v)|$
$\displaystyle\geqslant|N_{\widetilde{G}_{t_{c}}}(w)|-80\varepsilon|N_{\widetilde{G}_{t_{c}}}(u)|-80\varepsilon|N_{\widetilde{G}_{t_{c}}}(v)|$
$\displaystyle\geqslant(1-80\varepsilon)\max\\{|N_{\widetilde{G}_{t_{c}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(v)|\\}-80\varepsilon|N_{\widetilde{G}_{t_{c}}}(u)|-80\varepsilon|N_{\widetilde{G}_{t_{c}}}(v)|$
$\displaystyle\geqslant(1-240\varepsilon)\max\\{|N_{\widetilde{G}_{t_{c}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(v)|\\}$
$\displaystyle>0$

Where the last inequality holds for $\varepsilon$ small enough. Thus, we ended
in a contradiction. ∎

######  Corollary 37.

Let $u,v\in C_{\Phi}$, $\mathcal{R}$ implies that
$|N_{\widetilde{G}_{t_{c}}}(u)\cap
N_{\widetilde{G}_{t_{c}}}(v)|\geqslant(1-80\varepsilon)\max\\{|N_{\widetilde{G}_{t_{c}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(v)|\\}$.

###### Proof.

It is immediate from 35 and 36. ∎

Before proceeding to the last theorems of this section we state some useful
set inequalities.

######  Observation 38.

For sets $A,B$, $C$ and positive reals $\alpha,\beta$:

  1. 1.

If $|A\triangle B|\leqslant\varepsilon\max\\{|A|,|B|\\}$ then $|A\cap
B|\geqslant(1-\varepsilon)\max\\{|A|,|B|\\}$.

  2. 2.

If $|A\cap B|\geqslant(1-\varepsilon)\max\\{|A|,|B|\\}$ then for $\varepsilon$
small enough:

$|A\triangle B|\leqslant
2\varepsilon\max\\{|A|,|B|\\}\leqslant\frac{2\varepsilon}{1-\varepsilon}\min\\{|A|,|B|\\}\leqslant
3\varepsilon\min\\{|A|,|B|\\}$

  3. 3.

If $|A\triangle B|\leqslant\varepsilon\max\\{|A|,|B|\\}$ then for
$\varepsilon$ small enough $|A\triangle B|\leqslant
3\varepsilon\min\\{|A|,|B|\\}$

  4. 4.

$|A\triangle C|\leqslant|A\triangle B|+|B\triangle C|$.

  5. 5.

$\alpha\min\\{|A|,|B|\\}+\beta\min\\{|B|,|C|\\}\leqslant(\alpha+\beta)\max\\{|A|,|C|\\}$

We now proceed proving the main 39 of this section. Note that on 39 we also
argue that $\forall v\in C$ their degree when they last participated in an
“interesting event” is lower bounded by the $|C|/2$. The latter property will
be crucial in Appendix C.

######  Theorem 39.

$\mathcal{R}$ implies that cluster $C$ is dense and $\forall v\in C$:

$|N_{G_{t_{c}}}(v)\cap C|\geqslant(1-541080\varepsilon)|C|$

and

$|N_{G_{t_{u}}}(v)|\geqslant|C|/2.$

###### Proof.

Note that for node $v\in C_{\overline{\Phi}}$ its neighborhood in
$\widetilde{G}_{t_{c}}$ is a subset of $C_{\Phi}$. To relate the neighborhood
of $v$ inside $C$ in $G_{t_{c}}$ we construct an auxiliary graph which acts as
a bridge between $\widetilde{G}_{t_{c}}$ and ${G}_{t_{c}}$. We construct a
graph $\widehat{G}_{t_{c}}$ so that:

  1. 1.

$\forall u\in C$ and $u^{\prime}\in C_{\Phi}$
$N_{\widehat{G}_{t_{c}}}(u)\simeq N_{\widetilde{G}_{t_{c}}}(u^{\prime})$;

  2. 2.

$\widehat{G}_{t_{c}}\subseteq{G}_{t_{c}}$;

  3. 3.

$C$ is a connected component in $\widehat{G}_{t_{c}}$; and

  4. 4.

$\forall u\in C$ $|N_{\widehat{G}_{t_{c}}}(v)\cap
C|\geqslant(1-541080\varepsilon)|C|$

The existence of such a graph suffices to demonstrate the current theorem. For
each $v\in C_{\overline{\Phi}}$ let $\widehat{t}_{v}$ be the last time before
$t_{c}$ that $v$ was in $\varepsilon$-agreement with a node $u\in C_{\Phi}$,
one of either $u$ or $v$ was heavy and edge $(u,v)$ is added to the sparse
solution and remains until time $t_{c}$. Note that $\widehat{t}_{v}\geqslant
t_{v}$, otherwise we would have that $v\not\in C$ and
$\widehat{t}_{v}\geqslant t_{u}$ since edge $(u,v)$ remains in our sparse
solution until time $t_{c}$.

We now prove that the neighborhood $N_{G_{\widehat{t}_{v}}}(v)$ is almost the
same to the neighborhood of $N_{\widetilde{G}_{t_{c}}}(u^{\prime})$ for any
$u^{\prime}\in C_{\Phi}$. We first derive the following inequalities:

  1. (a)

$|N_{G_{\widehat{t}_{v}}}(v)\triangle
N_{G_{\widehat{t}_{v}}}(u)|\leqslant\varepsilon\max\\{|N_{G_{\widehat{t}_{v}}}(v)|,|N_{G_{\widehat{t}_{v}}}(u)|\\}\leqslant
3\varepsilon\min\\{|N_{G_{\widehat{t}_{v}}}(v)|,|N_{G_{\widehat{t}_{v}}}(u)|\\}$

  2. (b)

$|N_{G_{\widehat{t}_{v}}}(u)\triangle N_{G_{t_{u}}}(u)|\leqslant
8\varepsilon\max\\{|N_{G_{\widehat{t}_{v}}}(u)|,|N_{G_{t_{u}}}(u)|\\}\leqslant
24\varepsilon\min\\{|N_{G_{\widehat{t}_{v}}}(u)|,|N_{G_{t_{u}}}(u)|\\}$

  3. (c)

$|N_{G_{t_{u}}}(u)\triangle
N_{\widetilde{G}_{t_{u}}}(u)|\leqslant\varepsilon\max\\{|N_{G_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{u}}}(u)|\\}\leqslant
3\varepsilon\min\\{|N_{G_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{u}}}(u)|\\}$

  4. (d)

$|N_{\widetilde{G}_{t_{u}}}(u)\triangle N_{\widetilde{G}_{t_{c}}}(u)|\leqslant
13\varepsilon\max\\{|N_{\widetilde{G}_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(u)|\\}\leqslant
39\varepsilon\min\\{|N_{\widetilde{G}_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(u)|\\}$

  5. (e)

$|N_{\widetilde{G}_{t_{c}}}(u)\triangle
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\leqslant
160\varepsilon\max\\{|N_{\widetilde{G}_{t_{c}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}\leqslant
240\varepsilon\min\\{|N_{\widetilde{G}_{t_{c}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$

The right hand side of each inequality in (a), (b), (c), (d) and (e) uses 38
and the left hand side of (a) uses that $u$ and $v$ are in
$\varepsilon$-agreement at time $\widehat{t}_{v}$, (b) uses 32, (c) uses (1)
of Lemma 33 and (2) of Lemma 33, (d) uses (4) of Lemma 33 and (6) of Lemma 33
and (e) uses 37. By using the triangle inequality of 38 iteratively we can
conclude that:

$\displaystyle|N_{G_{\widehat{t}_{v}}}(v)\cap
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\geqslant(1-1113\varepsilon)\max\\{|N_{G_{\widehat{t}_{v}}}(v)|,||N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$

With the same line of reasoning for a node $u\in C_{\Phi}$ we can define
$\widehat{t}_{u}$ as the last time that an edge $(u,v)$ where $v\in C$ was
added to our sparse solution and remained until at least time $t_{c}$.
Inequalities (b), (c), (d) and (e) remain true and following the same
arguments we conclude that:

$\forall u,u^{\prime}\in C_{\Phi}$:

$\displaystyle|N_{G_{\widehat{t}_{u}}}(u)\cap
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\geqslant(1-1113\varepsilon)\max\\{|N_{G_{\widehat{t}_{u}}}(u)|,||N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$

Consequently, $\forall u\in C$ and $u^{\prime}\in C_{\Phi}$:

$|N_{G_{\widehat{t}_{u}}}(u)\cap
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\geqslant(1-1113\varepsilon)\max\\{|N_{G_{\widehat{t}_{u}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$
(*)

Let $d=\max\\{|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|:u^{\prime}\in
C_{\Phi}\\}$. Using Eq. * we can conclude that for $\varepsilon$ small enough:

$\frac{d}{2}\leqslant(1-1113\varepsilon)d\leqslant|N_{G_{\widehat{t}_{u}}}(u)|\leqslant\frac{d}{(1-1113\varepsilon)}\leqslant
2d$ (**)

Also note that since $N_{\widetilde{G}_{t_{c}}}(u^{\prime})\subseteq C$ we
also have that $\forall v\in C_{\overline{\Phi}}$ and $u^{\prime}\in
C_{\Phi}$:

$\displaystyle|(N_{G_{\widehat{t}_{v}}}(v)\cap C)\cap
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\geqslant(1-1113\varepsilon)\max\\{|N_{G_{\widehat{t}_{v}}}(v)\cap
C|,||N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$ (***)

and using the same arguments as in the case of $|N_{G_{\widehat{t}_{u}}}(u)|$
we can also lower and upper bound $|N_{G_{\widehat{t}_{v}}}(v)\cap C|$ as
follows:

$\frac{d}{2}\leqslant(1-1113\varepsilon)d\leqslant|N_{G_{\widehat{t}_{v}}}(v)\cap
C|\leqslant\frac{d}{(1-1113\varepsilon)}\leqslant 2d$ (****)

To facilitate the description of the intermediate graph $\widehat{G}_{t_{c}}$
for each $u\in C$ let $E_{u}=\\{(u,v):v\in N_{G_{\widehat{t}_{u}}}(u)\cap
C\\}$ be the set of edges between $u$ and nodes in
$N_{G_{\widehat{t}_{u}}}(u)\cap C$. Note that all these edges also exist in
$G_{t_{c}}$. We define $\widehat{G}_{t_{c}}=(C,\bigcup_{u\in C}E_{u})$ to be
the graph with set of nodes to be $C$ and edges $\bigcup_{u\in C}E_{u}$. Let
$N_{u}$ be the neighborhood of $u$ in that graph, then:

  1. 1.

$N_{u}\supseteq N_{G_{\widehat{t}_{u}}}(u)\cap C$

  2. 2.

$\widehat{G}_{t_{c}}\subseteq{G}_{t_{c}}$

  3. 3.

$N_{u}=(N_{G_{\widehat{t}_{u}}}(u)\cap C)\cup\\{v\in
C:\\{t_{v}^{\text{arrival}}>\widehat{t}_{u}\\}\land\\{(v\in
N_{G_{t_{c}}}(u)\\}\\}$

While (1) and (2) are immediate for (3) we further elaborate. Note that for
node $u\in C$ we can construct its neighborhood in $\widehat{G}_{t_{c}}$ as
follows: first add all edges to nodes in $N_{G_{\widehat{t}_{u}}}(u)\cap C$
and then for every node $v\in N_{G_{t_{c}}}(u)\cap(C\setminus
N_{G_{\widehat{t}_{u}}}(u))$ such that $\widehat{t}_{v}>\widehat{t}_{u}$ add
edge $(u,v)$. Then (3) follows by noting that sets $\\{v\in
N_{G_{t_{c}}}(u)\cap(C\setminus
N_{G_{\widehat{t}_{u}}}(u)):\widehat{t}_{v}>\widehat{t}_{u}\\}$ and $\\{v\in
C:\\{t_{v}^{\text{arrival}}>\widehat{t}_{u}\\}\land\\{(v\in
N_{G_{t_{c}}}(u)\\}\\}$ are equal. We now argue that
$N_{u}\simeq(N_{G_{\widehat{t}_{u}}}(u)\cap C)$. For each node $v\in C$ such
that $t_{v}^{\text{arrival}}>\widehat{t}_{u}$ and $v\in N_{G_{t_{c}}}(u)$ it
holds that:

  1. 1.

$v\in N_{G_{t_{c}}}(u)\setminus N_{G_{\widehat{t}_{u}}}(u)$; and

  2. 2.

$|N_{G_{\widehat{t}_{v}}}(v)|<2d$ where $\widehat{t}_{v}>t_{u}$

For the second point note that $\widehat{t}_{v}\geqslant
t_{v}^{\text{arrival}}$, $t_{v}^{\text{arrival}}>\widehat{t}_{u}$ and
$\widehat{t}_{u}\geqslant t_{u}$. From these two points note that
$\mathcal{R}$ implies that $|\\{v\in
C:\\{t_{v}^{\text{arrival}}>\widehat{t}_{u}\\}\land\\{(v\in
N_{G_{t_{c}}}(u)\\}\ |<\varepsilon/10^{2}d$ and from Eq. **** we have that
$|N_{G_{\widehat{t}_{u}}}(u)\cap C|\geqslant\frac{d}{2}$. Combining these
facts:

$\displaystyle|N_{u}\triangle(N_{G_{\widehat{t}_{u}}}(u)\cap C)|$
$\displaystyle=|N_{u}\setminus(N_{G_{\widehat{t}_{u}}}(u)\cap C)|$
$\displaystyle=|\\{v\in
C:\\{t_{v}^{\text{arrival}}>\widehat{t}_{u}\\}\land\\{(v\in
N_{G_{t_{c}}}(u)\\}\\}|$ $\displaystyle\leqslant\varepsilon/10^{2}d$
$\displaystyle\leqslant 2\varepsilon/10^{2}|N_{G_{\widehat{t}_{u}}}(u)\cap C|$
$\displaystyle\leqslant
2\varepsilon/10^{2}\min\\{|N_{u}|,|N_{G_{\widehat{t}_{u}}}(u)\cap C|\\}$

Also applying 38 to Eq. *** we get that $\forall u\in C_{\overline{\Phi}}$ and
$u^{\prime}\in C_{\Phi}$:

$\displaystyle|(N_{G_{\widehat{t}_{u}}}(u)\cap C)\triangle
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\leqslant
3339\varepsilon\min\\{|N_{G_{\widehat{t}_{u}}}(u)\cap
C|,||N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$

Thus, again from 38 and combining:

  1. 1.

$|(N_{G_{\widehat{t}_{u}}}(u)\cap C)\triangle
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\leqslant
3339\varepsilon\min\\{|N_{G_{\widehat{t}_{u}}}(u)\cap
C|,||N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$; and

  2. 2.

$|N_{u}\triangle(N_{G_{\widehat{t}_{u}}}(u)\cap C)|\leqslant
2\varepsilon/10^{2}\min\\{|N_{u}|,|N_{G_{\widehat{t}_{u}}}(u)\cap C|\\}$

We conclude that $\forall u\in C$ and $u^{\prime}\in C_{\Phi}$:

$\displaystyle|N_{u}\triangle N_{\widetilde{G}_{t_{c}}}(u^{\prime})|$
$\displaystyle\leqslant
3(3339+2\varepsilon/10^{2})\min\\{|N_{u}|,|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$
$\displaystyle\leqslant
10020\varepsilon\min\\{|N_{u}|,|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$
(*****)

Moreover, applying the latter inequality for any $u,w\in C$ and $u^{\prime}\in
C_{\Phi}$ we conclude that:

$\displaystyle|N_{u}\triangle N_{w}|$ $\displaystyle\leqslant
3(10020+10020)\min\\{|N_{u}|,|N_{w}|\\}$ $\displaystyle\leqslant
60120\varepsilon\min\\{|N_{u}|,|N_{w}|\\}$ $\displaystyle\leqslant
60120\varepsilon\max\\{|N_{u}|,|N_{w}|\\}$

and

$\displaystyle|N_{u}\cap N_{w}|$ $\displaystyle\geqslant
60120\varepsilon\max\\{|N_{u}|,|N_{w}|\\}$

Thus, $\forall u,w\in C$:

  1. 1.

$u$ and $w$ are connected; and

  2. 2.

If $u$ and $w$ are connected in $\widehat{G}_{t_{c}}$ then they are in
$60120\varepsilon$-agreement

Thus, $C$ is a cluster in the agreement decomposition of graph
$\widehat{G}_{t_{c}}$ when agreement and heaviness parameters are set to
$60120\varepsilon$. Using Property 4 we can deduce that $\forall u\in C$

$\displaystyle|N_{u}\cap C|$ $\displaystyle\geqslant(1-9\cdot
60120\varepsilon)|C|=(1-541080\varepsilon)|C|$

We now proceed lower bounding $|N_{G_{t_{u}}}(u)|$. For a node $u\in C$ and
$u^{\prime}\in C_{\Phi}$ using (c), (d), (e) and 38 we can deduce that:

$\displaystyle|N_{G_{t_{u}}}(u)\triangle
N_{\widetilde{G}_{t_{c}}}(u^{\prime})|$ $\displaystyle\leqslant
3\cdot(3\cdot(3+39)+240)\varepsilon\min\\{|N_{G_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$
$\displaystyle\leqslant
1098\varepsilon\min\\{|N_{G_{t_{u}}}(u)|,|N_{\widetilde{G}_{t_{c}}}(u^{\prime})|\\}$

Combining the latter with Eq. ***** we get:

$\displaystyle|N_{G_{t_{u}}}(u)\triangle N_{u}|$ $\displaystyle\leqslant
3\cdot(10020+1098)\varepsilon\min\\{|N_{G_{t_{u}}}(u)|,|N_{u}|\\}$
$\displaystyle\leqslant 33354\varepsilon\min\\{|N_{G_{t_{u}}}(u)|,|N_{u}|\\}$

We are now ready to deduce that:

$\displaystyle|N_{G_{t_{u}}}(u)|$
$\displaystyle\geqslant(1-33354\varepsilon)|N_{u}|$
$\displaystyle\geqslant(1-33354\varepsilon)|N_{u}\cap C|$
$\displaystyle\geqslant(1-33354\varepsilon)(1-541080\varepsilon)|C|$
$\displaystyle\geqslant(1-574434\varepsilon)|C|$ $\displaystyle\geqslant|C|/2$

where in the third inequality we used that $C$ is dense and the last
inequality holds for $\varepsilon$ small enough. ∎

##  Appendix C Runtime Analysis

In this section we compute the complexity of our algorithm and prove that, on
expectation, the time spent per each node insertion or deletion is
$O(\operatorname{polylog}n)$. Note that the $\varepsilon$ used in Algorithm 3
and in all proofs is a small enough constant which gets “absorbed” in the big
$O(\cdot)$ notation. We introduce some auxiliary random variable definitions:

  1. 1.

$W_{t}$ denotes the complexity of operations at time $t$;

  2. 2.

$L$ is the size of the largest connected component of $\widetilde{G}_{t-1}$;
and

  3. 3.

$Q_{t}$ is the total number of agreement and heaviness calculations at time
$t$.

Note that edge additions are at least as many as edge deletions and each edge
addition is preceded by a heaviness and agreement calculation between its
endpoints. Thus, the total complexity of Algorithm 3 is upper bounded by a
constant times the total complexity of agreement and heaviness calculations.
Since from Appendix E each agreement and heaviness calculation requires
$O(\log n)$ time we have that:

$\displaystyle{\bf E}\left[\sum_{t}W_{t}\right]$ $\displaystyle\leqslant
O(\log n)\cdot{\bf E}\left[\sum_{t}Q_{t}\right]$ $\displaystyle\leqslant
O(\log n)\cdot\sum_{t}{\bf E}\left[Q_{t}\right]$

The focus in the rest of the section will be to prove that ${\bf
E}\left[Q_{t}\right]=O(\operatorname{polylog}n)$. We start by arguing that the
number of nodes that participate in an “interesting event” at time $t$ is, on
expectation, at most $\operatorname{polylog}n$.

######  Lemma 40.

$\displaystyle{\bf
E}\left[|\mathcal{I}_{t}|\right]=O(\operatorname{polylog}n)$

###### Proof.

In the case of a node addition it is always true that
$|\mathcal{I}_{t}|\leqslant\left(\nicefrac{{10^{10}\log
n}}{{\varepsilon}}\right)^{4}=O(\operatorname{polylog}n)$. To argue that the
same bound holds on expectation in the case of a node deletion we introduce
some auxiliary notation. For a node $v\in G_{t^{\prime}}$ we use
$I_{v}^{i,t^{\prime}}$ and $B_{v}^{i,t^{\prime}}$ to denote the sets
$I_{v}^{i}$ and $B_{v}^{i}$ respectively at the end of iteration $t^{\prime}$.
At time $t$ we have that:

$\displaystyle|\mathcal{I}_{t}|$
$\displaystyle\leqslant\left|\bigcup_{i}B_{v_{t}}^{i,t-1}\right|\cdot\left(\nicefrac{{10^{10}\log
n}}{{\varepsilon}}\right)^{3}$
$\displaystyle\leqslant\sum_{i}|B_{v_{t}}^{i,t-1}|\cdot\Theta\left(\operatorname{polylog}n\right)$

Also, our algorithm maintains the following invariant:

$\displaystyle\sum_{v\in G_{t^{\prime}},i}|I_{v}^{i,t^{\prime}}|=\sum_{v\in
G_{t^{\prime}},i}|B_{v}^{i,t^{\prime}}|=O(n\operatorname{polylog}n),\;\forall
t^{\prime}$

Thus, at time $t$ if we select uniformly at random a node and delete it, we
have that:

$\displaystyle{\bf
E}\left[\sum_{i}|B_{v_{t}}^{i,t}|\right]=O(\operatorname{polylog}n)$

∎

The main 42 of this section requires a delicate coupling argument. We give a
proof sketch before proceeding to the formal proof. Similarly to Appendix B
let $t_{u}$ denote the last time strictly before $t$ that $u$ participated in
an “interesting event”. We remind the reader an important event definition of
Appendix B which will be used also in this section.

######  Definition 41.

$\displaystyle\mathcal{R}=$ $\displaystyle\bigcap_{u\in
C}M_{u}^{t_{u},t-1}\bigcap_{u\in
C,d\in\left[1,n\right]}\left\\{|P_{d,t_{u},t-1}^{u}|\leqslant\varepsilon/10^{2}d\right\\}$

Let $C_{u}$ be the connected component $u$ belongs to in $\widetilde{G}_{t-1}$
then from 39 we have that: $\mathcal{R}$ implies that $\forall v\in C_{u}$ it
holds that $|N_{G_{t_{u}}}(v)|\geqslant|C_{u}|/2$.

Since event $\mathcal{R}$ happens with high probability and $|C_{u}|\leqslant
n$, we can argue that ${\bf E}[N_{G_{t_{u}}}(u)|]\geqslant|C_{u}|/3$.
Consequently for a connected component $C$ of $\widetilde{G}_{t-1}$ we can
upper bound, on expectation, the number of nodes in the anchor set as follows:

$\displaystyle\sum_{u\in C}\nicefrac{{10^{7}\log
n}}{{\varepsilon|N_{G_{t_{u}}}(u)|}}$ $\displaystyle\simeq\sum_{u\in
C}\nicefrac{{3\cdot 10^{7}\log n}}{{\varepsilon|C|}}$
$\displaystyle=\nicefrac{{3\cdot 10^{7}\log n}}{{\varepsilon}}$
$\displaystyle=O(\log n)$

Consequently ${\bf E}[L]=O(\log n)$. In the last step of our proof we argue
that ${\bf E}[W_{t}]=O(\log n){\bf E}[|\mathcal{I}_{t}|]{\bf
E}[L]=O(\operatorname{polylog}n)$

######  Theorem 42.

$\displaystyle{\bf E}\left[\sum_{t}W_{t}\right]=O(\operatorname{polylog}n)$

###### Proof.

As already mentioned in the beginning of the section it is enough to argue
that ${\bf E}\left[Q_{t}\right]=O(\operatorname{polylog}n)$. We use $\Phi$ to
denote the set of anchor set nodes at time $t-1$ and by $L$ the maximum number
of anchor set nodes in any connected component of our sparse solution at time
$t-1$.

For a node $v\in\widetilde{G}_{t}$, on expectation, the number of agreement
and heaviness calculations for each subroutine is upper bounded as follows:

  1. 1.

Connect($v,\varepsilon,t$): $10^{7}\log n/\varepsilon\cdot L=L\cdot O(\log n)$

  2. 2.

Anchor($v,\varepsilon,t$): $\min\left\\{\\{|N_{G_{u}}(t)|\cdot\frac{10^{7}\log
n}{\varepsilon|N_{G_{u}}(t)|},|N_{G_{u}}(t)|\\}\right\\}=O(\log n)$

  3. 3.

Clean($v,\varepsilon,t$): $L$

Let $W_{t,v}$ be the total number of agreement and heaviness calculations
required by those three procedures, then:

$\displaystyle{\bf E}[W_{t,v}]=O(\log n)\cdot{\bf E}[L]$

We continue upper bounding ${\bf E}[L]\leqslant O(\log n)$.

From the law of total expectation we have:

$\displaystyle{\bf E}[L]$ $\displaystyle={\bf E}[L\mid\mathcal{R}]\cdot{\bf
Pr}[R]+{\bf E}[L\mid\overline{\mathcal{R}}]\cdot{\bf Pr}[\overline{R}]$
$\displaystyle\leqslant{\bf E}[L\mid\mathcal{R}]+n\cdot{\bf Pr}[\overline{R}]$
$\displaystyle\leqslant{\bf E}[L\mid\mathcal{R}]+n\cdot 1/n^{10^{2}}$
$\displaystyle<{\bf E}[L\mid\mathcal{R}]+1/n^{99}$

where in the first inequality we used that ${\bf Pr}[R]\leqslant 1$ and
$L\leqslant n$ are always true and in the second inequality we used 29. We now
concentrate on bounding the first term of the summation. We remind the reader
that $u_{i}$ is the $i$-th node in our node stream.

From the principled of deferred decisions we can construct an instance of
$\widetilde{G}_{t-1}$ as follows: we first run Notify($v_{1},\varepsilon$),
Notify($v_{2},\varepsilon$), …, Notify($v_{t-1},\varepsilon$) sequentially and
calculate $\mathcal{I}_{1},\mathcal{I}_{2},\dots,\mathcal{I}_{t-1}$. Note that
at this point for each node $u$ in $G_{t-1}$, the random variable $t_{u}$ is
realized, indeed $t_{u}=\max\\{i\in[1,t-1]:u\in\mathcal{I}_{i}\\}$. Moreover
$\Phi$ is not realized, since we did not sample any Bernoulli variable from
our Anchor procedure yet. We now run the “for loop” of our algorithm which
contains the Clean, Connect and Anchor procedures, sequentially for
$\mathcal{I}_{1},\mathcal{I}_{2},\dots,\mathcal{I}_{t-1}$. Let $F$ denote a
realization of the first step and let $X_{u}$ be the Bernoulli variables used
in the Anchor($u,\varepsilon,t_{u}$) procedures for all $u$’s.

Towards a coupling argument we now describe a second stochastic procedure to
construct a “sparse graph” $\widehat{G}_{t-1}$: we again run the
Notify($v_{1},\varepsilon$), Notify($v_{2},\varepsilon$), …,
Notify($v_{t-1},\varepsilon$) sequentially and calculate
$\mathcal{I}_{1},\mathcal{I}_{2},\dots,\mathcal{I}_{t-1}$. In the second step
we run the “for loop” of our algorithm sequentially for
$\mathcal{I}_{1},\mathcal{I}_{2},\dots,\mathcal{I}_{t-1}$ assuming that all
the Bernoulli variables which were sampled by the Anchor procedures are $1$.
As a final step we use the variables $X_{u}$ (also used by the first
procedure) and delete from the anchor set all nodes for which $X_{u}=0$ and
also delete all edges between nodes $u,v$ such that both $X_{u}$ and $X_{v}$
are $0$.

Let $\mathcal{F}$ be the set of possible realizations of the first step
conditioned on event $\mathcal{R}$. From the law of total expectation it
suffices to prove that $\forall F\in\mathcal{F}$ we have:

$\displaystyle{\bf E}[L\mid F\land\mathcal{R}]=O(\log n)$

Let $\widehat{\mathcal{C}}$ denote the set of connected components of the
sparse graph constructed by the second stochastic procedure at the second
step. Note that given $F$, $\widehat{\mathcal{C}}$ is a deterministic set.
Similarly let $\mathcal{C}$ be the random variable denoting the set of
connected components of $\widetilde{G}_{t-1}$. Note that the following is
always true: $\forall C\in\mathcal{C}$ there exists a set
$C^{\prime}\in\widehat{\mathcal{C}}$ such that $C\subseteq C^{\prime}$. Now,
for all sets $C^{\prime}\in\widehat{\mathcal{C}}$ let $L_{C^{\prime}}$ be the
random variable denoting the number of anchor set nodes in set $C^{\prime}$
after the third step. We have that
$\max_{C^{\prime}\in\widehat{\mathcal{C}}}L_{C^{\prime}}\geqslant L$.
Consequently, it is enough to bound the following quantity:

$\displaystyle{\bf
E}[\max_{C^{\prime}\in\widehat{\mathcal{C}}}L_{C^{\prime}}\mid
F\land\mathcal{R}]=O(\log n)$

Note that 39 also applies to the clustering $\widehat{\mathcal{C}}$. Let
$C^{\prime}\in\widehat{\mathcal{C}}$ then $\forall u\in C^{\prime}$:

${{\bf E}[X_{u}\mid F\land\mathcal{R}]\leqslant\nicefrac{{2\cdot 10^{7}\log
n}}{{\varepsilon|C^{\prime}|}}}$ ${\bf E}[L_{C^{\prime}}\mid
F\land\mathcal{R}]={\bf E}[\sum_{u\in C^{\prime}}X_{u}\mid
F\land\mathcal{R}]\leqslant\nicefrac{{2\cdot 10^{7}\log n}}{{\varepsilon}}$

Using Chernoff we can get that:

${\bf Pr}[L_{C^{\prime}}>2\cdot\frac{2\cdot 10^{7}\log n}{\varepsilon}\mid
F\land\mathcal{R}]\leqslant 1/n^{10}$

Let $T=\\{\forall C^{\prime}\in\widehat{\mathcal{C}}:L_{C^{\prime}}\leqslant
2\cdot\frac{2\cdot 10^{7}\log n}{\varepsilon}\\}$, we can conclude that:

$\displaystyle{\bf
E}[\max_{C^{\prime}\in\widehat{\mathcal{C}}}L_{C^{\prime}}\mid
F\land\mathcal{R}]$ $\displaystyle={\bf
E}[\max_{C^{\prime}\in\widehat{\mathcal{C}}}L_{C^{\prime}}\mid T\land
F\land\mathcal{R}]\cdot{\bf Pr}[T]+{\bf
E}[\max_{C^{\prime}\in\widehat{\mathcal{C}}}L_{C^{\prime}}\mid\overline{T}\land
F\land\mathcal{R}]\cdot{\bf Pr}[\overline{T}]$ $\displaystyle\leqslant
2\cdot\frac{2\cdot 10^{7}\log n}{\varepsilon}+n\cdot{\bf Pr}[\overline{T}]$
$\displaystyle\leqslant 2\cdot\frac{2\cdot 10^{7}\log n}{\varepsilon}+n\cdot
n\cdot 1/n^{10}$ $\displaystyle=O(\operatorname{polylog}n)$

where in the first inequality we used the definition of event $T$ and that
$\max_{C^{\prime}\in\widehat{\mathcal{C}}}L_{C^{\prime}}\leqslant n$ and in
the second inequality used a union bound on the sets of
$\widehat{\mathcal{C}}$.

We now conclude the proof. Note that while $W_{t,v}$ only depends on the
random choices of our algorithm up until time $t-1$, $\mathcal{I}_{t}$ is
independent of those. Consequently:

$\displaystyle{\bf E}\left[Q_{t}\right]$ $\displaystyle={\bf
E}\left[\sum_{v\in V}\mathbbm{1}\\{v\in\mathcal{I}_{t}\\}W_{t,v}\right]$
$\displaystyle=\sum_{v\in V}{\bf
E}\left[\mathbbm{1}\\{v\in\mathcal{I}_{t}\\}W_{t,v}\right]$
$\displaystyle=\sum_{v\in V}{\bf
E}\left[\mathbbm{1}\\{v\in\mathcal{I}_{t}\\}\right]{\bf
E}\left[W_{t,v}\right]$ $\displaystyle\leqslant\sum_{v\in V}{\bf
E}\left[\mathbbm{1}\\{v\in\mathcal{I}_{t}\\}\right]O(\log n){\bf
E}\left[L\right]$ $\displaystyle\leqslant O(\log n){\bf
E}\left[L\right]\sum_{v\in V}{\bf
E}\left[\mathbbm{1}\\{v\in\mathcal{I}_{t}\\}\right]$ $\displaystyle\leqslant
O(\log n){\bf E}\left[L\right]{\bf E}\left[\sum_{v\in
V}\mathbbm{1}\\{v\in\mathcal{I}_{t}\\}\right]$ $\displaystyle\leqslant O(\log
n){\bf E}\left[L\right]{\bf E}\left[|\mathcal{I}_{t}|\right]$
$\displaystyle\leqslant O(\operatorname{polylog}n)$

where in the last inequality we used 40.

∎

##  Appendix D Efficient Clustering Computation from Sparse Solutions

In previous sections we prove that our algorithm computes a series of sparse
graphs $\widetilde{G}_{1},\widetilde{G}_{2},\dots,\widetilde{G}_{n}$ such that
with high probability:

  1. 1.

a total update time complexity of $\Theta(n\operatorname{polylog}n)$ is
required; and

  2. 2.

$\forall t$, the connected components of $\widetilde{G}_{t}$ define constant
factor approximation correlation clustering for graph $G_{t}$.

This section aims to demonstrate how we can compute and output the connected
components of any sparse graph $\widetilde{G}_{t}$ in $\Theta(n)$ time. Note
that $\widetilde{G}_{t}$ contains at most $\Theta(n\operatorname{polylog}n)$
edges. Consequently, a naive approach of computing connected components by
traversing all edges of $\widetilde{G}_{t}$ would result in a time complexity
of $\Theta(n\operatorname{polylog}n)$.

It is worth emphasizing that the complexity of the offline algorithm proposed
in Assadi and Wang ((2022)) is also $\Theta(n\operatorname{polylog}n)$.
Therefore, if $\Theta(n\operatorname{polylog}n)$ time is required just to
compute the connected components of $\widetilde{G}_{t}$, simply rerunning the
algorithm from Assadi and Wang ((2022)) would be an equivalent solution our
algorithm; rendering our effort in maintaining a sequence of sparse graphs
meaningless.

Following the notation of the previous sections, let
$\widetilde{G}=(V,\widetilde{E})$ be a sparse graph maintained by our
algorithm, $\Phi$ the set of anchor nodes and
$\Phi_{v}=N_{\widetilde{G}}(v)\cap\Phi$ the anchor set nodes which are
connected to $v$ in our sparse solution $\widetilde{G}$. To ease notation, we
write $u\sim v$ if and only if $u$ and $v$ belong to the same connected
component of $\widetilde{G}$.

We will describe a procedure that constructs a function
$f:V\xrightarrow{}\mathbb{N}$. $f$ will encode our clustering solution as
follows: two nodes $u,v\in V$ are in the same cluster if and only if
$f(u)=f(v)$. We then argue that: if $\forall u,v\in\Phi$ which are in the same
connected of $\widetilde{G}$ it holds that $N_{\widetilde{G}}(u)\cap
N_{\widetilde{G}}(v)\neq\emptyset$ then $f$’s clustering coincides with the
connected components of $\widetilde{G}$. Note that from Appendix B we can use
36 to prove that the latter property holds with high probability. To ease
notation, We write $u\sim v$ if and only if $u$ and $v$ belong to

Algorithm 7 ComputeConnectedComponents($\widetilde{G}$)

0: $\forall v\in V$: $f(v)\xleftarrow{}-1$, $ID\xleftarrow{}0$,
$Q\xleftarrow{}\Phi$

while $Q\neq\emptyset$ do

Let $u$ be any node in $Q$

$f(u)\xleftarrow{}ID$

$T\xleftarrow{}\\{u\\}$

for all $v\in N_{\widetilde{G}}(u)$ do

if $f(v)=-1$ then

No conflict phase

$f(v)\xleftarrow{}ID$

$T\xleftarrow{}T\cup\\{v\\}$

else

Resolving conflict phase

for all $v^{\prime}\in T$ do

$f(v^{\prime})\xleftarrow{}f(v)$

end for

break from for loop

end if

end for

$ID\xleftarrow{}ID+1$

$Q\xleftarrow{}Q\setminus T$

end while

for all $v\in V\setminus\Phi$ such that $f(v)=-1$ do

Let $u$ be a node in $\Phi_{v}$

$f(v)\xleftarrow{}f(u)$

end for

######  Lemma 43.

If for $\widetilde{G}$ and $\Phi$:

  1. 1.

$V=\bigcup\limits_{v\in\Phi}N_{\widetilde{G}}(v)$; and

  2. 2.

$\forall u,v\in\Phi$ such that $u\sim v$, $N_{\widetilde{G}}(u)\cap
N_{\widetilde{G}}(v)\neq\emptyset$

then $f(u)=f(v)$ if and only if $u\sim v$.

###### Proof.

Note that after the while loop is terminated all nodes in $\Phi$ are assigned
a value different than $-1$. In addition, $\forall v\in V\setminus\Phi$ there
exists a node $u\in\Phi_{v}$ such that $f(v)=f(u)$. Thus, it suffices to argue
that for any two nodes $u,v\in\Phi$: $f(u)=f(v)$ if and only if $u\sim v$. Let
$u_{i}$ be the node selected from $Q$ in the beginning of the while’s loop
$i$-th iteration, $f_{i}$ the $f$ function assignment after the termination of
the $i$-th iteration and $\Phi_{i}$ all the nodes in $u\in\Phi$ such that
$f_{i}(u)\neq-1$. Note that for any node $u$ if $f_{i}(u)\neq-1$ then $\forall
j>i$: $f_{j}(u)\neq-1$ and $f_{j}(u)=f_{i}(u)$. Consequently,
$\Phi_{i}\subset\Phi_{i+1},\forall i$. We prove by induction the following
statements in tandem:

  1. 1.

if $f(u_{i})=i$ then $\forall j\geqslant i$ and $v\in N_{\widetilde{G}}(u)$
$f_{j}(v)=k$; and

  2. 2.

$\forall u,v\in\Phi_{i}$: $f_{i}(u)=f_{i}(v)$ if and only if $u\sim v$.

For $i=1$ note that the algorithm updates the $f$ function only in the No
conflict phase for all nodes in $N_{\widetilde{G}}(u_{1})$ with the same
$ID=1$. Thus, both statements hold. For $i>1$ we consider two cases:

  1. 1.

If $f$ is updated only in the No conflict phase then all nodes in
$N_{\widetilde{G}}(u_{i})$ receive the same $ID=i$. Since $ID=i$ is first used
in iteration $i$ all nodes that received an $ID$ in previous iterations
maintain their previous $ID$ (which is smaller than $i$). To conclude this
case, we need to argue that $\forall u\in\Phi_{i-1}$ $u\not\sim u_{i}$.
Towards a contradiction assume that such a node exists. Let $u\in\Phi_{i-1}$
be such that $f_{i-1}(u)=j<i$ and $u\sim u_{i}$. By definition, $u_{j}$ is the
first node to receive $ID=j$ and since $\sim$ is a transitive relation
$u_{j}\sim u_{i}$. By our inductive hypothesis $\forall v\in
N_{\widetilde{G}}(u_{j})$ $f_{i-1}(v)=j$ and by the conditions of the current
lemma, $\exists w\in N_{\widetilde{G}}(u_{j})\cap N_{\widetilde{G}}(u_{i})$.
However, this is a contradiction because $f$ would have been updated also in
Resolving conflict phase.

  2. 2.

If $f$ is updated also in the Resolving conflict phase then we have that
$f_{i}(u_{i})=j<i$ and it suffices to argue that there exists a node
$u\in\Phi_{i-i}$ such that $f_{i-1}(u)=j$ it holds that $u\sim u_{i}$. Let
$v\in N_{\widetilde{G}}(u_{i})$ be a node such that $f_{i-1}(v)=j\neq-1$. Note
that such a node exists since $f$ is also updated in the Resolving conflict
phase. W.l.o.g. assume that the value of $f$ at $v$ was updated at time
$j^{\prime}\in[j,i-1]$. Then, either $v\in\Phi_{i-i}$ or $v\in
N_{\widetilde{G}}(u_{j^{\prime}})$ where for $u_{j^{\prime}}\in\Phi_{i-1}$ it
holds that $f_{i-1}(u_{j^{\prime}})=j$. In both cases since $\sim$ is a
transitive relation we conclude that a node $u\in\Phi_{i-i}$ such that
$f_{i-1}(u)=j$ and $u\sim u_{i}$ always exists.

∎

######  Lemma 44.

Algorithm 7 has complexity $O(|V|)$.

###### Proof.

The final for loop has complexity at most $\Theta(|V|)$. To bound the
complexity of the while loop we simply note that for every node $v$ its $f$
function value changes at most twice. Consequently, operations of the form
“$f(\cdot)\xleftarrow{}$” are at most $2|V|$. ∎

##  Appendix E Agreement and Heaviness Calculation with $O(\log n)$ Sampled
Nodes

In this section we design the ProbabilisticAgreement($u,v,\varepsilon$) and
Heavy($u,\varepsilon$) procedures.

These two procedure are used to test if two nodes $u$ and $v$ are in
$\varepsilon$-agreement and if a node $u$ is $\varepsilon$-heavy. The idea is
that if we let some slack on how much in agreement and how much heavy a node
is then $O(\operatorname{polylog}n)$ samples of each node’s neighborhood are
enough to design a ProbabilisticAgreement($u,v,\varepsilon$) procedure that,
w.h.p. answers affirmatively if the two nodes are indeed in
$0.1\varepsilon$-agreement and at the same time answers negatively if these
two nodes are not in $\varepsilon$-agreement. Consequently, if two nodes are
in an $\varepsilon^{\prime}$-agreement for $\varepsilon^{\prime}$ between
$0.1\varepsilon$ and $\varepsilon$ then
ProbabilisticAgreement($u,v,\varepsilon$) may answer positively or negatively.
We do the same for the Heavy($u,\varepsilon$) procedure.

We start by proving some useful inequalities regarding the neighborhood of two
nodes in case they are indeed in $\varepsilon$-agreement and in case they are
not. Subsequently we analyze the properties of
ProbabilisticAgreement($u,v,\varepsilon$) and finally we do the same for the
Heavy($u,\varepsilon$) procedure.

Algorithm 8 ProbabilisticAgreement($u,v,\varepsilon$)

Initialization: $k=300\log n/\varepsilon$.

for $i=1$ to $k$ do

Draw a random neighbor $r_{i}$ of $u$ and a random neighbor $s_{i}$ of $v$.

Let $x_{i}=\mathbbm{1}\\{r_{i}\in N(u)\setminus N(v)\\}$,
$y_{i}=\mathbbm{1}\\{r_{i}\in N(v)\setminus N(u)\\}$

end for

if $\sum_{i}x_{i}/k<0.4\varepsilon$ and $\sum_{i}y_{i}/k<0.4\varepsilon$ then

Output “ YES”

else

Output “NO”

end if

Algorithm 9 Heavy($u,\varepsilon$)

Initialization: $k=1200\log n/\varepsilon$.

for $i=1$ to $k$ do

Draw a random neighbor $v_{i}$ of $u$.

Let
$x_{i}=\mathbbm{1}\\{\text{ProbabilisticAgreement}(u,v_{i},\varepsilon)=\text{``No''}\\}$

end for

if $\sum_{i}x_{i}/k<1.2\varepsilon$ then

Output “ Yes”

else

Output “No”

end if

######  Proposition 45.

Let $u,v$ be two nodes which are in $\varepsilon$-agreement then
$\frac{|N(v)|}{1-\varepsilon}\geqslant|N(u)|\geqslant(1-\varepsilon)|N(v)|$.

###### Proof.

Assume w.l.o.g. that $|N(u)|>|N(v)|$. Then
$|N(u)|-|N(v)|\leqslant|N(u)\setminus N(v)|\leqslant|N(u)\triangle
N(v)|\leqslant\varepsilon\max\\{|N(u)|,|N(v)|\\}$ ∎

######  Proposition 46.

Let $u,v$ be two nodes which are in $\varepsilon$-agreement then
$\frac{|N(u)\setminus N(v)|}{|N(u)|}\leqslant 1.1\varepsilon$ and
$\frac{|N(v)\setminus N(u)|}{|N(v)|}\leqslant 1.1\varepsilon$.

###### Proof.

$|N(u)\setminus N(v)|\leqslant|N(u)\triangle
N(v)|\leqslant\varepsilon\max\\{|N(u)|,|N(v)|\\}\leqslant\varepsilon\frac{|N(u)|}{1-\varepsilon}\leqslant
1.1|N(u)|$ for $\varepsilon$ small enough. ∎

######  Proposition 47.

Let $u,v$ be two nodes which are not in $\varepsilon$-agreement then either
$\frac{|N(u)\setminus N(v)|}{|N(u)|}\geqslant 0.5\varepsilon$ or
$\frac{|N(v)\setminus N(u)|}{|N(v)|}\geqslant 0.5\varepsilon$.

###### Proof.

Since $|N(v)\setminus N(u)|+|N(u)\setminus N(v)|=|N(u)\triangle
N(v)|\geqslant\varepsilon\max\\{|N(u)|,|N(v)|\\}$ then either $|N(v)\setminus
N(u)|>0.5\varepsilon|N(v)|$ or $|N(u)\setminus N(v)|>0.5\varepsilon|N(u)|$. ∎

######  Observation 48.

Let $u,v$ be two nodes which share an edge, $s,t$ two nodes chosen uniformly
at random from $N(u)$ and $N(v)$ respectively and $X_{s}=\mathbbm{1}\\{s\in
N(u)\setminus N(v)\\}$, $X_{t}=\mathbbm{1}\\{s\in N(v)\setminus N(u)\\}$. We
have the following:

  1. 1.

If $u,v$ are in agreement then ${\bf Pr}[X_{s}=1]\leqslant 1.1\varepsilon$ and
${\bf Pr}[X_{t}=1]\leqslant 1.1\varepsilon$.

  2. 2.

If $u,v$ are not in agreement then either ${\bf Pr}[X_{s}=1]\geqslant
0.5\varepsilon$ or ${\bf Pr}[X_{t}=1]\geqslant 0.5\varepsilon$.

######  Theorem 49.

(Chernoff bound) Let $X_{1},X_{2},\dots,X_{k}$ be $k$ i.i.d. random variables
in $[0,1]$. Let $X=\sum_{i}X_{i}/k$. Then:

  1. 1.

For any $\delta\in[0,1]$ and $U\geqslant E[X]$ we have

${\bf Pr}[X\geqslant(1+\delta)U]\leqslant\exp(-\delta^{2}Uk/3)$

  2. 2.

For any $\delta>0$ and $U\leqslant E[X]$ we have

${\bf Pr}[X\leqslant(1-\delta)U]\leqslant\exp(-\delta^{2}Uk/2)$

######  Lemma 50.

If Algorithm 8 outputs “YES” then $u,v$ are in $\varepsilon$-agreement with
probability greater than $1-1/n^{3}$.

###### Proof.

We proceed by upper bounding the probability that the algorithm outputs “YES”
and $u,v$ are not in agreement. Since $u,v$ are not in agreement by
observation 48 we have that either $E[\sum_{i}X_{i}/k]>0.5\varepsilon$ or
$E[\sum_{i}Y_{i}/k]>0.5\varepsilon$. W.l.o.g. assume that
$E[\sum_{i}X_{i}/k]>0.5\varepsilon$. By using the second inequality of the
Chernoff bound with $U=0.5\varepsilon$ and $\delta=0.2$. We have

${\bf Pr}[\sum_{i}X_{i}/k<(1-\delta)U]\leqslant\exp(-0.2^{2}\cdot
0.5\varepsilon\cdot 300\log n/\varepsilon\cdot 0.5)=\exp(-3\cdot\log
n)=\frac{1}{n^{3}}$

∎

######  Lemma 51.

If $u,v$ are in $0.1\varepsilon$-agreement then Algorithm 8 outputs “YES” with
probability greater than $1-1/n^{3}$.

###### Proof.

We will upper bound the probability that $u,v$ are in
$0.1\varepsilon$-agreement and the algorithm outputs “NO”. Note that since
$u,v$ are in $0.1\varepsilon$-agreement by observation 48 we have that
$E[\sum_{i}X_{i}/k]<1.1\cdot 0.1\varepsilon=0.11\varepsilon$ and
$E[\sum_{i}Y_{i}/k]\leqslant 1.1\cdot 0.1\varepsilon=0.11\varepsilon$. The
algorithm outputs “NO” if either $\sum_{i}X_{i}/k\geqslant 0.4\varepsilon$ or
$\sum_{i}Y_{i}/k\geqslant 0.4\varepsilon$. We bound the probability of the
first event using the first inequality of the Chernoff bound with
$U=0.4\varepsilon$ and $\delta=2$ $(>0.4/0.11-1)$. We have

${\bf Pr}[\sum_{i}X_{i}/k\geqslant(1+\delta)U]\leqslant\exp(-2^{2}\cdot
0.11\varepsilon\cdot 300\log n/\varepsilon\cdot 0.334)<\exp(-44\cdot\log
n)=1/n^{44}$

Overall the probability that the algorithm outputs “NO” by the union bound is
upper bounded by $1/n^{44}+1/n^{44}<1/n^{3}$ ∎

######  Lemma 52.

Let $u$ be a node and $v$ a random neighbor of $u$. Let
$X_{v}=\mathbbm{1}\\{\text{ProbabilisticAgreement}(u,v,\varepsilon)=\text{``No''}\\}$.
We have the following:

  1. 1.

If $u$ is in $0.1\varepsilon$-agreement with a $(1-\varepsilon)$-fraction of
its neighborhood then ${\bf Pr}[X_{u}=1]\leqslant 1.1\varepsilon$.

  2. 2.

If $u$ is not in $\varepsilon$-agreement with a $\varepsilon$-fraction of its
neighborhood then ${\bf Pr}[X_{u}=1]>3\varepsilon$.

###### Proof.

Let $A_{uv}$ be the event that $u$ and $v$ are in $0.1\varepsilon$-agreement
and $B_{uv}$ be the event that $u$ and $v$ are not in $\varepsilon$-agreement.
For (1) we have:

${{\bf Pr}[X_{u}=1]={\bf Pr}[X_{u}=1\mid A_{uv}]\cdot{\bf Pr}[A_{uv}]}+{{\bf
Pr}[X_{u}=1\mid\widetilde{A_{uv}}]\cdot{\bf
Pr}[\widetilde{A_{uv}}]}\leqslant{1/n^{3}\cdot
1+1\cdot\varepsilon}<1.1\varepsilon$

and for (2) we have that:

${{\bf Pr}[X_{u}=1]={\bf Pr}[X_{u}=1\mid B_{uv}]\cdot{\bf Pr}[B_{uv}]}+{{\bf
Pr}[X_{u}=1\mid\widetilde{B_{uv}}]\cdot{\bf
Pr}[\widetilde{B_{uv}}]}\geqslant{(1-1/n^{3})\cdot
1+1\cdot(1-\varepsilon)}>3\varepsilon$

∎

######  Lemma 53.

If $u$ is in $0.1\varepsilon$-agreement with at least a
$(1-\varepsilon)$-fraction of its neighborhood, then Algorithm 9 outputs
“Yes”, i.e., that the node is heavy, with probability greater than
$1-1/n^{3}$.

###### Proof.

We will upper bound the probability that Algorithm 9 outputs “No”. Note that
from lemma 52 $E[\sum_{i}X_{i}/k]>1.1\varepsilon$. By using the first
inequality of the Chernoff bound with $U=1.1\varepsilon$ and $\delta=1/11$. We
have:

${\bf Pr}[\sum_{i}X_{i}/k\geqslant(1+\delta)U]\leqslant\exp(-1/11^{2}\cdot
1.1\varepsilon\cdot 1200\log n/\varepsilon\cdot 1/3)<\exp(-3.63\cdot\log
n)<1/n^{3}$

∎

######  Lemma 54.

If $u$ is not in $\varepsilon$-agreement with at least a
$\varepsilon$-fraction of its neighborhood, then Algorithm 9 outputs “No”,
i.e., that the node is not heavy, with probability greater than $1-1/n^{3}$.

###### Proof.

We will upper bound the probability that Algorithm 9 outputs “Yes”. Note that
from lemma 52 $E[\sum_{i}X_{i}/k]>3\varepsilon$. By using the second
inequality of the Chernoff bound with $U=3\varepsilon$ and $\delta=0.6$. We
have:

${\bf Pr}[\sum_{i}X_{i}/k\leqslant(1-\delta)U]\leqslant\exp(-0.6^{2}\cdot
3\varepsilon\cdot 1200\log n/\varepsilon\cdot 1/2)<\exp(-648\cdot\log
n)<1/n^{3}$

∎

##  Appendix F Final Theorem

We are now ready to prove that the clustering produced by our algorithm for
every $t$ is a constant factor approximation to the optimal correlation
clustering solution for graph $G_{t}$. To this end note that by 4 it is enough
to argue that with high probability:

  1. 1.

all dense enough clusters found by the agreement algorithm on each graph
$G_{t}$ are also identified by our algorithm and all their nodes are clustered
together; and

  2. 2.

all clusters that are found by our dynamic agreement algorithm are dense
enough

For (1) we use 23 and for (2) we use 39.

See 6

###### Proof.

23 assumes the following event: for all pair of nodes $u,v$ that are in
$\varepsilon/10^{14}$-agreement and all nodes $u^{\prime}$ that are
$\varepsilon/10^{14}$-heavy the ProbabilisticAgreement($u,v,\varepsilon$) and
Heavy($u^{\prime},\varepsilon$) procedures of Appendix E output “Yes” and 39
assumes that: for all or all pair of nodes $u,v$ that are not in
$\varepsilon$-agreement and all nodes $u^{\prime}$ that are not
$\varepsilon$-heavy the ProbabilisticAgreement($u,v,\varepsilon$) and
Heavy($u^{\prime},\varepsilon$) procedures of Appendix E output “No”. Using
50, 51, 53 and 54 we bound the probability that this event does not happen by
$n^{2}/n^{3}+n^{2}/n^{3}+n/n^{3}+n/n^{3}<4/n$. Upper bounding over all times
and possible clusters and using 23 and 39 we conclude that the probability of
the dynamic algorithm to output at each time a $O(1)$-approximation is at
least:

$1-n^{3}/n^{10^{2}}-n^{3}/n^{10^{2}}-4/n>1-5/n$

∎

##  Appendix G Structural Properties of the Agreement Decomposition

Let $G$ be the graph and let $\mathcal{C}$ be the clustering produced by
AgreementAlgorithm($G$). Let $u,v$ be two nodes which belong to the same non-
trivial cluster $C$ of $\mathcal{C}$, then for $\varepsilon$ small enough the
following properties hold, which were shown in Cohen-Addad et al. ((2022a)).

  1. fnum@PropertiesiProperty 1Property 1

$\absolutevalue{N_{G}(u)\cap
C}\geqslant(1-3\varepsilon)\absolutevalue{N_{G}(u)}$

  2. fnum@PropertiesiProperty 2Property 2

$\absolutevalue{N_{G}(u)\setminus C}<3\varepsilon\absolutevalue{N_{G}(u)}$

  3. fnum@PropertiesiProperty 3Property 3

$\absolutevalue{C}\geqslant(1-3\varepsilon)\absolutevalue{N_{G}(u)}$

  4. fnum@PropertiesiProperty 4Property 4

$\absolutevalue{N_{G}(u)\cap C}\geqslant(1-9\varepsilon)\absolutevalue{C}$

  5. fnum@PropertiesiProperty 5Property 5

$\absolutevalue{C\setminus N_{G}(u)}<9\varepsilon\absolutevalue{C}$

  6. fnum@PropertiesiProperty 6Property 6

$\absolutevalue{N_{G}(u)}\geqslant(1-9\varepsilon)\absolutevalue{C}$

  7. fnum@PropertiesiProperty 7Property 7

$\absolutevalue{N_{G}(u)\cap
N_{G}(v)}\geqslant(1-5\varepsilon)\max\\{\absolutevalue{N_{G}(u)},\absolutevalue{N_{G}(v)}\\}$

  8. fnum@PropertiesiProperty 8Property 8

$\absolutevalue{N_{G}(v)}(1-5\varepsilon)\leqslant\absolutevalue{N_{G}(u)}\leqslant\frac{\absolutevalue{N_{G}(v)}}{1-5\varepsilon}$

  9. fnum@PropertiesiProperty 9Property 9

$\absolutevalue{C\setminus
N_{G}(u)}<9\varepsilon\absolutevalue{C}<\frac{9\varepsilon}{1-9\varepsilon}\absolutevalue{N_{G}(u)}$

  10. fnum@PropertiesiProperty 10Property 10

$\absolutevalue{N_{G}(u)\setminus
C}<3\varepsilon\absolutevalue{N_{G}(u)}<\frac{3\varepsilon}{1-3\varepsilon}\absolutevalue{C}$

  11. fnum@PropertiesiProperty 11Property 11

$N_{G}(u)\cap N_{G}(v)\neq\emptyset$

##  Appendix H Additional Experiments

Here we have the experiments for the rest of the datasets presented in Section
5. Moreover, we present the performance of each dataset/algorithm pair when we
restrict the node stream to only additions and we calculate the objective
after all nodes have arrived. The correlation clustering objective value of
each algorithm is divided by the performance of Singletons. Since PIVOT is (on
expectation) a 3-approximation we note that the solution achieved by all other
algorithms is at most a multiplicative factor 3 away from the optimum offline
solution.

Table 3: Performance on the entire graph when node stream contains only additions Dataset | Agree-Static | Pivot-Dynamic | Singletons | PIVOT
---|---|---|---|---
musae-facebook | 0.97 | 1.13 | 1.00 | 1.19
email-Enron | 0.95 | 1.08 | 1.00 | 1.25
cit-HepTh | 1.00 | 1.20 | 1.00 | 1.22
ca-AstroPh | 0.99 | 1.10 | 1.00 | 0.98
Figure 2: Correlation clustering objective relative to singletons Figure 3:
Correlation clustering objective relative to singletons Figure 4: Correlation
clustering objective relative to singletons


# Drivers of Magnetic Field Amplification at Oblique Shocks: In-Situ
Observations

Hadi Madanian Laboratory for Atmospheric and Space Physics,
University of Colorado Boulder,
Boulder, CO 800303, USA  Imogen Gingell School of Physics and Astronomy,
University of Southampton
Southampton, SO17 1BJ, UK  Li-Jen Chen NASA Goddard Space Flight Center,
Greenbelt,MD 20723, USA  Eli Monyek  Astrophysical and Planetary Sciences
Department,
University of Colorado Boulder,
Boulder, CO 80309, USA

###### Abstract

Collisionless shocks are ubiquitous structures throughout the universe. Shock
waves in space and astrophysical plasmas convert the energy of a fast-flowing
plasma to other forms of energy, including thermal and magnetic energies.
Plasma turbulence and high-amplitude electric and magnetic fluctuations are
necessary for effective energy conversion and particle acceleration. We survey
and characterize in-situ observations of reflected ions and magnetic field
amplification rates at quasi-perpendicular shocks under a wide range of
upstream conditions. We report magnetic amplification factors as high as 25
times the upstream magnetic field in our current dataset. Reflected ions
interacting with the incoming plasma create magnetic perturbations which cause
magnetic amplification in upstream and downstream regions of quasi-
perpendicular shocks. Our observations show that in general magnetic
amplification increases with the fraction of reflected ions, which itself
increases with Mach number. Both parameters plateau once full reflection is
reached. Magnetic amplification continuously increases with the inverse of the
magnetization parameter of the upstream plasma. We find that the extended foot
region upstream of shocks and nonlinear processes within that region are key
factors for intense magnetic amplification. Our observations at non-
relativistic shocks provide the first experimental evidence that below a
certain magnetization threshold, the magnetic amplification efficiency at
quasi-perpendicular shocks becomes comparable to that at the quasi-parallel
shocks.

††software: Data and Code Availability

##  1 Introduction

Our understanding of distant astrophysical shocks is based on remote
observations of emissions and accelerated particles at these structures.
Magnetic amplification at astrophysical shocks has direct impacts on the post-
shock plasma temperature and associated X-ray emissions (Blandford & Ostriker,
1978), and on the generation of galactic cosmic rays at supernova remnants
(Bell, 2013). Magnetic amplification at collisionless shocks is proportional
to the amount of upstream energy (Sulaiman et al., 2015; Russell et al.,
1982). The source of this energy, among others, can be from the shock
expansion into the upstream medium compressing the upstream field (Donnert et
al., 2018), density inhomogeneities and shock-generated vorticities and
turbulence (Fraschetti, 2013; Ji et al., 2016), and upstream magnetic
perturbations induced by backstreaming or reflected ions (RIs) (Madanian et
al., 2021b; Bell, 2004; Bohdan et al., 2021).

Oblique quasi-perpendicular ($Q_{\perp}$) shocks, which are focused in this
study, travel at large angles ($\theta_{Bn}>45^{\circ}$) to the upstream
magnetic field ($\textbf{B}_{U}$). At strong supercritical shocks, a fraction
of the incident ions is reflected upstream to allow for heating and
thermalization of already transmitted ions. Particle reflection is through a
combination of the cross-shock electrostatic potential and magnetic deflection
(Gedalin, 1997; Madanian et al., 2021a), with the latter (former) becoming
more (less) important with increasing Mach number (the ratio of the shock
speed to a characteristic wave speed in the medium) (Leroy et al., 1982;
Dimmock et al., 2012). RIs play a key role in energy repartition across the
shock. At shocks with significant particle reflection, most of the enthalpy
flux downstream of the shock is carried by the suprathermal population
returning RIs that have crossed the shock layer into the downstream (Schwartz
et al., 2022). The kinematics of RIs behind the shock front is associated with
the magnetic overshoot and undershoot structures (Leroy et al., 1982), and
relaxation of the directly transmitted ions (Gedalin, 2019). Presence of RIs
upstream of the shock front leads to a modest and gradual increase in the
upstream magnetic field and formation of the shock “foot”, with roughly the
size of an ion gyroradius (Sckopke et al., 1983). In the normal incidence
frame, in which the upstream flow is along the normal vector to the shock
surface $\hat{\textbf{{n}}}$, the gyroradius of a specularly reflected proton
is $r_{L}=2m_{p}V_{U}sin(\theta_{Bn})/eB_{U}$, where $m_{p}$ is the proton
mass and $V_{U}$ is the upstream flow speed. A weaker magnetic field in the
upstream plasma corresponds to a larger foot region. For non-planar bow
shocks, the reflection point across the shock also influences the ion
trajectory (Madanian et al., 2023; Gedalin, 2023).

RIs are a source of free energy upstream of the shock layer, making the plasma
unstable to develop electrostatic and electromagnetic waves (Buneman, 1958;
Weibel, 1959; Fried, 1959). Relative drift between RIs and the upstream
electrons and ions leads to various forms of streaming instability and
magnetic perturbations that can propagate at oblique angles to the background
magnetic field and towards upstream or downstream (Marcowith et al., 2016).
These waves are steepened and nonlinearly amplified as they traverse the foot,
and can modify the shock front (Madanian et al., 2021b, 2020; Burgess et al.,
2016). In this paper, we investigate factors influencing the magnetic
amplification rates at $Q_{\perp}$ shocks by analyzing the properties of RIs
that are responsible for magnetic field amplification.

##  2 Data and Method

We analyze data from the Magnetospheric Multiscale (MMS) mission (Burch et
al., 2016), a set of four spacecraft orbiting the Earth. During specific
phases of the mission, the spacecraft trajectories extend into the solar wind
and cross the Earth’s bow shock, enabling high time resolution in-situ
measurements of shock processes. Shock events in MMS data are surveyed and
cataloged through ongoing activities and reported in previous studies (Lalti
et al., 2022). Our analysis includes 222 $Q_{\perp}$ shock events. The
distribution of these events across the nominal bow shock boundary is shown in
Figure 1.

Figure 1: The distribution of the Earth’s bow shock crossing events. The
events are projected on the $XY$ plane of the Geocentric solar ecliptic (GSE)
coordinates, in which the $+X$ axis is towards the Sun, the $+Y$ axis points
opposite to the planetary motion, and the $+Z$ axis completes the right-hand
triple. Nominal bow shock (dashed line) and magnetopause (solid line)
boundaries are shown for reference (Farris & Russell, 1994; Shue et al.,
1998). The axes are in units of Earth radii (RE).

MMS spacecraft are equipped with plasma and field instruments including the
Fast Plasma Investigation (FPI) unit that measures charged particles (Pollock
et al., 2016) and the magnetometer system (Russell et al., 2016). Due to the
coarse resolution at very low energies, FPI measurements may underestimate the
density and overestimate the temperature of the cold solar wind beam. For each
event, we determine the upstream plasma temperature $T_{U}$ from the solar
wind monitor measurements at Lagrange point 1 shifted to the nose of the bow
shock (King & Papitashvili, 2005). The upstream plasma density $n_{U}$ is
selected by comparing MMS measurements in the pristine solar wind and the
shifted solar wind monitor data and selecting the higher value. We obtain
$\textit{B}_{U}$ from MMS data in the unperturbed solar wind. The Alfvén Mach
number, $M_{Alf}=v_{shock}/v_{Alf}$ is calculated using the solar wind flow
speed along the shock normal direction as a proxy for the shock speed
($v_{shock}$). $v_{Alf}=B_{U}/\sqrt{\mu_{0}\rho}$ is the Alfvén speed in which
$\mu_{0}$ is the vacuum permeability and $\rho$ is the plasma mass density.
The distribution function of various ion populations in units of energy flux
$\phi(E,\Omega)$ is derived from FPI count rate measurements in field-of-view
(FOV, $d\Omega$) and energy ($dE$) bins. For an ion population occupying a
specific region of the phase space, the total particle flux,
$\textbf{{F}}=n\textbf{{V}}$, can be obtained by integrating the energy flux
across the occupied solid angles and energy ranges:

$\textbf{{F}}=\sum\sum\frac{\phi(E,\Omega)}{E}dEd\Omega$ (1)

The population density is determined from:

$n=\sqrt{\frac{m}{2}}\sum\sum\frac{\phi(E,\Omega)}{E^{\frac{3}{2}}}dEd\Omega$
(2)

We define the momentum tensor, $\bar{\textbf{P}}=m<v>$, as:

$\bar{\textbf{P}}=\sqrt{2m}\sum\sum\sqrt{E}\phi(E,\Omega)dEd\Omega$ (3)

which we use to obtain the pressure tensor in the frame of reference of the
ion population:

$\textbf{p}=\bar{\textbf{P}}-m\textbf{{V}}\textbf{{F}}$ (4)

For some bow shock crossing events, the RI population upstream of the shock is
clearly separate from the solar wind ions in the FPI FOV which allows us to
study RI properties by calculating plasma moments for each population. The
separation is dependent on the Lorentz force factor in the upstream plasma.
The two populations can be tracked and distinguished from one another
typically up to the shock ramp, beyond which ions are scattered, heated, and
mixed by the enhanced magnetic field. We label these events as “RI Track”. See
the Supplementary Figure 7 for an example. In addition to density and velocity
(Eqs. 1 and 2), the RI beam temperature ($T_{RI}$) can be obtained by taking
the average of the two smallest eigenvalues of the temperature tensor,
$\textbf{p}/n$. For events that a unique set of FOV bins for RIs cannot be
selected, we calculate the density of the solar wind beam based on its trace
in the FPI FOV and its energy range and subtract it from the total density to
obtain the density of the RIs. These events are labeled as “SW Subtract” and
an example is shown in Supplementary Figure 8.

The abundance of RIs decreases rapidly with distance to the shock front. To
make reasonable comparisons of the ion reflection rate between various shock
events, the RI density must be selected at the same distance to each shock.
Given the dynamic motion of the shocks and nonstationarity effects, consistent
and reliable identification of a specific position in the foot region of every
shock becomes nontrivial. However, there are several indicators in the data
for identifying the shock front, such as the jump in the magnetic field,
heating of solar wind electrons, and deflection of the solar wind ion beam in
the FPI FOV. For each event, we first determine the shock crossing time and
then isolate the solar wind and RI populations and calculate the moments. We
select the RI density ($n_{RI}$) at the closest point to the shock front where
the moments could be determined. Roughly, half of that density is associated
with freshly-reflected ions. It is worth noting that steepened waves or
nonstationarity effects can appear in time series data as transient structures
containing heated, compressed, and nearly isotropic plasma much like the
downstream plasma. These instances are easily identified in the data and are
avoided during the selection.

##  3 Results

Figure 2: Magnetic amplification rate as a function of RI fraction. The color
scale represents the Alfvén Mach number of the shocks. The black squares are
binned density averages with associated standard error within each bin shown
with error bars. The histogram in the background shows the number of events in
each bin. Data points are distinguished by upside-down triangle and circle
markers for the analysis method based on “RI Track” and “SW Subtract”,
respectively.

We begin by quantifying the magnetic amplification rate across the shocks and
by establishing a relationship between this parameter and the RI abundance
using the large number of events in our dataset. In Figure 2 we compare the
ion reflection ($n_{RI}/n_{U}$) and magnetic amplification ($B_{Max}/B_{U}$)
rates normalized by corresponding upstream values ($B_{U}$ and $n_{U}$). Black
squares on this figure are averaged binned data points showing the overall
trend in the data. The magnetic amplification rate increases with ion
reflection. For $n_{RI}/n_{U}$ between 0.2 to 0.5, $B_{Max}/B_{U}$ continues
to increase but at a lower rate. We see further increase in the average
magnetic amplification rate as the RI fraction increases beyond 0.6. But it
remains constant at slightly above 10 for larger reflection rates. The plateau
in the magnetic amplification rates suggests that with all other shock
parameters held fixed, the increased in abundance of RIs cause magnetic
perturbations across the shock up to a threshold reached at $B_{Max}/B_{U}\sim
10$. As the color scale in Figure 2 indicates, shock events that exhibit
higher amplification rates also occur at higher Mach numbers (red colors).

Figure 3: Ion reflection rate as a function of Alfvén Mach number. Data are
color-coded by the upstream plasma temperature. The black squares are averages
of binned densities. The associated standard error within each bin is shown
with error bars. The horizontal dashed line is drawn at $n_{RI}/n_{U}=1$.

In Figure 3 we show changes in the fraction of RIs as a function of $M_{Alf}$.
Similar to Figure 2, the black squares are averages of binned data and they
show that ion reflection at $Q_{\perp}$ shocks increases with the upstream
Mach number. In addition, with increasing upstream energy ($M_{Alf}>\sim 20$),
shocks approach “full reflection” $n_{RI}/n_{U}\sim 1$, or when there are
equal or even more ion densities reflected from the shock than there are ions
in the far upstream and pristine solar wind. This effect is known as the
precursor effect and is discussed in more details in Figure 6. The
$n_{RI}/n_{U}\sim 1$ threshold explains the flattening of the magnetic
amplification rate observed in Figure 2. The ion reflection rates shown in
Figure 3 are much higher than the predictions of analytical models (Leroy et
al., 1982; Wilkinson & Schwartz, 1990). While such models also predict that
the ion reflection rate increases with Mach number, they limit the reflection
rate at $\sim 0.2$ times the upstream plasma density. The reflection rate in
these models is highly sensitive to the adiabatic index chosen in the Rankine-
Hugoniot relations. The constant reflection rate of 0.2, and in some cases
values as high as 0.5, is routinely adopted in theoretical studies of kinetic
effects and instabilities at collisionless shocks (Matsukiyo & Scholer, 2003).
Changes to this parameter can modify the solution to the dispersion relation,
the amount of cross field current, and estimates of the instability growth
rates upstream of the shock.

Figure 4: Reflected ion temperatures as a function of upstream ion plasma
temperature. Both axes are in units of electron-volt (eV). The linear fit
(blue line) and the $95\%$ confidence intervals (red lines) are overplotted.
The fitting function is annotated in blue on the top of the figure. RI
temperatures can only be obtained for “RI Track” events.

The data points in Figure 3 are color-coded by the upstream plasma
temperature, indicating higher Mach number shocks are observed at colder solar
wind plasmas. Some instabilities upstream of the shock are caused by
temperature anisotropy caused by RIs that gyrate perpendicular to the magnetic
field. We show the dependence of the RI beam temperature on the upstream
plasma temperature in Figure 4. RI temperatures are much higher than the
upstream ion beam temperature. The first order linear fit shows the following
relationship between the RI temperature and the upstream plasma temperature:

$T_{RI}=7.8T_{U}+20.0[eV]$ (5)

The fit function and $95\%$ intervals are shown on Figure 4. The R2 goodness-
of-fit is 0.506. Several factors contribute to such high RI temperatures. Ion
reflection is not necessarily always specular, and the spread of the reflected
ion beam can change due to non-specular reflection. Especially at high Mach
numbers, where upstream magnetic perturbations change the morphology of the
shock surface (Krasnoselskikh et al., 2002), some ions are non-specularly
reflected or scattered upon reflection. In addition, non-local ion reflection
and extended trajectory of RIs upstream of the shock further increases the
velocity spread of RIs (Gedalin, 2023; Madanian et al., 2023).

While there seems to be a good correlation between the temperature of RIs and
the upstream plasma temperature, we find no relationship between the RI
temperature and the magnetic amplification rate. We see a strong correlation
(not shown) between the magnetic amplification rates and the upstream Mach
number, as has been shown in previous observational and analytical studies
(Russell et al., 1982; Sulaiman et al., 2015; Fraschetti, 2013; Bell, 2013).
In addition, magnetic amplification increases with the increase in the
normalized drift speed of RIs
$v_{d}=(|\textbf{{V}}_{U}-\textbf{{V}}_{RI}|)/v_{Alf}$. These correlations
lead to the fact that the magnetic field amplification is strongly driven by
the ratio of upstream dynamic pressure to the magnetic pressure, a parameter
also known as the inverse of the magnetization parameter of the upstream
plasma ($1/\sigma$,):

$1/\sigma=P_{Dyne.}/P_{B}=\frac{\mu_{0}\rho V_{U}^{2}}{B_{U}^{2}}$ (6)

Figure 5: Magnetic amplification rate as a function of $P_{Dyne.}/P_{B}$
($1/\sigma$). Data points are color-coded by the upstream plasma temperature.
Events with low upstream plasma temperatures occur in weaker magnetic field
strengths.

The dependence of the magnetic amplification rate on inverse magnetization (or
$M_{Alf}^{2}$) is shown in Figure 5, where a strong positive correlation
between the two parameters is observed.

Increase in the RI drift speed and decrease in magnetization result in a
larger ion gyroradius and a larger foot region to be transversed by ions. With
decreasing magnetization, RIs can propagate farther upstream of the shock.
Therefore, instabilities that they generate have more time to develop and
waves have time to steepen as they traverse the foot, much like upstream waves
in the foreshock region of quasi-parallel shocks (Chen et al., 2022, 2021).
Interestingly, theoretical studies of relativistic shocks have argued that for
low upstream magnetization, the magnetic field perturbation and the flux of
cosmic rays generated at $Q_{\perp}$ shocks can be derived using the same
formalism as that used for quasi-parallel shocks (Bell et al., 2018; Sironi et
al., 2013).

As shown in Figures 2 and 3, some events exhibit significant ion reflection
rates $n_{RI}/n_{U}>1$. This may seem to violate the conservation of particle
flux at the shock. To validate our methodology, we perform a series of
particle-in-cell simulations to examine the density ratio of RIs (Winske &
Quest, 1988). The simulation conditions are listed in Table 1. The model
discussed here combines a fully-kinetic particle-in-cell treatment of the ions
with a charge-neutralizing, massless and isothermal electron fluid. The
electromagnetic fields and particle moments are advanced using Maxwell’s
equations in the low-frequency limit using the ’current advance method-cyclic
leapfrog’ (CAM-CL) algorithm (Matthews, 1994). The code is otherwise adapted
from the particle-in-cell code EPOCH (Arber et al., 2015). We use a 2D grid of
size $(N_{x},N_{y})=(2400,160)$ and resolution $\Delta x,y=0.15d_{i}$, where
$d_{i}$ is the upstream ion inertial length. The model is “2.5D” such that all
three vector components electromagnetic fields and particle moments may vary
on the two-dimensional grid, e.g. $B_{x,y,z}(x,y,t)$. The boundary conditions
are periodic at the upper and lower edges in $y$-direction, reflecting at the
downstream edge, and a source of inflowing solar wind plasma is generated at
the upstream edge. The interaction of the flow with the reflecting boundary
generates a shock moving in the $-x$ direction. The initial upstream
conditions are uniform with normalized number density $n_{0}$, magnetic field
$\mathbf{B}=B_{U}[-\cos(\theta_{Bn}),\sin(\theta_{Bn}),0]$, and solar wind
inflow velocity $\mathbf{V}=[V_{U},0,0]$. The ions and electron fluid are
initialized with plasma beta $\beta_{i}=0.5$ and $\beta_{e}=1.1$. In order to
reduce the noise as far as possible, we sample the ion phase space with 200
pseudo-particles per cell.

We determine the density ratio of RIs by examining individual ion trajectories
in the simulations. An ion is labeled as reflecting if it occupies the region
of phase space defined by $(v_{i,x}-v_{sh})^{2}+v_{i,z}^{2}>v_{sh}^{2}$ while
upstream of the shock ramp. The ion velocities $v_{i,x}$ and $v_{i,z}$ and
shock velocity $v_{sh}$ are given in the downstream frame. We then find the
density ratio by comparing the number of reflecting ions $n_{p,ref}$ to the
number of inflowing ions $n_{p,SW}$. This analysis is performed for all times
after $t=5\Omega_{i}^{-1}$ so that the shock structure is well-developed and
unaffected by the downstream reflecting boundary.

The time-averaged density ratios as a function of distance from the shock ramp
is shown in Figure 6. In Panel (a), showing the U6T65 case, we observe an
increase of the density of the inflowing ions up to $\sim 1d_{i}$ upstream of
the shock ramp. This is due to the solar wind beam slowing down (and therefore
compressing) in the shock foot. We also note that, for this case, the density
of reflected ions is higher than the density of inflowing ions for
$x<0.5d_{i}$, which is what we observe in MMS data for some shock crossings.
In Panel (b) we compare the RI density ratios for all simulation runs.
Generally, we observe higher densities of RIs for higher Mach numbers near the
shock ramp, which supports our approach in selecting the representative RI
density closest to the shock in time series data. In comparing runs U6T65
(orange) and U6T80 (brown) we find that the shock orientation $\theta_{Bn}$
does not strongly affect the density of RIs. We also note that at higher shock
speeds and when $\theta_{Bn}$ approaches the quasi-parallel regime, a small
fraction of RIs become back-streaming ions and escape the simulation box.

Table 1:  Shock parameters for the set of simulations described in this study, including inflow speed $V_{U}$, $M_{A}lf$ and $\theta_{Bn}.$ ID | $V_{U}/v_{Alf}$ | $M_{Alf}$ | $\theta_{Bn}(^{\circ})$
---|---|---|---
U3T65 | 3.0 | 3.2 | 65
U6T65 | 6.0 | 6.5 | 65
U9T65 | 9.0 | 9.7 | 65
U12T65 | 12.0 | 12.8 | 65
U6T50 | 6.0 | 6.5 | 50
U6T80 | 6.0 | 6.5 | 80
Figure 6:  Simulation results for the density of reflected ions $n_{p,ref}$
normalized by the mean upstream solar wind density $\left<n_{p,SW}\right>$, as
a function of distance $x$ upstream of the shock ramp. Panels are as follows:
(a) Comparison of the density of reflected ions to the density of inflowing
solar wind ions for the run U6T65, (b) Comparison of the normalized density of
reflected ions for all of the simulations, and (c) Magnetic field strength in
the shock layer for run U6T65 at a single timestep, showing upstream
enhancements and non-planar shock morphology.

##  4 Discussions and Conclusion

Magnetic amplification at quasi-perpendicular shocks is an energy conversion
problem. We address factors involved in field amplification from an ion
kinetic perspective. We use in-situ spacecraft observations during 222
crossings of the Earth’s $Q_{\perp}$ bow shock to quantify the ion reflection
and magnetic amplification over a wide range of upstream conditions. The
upstream Alfvén Mach number in these events varies between 3.1 and 53.9, the
upstream plasma temperature is in the 0.9 – 45.1 eV range, the upstream flow
speed relative to the shock varies between 296.0 and 748.8 kms-1, the upstream
magnetic field strengths range between 0.8 and 12.6 nT, while the
magnetization varies between $3.51\times 10^{-4}$ and 0.07 across all events.

Increase in the abundance of RIs contributes to magnetic amplification up to a
certain limit. Both magnetic amplification and ion reflection increase with
upstream Mach number till the full reflection condition is reached. We find
that the magnetic amplification rates are closely correlated with RI drift
speed, and decreasing magnetization in the upstream plasma. All these factors
result in a larger ion gyroradius and creating a larger foot region upstream
of a $Q_{\perp}$ shock. Ions can propagate farther upstream as the
magnetization decreases to create magnetic perturbations that are steepended
across the foot and contribute to higher magnetic amplification.

The density of RIs upstream of $Q_{\perp}$ shocks can be substantially higher
than previous analytical estimates. Our simulations in Figure 6 indicates that
very close to the shock layer, the solar wind beam itself experiences signs of
compression and increased beam density from the pristine conditions. In other
words, the nature of the upstream conditions (Mach number, plasma beta, etc.)
just upstream of the shock ramp intermittently changes. While non-negligible
momentum and current density are carried by RIs away from the shock which can
induce a response in the incident solar wind beam, waves and magnetic
structures that develop upstream of the shock, as shown in Panel (c), interact
with the incident ions and tend to create momentary compression in the flow
close to the shock ramp.

This precursor effect (not to be confused with the whistler precursor) is
likely transient and localized within the region of intense ion reflection,
and will evolve as the ion reflection rate adjusts to the new conditions. The
effect can be viewed as the shock’s attempt to intermittently change the local
upstream plasma in order to process the upstream energy; or as an extended
shock transition region beyond the shock ramp where plasma heating lags
compression, and heating of the solar wind is mainly through dissipation of
ions rather than resistive processes. Such an understanding of shocks has not
been realized in previous spacecraft observations, as the required time
resolution to detect this effect has only become available recently through
MMS observations. We see enhanced densities of RIs ($n_{RI}/n_{U}>1$) in both
types of events, “RI Track” and “SW Subtract”, though there are more events
under the latter category. Because of the way “SW Subtract” events are
analyzed, RI densities under this category can still have some contamination
from other populations.

The upper limit of the Mach numbers reported here is close to Mach numbers
expected at supernova remnant shocks ($M_{Alf}\sim 50$) (Caprioli &
Spitkovsky, 2013). The highest Mach number shocks in our analysis are observed
during upstream periods of very low magnetic field strength carried in a cold
plasma flow (i.e., low Alfvénic and sonic speeds). This indicates that to
study magnetic amplification at higher Mach numbers, spacecraft observations
of planetary bow shocks at larger heliocentric distances must be utilized. The
positive correlation between the interplanetary magnetic field strength and
the proton temperature is a characteristic of the expanding solar wind plasma
experiencing adiabatic cooling. As such, interpretation of changes in derived
parameters based simultaneously on the upstream magnetic field strength and
the ion temperature, such as plasma $\beta$, should be taken with caution. A
highly dense, cold, and weakly magnetized solar wind plasma can have a $\beta$
value similar to a hot and moderately magnetized solar wind, though the shock
profile will be vastly different between the two cases.

There are only a few low Mach number shocks in our dataset despite such shocks
being readily accessible at the Earth’s bow shock. Although theoretically
shocks become supercritical and begin reflecting ions to dissipate energy at
$M_{Alf}\sim 2.7$ and above (Marshall, 1955), ion reflection at such low Mach
numbers is rather sparse and difficult to detect even in high resolution data.
Further, for $M_{Alf}$ below the critical whistler Mach number,
$M_{wh}=1/2\sqrt{m_{p}/m_{e}}\cdot cos(\theta_{Bn})$ where $m_{e}$ is the
electron mass, shock generated whistler waves can phase stand upstream of the
shock, interact with and scatter both the solar wind beam ions and RIs
(Krasnoselskikh et al., 2002). This makes it difficult to isolate either
populations.

We finally emphasize that such high magnetic amplification rates reported in
this study are not typically expected at $Q_{\perp}$ shock observations, and
is hardly achieved in the numerical shock analysis. For instance, in 2D PIC
simulations of a perpendicular shock with upstream magnetization of $6\times
10^{-5}$ ($M_{Alf}\sim 130$), a magnetic amplification of only a factor of 15
was achieved (Kato & Takabe, 2010). In-situ observations reported here provide
a quantitative measure of the relationship between ion reflection and magnetic
field enhancement rates under various upstream conditions. Our observations
show that magnetic amplification at $Q_{\perp}$ shocks propagating in weakly
magnetized plasmas is comparable to those at quasi-parallel shocks.

We thank Y. Khotyaintsev for useful discussions. This work was supported in
part by the MMS project Early Career Program through the National Aeronautics
and Space Administration (NASA) grant number 80NSSC23K0009. I. Gingell is
supported by the Royal Society University Research Fellowship URF\R1\191547.
All data used in this study are hosted by NASA and are publicly accessible at
https://spdf.gsfc.nasa.gov/pub/data/mms. The Space Physics Environment Data
Analysis Software (SPEDAS) used in this work is publicly available at
http://spedas.org

##  Appendix A Supplementary Figures

Examples of shock crossings for each analysis type are shown in Figures 7 and
8 in this section.

Figure 7: Examples of shock crossings for “RI Track” (left) and “SW Subtract”
(right) analysis methods. An example of spacecraft measurements of a quasi-
perpendicular shock for which we track the reflected ions (“RI Track”) in the
FPI FOV. Panels show time series data of: a) magnetic field strength and
components in GSE coordinates, b) ion energy flux spectrogram, c) ion energy
flux in the polar angle ($\theta$) in the FPI FOV, and d) ion energy flux
along the azimuth $\phi$. The shock layer is at 16:43:55 UT. On panel c we
mark the FOV angles associated with RIs with white rectangles, which are used
in calculation of partial moments. The solar wind beam is evident at
$\theta\sim 0^{\circ}$. Figure 8: An example of spacecraft measurements of a
quasi-perpendicular shock for which we track the solar wind beam and subtract
it from the total ion density to obtain the reflected ion densities (“SW
Subtract”). The format of the figure is similar to 7. The shock layer is at
12:01:06 UT for this event. A substantial overlap between the solar wind ion
beam and non-solar wind ions is evident in panels c and d. On panel d we mark
the angles associated with the solar wind beam with white dashed rectangles,
which are used in calculation of partial moments.

## References

  * Arber et al. (2015) Arber, T. D., Bennett, K., Brady, C. S., et al. 2015, Plasma Physics and Controlled Fusion, 57, 113001, doi: 10.1088/0741-3335/57/11/113001
  * Bell (2013) Bell, A. 2013, Astroparticle Physics, 43, 56, doi: 10.1016/j.astropartphys.2012.05.022
  * Bell (2004) Bell, A. R. 2004, Monthly Notices of the Royal Astronomical Society, 353, 550, doi: 10.1111/j.1365-2966.2004.08097.x
  * Bell et al. (2018) Bell, A. R., Araudo, A. T., Matthews, J. H., & Blundell, K. M. 2018, Monthly Notices of the Royal Astronomical Society, 473, 2364, doi: 10.1093/mnras/stx2485
  * Blandford & Ostriker (1978) Blandford, R. D., & Ostriker, J. P. 1978, The Astrophysical Journal, 221, L29, doi: 10.1086/182658
  * Bohdan et al. (2021) Bohdan, A., Pohl, M., Niemiec, J., et al. 2021, Physical Review Letters, 126, 095101, doi: 10.1103/PhysRevLett.126.095101
  * Buneman (1958) Buneman, O. 1958, Physical Review Letters, 1, 8, doi: 10.1103/PhysRevLett.1.8
  * Burch et al. (2016) Burch, J. L., Moore, T. E., Torbert, R. B., & Giles, B. L. 2016, Space Science Reviews, 199, 5, doi: 10.1007/s11214-015-0164-9
  * Burgess et al. (2016) Burgess, D., Hellinger, P., Gingell, I., & Trávníček, P. M. 2016, Journal of Plasma Physics, 82, 905820401, doi: 10.1017/S0022377816000660
  * Caprioli & Spitkovsky (2013) Caprioli, D., & Spitkovsky, A. 2013, The Astrophysical Journal, 765, L20, doi: 10.1088/2041-8205/765/1/L20
  * Chen et al. (2021) Chen, L., Wang, S., Ng, J., et al. 2021, Geophysical Research Letters, 48, doi: 10.1029/2020GL090800
  * Chen et al. (2022) Chen, L., Halekas, J., Wang, S., et al. 2022, Geophysical Research Letters, doi: 10.1029/2021GL097600
  * Dimmock et al. (2012) Dimmock, A. P., Balikhin, M. A., Krasnoselskikh, V. V., et al. 2012, Journal of Geophysical Research: Space Physics, 117, doi: 10.1029/2011JA017089
  * Donnert et al. (2018) Donnert, J., Vazza, F., Brüggen, M., & ZuHone, J. 2018, Space Science Reviews, 214, 122, doi: 10.1007/s11214-018-0556-8
  * Farris & Russell (1994) Farris, M. H., & Russell, C. T. 1994, Journal of Geophysical Research, 99, 17681, doi: 10.1029/94JA01020
  * Fraschetti (2013) Fraschetti, F. 2013, The Astrophysical Journal, 770, 84, doi: 10.1088/0004-637X/770/2/84
  * Fried (1959) Fried, B. D. 1959, The Physics of Fluids, 2, 337, doi: 10.1063/1.1705933
  * Gedalin (1997) Gedalin, M. 1997, Surveys in Geophysics, 18, 541, doi: 10.1023/A:1006509702173
  * Gedalin (2019) —. 2019, The Astrophysical Journal, 880, 140, doi: 10.3847/1538-4357/ab2bee
  * Gedalin (2023) —. 2023, Journal of Plasma Physics, 89, 905890416, doi: 10.1017/S0022377823000831
  * Ji et al. (2016) Ji, S., Oh, S. P., Ruszkowski, M., & Markevitch, M. 2016, Monthly Notices of the Royal Astronomical Society, 463, 3989, doi: 10.1093/mnras/stw2320
  * Kato & Takabe (2010) Kato, T. N., & Takabe, H. 2010, The Astrophysical Journal, 721, 828, doi: 10.1088/0004-637X/721/1/828
  * King & Papitashvili (2005) King, J. H., & Papitashvili, N. E. 2005, Journal of Geophysical Research: Space Physics, 110, 2004JA010649, doi: 10.1029/2004JA010649
  * Krasnoselskikh et al. (2002) Krasnoselskikh, V., Lembège, B., Savoini, P., & Lobzin, V. V. 2002, Physics of Plasmas, 9, 1192, doi: 10.1063/1.1457465
  * Lalti et al. (2022) Lalti, A., Khotyaintsev, Y. V., Dimmock, A. P., et al. 2022, Journal of Geophysical Research: Space Physics, 127, e2022JA030454, doi: 10.1029/2022JA030454
  * Leroy et al. (1982) Leroy, M. M., Winske, D., Goodrich, C. C., Wu, C. S., & Papadopoulos, K. 1982, Journal of Geophysical Research: Space Physics, 87, 5081, doi: 10.1029/JA087iA07p05081
  * Madanian et al. (2021a) Madanian, H., Schwartz, S. J., Fuselier, S. A., et al. 2021a, The Astrophysical Journal Letters, 915, L19, doi: 10.3847/2041-8213/ac0aee
  * Madanian et al. (2020) Madanian, H., Schwartz, S. J., Halekas, J. S., & Wilson III, L. B. 2020, Geophysical Research Letters, 47, doi: 10.1029/2020GL088309
  * Madanian et al. (2021b) Madanian, H., Desai, M. I., Schwartz, S. J., et al. 2021b, The Astrophysical Journal, 908, 40, doi: 10.3847/1538-4357/abcb88
  * Madanian et al. (2023) Madanian, H., Omidi, N., Sibeck, D. G., et al. 2023, Geophysical Research Letters, 50, e2022GL101734, doi: 10.1029/2022GL101734
  * Marcowith et al. (2016) Marcowith, A., Bret, A., Bykov, A., et al. 2016, Reports on Progress in Physics, 79, 046901, doi: 10.1088/0034-4885/79/4/046901
  * Marshall (1955) Marshall, W. 1955, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 233, 367, doi: 10.1098/rspa.1955.0272
  * Matsukiyo & Scholer (2003) Matsukiyo, S., & Scholer, M. 2003, Journal of Geophysical Research: Space Physics, 108, 1459, doi: 10.1029/2003JA010080
  * Matthews (1994) Matthews, A. P. 1994, Journal of Computational Physics, 112, 102, doi: 10.1006/jcph.1994.1084
  * Pollock et al. (2016) Pollock, C., Moore, T., Jacques, A., et al. 2016, Space Science Reviews, 199, 331, doi: 10.1007/s11214-016-0245-4
  * Russell et al. (1982) Russell, C. T., Hoppe, M. M., & Livesey, W. A. 1982, Nature, 296, 45, doi: 10.1038/296045a0
  * Russell et al. (2016) Russell, C. T., Anderson, B. J., Baumjohann, W., et al. 2016, Space Science Reviews, 199, 189, doi: 10.1007/s11214-014-0057-3
  * Schwartz et al. (2022) Schwartz, S. J., Goodrich, K. A., Wilson, L. B., et al. 2022, Journal of Geophysical Research: Space Physics, 127, e2022JA030637, doi: 10.1029/2022JA030637
  * Sckopke et al. (1983) Sckopke, N., Paschmann, G., Bame, S. J., et al. 1983, Journal of Geophysical Research, 88, 6121, doi: 10.1029/JA088iA08p06121
  * Shue et al. (1998) Shue, J.-H., Song, P., Russell, C. T., et al. 1998, Journal of Geophysical Research: Space Physics, 103, 17691, doi: 10.1029/98JA01103
  * Sironi et al. (2013) Sironi, L., Spitkovsky, A., & Arons, J. 2013, The Astrophysical Journal, 771, 54, doi: 10.1088/0004-637X/771/1/54
  * Sulaiman et al. (2015) Sulaiman, A., Masters, A., Dougherty, M., et al. 2015, Physical Review Letters, 115, doi: 10.1103/PhysRevLett.115.125001
  * Weibel (1959) Weibel, E. S. 1959, Physical Review Letters, 2, 83, doi: 10.1103/PhysRevLett.2.83
  * Wilkinson & Schwartz (1990) Wilkinson, W., & Schwartz, S. 1990, Planetary and Space Science, 38, 419, doi: 10.1016/0032-0633(90)90108-3
  * Winske & Quest (1988) Winske, D., & Quest, K. B. 1988, Journal of Geophysical Research, 93, 9681, doi: 10.1029/ja093ia09p09681