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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Holey Graphs: Very Large Betti Numbers are Testable

  • Dániel Szabó,
  • Simon Apers

摘要

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.