一种基于人工智能增强的树单峰性猜想研究方法 (An AI enhanced approach to the tree unimodality conjecture)

from arxiv, V2 - Fixed typographical errors. Added a remark noting a private correspondence with Galvin and Bencs, who have shown the existence of trees with log concavity breakage at multiple indices

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.

翻译：给定图$G$，其独立集序列是指整数序列$a_1,a_2,...,a_n$，其中$a_i$表示大小为i的顶点独立集的数量。在20世纪80年代末，Alavi、Erdos、Malde和Schwenk证明了该序列对于一般图不一定是单峰的，但猜想当$G$为树时该序列总是单峰的。这一猜想随后被自然地推广为：树的独立集序列应具有对数凹性，即$a_i^2$总是大于$a_{i-1}a_{i+1}$。该猜想在多年后，直至2023年才被Kadrawi、Levit、Yosef和Mizrachi证明存在恰好两棵26个顶点的树，其独立集序列不具有对数凹性。本文采用由Charton、Ellenberg、Wagner和Williamson开发的AI架构PatternBoost，训练机器学习模型以寻找对数凹性猜想的反例。我们将讨论该方法的成功之处——发现了数万个顶点规模从27到101不等的新对数凹性反例——以及一些引人注目的失败案例。