MIT Combinatorics Seminar

Testing Triangle-Freeness in General Graphs

Tali Kaufman (Massachusetts Institute of Technology)

Wednesday May 10, 2006    4:30 PM   Building 2 Room 105 


We consider the problem of testing whether a graph on $n$ vertices and average degree $d$ is triangle-free. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a large fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when $d = \Theta(n)$.

Our main finding is a lower bound of $\Omega(n^{1/3})$ on the necessary number of queries, where this bound holds for *every* $d < n^{1-o(1)}$. Since when $d = \Theta(n)$ the number of queries sufficient for testing does not depend on $n$, we observe an abrupt, *threshold-like* behavior of the complexity of testing around $n$.

In the course of our analysis we show that dense random Cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the ``correct'' edge density. The result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets.

This is joint work with Noga Alon, Michael Krivelevich and Dana Ron.