用AI生成非对数凹的支配集序列图与树，突破理论预期。
Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools
- 基于Transformer强化学习工具PatternBoost生成反例
- 任意长度非对数凹序列可通过构造实现
- 适合组合数学与算法设计研究者
我们给出了新的图与树的例子，其支配集序列不是对数凹的。这些例子由Charton-Ellenberg-Wagner-Williamson开发的基于Transformer的强化学习软件PatternBoost生成。此外，我们证明：对于任意正整数 $m$，存在一棵树，其支配集序列在至少 $m$ 个索引处不满足对数凹性，该构造基于Bautista-Ramos对独立集序列的类似方法。我们还证明，一大类蛛形图（caterpillar graphs）的支配集序列是对数凹的。此外，序列的连续类比对所有图均是对数凹的。
原文摘要 · Abstract (English)
We give new examples of graphs and trees with dominating set sequences that are not log-concave. These examples were generated by PatternBoost, a transformer-based reinforcement learning software developed by Charton-Ellenberg-Wagner-Williamson. We also show: for any positive integer $m$, there exists a tree whose dominating set sequence is not log-concave for at least $m$ indices by modifying a similar construction of Bautista-Ramos for the independent set sequence. We show that a large class of caterpillar graphs has log-concave dominating set sequences. A continuous analogue of the sequence is also log-concave for all graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。