Holey Graphs: Very Large Betti Numbers are Testable
摘要
We show that the graph property of having a (very) large k-th Betti number \(\beta _k\) (over \(\mathbb {Z}_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 \(\varepsilon >0\) , there exists \(\delta (\varepsilon ,k)>0\) such that testing whether \(\beta _k \ge (1-\delta ) d_k\) for \(\delta \le \delta (\varepsilon ,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. For our result we consider simplicial complexes as combinatorial objects, and combine matroid theory and the graph removal lemma.