Holey graphs: very large Betti numbers are testable
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917926472253440 |
|---|---|
| author | Szabó, Dániel Apers, Simon |
| author_facet | Szabó, Dániel Apers, Simon |
| contents | We show that the graph property of having a (very) large $k$-th Betti number $β_k$ 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 $δ(\varepsilon,k)>0$ such that testing whether $β_k \geq (1-δ) d_k$ for $δ\leq δ(\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. Our result combines the Euler characteristic, matroid theory and the graph removal lemma. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06109 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Holey graphs: very large Betti numbers are testable Szabó, Dániel Apers, Simon Data Structures and Algorithms Discrete Mathematics Combinatorics We show that the graph property of having a (very) large $k$-th Betti number $β_k$ 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 $δ(\varepsilon,k)>0$ such that testing whether $β_k \geq (1-δ) d_k$ for $δ\leq δ(\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. Our result combines the Euler characteristic, matroid theory and the graph removal lemma. |
| title | Holey graphs: very large Betti numbers are testable |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2401.06109 |