Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools

Alina Du; Greta Panova; Steven Heilman

arxiv: 2605.02193 · v1 · submitted 2026-05-04 · 🧮 math.CO · cs.AI· cs.DM· cs.LG

Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools

Alina Du , Steven Heilman , Greta Panova This is my paper

Pith reviewed 2026-05-08 18:42 UTC · model grok-4.3

classification 🧮 math.CO cs.AIcs.DMcs.LG

keywords dominating setslog-concave sequencestreescaterpillar graphscombinatorial sequencesAI-assisted discovery

0 comments

The pith

There exist trees whose dominating set sequences fail to be log-concave at arbitrarily many positions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to build trees where the numbers of dominating sets of each size break log-concavity at as many places as desired. It starts with examples found by running a transformer-based reinforcement learning program called PatternBoost on graph problems. The authors then modify an earlier construction that produced non-log-concave independent-set sequences and transfer the idea to dominating sets. They also prove that every caterpillar graph has a log-concave dominating-set sequence and that replacing the discrete sequence by a continuous function preserves log-concavity for every graph.

Core claim

For every positive integer m there exists a tree whose dominating-set sequence is not log-concave at m or more indices; the tree is obtained by adapting Bautista-Ramos' construction for independent sets. Separate computer-generated examples of both trees and general graphs with the same failure were produced by PatternBoost. Every caterpillar graph has a log-concave dominating-set sequence, and the natural continuous interpolation of the sequence is log-concave for every graph.

What carries the argument

A modification of the Bautista-Ramos ladder-like tree construction that controls the ratios of consecutive dominating-set counts so that several of those ratios fall below 1.

If this is right

The number of positions where log-concavity can fail can be made arbitrarily large inside the class of trees.
Caterpillar graphs form a large, explicitly described family that obeys the log-concavity property.
Replacing the discrete dominating-set sequence by a continuous function yields a log-concave object on every graph.
Reinforcement-learning search over graph representations can locate small counterexamples that are then turned into infinite families.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same style of construction may produce non-log-concave sequences for other counting functions such as the number of matchings or the number of colorings.
One could run the same AI search on larger or differently encoded graphs to look for minimal counterexamples or for other broken properties such as unimodality.
The continuous analogue being always log-concave suggests that the failures in the discrete case are caused by the integer constraints on set sizes rather than by any deeper obstruction.

Load-bearing premise

The change from independent sets to dominating sets in the Bautista-Ramos construction still forces the desired ratios below 1 at the chosen indices.

What would settle it

Pick any m, build the modified tree described for that m, compute its dominating-set numbers d_k for each k, and check whether d_k^2 < d_{k-1} d_{k+1} holds for at least m values of k.

Figures

Figures reproduced from arXiv: 2605.02193 by Alina Du, Greta Panova, Steven Heilman.

**Figure 1.** Figure 1: The unique graph on 9 vertices with non log-concave dominating set sequence: 0, 0, 1, 7, 50, 89, 75, 35, 9, 1 We are not aware of other published examples of such non-tree graphs. Alikhani and Peng [AP14] showed that for any n-vertex graph G, d0(G) ≤ · · · ≤ d⌈n/2⌉ (G). Beaton showed [B21] that for any n-vertex graph without isolated vertices, d⌊3n/4⌋−1 (G) ≥ · · · ≥ dn. It was also shown in [BB22, Theorem… view at source ↗

**Figure 2.** Figure 2: The tree Wm,t. The top root r is adjacent to m copies of Ht and to one additional copy of X. In the leftmost branch, one copy of Ht is expanded; inside it, the middle copy of Ft is expanded; and inside that copy of Ft , the rooted path L is repeated t times. • BS(x): generating polynomial for dominating sets of S in which ρ is not chosen and is not dominated by its parent (so it is dominated by one of its … view at source ↗

**Figure 3.** Figure 3: A 12-vertex graph with a non log-concave dominating set sequence 15 view at source ↗

**Figure 4.** Figure 4: A 12-vertex graph with a non log-concave dominating set sequence 16 view at source ↗

**Figure 5.** Figure 5: A 12-vertex graph with a non log-concave dominating set sequence 17 view at source ↗

**Figure 6.** Figure 6: A 58-vertex tree with a non log-concave dominating set sequence 18 view at source ↗

**Figure 7.** Figure 7: A 58-vertex tree with a non log-concave dominating set sequence 19 view at source ↗

**Figure 8.** Figure 8: A 32-vertex tree with a non log-concave dominating set sequence 20 view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives explicit AI-found counterexamples plus a modified Bautista-Ramos construction that produces trees whose dominating set sequences violate log-concavity at arbitrarily many indices.

read the letter

The key takeaway is that this paper produces explicit trees and graphs where the dominating set sequence fails to be log-concave, including a family where you can force as many violations as you like by modifying the Bautista-Ramos trees. They use PatternBoost, an AI tool, to generate small examples that serve as base cases. From there they show how to extend the construction so that the non-log-concavity persists for dominating sets at m positions for any m. They also establish that caterpillar graphs always have log-concave dominating set sequences and that a continuous version of the sequence is log-concave for any graph. The construction and the AI examples are the real additions here. Having a parameterized way to get many violations is helpful for understanding the limits of log-concavity in these sequences. The positive results on caterpillars and the continuous case are straightforward but nice to have as they show where the property does hold. One place that needs care is the adaptation step. The original Bautista-Ramos work is for independent sets, and dominating sets count more subsets, so the generating function or the recurrence for the numbers d_k changes. The paper claims the modification preserves the desired inequality violations, which suggests they either recomputed the sequence for the new family or proved the inequality carries over. As long as that part is explicit and correct, there is no issue. This is aimed at researchers in enumerative combinatorics who work on graph sequences and log-concavity questions. A reader who wants concrete counterexamples or is curious about using machine learning for finding combinatorial objects will get something out of it. It is not revolutionary, but the new families are worth documenting. I would bring this to a reading group on combinatorial sequences or AI in math. I would not cite it myself in the next year. It should go to peer review; the claims are specific enough that referees can check the construction details and the AI outputs.

Referee Report

1 major / 2 minor

Summary. The manuscript presents new examples of trees and graphs whose dominating set sequences fail to be log-concave, discovered via the PatternBoost transformer-based reinforcement learning tool. It proves that for any positive integer m there exists a tree whose dominating set sequence is not log-concave at least m indices, obtained by modifying the Bautista-Ramos construction originally developed for independent set sequences. It further shows that a large class of caterpillar graphs has log-concave dominating set sequences and that a continuous analogue of the dominating set sequence is log-concave for all graphs.

Significance. If the central claims hold, the work supplies explicit counterexamples to log-concavity for dominating sets, extending prior results on independent sets, together with positive theorems for caterpillars and a continuous version. The use of AI tools for generating concrete combinatorial examples is a clear strength, as is the explicit construction for arbitrarily many violations and the log-concavity results for restricted graph families. These contributions are likely to stimulate further study of unimodality properties in domination and other graph sequences.

major comments (1)

[proof of the existence theorem for arbitrary m] The existence result for arbitrary m (modifying the Bautista-Ramos construction): the manuscript asserts that the modification preserves non-log-concavity at the desired indices, but provides no explicit computation of the first several dominating-set numbers d_k nor a direct argument showing that the inequality d_i^2 > d_{i-1}d_{i+1} survives the change from independent-set to dominating-set counting. Because dominating sets and independent sets are related only by inclusion, the modification (e.g., pendant-vertex adjustments) may alter the recurrence or shift the violating positions; without this verification the transfer remains unproven and is load-bearing for the main theorem.

minor comments (2)

[section on AI-generated examples] The description of the PatternBoost-generated examples should include the explicit dominating-set sequences (or at least the first 10–15 terms) for the reported graphs so that readers can independently confirm the log-concavity failures.
[final section on continuous analogue] The continuous analogue is stated to be log-concave for all graphs; a brief indication of how the continuous version is defined (e.g., via generating functions or interpolation) would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. We address the single major comment below and will revise the manuscript to strengthen the presentation of the existence theorem.

read point-by-point responses

Referee: The existence result for arbitrary m (modifying the Bautista-Ramos construction): the manuscript asserts that the modification preserves non-log-concavity at the desired indices, but provides no explicit computation of the first several dominating-set numbers d_k nor a direct argument showing that the inequality d_i^2 > d_{i-1}d_{i+1} survives the change from independent-set to dominating-set counting. Because dominating sets and independent sets are related only by inclusion, the modification (e.g., pendant-vertex adjustments) may alter the recurrence or shift the violating positions; without this verification the transfer remains unproven and is load-bearing for the main theorem.

Authors: We agree that the manuscript would benefit from additional explicit verification to make the transfer from the independent-set construction fully rigorous. In the revised version we will add a dedicated subsection containing: (i) direct computation of the first several terms of the dominating-set sequence for the base modified tree, (ii) a short inductive argument showing that the pendant-vertex adjustments increase each d_k by a predictable amount that preserves the strict inequality d_i^2 > d_{i-1}d_{i+1} at the chosen indices, and (iii) a table comparing the relevant ratios before and after modification. This will confirm that the violations survive the change without relying solely on the analogy with independent sets. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit constructions from external references and direct proofs

full rationale

The paper's central existence result for trees with arbitrarily many non-log-concave indices in the dominating set sequence is obtained by modifying the Bautista-Ramos construction (an external reference on independent sets) and verifying the transfer combinatorially. Examples are generated via the external PatternBoost AI tool. Separate theorems establish log-concavity for a large class of caterpillar graphs and for the continuous analogue on all graphs. No step reduces by definition or construction to a fitted input, self-citation chain, or ansatz smuggled from prior author work; the derivation chain consists of explicit combinatorial arguments and external tools, remaining self-contained without circular reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claims rest on standard definitions of dominating sets, log-concavity, and caterpillar graphs together with an explicit modification of a known construction; no free parameters, additional axioms, or invented entities are introduced.

pith-pipeline@v0.9.0 · 5405 in / 1256 out tokens · 32296 ms · 2026-05-08T18:42:36.019824+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Hodge theory for combinatorial geometries

Karim Adiprasito, June Huh and Eric Katz. Hodge theory for combinatorial geometries. Annals of Mathematics. 2 (2018), vol. 188, pp. 381--452

work page 2018
[2]

Malde, Allen J

Yousef Alavi, Paresh J. Malde, Allen J. Schwenk, and Paul Erd o s. The vertex independence sequence of a graph is not constrained, Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla.), (1987) vol. 58, pp. 15--23

work page 1987
[3]

Alikhani and Y

S. Alikhani and Y. H. Peng. Introduction to domination polynomial of a graph. Ars Combinatoria, 5 (2014), vol. 114, pp. 257–-266

work page 2014
[4]

Bahls, B

P. Bahls, B. Ethridge and L. Szabo. Unimodality of the independence polynomials of non-regular caterpillars, Australas. J. Combin. 1 (2018), vol. 71, pp. 104--112

work page 2018
[5]

Multiple breaks of log-concavity in the independence polynomials of trees

C\' e sar Bautista-Ramos. Multiple breaks of log-concavity in the independence polynomials of trees. Preprint (2025), arXiv:2511.00334 https://arxiv.org/abs/2511.00334

work page arXiv 2025
[6]

I. Beaton. On dominating sets and the domination polynomial. Ph.D. Thesis. 2021

work page 2021
[7]

On the Unimodality of Domination Polynomials

Beaton, I., Brown, J.I. On the Unimodality of Domination Polynomials. Graphs and Combinatorics 3 (2022), vol. 38, pp. 1--11

work page 2022
[8]

On the Independent Set Sequence of a Tree

Abdul Basit and David Galvin. On the Independent Set Sequence of a Tree. The Electronic Journal of Combinatorics. 3 (2021), vol. 28. pp. 1--23

work page 2021
[9]

On the unimodality of nearly well-dominated trees

Iain Beaton and Sam Schoonhoven. On the unimodality of nearly well-dominated trees. Preprint (2024), arxiv:2411.02288 https://arxiv.org/abs/2411.02288

work page arXiv 2024
[10]

Charton, J.S

Fran c ois Charton, Jordan S. Ellenberg, Adam Zsolt Wagner, Geordie Williamson. PatternBoost: Constructions in Mathematics with a Little Help from AI. Preprint (2024), arxiv:2411.00566 https://arxiv.org/abs/2411.00566

work page arXiv 2024
[11]

The independent set sequence of some families of trees, Australas

David Galvin and Justin Hilyard. The independent set sequence of some families of trees, Australas. J. Combin., 2 (2018), vol. 70, pp. 236--252

work page 2018
[12]

An invariance principle for polytopes

Prahladh Harsha, Adam Klivans and Raghu Meka. An invariance principle for polytopes. Proceedings of the Forty-Second ACM Symposium on Theory of Computing (2010). pp. 543–552

work page 2010
[13]

Independent Sets of Random Trees and Sparse Random Graphs

Steven Heilman. Independent Sets of Random Trees and Sparse Random Graphs. Journal of Graph Theory, 3 (2025), vol. 109, pp. 1--28

work page 2025
[14]

Ohr Kadrawi and Vadim E. Levit. The independence polynomial of trees is not always log-concave starting from order 26. Ars Mathematica Contemporanea. 4 (2025), vol. 25, pp. 1--23

work page 2025
[15]

Domination Polynomials of Graph Products

Tomer Kotek, James Preen and Peter Tittmann. Domination Polynomials of Graph Products. Journal of Combinatorial Mathematics and Combinatorial Computing. 1 (2017), vol. 101, pp. 245--258

work page 2017
[16]

An AI enhanced approach to the tree unimodality conjecture

Eric Ramos, Sunny Sun. An AI enhanced approach to the tree unimodality conjecture. Preprint (2025), arXiv:2510.18826 https://arxiv.org/abs/2510.18826

work page arXiv 2025
[17]

On the unimodality of independence polynomials of some graphs

Yi Wang and Bao-Xuan Zhu. On the unimodality of independence polynomials of some graphs. European J. Combin. 1 (2011), vol. 32, pp. 10--20

work page 2011
[18]

The unimodality of independence polynomials of some graphs

Zhi-Feng Zhu. The unimodality of independence polynomials of some graphs. Australas. J. Combin. 1 (2007), vol. 38, pp. 27--33

work page 2007

[1] [1]

Hodge theory for combinatorial geometries

Karim Adiprasito, June Huh and Eric Katz. Hodge theory for combinatorial geometries. Annals of Mathematics. 2 (2018), vol. 188, pp. 381--452

work page 2018

[2] [2]

Malde, Allen J

Yousef Alavi, Paresh J. Malde, Allen J. Schwenk, and Paul Erd o s. The vertex independence sequence of a graph is not constrained, Eighteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, Fla.), (1987) vol. 58, pp. 15--23

work page 1987

[3] [3]

Alikhani and Y

S. Alikhani and Y. H. Peng. Introduction to domination polynomial of a graph. Ars Combinatoria, 5 (2014), vol. 114, pp. 257–-266

work page 2014

[4] [4]

Bahls, B

P. Bahls, B. Ethridge and L. Szabo. Unimodality of the independence polynomials of non-regular caterpillars, Australas. J. Combin. 1 (2018), vol. 71, pp. 104--112

work page 2018

[5] [5]

Multiple breaks of log-concavity in the independence polynomials of trees

C\' e sar Bautista-Ramos. Multiple breaks of log-concavity in the independence polynomials of trees. Preprint (2025), arXiv:2511.00334 https://arxiv.org/abs/2511.00334

work page arXiv 2025

[6] [6]

I. Beaton. On dominating sets and the domination polynomial. Ph.D. Thesis. 2021

work page 2021

[7] [7]

On the Unimodality of Domination Polynomials

Beaton, I., Brown, J.I. On the Unimodality of Domination Polynomials. Graphs and Combinatorics 3 (2022), vol. 38, pp. 1--11

work page 2022

[8] [8]

On the Independent Set Sequence of a Tree

Abdul Basit and David Galvin. On the Independent Set Sequence of a Tree. The Electronic Journal of Combinatorics. 3 (2021), vol. 28. pp. 1--23

work page 2021

[9] [9]

On the unimodality of nearly well-dominated trees

Iain Beaton and Sam Schoonhoven. On the unimodality of nearly well-dominated trees. Preprint (2024), arxiv:2411.02288 https://arxiv.org/abs/2411.02288

work page arXiv 2024

[10] [10]

Charton, J.S

Fran c ois Charton, Jordan S. Ellenberg, Adam Zsolt Wagner, Geordie Williamson. PatternBoost: Constructions in Mathematics with a Little Help from AI. Preprint (2024), arxiv:2411.00566 https://arxiv.org/abs/2411.00566

work page arXiv 2024

[11] [11]

The independent set sequence of some families of trees, Australas

David Galvin and Justin Hilyard. The independent set sequence of some families of trees, Australas. J. Combin., 2 (2018), vol. 70, pp. 236--252

work page 2018

[12] [12]

An invariance principle for polytopes

Prahladh Harsha, Adam Klivans and Raghu Meka. An invariance principle for polytopes. Proceedings of the Forty-Second ACM Symposium on Theory of Computing (2010). pp. 543–552

work page 2010

[13] [13]

Independent Sets of Random Trees and Sparse Random Graphs

Steven Heilman. Independent Sets of Random Trees and Sparse Random Graphs. Journal of Graph Theory, 3 (2025), vol. 109, pp. 1--28

work page 2025

[14] [14]

Ohr Kadrawi and Vadim E. Levit. The independence polynomial of trees is not always log-concave starting from order 26. Ars Mathematica Contemporanea. 4 (2025), vol. 25, pp. 1--23

work page 2025

[15] [15]

Domination Polynomials of Graph Products

Tomer Kotek, James Preen and Peter Tittmann. Domination Polynomials of Graph Products. Journal of Combinatorial Mathematics and Combinatorial Computing. 1 (2017), vol. 101, pp. 245--258

work page 2017

[16] [16]

An AI enhanced approach to the tree unimodality conjecture

Eric Ramos, Sunny Sun. An AI enhanced approach to the tree unimodality conjecture. Preprint (2025), arXiv:2510.18826 https://arxiv.org/abs/2510.18826

work page arXiv 2025

[17] [17]

On the unimodality of independence polynomials of some graphs

Yi Wang and Bao-Xuan Zhu. On the unimodality of independence polynomials of some graphs. European J. Combin. 1 (2011), vol. 32, pp. 10--20

work page 2011

[18] [18]

The unimodality of independence polynomials of some graphs

Zhi-Feng Zhu. The unimodality of independence polynomials of some graphs. Australas. J. Combin. 1 (2007), vol. 38, pp. 27--33

work page 2007