The induced C4C_4-freeness polynomial testability conjecture

About 1 year old · traced to

Let C4C_4 denote the cycle with four vertices, and let qind-C4-free(ε)q_{\text{ind-}C_4\text{-free}}(\varepsilon) be the query complexity for testing induced C4C_4-freeness. Induced C4C_4-freeness conjecture.

qind-C4-free(ε)=poly⁡(1/ε).q_{\text{ind-} C_4\text{-free}}(\varepsilon)=\operatorname{poly}(1/\varepsilon).

This is the remaining case in the characterization of graphs with polynomially testable induced-freeness, following the known results for the other graphs.

References

Primary source

Lior Gishboliner and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.