用AI找到超万例反例，推翻树图独立集序列的对数凹性猜想
An AI enhanced approach to the tree unimodality conjecture
- 用PatternBoost AI架构自动搜索树图反例
- 发现27至101个顶点间超万例不满足对数凹性的树
- 揭示猜想在更大规模下失效，适合图论与AI交叉研究者
给定图G，其独立集序列是整数序列a₁,a₂,...,aₙ，其中aᵢ表示大小为i的独立集数量。上世纪80年代，Alavi、Erdos、Malde、Schwenk指出该序列对一般图未必单峰，但猜想对树图恒为单峰。此猜想后被推广为：树图的独立集序列应满足对数凹性，即aᵢ² ≥ aᵢ₋₁aᵢ₊₁。该猜想长期未被推翻，直至2023年Kadrawi、Levit、Yosef、Mizrachi证明仅存在两个26个顶点的树违反对数凹性。本文采用Charton等人开发的PatternBoost AI架构，训练机器寻找对数凹性反例。结果成功发现数十万个新反例，覆盖27至101个顶点的树，同时揭示了该方法的部分局限性。
原文摘要 · Abstract (English)
Given a graph $G$, its independence sequence is the integral sequence $a_1,a_2,...,a_n$, where $a_i$ is the number of independent sets of vertices of size i. In the late 80's Alavi, Erdos, Malde, Schwenk showed that this sequence need not be unimodal for general graphs, but conjectured that it is always unimodal whenever $G$ is a tree. This conjecture was then naturally generalized to claim that the independence sequence of trees should be log concave, in the sense that $a_i^2$ is always above $a_{i-1}a_{i+1}$. This conjecture stood for many years, until in 2023, Kadrawi, Levit, Yosef, and Mizrachi proved that there were exactly two trees on 26 vertices whose independence sequence was not log concave. In this paper, we use the AI architecture PatternBoost, developed by Charton, Ellenberg, Wagner, and Williamson to train a machine to find counter-examples to the log-concavity conjecture. We will discuss the successes of this approach - finding tens of thousands of new counter-examples to log-concavity with vertex set sizes varying from 27 to 101 - and some of its fascinating failures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。