Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools
For combinatorialists studying log-concavity of graph sequences, this paper provides new counterexamples and partial positive results, but the contributions are incremental.
The paper provides new examples of graphs and trees with non-log-concave dominating set sequences, generated by a transformer-based RL tool, and proves that for any positive integer m there exists a tree whose sequence fails log-concavity at m indices. It also shows log-concavity for a large class of caterpillar graphs and for a continuous analogue of the sequence.
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.