Our first theorem in this papers is a hierarchy theorem for the query complexity of testing graph properties with $1$-sided error; more precisely, we show that for every super-polynomial $f$, there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$. No result of this type was previously known for any $f$ which is super polynomial. Goldreich [ECCC 2005] asked to exhibit a graph property whose query complexity is $2^{\Theta(1/\varepsilon)}$. Our hierarchy theorem partially resolves this problem by exhibiting a property whose 1-sided-error query complexity is $2^{\Theta(1/\varepsilon)}$. We also use our hierarchy theorem in order to resolve a problem raised by the second author and Alon [STOC 2005] regarding testing relaxed versions of bipartiteness.

Our second theorem states that for any function $f$ there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$ while its $2$-sided-error query complexity is only $\poly(1/\varepsilon)$. This is the first indication of the surprising power that 2-sided-error testing algorithms have over 1-sided-error ones, even when restricted to properties that are testable with $1$-sided error. Again, no result of this type was previously known for any $f$ that is super polynomial.

The above two theorems are derived from a graph theoretic result which we think is of independent interest, and might have further applications. Alon and Shikhelman [JCTB 2016] recently introduced the following generalized Turan problem: for fixed graphs $H$ and $T$, and an integer $n$, what is the maximum number of copies of $T$, denoted by $\mbox{ex}(n,T,H)$, that can appear in an $n$-vertex $H$-free graph? This problem received a lot of attention recently, with an emphasis on $\mbox{ex}(n,C_3,C_{2\ell +1})$. Our third theorem in this paper gives tight bounds for $\mbox{ex}(n,C_k,C_{\ell})$ for all the remaining values of $k$ and $\ell$.