Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914958615248896 |
|---|---|
| author | Roucairol, Milo Cazenave, Tristan |
| author_facet | Roucairol, Milo Cazenave, Tristan |
| contents | We are interested in the automatic refutation of spectral graph theory conjectures. Most existing works address this problem either with the exhaustive generation of graphs with a limited size or with deep reinforcement learning. Exhaustive generation is limited by the size of the generated graphs and deep reinforcement learning takes hours or days to refute a conjecture. We propose to use search algorithms to address these shortcomings to find potentially large counter-examples to spectral graph theory conjectures in seconds. We apply a wide range of search algorithms to a selection of conjectures from Graffiti. Out of 13 already refuted conjectures from Graffiti, our algorithms are able to refute 12 in seconds. We also refute conjecture 197 from Graffiti which was open until now. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_18626 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Refutation of Spectral Graph Theory Conjectures with Search Algorithms) Roucairol, Milo Cazenave, Tristan Artificial Intelligence 05-04, 05-08, 05B30, 05C40, 05C50, 68Q25, 68Q87, 68R05, 68R10, 68T05, 68W20, 68W40 We are interested in the automatic refutation of spectral graph theory conjectures. Most existing works address this problem either with the exhaustive generation of graphs with a limited size or with deep reinforcement learning. Exhaustive generation is limited by the size of the generated graphs and deep reinforcement learning takes hours or days to refute a conjecture. We propose to use search algorithms to address these shortcomings to find potentially large counter-examples to spectral graph theory conjectures in seconds. We apply a wide range of search algorithms to a selection of conjectures from Graffiti. Out of 13 already refuted conjectures from Graffiti, our algorithms are able to refute 12 in seconds. We also refute conjecture 197 from Graffiti which was open until now. |
| title | Refutation of Spectral Graph Theory Conjectures with Search Algorithms) |
| topic | Artificial Intelligence 05-04, 05-08, 05B30, 05C40, 05C50, 68Q25, 68Q87, 68R05, 68R10, 68T05, 68W20, 68W40 |
| url | https://arxiv.org/abs/2409.18626 |