Holey graphs: very large Betti numbers are testable

Abstract

We show that the graph property of having a (very) large $k$-th Betti number ${\hat{I}}_k^2$ for constant $k$ is testable with a constant number of queries in the dense graph model. More specifically, we consider a clique complex defined by an underlying graph and prove that for any $\epsilon >0$, there exists $\hat{I}´(\epsilon ,k)>0$ such that testing whether ${\hat{I}}_k^2\ge (1-\hat{I}´)d_k$ for $\hat{I}´\le \hat{I}´(\epsilon ,k)$ reduces to tolerantly testing $(k+2)$-clique-freeness, which is known to be testable. This complements a result by Elek (2010) showing that Betti numbers are testable in the bounded-degree model. Our result combines the Euler characteristic, matroid theory and the graph removal lemma.

12 pages, 0 figures