  In the distributed subgraph-freeness problem, we are given a graph $H$, and
asked to determine whether the network graph contains $H$ as a subgraph or not.
Subgraph-freeness is an extremely local problem: if the network had no
bandwidth constraints, we could detect any subgraph $H$ in $|H|$ rounds, by
having each node of the network learn its entire $|H|$-neighborhood. However,
when bandwidth is limited, the problem becomes harder.
  Upper and lower bounds in the presence of congestion have been established
for several classes of subgraphs, including cycles, trees, and more complicated
subgraphs. All bounds shown so far have been linear or sublinear. We show that
the subgraph-freeness problem is not, in general, solvable in linear time: for
any $k \geq 2$, there exists a subgraph $H_k$ such that $H_k$-freeness requires
$\Omega( n^{2-1/k} / (Bk) )$ rounds to solve. Here $B$ is the bandwidth of each
communication link. The lower bound holds even for diameter-3 subgraphs and
diameter-3 network graphs. In particular, taking $k = \Theta(\log n)$, we
obtain a lower bound of $\Omega(n^2 / (B \log n))$.
