A Generalized Turan Problem and its Applications

by Lior Gishboliner and Asaf Shapira

Oded's comments

Both results refer to testing graph properties in the dense graph model, withing complexity that only depends on the proximity parameter.

The first result is a hierarchy of one-sided error testing problems having complexity that is an arbitrary function of the proximity parameter. It would be even nicer to have such a result for general (i.e., two-sided error) testing, but what is achieved is interesting enough.

The second result is a separation between general testing (with two-sided error) and one-sided error testing. Specifically, the separation is between general testing of query complexity that is polynomial in the proximity parameter and one-sided error testing requiring an arbitrarily large complexity (which is still depending only on the proximity parameter).

The original abstract

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$.

Back to list of Oded's choices.