用搜索算法秒级找出图论猜想反例，效率远超传统方法。
Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
- 采用多种搜索算法自动寻找图论猜想的反例
- 13个已知反例中12个在秒级被重新验证，1个新猜想被攻破
- 适合对自动推理与图论感兴趣的科研人员
我们关注谱图理论猜想的自动反证问题。现有方法或依赖小规模图的穷举生成，或使用深度强化学习，但后者需数小时甚至数天才能反驳一个猜想。本文提出使用搜索算法克服这些局限，可在数秒内发现潜在的大规模反例。我们在Graffiti中的多个猜想上应用了广泛的搜索算法，成功在秒级时间内重新验证了13个已知被反例的猜想中的12个，并首次攻破了此前未解决的Graffiti第197号猜想。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。