by an edge (so that the graphs are not bipartite), and for each such edge
$(v_{1},v_{2})$, there are two vertices $u_{1}$ and $u_{2}$ in $Y_{b}$, such
that $u_{1}$ neighbors $v_{1}$ and $u_{2}$ neighbors $v_{2}$.

In $G_{0}$, every pair of vertices $u_{1},u_{2}$ in $Y_{0}$ either neighbor a
unique vertex $v_{0}$ in $X_{0}$ or there is a unique edge $(v_{1},v_{2})$
between a pair of vertices in $X_{0}$ such that $u_{1}$ neighbors $v_{1}$ and
$u_{2}$ neighbors $v_{2}$. On the other hand, in $G_{1}$, edge-disjoint
$C_{5}$s are created by having the same pair $u_{1},u_{2}$ in $Y_{1}$ neighbor
both a single vertex $v_{0}$ and the endpoints of an edge $(v_{1},v_{2})$ as
described above, so that $(v_{0},u_{1},v_{1},v_{2},u_{2})$ is a $C_{5}$.

##  Appendix D An upper bound for $C_{6}$

In this section we prove Theorem 11, which is restated next.

###### Theorem 11

There exists a one-sided error algorithm for testing $C_{6}$-freeness in
graphs of constant arboricity whose query complexity and running time are
$\tilde{O}(n^{1/2}\cdot{\rm poly}(1/\epsilon))$.

The algorithm referred to in Theorem 11 is presented next.

Test-$C_{6}$-freeness($n,\epsilon,\alpha$)

  1. 1.

Let $\theta_{0}=4\alpha/\epsilon$, and $\theta_{1}=c_{1}\cdot
n^{1/2}\log^{2}n/\epsilon^{2}$ (for a sufficiently large constant $c_{1}$).

  2. 2.

Repeat the following $t=\textrm{poly}(\log n/\epsilon)$ times:

    1. (a)

Select a vertex $v$ uniformly at random and query its degree. If
$d(v)>\theta_{0}$, then continue to the next iteration.

    2. (b)

Perform a _restricted_ BFS starting from $v$ to depth $4$, where the BFS is
restricted in the following sense.

      1. i.

Whenever a vertex $u$ is reached such that $d(u)\leq\theta_{0}$, all its
neighbors are queried.

      2. ii.

Whenever a vertex $u$ is reached such that $d(u)>\theta_{0}$ and $u$ is
reached from a vertex $u^{\prime}$ such that $d(u^{\prime})\leq\theta_{0}$,
there are two sub-cases. If $d(u)\leq\theta_{1}$, then all of $u$’s neighbors
are queried. Otherwise, $\theta_{1}$ neighbors of $u$ are selected uniformly
at random.

      3. iii.

Whenever a vertex $u$ is reached from a vertex $u^{\prime}$ such that both
$d(u)>\theta_{0}$ and $d(u^{\prime})>\theta_{0}$, the BFS does not continue
from $u$.

    3. (c)

If a $C_{6}$ is detected, then return ‘Reject’ (and terminate).

  3. 3.

Return ‘Accept’.

Since the algorithm rejects only when it detects a $C_{6}$, it always accepts
when the graph $G$ is $C_{6}$-free, and hence, from this point on, we focus on
the case that $G$ is $\epsilon$-far from $C_{6}$-free. Let ${\mathcal{C}}$ be
a maximal set of edge-disjoint $C_{6}$s in $G$ where for every $C_{6}$ in
${\mathcal{C}}$, there are no edges in which both endpoints have degree
greater than $\theta_{0}$ (where $\theta_{0}=4\alpha/\epsilon$, as defined in
the algorithm). Since the arboricity of $G$ is at most $\alpha$, we have that
$|{\mathcal{C}}|\geq\epsilon m/12$.

Let $L$ denote the set of vertices with degree at most $\theta_{0}$, let $M$
denote the vertices with degree greater than $\theta_{0}$, and let $H$ denote
those with degree greater than $\theta_{1}$ (where $L$ stands for _low_ , $M$
for _medium_ , and $H$ for _high_). We partition the $C_{6}$s in
${\mathcal{C}}$ into three subsets: ${\mathcal{C}}_{1}$ contains those with at
most one vertex in $M$, and for $b\in\\{2,3\\}$, ${\mathcal{C}}_{b}$ contains
those with exactly $b$ vertices in $M$. For each $b\in\\{1,2,3\\}$, we
consider the case that $|{\mathcal{C}}_{b}|\geq\epsilon m/36$, where for at
least one of the three this lower bound should hold.

###### Claim 7

If $|{\mathcal{C}}_{1}|\geq\epsilon m/36$, then the algorithm will detect a
$C_{6}$ with probability at least $2/3$.

Proof: Consider the following set of _useful_ vertices $U$. For each
$\rho\in{\mathcal{C}}_{1}$, if all vertices on $\rho$ belong to $L$, then they
all belong to $U$. If there is a vertex $u$ on $\rho$ that belongs to $M$,
then the vertex $v\in L$ at distance $3$ from $u$ (on $\rho$), belongs to $U$
(that is, the vertex $v$ that is opposite to $u$ on $\rho$). Since
$|{\mathcal{C}}_{1}|\geq\epsilon m/36$, and each vertex in $L$ belongs to at
most $\theta_{0}/2$ edge-disjoint $C_{6}$s in ${\mathcal{C}}_{1}$, we have
that $|U|=\Omega(\epsilon n)$. Therefore, with probability at least $2/3$,
some vertex $v\in U$ is selected in at least one of the iterations of the
algorithm. Conditioned on this event, the restricted BFS starting from $v$
will detect a $C_{6}$. $\Box$

###### Claim 8

If $|{\mathcal{C}}_{2}|\geq\epsilon m/36$, then the algorithm will detect a
$C_{6}$ with probability at least $2/3$.

Proof: Recall that ${\mathcal{C}}_{2}$ is the set of $C_{6}$s in
${\mathcal{C}}$ with exactly two vertices in $M$, i.e., that have degree
greater than $\theta_{0}$. We consider several sub-cases depending on the
number of these vertices that are also in $H$. Let ${\mathcal{C}}_{2,1}$
consists of those $C_{6}$s in ${\mathcal{C}}_{2}$ that contain at most one
vertex in $H$, and ${\mathcal{C}}_{2,2}$ those that contain two vertices in
$H$, and note that
${\mathcal{C}}_{2}={\mathcal{C}}_{2,1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}{\mathcal{C}}_{2,2}$
so that at least one of these subsets is of size at least
$|{\mathcal{C}}_{2}|/2$.

If $|{\mathcal{C}}_{2,1}|\geq|{\mathcal{C}}_{2}|/2$, then let $U$ denote those
vertices in $L$ that reside on $C_{6}$s in ${\mathcal{C}}_{2,1}$ that either
do not have any vertex in $H$, or are at distance at least two from the single
vertex in $H$ on the $C_{6}$. Similarly to the proof of Claim 7, the algorithm
selects a vertex from $U$ with probability at least $2/3$, and conditioned on
this event, a $C_{6}$ is detected.

We now turn to the case that $|{\mathcal{C}}_{2,2}|\geq|{\mathcal{C}}_{2}|/2$.
We further partition the $C_{6}$s in ${\mathcal{C}}_{2,2}$ according to the
distance on the $C_{6}$ between the two vertices in $H$, which is either $2$
or $3$, and denote the two subsets by ${\mathcal{C}}_{2,2,2}$ and
${\mathcal{C}}_{2,2,3}$, respectively. In what follows we analyze the case
that $|{\mathcal{C}}_{2,2,2}|\geq|{\mathcal{C}}_{2,2}|/2$. The case that
$|{\mathcal{C}}_{2,2,3}|\geq|{\mathcal{C}}_{2,2}|/2$, is analyzed similarly.

For each pair of vertices $u,u^{\prime}\in H$, let
${\mathcal{C}}(u,u^{\prime})$ denote the subset of $C_{6}$s in
${\mathcal{C}}_{2,2,2}$ on which $u$ and $u^{\prime}$ reside. We shall say
that the set ${\mathcal{C}}(u,u^{\prime})$ is _useful_ if
$|{\mathcal{C}}(u,u^{\prime})|\geq\frac{(\epsilon/600)\cdot\max\\{d(u),d(u^{\prime})\\}}{|H|}$,
otherwise it is _un-useful_. By this definition, the number of $C_{6}$s in
${\mathcal{C}}_{2,2,2}$ that belong to un-useful sets is at most

$\sum_{u\in H}\sum_{u^{\prime}\in H:d(u^{\prime})\leq
d(u)}\frac{(\epsilon/600)\cdot d(u)}{|H|}\leq\epsilon m/300\;.$ (23)

Let ${\mathcal{C}}^{\prime}_{2,2,2}$ denote the subset of $C_{6}$s in
${\mathcal{C}}_{2,2,2}$ that belong to useful sets, so that
$|{\mathcal{C}}^{\prime}_{2,2,2}|\geq\epsilon m/300$.

The algorithm “tries” to detect $C_{6}$s of this form by starting from a
vertex $v$ that is at distance $2$ from both $u$ and $u^{\prime}$ on some
$C_{6}$ in ${\mathcal{C}}(u,u^{\prime})$, and obtaining a path of length 2 and
a path of length 4 that collide on either $u$ or $u^{\prime}$. Assume w.l.o.g.
that $d(u^{\prime})\leq d(u)$. Recall that except for $u$ and $u^{\prime}$,
all other vertices on the $C_{6}$s in ${\mathcal{C}}(u,u^{\prime})$ are in
$L$. Therefore, a restricted BFS starting from $v$ will surely reach both $u$
and $u^{\prime}$ at depth 2. Then, for the algorithm to reach $u$ from
$u^{\prime}$ in two more steps, it suffices that one of their common neighbors
in $L$ is selected in Step 2(b)ii among the $\theta_{1}$ sampled random
neighbors of $u^{\prime}$. In such a case the restricted BFS will surely reach
$u$ via $u^{\prime}$, and thus obtain a $C_{6}$. Since the number of common
neighbors of $u$ and $u^{\prime}$ is at last $|{\mathcal{C}}(u,u^{\prime})|$,
the probability of this event is at least

$1-\left(1-\frac{(\epsilon/600)\cdot\max\\{d(u),d(u^{\prime})\\}}{|H|\cdot\min\\{d(u),d(u^{\prime})\\}}\right)^{\theta_{1}}\;.$

Since $|H|\leq 2m/\theta_{1}$, by the setting of $\theta_{1}$ (for a
sufficiently large constant $c_{1}$ and recalling that the graph has constant
arboricity, so that $m=O(n)$), this probability is at least $9/10$. Combining
this with the probability of the selection of some vertex $v$ in $L$ as
defined above (which occurs with probability $\Omega(\epsilon^{2})$), the
claim follows. $\Box$

###### Claim 9

If $|{\mathcal{C}}_{3}|\geq\epsilon m/36$, then the algorithm will detect a
$C_{6}$ with probability at least $2/3$.

Proof: Recall that by the definition of ${\mathcal{C}}_{3}$, for each $C_{6}$
in ${\mathcal{C}}_{3}$ there are three vertices that belong to $M$, and three
that belong to $L$, where each vertex in $M$ neighbors two vertices in $L$. We
start by selecting a subset of ${\mathcal{C}}_{3}$, denoted
${\mathcal{C}}_{3}^{\prime}$, such that each vertex in $L$ belongs to at most
a single $C_{6}$ in ${\mathcal{C}}_{3}^{\prime}$. Since each vertex in $L$ has
degree at most $\theta_{0}=O(1/\epsilon)$, if we select
${\mathcal{C}}_{3}^{\prime}$ in a simple iterative greedy manner, then we get
that $|{\mathcal{C}}_{3}^{\prime}|\geq\epsilon_{3}m$, where
$\epsilon_{3}=\Omega(\epsilon^{2})$. Let $M^{\prime}\subseteq M$ be the subset
of vertices in $M$ that reside on $C_{6}$s in ${\mathcal{C}}_{3}^{\prime}$ and
let $L^{\prime}\subseteq L$ be the corresponding subset of vertices in $L$.
Let the edges on the $C_{6}$s in ${\mathcal{C}}_{3}^{\prime}$ be colored green
in $G$.

We next define an auxiliary multi-graph $G^{\prime}$ where (some of the)
triangles in $G^{\prime}$ correspond to $C_{6}$s in $G$. For each vertex in
$M^{\prime}$ we have a vertex in $G^{\prime}$. In addition, there is a special
_ground_ vertex, which we denote by $v_{g}$. For each pair of vertices,
$u_{1},u_{2}\in M^{\prime}$ and for each length-2 green path $(u_{1},v,u_{2})$
(where $v\in L^{\prime}$), there is an edge in $G^{\prime}$. We think of this
edge as being colored blue in $G^{\prime}$ and labeled by the vertex $v$ in
$L^{\prime}$. In addition, for each $u\in M^{\prime}$, and each non-green
incident edge that it has in $G$, there is an (“uncolored”) edge between $u$
and $v_{g}$. By this construction, there are $|{\mathcal{C}}_{3}^{\prime}|$
blue edge-disjoint triangles in $G^{\prime}$ (and the degree of every vertex
$u\in M^{\prime}$ in $G^{\prime}$ is the same as its degree in $G$).

###### Claim 10

Let $G^{\prime}$ be a multigraph over $m^{\prime}\leq m$ edges, with
$m^{\prime}_{b}$ blue edges, and at least $\epsilon_{3}m$ edge-disjoint blue
triangles. Let $D$ be any distribution over edges in $G^{\prime}$ such that
for each blue edge in $G^{\prime}$, the probability that it is selected
according to $D$ is $\Omega(1/m^{\prime}_{b})$. Consider the following
process. First we select a blue edge $(u,u^{\prime})$ according to $D$. Next,
for each of $u$ and $u^{\prime}$, if its degree is at most $\theta_{1}$, then
we query all its neighbors in $G^{\prime}$, and otherwise we select
$\theta_{1}$ random neighbors in $G^{\prime}$. The probability that the
process obtains a triangle $(u,u^{\prime},u^{\prime\prime})$ in $G^{\prime}$
where $u^{\prime\prime}\in M^{\prime}$ is $\Omega(\epsilon_{3}/\log^{4}n)$.

Proof: Let ${\mathcal{T}}$ denote a maximal set of edge-disjoint triangles in
$G^{\prime}$ whose edges are all colored blue, so that
$|{\mathcal{T}}|\geq\epsilon_{3}m$. Let ${\mathcal{T}}_{1}$ denote the subset
of triangles in ${\mathcal{T}}$ that contain at most one vertex in $H$, and
let ${\mathcal{T}}_{2}$ denote those that contain at least two vertices in
$H$. If $|{\mathcal{T}}_{1}|\geq|{\mathcal{T}}|/2$, then we are done:
conditioned on selecting an edge between two vertices in $M^{\prime}\setminus
H$ that belongs to a triangle in ${\mathcal{T}}_{1}$, the procedure will
detect this triangle, as it queries all neighbors of the selected edge’s
endpoints, and the probability of selecting such an edge is
$\Omega(\epsilon_{3})$.

From this point on we address the case that
$|{\mathcal{T}}_{2}|\geq|{\mathcal{T}}|/2$. For a vertex $u\in M^{\prime}$ we
use $d(u)$ to denote its degree in $G^{\prime}$. For each pair of vertices
$u_{1},u_{2}\in M^{\prime}$, let $E(u_{1},u_{2})$ denote the set of edges
between $u_{1}$ and $u_{2}$ that reside on triangles in ${\mathcal{T}}_{2}$
(so that in particular, they are all blue), and let
$e(u_{1},u_{2})=|E(u_{1},u_{2})|$. Suppose the procedure described in the
claim selects an edge $(a,b)\in E(u_{1},u_{2})$ where $a,b\in H$. Recall that
in such a case, $\theta_{1}$ random neighbors of $a$ and $\theta_{1}$ random
neighbors of $b$ are sampled. For $i\in[\theta_{1}]$ and $j\in[\theta_{1}]$,
let $\chi_{i,j}(a,b)$ be a Bernoulli random variable that is $1$ if and only
if the $i$th randomly selected neighbor of $a$ equals the $j$th randomly
selected neighbor of $b$, where this neighbor is not $v_{g}$ (thus detecting a
blue triangle). Note that by this definition, the expected number of triangles
detected (conditioned on selecting $(a,b)$) is
$\sum_{i,j\in[\theta_{1}]}\chi_{i,j}(a,b)$, where

$\Pr[\chi_{i,j}(a,b)=1]=\sum_{c\in
M}\frac{e(a,c)}{d(a)}\cdot\frac{e(b,c)}{d(b)}\;.$ (24)

A simple but important observation is that, since each of the $e(a,b)$ edges
in $E(a,b)$ participates in some triangle $(a,b,c)$ in ${\mathcal{T}}_{2}$
where these triangles are edge-disjoint, $e(a,b)$ is upper bounded by
$\sum_{c\in M}\min\\{e(a,c),e(b,c)\\}$, which in turn is upper bounded by
$\sum_{c\in M}e(a,c)\cdot e(b,c)$. That is,

$\sum_{c\in M}e(a,c)\cdot e(b,c)\geq\sum_{c\in M}\min\\{e(a,c),e(b,c)\\}\geq
e(a,b)\;.$

Therefore,

$\Pr[\chi_{i,j}(a,b)=1]\geq\sum_{c\in M}\frac{e(a,b)}{d(a)\cdot d(b)}\;.$ (25)

We next show that there exists a relatively large set of edges between pairs
$(a,b)$ where $a,b\in H$, for which
$\Pr[\chi_{i,j}(a,b)=1]=\tilde{\Omega}(1/n)$. We shall refer to such pairs
$a,b$ as _useful_ pairs. This will imply that the expected number of triangles
detected when selecting an edge between one of these pairs is
$\tilde{\Omega}(\theta_{1}^{2}/n)$. By the setting of $\theta_{1}$, this is
greater than 1. Our definition of this set of useful pairs will also ensure
that the variance is bounded, allowing us to deduce that a triangle is
detected with sufficiently high probability. Details follow.

We start by partitioning the set ${\mathcal{T}}_{2}$ into subsets as follows.
First, for each triangle $\Delta\in{\mathcal{T}}_{2}$, we denote it by
$(a_{\Delta},b_{\Delta},c_{\Delta})$, where, without loss of generality,
$a_{\Delta},b_{\Delta}\in H$. For every four integers $x_{\tiny A},x_{\tiny
B},y_{\tiny A,C},y_{\tiny B,C}$, the subset ${\mathcal{T}}_{2}(x_{\tiny
A},x_{\tiny B},y_{\tiny A,C},y_{\tiny B,C})$ consists of all triangles
$\Delta\in{\mathcal{T}}_{2}$ for which the following holds.
$d(a_{\Delta})\in[2^{x_{\tiny A}-1}\cdot\theta_{1},2^{x_{\tiny
A}}\cdot\theta_{1})$, $d(b_{\Delta})\in[2^{x_{\tiny
B}-1}\cdot\theta_{1},2^{x_{\tiny B}}\cdot\theta_{1})$,
$e(a_{\Delta},c_{\Delta})\in[2^{y_{\tiny A,C}-1},2^{y_{\tiny A,C}})$, and
$e(b_{\Delta},c_{\Delta})\in[2^{y_{\tiny B,C}-1},2^{y_{\tiny B,C}})$. Let
${\mathcal{T}}^{*}_{2}={\mathcal{T}}_{2}(x^{*}_{\tiny A},x^{*}_{\tiny
B},y^{*}_{\tiny A,C},y^{*}_{\tiny B,C})$ be the largest subset, so that
$|{\mathcal{T}}^{*}_{2}|\geq\epsilon_{3}m/\log^{4}n$. Let
$A^{*}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{a_{\Delta}:\Delta\in{\mathcal{T}}^{*}_{2}\\}$ and
$B^{*}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{b_{\Delta}:\Delta\in{\mathcal{T}}^{*}_{2}\\}$. For each pair of
vertices $a\in A^{*}$ and $b\in B^{*}$, let $E^{*}(a,b)$ be the subset of
edges between $a$ and $b$ such that there exists
$\Delta\in{\mathcal{T}}^{*}_{2}$ for which $a=a_{\Delta}$ and $b=b_{\Delta}$,
let $e^{*}(a,b)=|E^{*}(a,b)|$ and let $C^{*}_{a,b}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{c_{\Delta}\,:\,a=a_{\Delta},b=b_{\Delta},\Delta\in{\mathcal{T}}^{*}_{2}\\}$.
We have:

$s^{*}\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{a\in A^{*},b\in
B^{*}}e^{*}(a,b)\geq\frac{\epsilon_{3}m}{\log^{4}n}\;,$ (26)

and for every $a\in A^{*}$ and $b\in B^{*}$, similarly to what was argued
before regarding $e(a,b)$,

$\sum_{c\in C^{*}(a,b)}e(a,c)\cdot e(b,c)\geq e^{*}(a,b)\;.$ (27)

Let

$P^{*}\stackrel{{\scriptstyle\rm def}}{{=}}\left\\{(a,b)\,:\,a\in A^{*},b\in
B^{*},e^{*}(a,b)\geq\frac{s^{*}}{2\cdot|A^{*}|\cdot|B^{*}|}\right\\}\;.$ (28)

Since

$\sum_{(a,b)\in A^{*}\times B^{*}\setminus
P^{*}}e^{*}(a,b)\leq|A^{*}|\cdot|B^{*}|\cdot\frac{s^{*}}{2\cdot|A^{*}|\cdot|B^{*}|}=s^{*}/2\;,$
(29)

by Equation (26),

$\sum_{(a,b)\in P^{*}}e^{*}(a,b)\geq\frac{\epsilon_{3}m}{2\log^{4}n}\;.$ (30)

By Equation (30) and the premise of the claim regarding $D$, if we select an
edge according to $D$, then the probability that we obtain an edge in
$E^{*}(a,b)$ for $(a,b)\in P^{*}$ is $\Omega(\epsilon_{3}/\log^{4}n)$. Fixing
any such pair $(a,b)$, we slightly modify the definition of the random
variables $\chi_{i,j}(a,b)$ so that $\chi_{i,j}(a,b)=1$ if and only if the
$i$th random sampled neighbor of $a$ and the $j$th random sampled neighbor of
$b$ are both a common neighbor $c\in C^{*}(a,b)$ (the original definition
allowed any common neighbor $c$ (other than $v_{g}$)). We next upper bound the
probability that $\sum_{i,j\in[\theta_{1}]}\chi_{i,j}(a,b)=0$. Let

$\mu(a,b)\stackrel{{\scriptstyle\rm def}}{{=}}\sum_{c\in
C^{*}(a,b)}\frac{e(a,c)}{d(a)}\cdot\frac{e(b,c)}{d(b)}\;,$ (31)

so that $\mathbb{E}[\chi_{i,j}(a,b)]=\Pr[\chi_{i,j}(a,b)=1]=\mu(a,b)$. Since
$(a,b)\in P^{*}$, by Equations (26)–(28),

$\mu(a,b)\geq\frac{e^{*}(a,b)}{d(a)\cdot
d(b)}\geq\frac{\epsilon_{3}m}{2\log^{4}n\cdot d(a)\cdot
d(b)\cdot|A^{*}|\cdot|B^{*}|}\geq\frac{\epsilon_{3}}{8\log^{4}n\cdot m}\;,$
(32)

where we have used the fact that $d(a)\cdot|A^{*}|\leq 2m^{\prime}\leq 2m$ and
$d(b)\cdot|B^{*}|\leq 2m^{\prime}\leq 2m$. From this point on we shall use the
shorthand $\chi_{i,j}$ for $\chi_{i,j}(a,b)$ and $\mu$ for $\mu(a,b)$.

At this point we would have liked to apply Corollary 16 to upper bound the
probability that $\sum_{i,j\in[\theta_{1}]}\chi_{i,j}=0$, but it does not
exactly meet our needs, and hence we give a direct proof. First we observe
that

$\mathbb{E}\left[\sum_{i,j\in[\theta_{1}]}\chi_{i,j}\right]=\theta_{1}^{2}\cdot\mu\;.$
(33)

By applying Claim 15 (see Appendix G), with $s_{1}=s_{2}=\theta_{1}$ and using
the notation $\mu_{1,2}=\Pr[\chi_{i,j_{1}}=\chi_{i,j_{2}}=1]$ (for every
$i,j_{1},j_{1}\in[\theta_{1}]$) and
$\mu_{2,1}=\Pr[\chi_{i_{1},j}=\chi_{i_{2},j}=1]$ (for every
$i_{1},i_{2},j\in[\theta_{1}]$) from that claim, we have that

$\mathbb{V}\left[\sum_{i,j\in[\theta_{1}]}\chi_{i,j}\right]\leq\theta_{1}^{2}\cdot\mu+\theta_{1}^{3}\cdot\mu_{1,2}+\theta_{1}^{3}\cdot\mu_{2,1}+{\theta_{1}\choose
2}^{2}\cdot\mu^{2}-(\theta_{1}^{2}\cdot\mu)^{2}\;.$ (34)

By Chebishev’s inequality and the above two equations,

$\Pr\left[\sum_{i,j\in[\theta_{1}]}\chi_{i,j}=0\right]\leq\frac{\mathbb{V}\left[\sum_{i,j\in[\theta_{1}]}\chi_{i,j}\right]}{\left(\mathbb{E}\left[\sum_{i,j\in[\theta_{1}]}\chi_{i,j}\right]\right)^{2}}\leq\frac{1}{\theta_{1}^{2}\mu}+\frac{\mu_{1,2}}{\theta_{1}\cdot\mu^{2}}+\frac{\mu_{2,1}}{\theta_{1}\cdot\mu^{2}}\;.$
(35)

We next upper bound each of the three terms on the right-hand-side of Equation
(35).

By Equation (32) and the setting of $\theta_{1}=c_{1}\cdot
n^{1/2}\log^{2}n/\epsilon^{2}$, the first term contributes at most $1/6$ (for
a sufficiently large constant $c_{1}$).

Turning to the second term,

$\mu_{1,2}=\Pr[\chi_{i,j_{1}}=\chi_{i,j_{2}}=1]=\sum_{c\in
C^{*}(a,b)}\frac{e(a,c)\cdot(e(b,c))^{2}}{d(a)\cdot(d(b))^{2}}\;.$ (36)

By the definition of $\mu$ in Equation (31) and again using Equations
(26)–(28), the second term is upper bounded by

$\displaystyle\frac{1}{\theta_{1}}\cdot\frac{d(a)\cdot\sum_{c\in
C^{*}(a,b)}e(a,c)\cdot(e(b,c))^{2}}{\left(\sum_{c\in C^{*}(a,b)}e(a,c)\cdot
e(b,c)\right)^{2}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{\theta_{1}}\cdot\frac{d(a)\cdot|C^{*}(a,b)|\cdot
2^{y^{*}_{\tiny A,C}}\cdot 2^{2y^{*}_{\tiny B,C}}}{|C^{*}(a,b)|^{2}\cdot
2^{2(y^{*}_{\tiny A,C}-1)}\cdot 2^{2(y^{*}_{\tiny B,C}-1)}}$ (37)
$\displaystyle=$
$\displaystyle\frac{1}{\theta_{1}}\cdot\frac{16d(a)}{|C^{*}(a,b)|\cdot
2^{y^{*}_{\tiny A,C}}}$ (38) $\displaystyle\leq$
$\displaystyle\frac{1}{\theta_{1}}\cdot\frac{16d(a)}{e^{*}(a,b)}$ (39)
$\displaystyle\leq$
$\displaystyle\frac{1}{\theta_{1}}\cdot\frac{8\log^{4}n\cdot
d(a)\cdot|A^{*}|\cdot|B^{*}|}{\epsilon_{3}m}$ (40) $\displaystyle\leq$
$\displaystyle\frac{16\log^{4}n\cdot|B^{*}|}{\epsilon_{3}\theta_{1}}\;.$ (41)

Since $|B^{*}|\leq 2m/\theta_{1}$ (as $B^{*}\subseteq H$), by the setting of
$\theta_{1}$, the contribution of this term is at most $1/6$ as well.

For the third term we have that

$\mu_{2,1}=\Pr[\chi_{i_{1},j_{1}}=\chi_{i_{1},j_{2}}]=\sum_{c\in
C^{*}(a,b)}\frac{(e(a,c))^{2}\cdot e(b,c)}{d(a)\cdot d(b)}\;.$ (42)

By essentially the same argument as the one bounding the second term
(replacing the roles of $a$ and $b$ ($A^{*}$ and $B^{*}$), this term
contributes at most $1/6$ as well.

We have thus shown that, conditioned on selecting an edge between a pair
$(a,b)\in P^{*}$, the probability that we obtain a triangle is at least $1/2$,
and Claim 10 follows. $\Box$

In order to complete the proof of Claim 9 by applying Claim 10, we make the
following observations. First, by the construction of $G^{\prime}$, each
vertex in $L^{\prime}$ corresponds to exactly one blue edge in $G^{\prime}$.
In particular, if we select a vertex in $L^{\prime}$ and query all its
neighbors (as done in the algorithm), then we effectively obtain an edge in
$G^{\prime}$. Since $|{\mathcal{C}}_{3}^{\prime}|=\Omega(\epsilon^{2}m)$, we
have that $|L^{\prime}|=\Omega(\epsilon^{2}n)$. Therefore, the probability in
each iteration that the algorithm selects a vertex in $L^{\prime}$, and hence
an edge in $G^{\prime}$, is $\Omega(\epsilon^{2})$.

Next, consider each of the endpoints $u$ of such an edge. If
$d(u)\leq\theta_{1}$, then our algorithm queries all the neighbors of $u$, and
for each neighbor $v$ of $u$ such that $d(v)\leq\theta_{0}$, the algorithm
queries all the neighbors of $v$. This implies that the algorithm reaches all
of the neighbors $u^{\prime}\in M^{\prime}$ of $u$ in $G^{\prime}$ (as in the
corresponding case described in Claim 10). Similarly, if $d(u)>\theta_{1}$,
then our algorithms samples $\theta_{1}$ random neighbors of $u$, and for each
sampled neighbor $v$ such that $d(v)\leq\theta_{0}$, it queries all the
neighbors of $v$. This implies that for every $u^{\prime}\in M^{\prime}$, the
probability that it is reached from $u$ by such a length-2 path in $G$, is at
least as large as the probability that it is reached in one random step from
$u$ in $G^{\prime}$. Since blue triangles in $G^{\prime}$ correspond to
$C_{6}$s in $G$, Claim 9 follows. $\Box$

The proof of Theorem 11 follows directly from Claims 7–9 (together with the
description of the algorithm for obtaining the upper bound on the complexity
of the algorithm).

##  Appendix E A lower bound of $\Omega(n^{1/3})$ for all constant-length
cycles

For the ease of readability, we first restate Theorem 2

Theorem 2 _Let $k\geq 6$. Any one-sided error tester for the property of
$C_{k}$-freeness in graphs of constant arboricity over $n$ vertices must
perform $\Omega(n^{1/3})$ queries. _

As noted in the introduction, the lower bound stated in Theorem 2 also applies
to graphs with non-constant arboricity by adding a $C_{k}$-free subgraph with
higher arboricity. For an odd $k$, it suffices to add a dense bipartite graph,
and for even $k$, by the Erdős girth conjecture [16], one can add a subgraph
with arboricity $n^{2/k}$.

To prove the theorem we shall reduce (in a non black-box manner) from the
following result:

######  Theorem 12 ([3, Lemma 2])

Every one-sided error algorithm for testing triangle-freeness in graphs with
${n^{\prime}}$ vertices and average degree $d$ must perform
$\Omega(d,{n^{\prime}}/d)$ queries. This lower bound holds even when the
maximum degree is $O(d)$.

######  Lemma 11 (Implicit in the proof of Lemma 2 in [3])

There exists a family of (multi-)graphs ${\mathcal{G}}_{{n^{\prime}}}$ such
that the following holds.

  * •

The graphs are tripartite and have ${n^{\prime}}$ vertices in each part

  * •

The graphs are $d$-regular for $d=\Theta(\sqrt{{n^{\prime}}})$,

  * •

All but at most a small constant fraction of graphs in the family are
$\Omega(1)$-far from triangle-free.

Every algorithm that uses neighbor and/or vertex-pair queries on a graph
selected uniformly at random from ${\mathcal{G}}_{{n^{\prime}}}$ must perform
$\Omega(\sqrt{{n^{\prime}}})$ queries before it views a triangle with
sufficiently high constant probability. Furthermore, this holds even when the
algorithm knows in advance which vertex belongs to which of the three parts.

Proof of Theorem 2: To prove the theorem, assume towards a contradiction that
there exists a one-sided error algorithm ${\mathcal{A}}$ for testing
$C_{k}$-freeness using at most $n^{1/3}/c$ queries (for some constant $c$) in
graphs with $n$ vertices and arboricity $2$. We shall prove that there exists
an algorithm ${{\mathcal{A}}^{\prime}}$ that finds, with high constant
probability, a triangle in graphs selected uniformly from
${\mathcal{G}}_{{n^{\prime}}}$ using at most $\sqrt{{n^{\prime}}}/c^{\prime}$
queries for some constant $c^{\prime}$, thus reaching a contradiction to Lemma
11.

Algorithm ${{\mathcal{A}}^{\prime}}$ will operate as follows. Given query
access to a graph ${G^{\prime}}\in{\mathcal{G}}_{{n^{\prime}}}$, algorithm
${{\mathcal{A}}^{\prime}}$ (implicitly) defines a graph $G$ and invokes
algorithm ${\mathcal{A}}$ on it, where each query to $G$ is answered using a
constant number of queries to ${G^{\prime}}$ (in expectation). Once
${\mathcal{A}}$ terminates its execution on $G$, if it found a $C_{k}$ in $G$,
then ${{\mathcal{A}}^{\prime}}$ returns a corresponding triangle in
${G^{\prime}}$, where there is a small probability ($o(1)$) that
${{\mathcal{A}}^{\prime}}$ terminates early (before ${\mathcal{A}}$ makes its
decision).

We shall show that if ${G^{\prime}}$ is ${\epsilon^{\prime}}$-far from
triangle-free, then $G$ is $\epsilon=\Omega({\epsilon^{\prime}})$-far from
$C_{k}$-free. In such a case (when executed with a distance parameter
$\epsilon$), ${\mathcal{A}}$ must reject $G$ with high constant probability.
Since ${\mathcal{A}}$ has one-sided error, when it rejects, it must have
evidence in the form of a $C_{k}$.181818This statement holds for the graphs
constructed, and assuming the number of queries performed by ${\mathcal{A}}$
is indeed at most $n^{1/3}/c$. The reason is that if after performing these
many queries the algorithm did not detect a $C_{k}$, then the algorithm’s
“knowledge graph” (which includes all queried edges as well as degrees) can be
completed to a graph that is $C_{k}$-free.

For every graph ${G^{\prime}}$ in ${\mathcal{G}}_{{n^{\prime}}}$, we consider
an orientation of its edges so that for edge $(u,v)$ if $id(u)<id(v)$, then
the edge is oriented from $u$ to $v$. For ease of presentation, assume for now
that $k$ is divisible by $3$. The graph $G$ is constructed in two steps where
the first is deterministic and the second is randomized. First a graph $G^{+}$
is obtained by replacing each oriented edge $e=(u,u^{\prime})$ in
${G^{\prime}}$ with a path of length $k/3$, where the original endpoints are
kept in $G^{+}$, and $\ell=k/3-1$ new vertices $v_{e}^{1},\ldots,v_{e}^{\ell}$
are added along the path (where $u=v_{e}^{0}$ and
$u^{\prime}=v_{e}^{\ell+1}$). We refer to the set of vertices in $G^{+}$ that
originated from endpoints of edges in ${G^{\prime}}$ as “original vertices”,
and to the set of new vertices as “path vertices”. See Figure 4 for an
illustration. (Note that even if the graph ${G^{\prime}}$ has parallel edge,
since every edge in ${G^{\prime}}$ is replaced by a distinct path in $G^{+}$,
the resulting graph $G^{+}$ has no parallel edges.)

In the second step, the graph $G$ is obtained by applying a random permutation
on the ids of the vertices of $G^{+}$, where the permutation is applied
separately to the ids of the original vertices and to the ids of the path
vertices. That is, the algorithm ${{\mathcal{A}}^{\prime}}$ knows at the
beginning of its execution, what is the set of ids of the original vertices
and of path vertices. If $k$ is not divisible by $3$, then to obtain $G^{+}$
from ${G^{\prime}}$, a similar process to the above is done with either
$\lceil k/3\rceil,\lceil k/3\rceil,\lfloor k/3\rfloor$ or $\lceil
k/3\rceil,\lfloor k/3\rfloor,\lfloor k/3\rfloor$, where all edges between the
same two parts in the original graph ${G^{\prime}}$, are replaced by a path of
the same length in $G^{+}$.

Recall that all graphs ${G^{\prime}}$ in ${\mathcal{G}}_{{n^{\prime}}}$ have
${m^{\prime}}=\Theta({n^{\prime}}\cdot d)=\Theta({n^{\prime}}^{3/2})$ edges so
that $G$ has $n=\Theta(k\cdot{m^{\prime}})=\Theta({n^{\prime}}^{3/2})$
vertices and $m=\Theta({n^{\prime}}^{3/2})$ edges (recall that $k$ is a
constant). Also note that $G$ has arboricity $2$, as for any subgraph of $G$,
its average degree is at most $2$.

Observe that by the above construction, every triangle in ${G^{\prime}}$ is
transformed into a $k$-cycle in $G$, and every $k$-cycle in $G$ originates
from a triangle in ${G^{\prime}}$. Therefore, if a $k$-cycle is detected in
$G$, then a triangle is detected in ${G^{\prime}}$. We also claim that the
distance is preserved (up to a constant factor), i.e., that
$dist(G,C_{k}\mbox{-}free)=\Omega(dist({G^{\prime}},C_{3}\mbox{-}free))$. To
verify this, let $R$ be a minimum-size set of edges so that if we remove $R$
from $G$, then it becomes $C_{k}$-free. Map each edge $e\in R$ that resides on
some path in $G$ to the edge $e^{\prime}\in E({G^{\prime}})$ that this path
replaced, and let ${R^{\prime}}$ be the set of edges that $R$ maps to. Then
$|{R^{\prime}}|=|R|$, and removing ${R^{\prime}}$ from ${G^{\prime}}$ will
make ${G^{\prime}}$ triangle-free.191919Assume the contrary, i.e., that after
removing ${R^{\prime}}$ from ${G^{\prime}}$, there exists a triangle in
${G^{\prime}}$. Then the three paths in $G$ that replaced this triangle are
disjoint from $R$, as otherwise this path would not have survived. Therefore,
$G$ after removing $R$ is not $C_{k}$-free which is a contradiction to the
definition of $R$. Therefore,

$dist({G^{\prime}},C_{3}\mbox{-}free)\leq\frac{|{R^{\prime}}|}{{m^{\prime}}}=\frac{|R|}{{m^{\prime}}}\leq\frac{|R|}{m\cdot\lfloor
3/k\rfloor}=\Omega(dist(G,C_{k}\mbox{-}free))\;,$ (43)

as claimed.

Hence, given access to ${G^{\prime}}$ in ${\mathcal{G}}_{{n^{\prime}}}$, we
shall invoke ${\mathcal{A}}$ on $G$. If ${G^{\prime}}$ is
${\epsilon^{\prime}}$-far from being triangle-free (for some constant
${\epsilon^{\prime}}$, as almost all graphs in ${\mathcal{G}}_{{n^{\prime}}}$
are), then $G$ is ${\epsilon^{\prime}}/c^{\prime}$-far from being $C_{k}$-free
for some constant $c^{\prime}$. Therefore, by the assumption on
${\mathcal{A}}$, we can, with high constant probability, using at most
$n^{1/3}/c\leq\sqrt{{n^{\prime}}}/c^{\prime}$ queries on $G$, obtain a
triangle in ${G^{\prime}}$. Thus we get a contradiction to Lemma 11.

It remains to show that the invocation of ${\mathcal{A}}$ on $G$ can be
simulated by giving ${{\mathcal{A}}^{\prime}}$ query access to ${G^{\prime}}$,
with the same order of query complexity.

To answer queries to $G$ using queries to ${G^{\prime}}$,
${{\mathcal{A}}^{\prime}}$ constructs uniform permutations
$\sigma_{1}\in\Pi_{{n^{\prime}}}$ and $\sigma_{2}\in\Pi_{n-{n^{\prime}}}$ “on
the fly”, so that $\sigma_{1}$ maps original vertices in $G$ to original
vertices in $G^{+}$ and $\sigma_{2}$ maps path vertices in $G$ to path
vertices in $G^{+}$.

Let $I_{1,t}\subset[{n^{\prime}}]$ and $I_{2,t}\subset[{n^{\prime}}+1,n]$ be
the set of indices, for which $\sigma_{1}$ and $\sigma_{2}$, respectively,
were not yet decided on by the $t$th query. Further let $\sigma(I_{1,t})$ and
$\sigma(I_{2,t})$ be the set of indices in $[{n^{\prime}}]$ and
$[{n^{\prime}}+1,n]$, respectively, that were not yet mapped to by $\sigma$ by
the $t$th query. For any $t\geq 0$, the $t+1$ query is answered by
${\mathcal{A}}$ as follows.

##### Degree queries $deg(u)$:

Recall that every ${G^{\prime}}\in{\mathcal{G}}_{{n^{\prime}}}$ is
$d$-regular, so that all the original vertices in $G$ have degree $d$. Also,
by construction, all path vertices in $G$ have degree exactly $2$. Finally, by
construction, the set of ids of each group of vertices is known in advance.
Hence, we can assume without loss of generality that no degree queries are
performed.

##### Neighbor queries $nbr(u,p)$:

The query is answered differently depending on whether $u\in[{n^{\prime}}]$ or
$u\in[{n^{\prime}}+1,n]$. If $u\in[{n^{\prime}}]$, then
${{\mathcal{A}}^{\prime}}$ first selects $\sigma_{1}(u)$ by choosing an index
in $[{n^{\prime}}]\setminus\sigma_{1}(I_{t})$ u.a.r.. Then
${{\mathcal{A}}^{\prime}}$ performs a neighbor query on the original vertex
$\sigma(u)$ in ${G^{\prime}}$. That is, ${{\mathcal{A}}^{\prime}}$ performs
the query $nbr(\sigma(u),p)$ on ${G^{\prime}}$. Let $e^{\prime}=(\sigma(u),v)$
denote the returned edge. If $v$ was not previously discovered (i.e., was not
previously queried or was returned as an answer to a previous query), then
${{\mathcal{A}}^{\prime}}$ decides on its id in $G$ , i.e.,
$\sigma^{-1}_{1}(v)$, by choosing uniformly from the indices in
$[{n^{\prime}}]\setminus I_{1,t}$. ${{\mathcal{A}}^{\prime}}$ also performs a
_path labeling process_ on the path that replaces the edge $e^{\prime}$ in
$G$: Let $v_{e^{\prime}}^{1},\ldots,v_{e^{\prime}}^{\ell}$ be the path
vertices in $G^{+}$ that on the path that replaced the edge $e^{\prime}$ in
${G^{\prime}}$ (where $\sigma(u)=v_{e^{\prime}}^{0}$ and
$v=v_{e^{\prime}}^{\ell+1}$). ${{\mathcal{A}}^{\prime}}$ labels the path
vertices by choosing for each $v_{e^{\prime}}^{r}$ a value
$\sigma_{2}^{-1}(v_{e^{\prime}}^{r})$ u.a.r. in $[{n^{\prime}}+1,n]\setminus
I_{2,t}$. Finally, ${{\mathcal{A}}^{\prime}}$ answers the query with all the
vertices of the path and their ids. We refer to this as a “path answer”.

We turn to the case that the neighbor query is performed on a path vertex.
That is, $u\in[{n^{\prime}}+1,n]$. In this case we would like to map $u\in G$
to an edge $e^{\prime}\in{G^{\prime}}$. Recall that the id $u$ not only
specifies that $u$ is a path vertex, but also to which two parts its path
belongs to. Assume without loss of generality that $u$ belongs to the set of
path vertices that reside on paths between parts $1$ and $2$. In order to map
$u$ to an edge between parts $P_{1},P_{2}$, we need to first sample an edge
$e$ between $P_{1}$ and $P_{2}$ uniformly at random (we shortly explain how).
If the edge $e^{\prime}\in{G^{\prime}}$ has already been discovered, then
${{\mathcal{A}}^{\prime}}$ terminates and returns that ${G^{\prime}}$ is
triangle free. This only happens with negligible probability $O(Q/m)=o(1)$,
where $Q$ is the number of queries performed by ${\mathcal{A}}$. Otherwise,
${{\mathcal{A}}^{\prime}}$ draws a uniform index $r\in[\ell]$, and lets
$\sigma(u)=v_{e^{\prime}}^{r}$. Then ${{\mathcal{A}}^{\prime}}$ performs a
path labeling process on the remaining path vertices and returns a path answer
for $e^{\prime}$.

To sample a uniform edge in ${G^{\prime}}$ between two specific parts, say
$P_{1}$ and $P_{2}$, ${{\mathcal{A}}^{\prime}}$ samples $w$ in the set of
indices of $P_{1}$ and $r^{\prime}\in[d]$ u.a.r. and performs neighbor queries
$nbr(w,r^{\prime})$ on ${G^{\prime}}$ until the returned neighbor belongs to
the desired part, in this case $P_{2}$. Since ${G^{\prime}}$ is $d$-regular,
this results in a uniformly distributed edge $e^{\prime}$ in $E(P_{1},P_{2})$.
Note that since every vertex $v\in G$ has exactly half of its neighbors in
each of the other two parts, the above process returns an edge in the desired
part with probability $1/2$. Hence, the expected number of queries per one
query simulation is constant.

##### Pair queries $pair(u_{1},u_{2})$:

If the two queried vertices are original vertices in ${G^{\prime}}$ then the
answer to the query is no. If at least one of them is a path vertex, then
${\mathcal{A}}$ maps it to an edge, as described above for neighbor queries,
and answers accordingly.

Finally, as each query to $G$ can be simulated in a constant number of queries
to ${G^{\prime}}$ in expectation, it follows that with high probability
$1-o(1)$ (over the randomness of ${{\mathcal{A}}^{\prime}}$), the total number
of queries does not exceed that of ${\mathcal{A}}$ by more than a constant
factor, and otherwise ${{\mathcal{A}}^{\prime}}$ may terminate. This concludes
the proof. $\Box$

##  Appendix F A general upper bound for testing $C_{k}$-freeness (and
$F$-freeness in general)

In this we section describe and analyze our algorithms for testing
$C_{k}$-freeness, for even and odd $k$, and more generally for $F$-freeness,
for any fixed subgraph $F$. We shall use $k$ to denote the number of vertices
in $F$ (which is consistent with the special case that $F=C_{k}$). In order to
present the result for $F$-freeness, we introduce a measure that extends the
notion of the size of a minimum vertex cover.

###### Definition 1

For a graph $F=(V_{F},E_{F})$ let $\mathcal{VC}(F)$ denote the set of all
vertex covers of $F$. For a vertex cover $Z$ of $F$ we denote by
$\mathcal{VC}^{\prime}(Z)$ the set of vertex covers of $F$ that are subsets of
$Z$. We define
$\ell(F)=\max_{Z\in\mathcal{VC}(F)}\left\\{min_{B\in\mathcal{VC}^{\prime}(Z)}\left(|B|\right)\right\\}$.

Observe that by Definition 1, we have that $\ell(F)$ is lower bounded by the
size of a minimum vertex cover of $F$ and is upper bounded by $k=|V_{F}|$.

Our algorithm for testing $F$-freeness appears next. The algorithm receives
the number of edges, $m$, as a parameter. We note that $m$ can be an upper
bound on the number of edges of the graph. The algorithm also receives
$\alpha$ as a parameter. As noted before, if $m$ is given (and not just an
upper bound) then we can estimate the effective arboricity instead of
receiving $\alpha$ as a parameter. Another option is to receive only $\alpha$
(without $m$) and use $\alpha n$ as an upper bound on $m$.

Test-subgraph-freeness($F,n,m,\alpha,\epsilon$)

  1. 1.

Set $\theta_{0}=4\alpha/\epsilon$.

  2. 2.

Sample u.a.r. $s=$$\Theta\left(k^{2+1/\ell(F)}\cdot
m\cdot\left(\frac{\alpha}{m}\right)^{1/\ell(F)}\cdot\left(\frac{1}{\epsilon}\right)^{1+2/\ell(F)}\right)$
vertices from $G$ (where $\ell(F)$ is as defined in Definition 1).

  3. 3.

Query all the neighbors of every vertex $v$ in the sample such that
$d(v)\leq\theta_{0}$ .

  4. 4.

Reject if and only there is a witness for $F$ in the resulting subgraph.

In order to analyze the algorithm Test-subgraph-freeness, we introduce some
definitions, and prove a claim regarding sampling of tuples.

For the threshold $\theta_{0}$ as defined in the algorithm, let $L$ denote the
subset of vertices in $G$ whose degree is at most $\theta_{0}$, and let $H$
denote the subset of vertices whose degree is greater than $\theta_{0}$. We
refer to the former as _light_ vertices and the latter as _heavy_ vertices. We
say that a subset of subgraphs of $G$ (in particular, that are isomorphic of
$F$), are light-vertex-disjoint if they do not share any light vertex. Let
$G_{\leq\theta_{0}}$ denote the subgraph of $G$ that contains all vertices of
$G$ but only edges that have at least one light endpoint.

###### Claim 12

Let $X$ be a set of elements and let
$\mathcal{T}=\\{(x^{j}_{1},\ldots,x^{j}_{\ell})\\}_{j\in[|{\mathcal{T}}|]}$ be
a set of $\ell$-tuples of elements of $X$ such that each $x\in X$ appears at
most once in some $\rho\in\mathcal{T}$ (namely, the $\ell$-tuples are disjoint
and each tuple contains distinct elements). Let $S=\\{u_{1},\ldots u_{s}\\}$
be a multi-set of $s$ elements chosen independently, uniformly, at random from
$X$. If $s\geq 16\ell|X|/(|\mathcal{T}|^{1/\ell})$, then with high constant
probability over the choice of $S$, it contains $\ell$ elements that belong to
a common tuple in ${\mathcal{T}}$.

Proof: We say that an $\ell$-tuple of indices $(i_{1},\ldots i_{\ell})$ where
$i_{j}\in[s]$ for each $j\in[\ell]$ is _good_ with respect to $S$ and
$\mathcal{T}$ if $(u_{i_{1}},\ldots u_{i_{\ell}})$ belongs to $\mathcal{T}$.
Let $r={s\choose\ell}\cdot\ell!$ denote the number of different $\ell$-tuples
of indices in $[s]$. Consider any fixed ordering of these tuples, and let
$\chi_{i}$ be the indicator variable for the event that the $i$-th tuple of
indices is good with respect to $S$ and $\mathcal{T}$. We next upper bound the
probability that $\sum_{i\in[r]}\chi_{i}=0$. Let $\mu=\mathbb{E}[\chi_{i}]$
and $\bar{\chi}_{i}=\chi_{i}-\mu$, so that $\mathbb{E}[\bar{\chi}_{i}]=0$. By
Chebyshev’s inequality,

$\Pr\left[\sum_{i\in[r]}\chi_{i}=0\right]\leq\frac{\mathbb{V}\left[\sum_{i\in[r]}\chi_{i}\right]}{\left(\mathbb{E}\left[\sum_{i\in[r]}\chi_{i}\right]\right)^{2}}=\frac{\sum_{i,j}\mathbb{E}[\bar{\chi}_{i}\cdot\bar{\chi}_{j}]}{r^{2}\cdot\mu^{2}}\;.$
(44)

We first calculate:

$\mathbb{E}\left[\sum_{i\in[r]}\chi_{i}\right]=r\cdot\mu={s\choose\ell}\cdot\ell!\cdot|\mathcal{T}|\cdot\left(\frac{1}{|X|}\right)^{\ell}=\frac{s!}{(s-\ell)!}\cdot|{\mathcal{T}}|\cdot\left(\frac{1}{|X|}\right)^{\ell}\geq(s/2)^{\ell}\cdot|{\mathcal{T}}|\cdot\left(\frac{1}{|X|}\right)^{\ell}\geq(8\ell)^{\ell}\;.$
(45)

We next break the sum
$\sum_{i,j}\mathbb{E}[\bar{\chi}_{i}\cdot\bar{\chi}_{j}]$ into several sub-
sums as follows. We say that $(i,j)\in[r]\times[r]$ is in $R_{t}$ if the
number of elements (namely, indexes of samples) that belong both to the $i$-th
tuple and the $j$-th tuple is exactly $t$ (namely the intersection of the
tuples is of size $t$ when they are viewed as sets).

If $(i,j)\in R_{0}$ then $\chi_{i}$ and $\chi_{j}$ are independent and so

$\mathbb{E}[\bar{\chi}_{i}\cdot\bar{\chi}_{j}]=\mathbb{E}[\bar{\chi}_{i}]\cdot\mathbb{E}[\bar{\chi}_{j}]=0\;.$
(46)

Hence, the pairs in $R_{0}$ do not contribute anything to the right-hand side
of Equation (44).

If $i=j$ then

$\mathbb{E}[\bar{\chi}_{i}\cdot\bar{\chi}_{j}]=\mathbb{E}[(\bar{\chi}_{i})^{2}]\leq\mathbb{E}[(\chi_{i})^{2}]=\mathbb{E}[\chi_{i}]=\mu\;,$
(47)

where the second inequality follows from the definition of $\bar{\chi}_{i}$.

Given that $(i,j)\in R_{t}$ it holds that

$\mathbb{E}[\bar{\chi}_{i}\cdot\bar{\chi}_{j}]\leq\mathbb{E}[\chi_{i}\chi_{j}]\leq|{\mathcal{T}}|\cdot\left(\frac{1}{|X|}\right)^{2\ell-t}\;.$
(48)

Since there are at most ${\ell\choose t}\cdot s^{2\ell-t}$ pairs in $R_{t}$ we
obtain that

$\displaystyle\sum_{(i,j)\in
R_{t}}\mathbb{E}[\bar{\chi}_{i}\cdot\bar{\chi}_{j}]$ $\displaystyle\leq$
$\displaystyle{\ell\choose t}\cdot
s^{2\ell-t}\cdot|{\mathcal{T}}|\cdot\left(\frac{1}{|X|}\right)^{2\ell-t}\leq\ell^{t}\cdot|{\mathcal{T}}|\cdot\left(\frac{s}{|X|}\right)^{2\ell-t}\;\leq\;\ell^{\ell}\cdot|{\mathcal{T}}|\cdot\left(\frac{s}{|X|}\right)^{\ell}$
(49) $\displaystyle=$
$\displaystyle\left(\frac{|{\mathcal{T}}|^{1/\ell}\cdot\ell\cdot
s}{|X|}\right)^{\ell}\;\leq\;(16\ell^{2})^{\ell}\;,$

Thus,

$\frac{\sum_{i,j}\mathbb{E}[\bar{\chi}_{i}\cdot\bar{\chi}_{j}]}{r^{2}\cdot\mu^{2}}\leq\frac{1}{r\mu}+\frac{\ell(16\ell^{2})^{\ell}}{(r\mu)^{2}}\leq\frac{1}{(8\ell)^{\ell}}+\frac{\ell(16\ell^{2})^{\ell}}{(8\ell)^{2\ell}}\leq\frac{1}{8}+\frac{\ell}{2^{2\ell}}\leq\frac{3}{8}\;,$
(50)

which concludes the proof of the claim. $\Box$

###### Theorem 13

The algorithm Test-subgraph-freeness is a one-sided error tester for
$F$-freeness whose query complexity is

$O\left(k^{2+1/\ell(F)}\cdot
m\cdot\left(\frac{\alpha}{m}\right)^{1/\ell(F)}\cdot\left(\frac{1}{\epsilon}\right)^{1+2/\ell(F)}\right)\;.$

Proof: The completeness of the tester follows by construction. We next prove
its soundness (where we start similarly to previous proofs). Assume $G$ is
$\epsilon$-far from being $F$-free. By the setting of
$\theta_{0}=4\alpha/\epsilon$, the graph $G_{\leq\theta_{0}}$ is
$\epsilon/2$-far from being $F$-free. By the definition of
$G_{\leq\theta_{0}}$, every copy of $F$ in $G_{\leq\theta_{0}}$ (i.e.,
subgraph of $G_{\leq\theta_{0}}$ that is isomorphic to $F$) only contains
edges that are incident to light vertices. Consider an iterative process, that
constructs a set $\mathcal{F}$ of light-vertex-disjoint copies of $F$ in
$G_{\leq\theta_{0}}$ in the following greedy manner. In each iteration it
selects a new copy of $F$ in $G_{\leq\theta_{0}}$ that does not share any
light vertices with previously selected copies. It follows that
$|\mathcal{F}|\geq\epsilon m/(2\theta_{0}k)$ (to see this consider a greedy
process which removes all the edges that are incident to the light vertices of
previously selected copies).

From each one of these copies we pick a subset of light vertices that covers
the edges of this copy (since the copy is in $G_{\leq\theta_{0}}$ there exists
a vertex cover which is composed of only light vertices). Moreover, by the
definition of $\ell(F)$, it suffices to pick $\ell(F)$ light vertices for each
copy. By ordering these vertices (arbitrarily) we obtain an $\ell(F)$-tuple of
light vertices for each one of these copies. Let ${\mathcal{T}}$ to be the set
of $\ell(F)$-tuples corresponding to these copies. According to Claim 12, if
we set $s$ to be at least $16\ell(F)n/((\epsilon
m/(2\theta_{0}k))^{1/\ell(F)})$ vertices, then w.h.c.p. there exists a copy of
$F$ in $G$ such that we hit all its light vertices. Conditioned on this event,
since the algorithm queries all the neighbors of all light vertices in the
sample, the copy will be revealed. By Claim 14, w.h.p., the number of queries
the algorithm needs to preform is bounded by $s\cdot
2\bar{d}=O\left(k^{2+1/\ell(F)}\cdot
m\cdot\left(\frac{\alpha}{m}\right)^{1/\ell(F)}\cdot\left(\frac{1}{\epsilon}\right)^{1+2/\ell(F)}\right)$.
If the number of queries exceeds this bound (and the algorithm did not find a
witness for rejection) the algorithm can simply accept. $\Box$

###### Corollary 14

There exists a one-sided error tester for $C_{k}$-freeness whose query
complexity is

$O\left(k^{2+(2/k))}\cdot
m\cdot\left(\frac{\alpha}{m}\right)^{2/k}\cdot\left(\frac{1}{\epsilon}\right)^{1+(4/k)}\right)$

for even $k$, and

$O\left(k^{2+2/(k+1)}\cdot
m\cdot\left(\frac{\alpha}{m}\right)^{2/(k+1)}\cdot\left(\frac{1}{\epsilon}\right)^{1+4/(k+1))}\right)$

for odd $k$.

We next turn to describe and analyze an algorithm for testing $C_{k}$-freeness
when $k$ is odd, where the algorithm improves on the upper bound stated in
Corollary 14 (when $k$ is odd) for a certain range of values of $\alpha$.

We first slightly modify the algorithm Select-an-edge from Section 3 to obtain
an algorithm that samples a uniform edge from $G_{\leq\theta_{0}}$. As shown
in [25], the expected running time of this algorithm is $O(\theta_{0}n/m)$.

Sample a uniform edge from $G_{\leq\theta_{0}}$

  * •

Repeat until an edge is returned:

    1. 1.

Sample u.a.r. a vertex $v$ from $V(G)$.

    2. 2.

Pick $j\in[\theta_{0}]$ and toss a fair coin
$b\in\\{\rm{Heads},\rm{Tails}\\}$.

    3. 3.

If $v\in L$ and $v$ has a $j$-th neighbour, $u$ then:

      1. (a)

If $u\in H$, then return $\\{u,v\\}$.

      2. (b)

If $u\in L$ and $b=\rm{Heads}$, then return $\\{u,v\\}$.

###### Claim 13

Let $E^{\prime}$ be a set of $\beta m$ edges in $G_{\leq\theta_{0}}$, where
$\beta\in(0,1]$ and let $m^{\prime}$ denote the number of edges in
$G_{\leq\theta_{0}}$. If we sample $\log n/\beta\leq y\leq m^{\prime}/2$ edges
uniformly from $G_{\leq\theta_{0}}$, then with high probability we sample at
least $c\beta y$ different edges from $E^{\prime}$, where $c$ is an absolute
constant.

Proof: Let $X_{i}$ denote the indicator variable for the event that the $i$-th
sample is an edge from $E^{\prime}$. Since the edges are sampled uniformly
from $G_{\leq\theta_{0}}$, $\mathbb{E}(X_{i})=\beta$. Thus, by multiplicative
Chernoff’s bound, with high probability $\sum_{i}X_{i}=b\beta y$, where $b$ is
a constant. Let $Y_{i}$ be the indicator variable for the event that the
$i$-th sample is a new edge from $E^{\prime}$ (with respect to the $(i-1)$
first samples). We consider, without loss of generality, the sampling process
as if it first decides the values of $X_{i}$ for each sample $i$ and then
samples the edges one by one accordingly. Consider the $j$-th sample. Given
the values of $X_{i}$ for every $i$ and the values of the samples for each
$i<j$, the probability that the $j$-th sample is a new edge, conditioned on
the event that $X_{j}=1$ is constant (since $y\leq x/2)$. Therefore, with high
probability we sample $c\beta y$ different edges from $E^{\prime}$ for some
absolute constant $c$. $\Box$

Test-$C_{k}$-freeness when $k$ is odd($n,m,\alpha,\epsilon$)

  1. 1.

Set $\theta_{0}=4\alpha/\epsilon$.

  2. 2.

Sample u.a.r. $s_{1}=\Theta\left(k\cdot
m^{1-\frac{2}{k-1}}\cdot(1/\alpha)^{1-\frac{4}{k-1}}\cdot\epsilon^{1-\frac{6}{k-1}}\right)$
edges from $G_{\leq\theta_{0}}$ (as described above). For each edge in the
sample, reveal the neighborhood of both endpoints if both are light.

  3. 3.

If $k>3$, then sample u.a.r. $s_{2}=O\left(k\cdot
n\cdot(\alpha^{2}/m)^{\frac{2}{k-1}}\cdot\left(\frac{1}{\epsilon}\right)^{\frac{6}{k-1}}\right)$
vertices and reveal the neighborhood of all the light vertices in the sample.

  4. 4.

Reject iff there is a witness for $C_{k}$ in the resulting subgraph.

The following bound is an improved bound for testing $C_{k}$-freeness for odd
$k$ whenever $m=\Omega(\alpha^{(k+3)/2})$ and in particular when $\alpha$ is a
constant.

###### Theorem 15

There exists a one-sided error tester for $C_{k}$-freeness for odd $k$ whose
query complexity is

$O\left(k\cdot
m\cdot(\alpha^{2}/m)^{\frac{2}{k-1}}\cdot\left(\frac{1}{\epsilon}\right)^{\frac{6}{k-1}}\right)$

Proof: The completeness of the tester follows by construction. We next prove
its soundness. Assume $G$ is $\epsilon$-far from being $C_{k}$-free. As in the
proof of Theorem 13, there exists a set ${\mathcal{C}}$ of light-vertex-
disjoint copies of $C_{k}$ in $G_{\leq\theta_{0}}$ such that
$|{\mathcal{C}}|\geq\epsilon m/(2\theta_{0}k)$. For each one of the copies in
${\mathcal{C}}$ we pick a subset of light vertices that covers the edges of
this copy (since the copy is in $G_{\leq\theta_{0}}$ there exists a vertex
cover which is composed of only light vertices). By the structure of $C_{k}$,
it suffices to pick $\lceil k/2\rceil$ light vertices from each copy.
Moreover, exactly one pair of these vertices are on the same edge of the
corresponding copy $C_{k}$. By excluding this pair and ordering the rest of
these vertices (arbitrarily) , we obtain an $(k-3)/2)$-tuple of light vertices
for each one of these copies.

Let ${\mathcal{T}}$ denote the set of these tuples. We also consider the set
of pairs of vertices we excluded from each copy. Each such pair is an edge of
a $C_{k}$ in ${\mathcal{C}}$. Denote this set of edges by $Y$, so that
$|Y|\geq\epsilon m/(2\theta_{0}k)$. By Claim 13, w.h.p., we sample at least
$c\epsilon s_{1}/(2\theta_{0}k)$ edges from $Y$ (where $c$ is a constant). Let
${\mathcal{T}}^{\prime}\subseteq{\mathcal{T}}$ be the set of tuples
corresponding to copies for which we sampled an edge from $Y$. By the above,
w.h.p., $|{\mathcal{T}}^{\prime}|\geq c\epsilon s_{1}/(2\theta_{0}k)$.
Conditioning on this event, according to Claim 12, if $s_{2}$ is at least
$16kn/(c\epsilon s_{1}/(2\theta_{0}k))^{2/(k-3)}$, then w.h.c.p. the algorithm
will find a copy of $C_{k}$. By Claim 14 the expected query complexity of the
algorithm is bounded by
$O(s_{1}\cdot\theta_{0}+s_{2}\cdot\bar{d})=O\left(k\cdot
m^{1-\frac{2}{k-1}}\cdot\alpha^{\frac{4}{k-1}}\cdot\left(\frac{1}{\epsilon}\right)^{\frac{6}{k-1}}\right)$.
Thus, by Markov’s inequality, if the number of queries exceeds this bound (and
the algorithm did not find a witness for rejection) the algorithm can simply
accept. $\Box$

###### Claim 14

Let $\bar{d}$ be the average degree in $G$, and let
$S=\\{v_{1},\ldots,v_{s}\\}$ be a uniform sample of size at least
$s=(\theta_{0}/\bar{d})\cdot 12\ln(1/\delta)$ vertices (with repetitions). Let
$\chi_{i}=d(v_{i})$ if $d(v_{i})\leq\theta_{0}$ and $\chi_{i}=0$ otherwise.
Then with probability at least $1-\delta$,
$\frac{1}{s}\sum_{i=1}^{s}\chi_{i}\leq 2\bar{d}$.

Proof: It holds that $\mathbb{E}[\chi_{i}]\leq\frac{1}{n}\sum_{v\in
V}d(v)=\bar{d}$. For any $\epsilon<\frac{1}{2}$,
$\mathbb{E}[\chi_{i}]\geq\frac{1}{n}\sum_{v:d(v)\leq
t}d(v)\geq\frac{1}{n}\cdot 2(1-\epsilon)m\geq\bar{d}$.

Also, for every $i\in[s]$, $\chi_{i}\in[0,\theta_{0}]$ for every $i$. Let
$x_{i}=\chi/\theta_{0}$ and $X=\sum_{i=1}^{s}x_{i}$. Then the $x_{i}$’s are
bounded independent random variables in $[0,1]$ with $\mathbb{E}[X]\leq
s\cdot\bar{d}/\theta_{0}$. Therefore, by a coupling argument and the
multiplicative Chernoff’s bound

$\Pr\left[X>2s\cdot\frac{\bar{d}}{\theta_{0}}\right]\leq\exp\left(-s\cdot\bar{d}/3\theta_{0}\right)<\delta.$

$\Box$

##  Appendix G Some probabilistic claims

###### Claim 15

For integers $s_{1}$ and $s_{2}$ let
$\\{\chi_{i,j}\\}_{(i,j)\in[s_{1}]\times[s_{2}]}$ be Bernoulli random
variables for which the following holds.

  1. 1.

$\Pr[\chi_{i,j}=1]=\mu$ for every $(i,j)\in[s_{1}]\times[s_{2}]$.

  2. 2.

For every $i_{1},i_{2}\in[s_{1}]$, $j_{1},j_{2}\in[s_{2}]$ such that
$i_{1}\neq i_{2}$ and $j_{1}\neq j_{2}$, the random variables
$\chi_{i_{1},j_{2}}$ and $\chi_{i_{2},j_{2}}$ are independent.

  3. 3.

For every $i\in[s_{1}]$, $j_{1},j_{2}\in[s_{2}]$ such that $j_{1}\neq j_{2}$,
$\Pr[\chi_{i,j_{1}}=\chi_{i,j_{2}}=1]=\mu_{1,2}$, and for every
$i_{1},i_{2}\in[s_{1}]$ and $j\in[s_{2}]$ such that $i_{1}\neq i_{2}$,
$\Pr[\chi_{i_{1},j}=\chi_{i_{2},j}=1]=\mu_{2,1}$.

Then

$\mathbb{V}\left[\sum_{i\in[s_{1}],j\in[s_{2}]}\chi_{i,j}\right]\leq
s_{1}\cdot s_{2}\cdot\mu+s_{1}\cdot{s_{2}\choose
2}\cdot\mu_{1,2}+{s_{1}\choose 2}\cdot s_{2}\cdot\mu_{2,1}\;.$

Proof: For each pair $(i,j)\in[s_{1}]\times[s_{2}]$, let
$\bar{\chi}_{i,j}=\chi_{i,j}-\mu$, so that $\bar{\chi}_{i,j}\leq\chi_{i,j}$,
and $\mathbb{E}[\bar{\chi}_{i,j}]=0$. By the definition of the variance,

$\mathbb{V}\left[\sum_{i\in[s_{1}],j\in[s_{2}]}\chi_{i,j}\right]=\sum_{(i_{1},j_{2}),(i_{2},j_{2})\in[s_{1}]\times[s_{2}]}\mathbb{E}[\bar{\chi}_{i_{1},j_{1}}\cdot\bar{\chi}_{i_{2},j_{2}}]\;.$
(51)

We upper bound the right-hand-side of Equation (51) by breaking the sum
$\sum_{i_{1},j_{2},i_{2},j_{2}}\mathbb{E}[\bar{\chi}_{i_{1},j_{1}}\cdot\bar{\chi}_{i_{2},j_{2}}]$
into four sub-sums.

##### The first

is over $(i_{1},j_{1}),(i_{2},j_{2})\in[s_{1}]\times[s_{2}]$ such that all
four indices are distinct. By the second condition in the claim, for such
quadruples of indices, $\chi_{i_{1},j_{1}}$ is independent of
$\chi_{i_{2},j_{2}}$ and so

$\mathbb{E}[\bar{\chi}_{i_{1},j_{1}}\cdot\bar{\chi}_{i_{2},j_{2}}]=\mathbb{E}[\bar{\chi}_{i_{1},j_{1}}]\cdot\mathbb{E}[\bar{\chi}_{i_{2},j_{2}}]=0\;.$
(52)

##### The second

is over $i_{1}=i_{2}$ and $j_{1}=j_{2}$, so that

$\mathbb{E}[\bar{\chi}_{i_{1},j_{1}}\cdot\bar{\chi}_{i_{2},j_{2}}]=\mathbb{E}[(\bar{\chi}_{i_{1},j_{1}})^{2}]\leq\mathbb{E}[(\chi_{i_{1},j_{1}})^{2}]=\mathbb{E}[\chi_{i_{1},j_{1}}]=\mu\;,$
(53)

where the second inequality follows from the definition of $\bar{\chi}_{i,j}$.
There are $s_{1}\times s_{2}$ such quadruples.

##### The third

is over $i_{1}=i_{2}$ and $j_{1}\neq j_{2}$, in which case we have

$\mathbb{E}[\bar{\chi}_{i_{1},j_{1}}\cdot\bar{\chi}_{i_{1},j_{2}}]\leq\mathbb{E}[\chi_{i_{1},j_{1}}\cdot\chi_{i_{1},j_{2}}]=\Pr[\chi_{i_{1},j_{1}}=\chi_{i_{1},j_{2}}=1]=\mu_{1,2}\;.$
(54)

There are $s_{1}\times{s_{2}\choose 2}$ such pairs.

##### The fourth

is over $i_{1}\neq i_{2}$ and $j_{1}=j_{2}$, where similarly to the third case
we get

$\mathbb{E}[\bar{\chi}_{i_{1},j_{1}}\cdot\bar{\chi}_{i_{2},j_{2}}]\leq\mu_{2,1}\;$
(55)

where there are ${s_{1}\choose 2}\cdot s_{2}$ such pairs.

The claim follows by summing all four sub-sums. $\Box$

The next claim is very similar to Claim 15, but the setting is slightly
different, and will be used in our analysis several time. In what follows, for
an integer $s$ we use $\Phi(s)$ to denote the set of pairs $i,j\in[s]$ such
that $i<j$.

###### Claim 16

For an integer $s$l let $\\{\chi_{i,j}\\}_{(i,j)\in\Phi(s)}$ be Bernoulli
random variables for which the following holds.

  1. 1.

$\Pr[\chi_{i,j}=1]=\mu$ for every $(i,j)\in\Phi(s)$.

  2. 2.

For every $i_{1},i_{2}\in[s_{1}]$, $j_{1},j_{2}\in[s_{2}]$ such that
$i_{1}\neq i_{2}$ and $j_{1}\neq j_{2}$, the random variables
$\chi_{i_{1},j_{2}}$ and $\chi_{i_{2},j_{2}}$ are independent.

  3. 3.

For every $(i_{1},j_{1})\in\Phi(s)$ and $(i_{2},j_{2})\in\Phi(s)$ such that
exactly two of the four indices are the same,
$\Pr[\chi_{i_{1},j_{1}}=\chi_{i_{2},j_{2}}=1]=\mu_{1,2}$.

Then $\mathbb{V}\left[\sum_{(i,j)\in\Phi(s)}\chi_{i,j}\right]\leq{s\choose
2}\cdot\mu+{s\choose 3}\mu_{1,2}$.

The proof of Claim 16 is very similar to the proof of Claim 15, and is hence
omitted. As a corollary of this claim we get:

###### Corollary 16

For an integer $s$ let $\\{\chi_{i,j}\\}_{(i,j)\in\Phi(s)}$ be Bernoulli
random variables where $\Pr[\chi_{i,j}=1]=\mu$ for every $(i,j)\in\Phi(s)$.
Suppose that the following conditions hold for some $c_{1}>0$ and $c_{2}>4$.

  1. 1.

For every $(i_{1},j_{1})\in\Phi(s)$ and $(i_{2},j_{2})\in\Phi(s)$ such that
the four indices are distinct, $\chi_{i_{1},j_{1}}$ and $\chi_{i_{2},j_{2}}$
are independent.

  2. 2.

For every $(i_{1},j_{1})\in\Phi(s)$ and $(i_{2},j_{2})\in\Phi(s)$ such that
exactly two of the four indices are the same,
$\Pr[\chi_{i_{1},j_{1}}=\chi_{i_{2},j_{2}}=1]\leq c_{1}\cdot\mu^{3/2}$.

  3. 3.

$s\geq c_{2}/\sqrt{\mu}$ .

Then
$\Pr\left[\sum_{(i,j)\in\Phi(s)}\chi_{i,j}=0\right]\leq\frac{1+c_{1}}{c_{2}}$.

Proof: By Chebishev’s inequality,

$\Pr\left[\sum_{(i,j)\in\Phi(s)}\chi_{i,j}=0\right]\leq\frac{\mathbb{V}\left[\sum_{(i,j)\in\Phi(s)}\chi_{i,j}\right]}{\left(\mathbb{E}\left[\sum_{(i,j)\in\Phi(s)}\chi_{i,j}\right]\right)^{2}}\;$
(56)

The denominator of the right-hand-side of Equation (56) equals ${s\choose
2}^{2}\cdot\mu^{2}$. By Claim 16 and the first two conditions of the current
claim, the numerator of the right-hand-side of Equation (56) is upper bounded
by ${s\choose 2}\cdot\mu+{s\choose 3}\cdot c_{1}\cdot\mu^{3/2}$, so that the
claim follows. $\Box$