  We consider the pattern detection problem in graphs: given a constant size
pattern graph $H$ and a host graph $G$, determine whether $G$ contains a
subgraph isomorphic to $H$. Our main results are:
  * We prove that if a pattern $H$ contains a $k$-clique subgraph, then
detecting whether an $n$ node host graph contains a not necessarily induced
copy of $H$ requires at least the time for detecting whether an $n$ node graph
contains a $k$-clique. The previous result of this nature required that $H$
contains a $k$-clique which is disjoint from all other $k$-cliques of $H$.
  * We show that if the famous Hadwiger conjecture from graph theory is true,
then detecting whether an $n$ node host graph contains a not necessarily
induced copy of a pattern with chromatic number $t$ requires at least the time
for detecting whether an $n$ node graph contains a $t$-clique. This implies
that: (1) under Hadwiger's conjecture for every $k$-node pattern $H$, finding
an induced copy of $H$ requires at least the time of $\sqrt k$-clique
detection, and at least size $\omega(n^{\sqrt{k}/4})$ for any constant depth
circuit, and (2) unconditionally, detecting an induced copy of a random
$G(k,p)$ pattern w.h.p. requires at least the time of $\Theta(k/\log k)$-clique
detection, and hence also at least size $n^{\Omega(k/\log k)}$ for circuits of
constant depth.
  * Finally, we consider the case when the pattern is a directed cycle on $k$
nodes, and we would like to detect whether a directed $m$-edge graph $G$
contains a $k$-Cycle as a not necessarily induced subgraph. We resolve a 14
year old conjecture of [Yuster-Zwick SODA'04] on the complexity of $k$-Cycle
detection by giving a tight analysis of their $k$-Cycle algorithm. Our analysis
improves the best bounds for $k$-Cycle detection in directed graphs, for all
$k>5$.
