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 ( (1 )) . 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 (1 ) . Our hierarchy theorem partially resolves this problem by exhibiting a property whose 1-sided-error query complexity is 2 (1 ) . 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 ( (1 )) while its 2 -sided-error query complexity is only \poly (1 ) . 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 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 ex ( n C 3 C 2 +1 ) . Our third theorem in this paper gives tight bounds for ex ( n C k C ) for all the remaining values of k and .