TLDR: A new research paper by Eric Ramos and Sunny Sun details the use of the AI architecture PatternBoost to discover tens of thousands of novel counter-examples to the log-concavity conjecture for tree independence sequences. Expanding on previous findings for 26-vertex trees, the AI-driven approach, which utilized Prüfer codes and a specific scoring mechanism, revealed a greater diversity of non-log-concave trees with vertex counts ranging from 27 to 101. The study also highlighted interesting AI behaviors, such as its tendency to produce trees with small independence numbers and the challenges of finding breakage at specific sequence indices, paving the way for future mathematical discovery.
A recent research paper, “An AI enhanced approach to the tree unimodality conjecture,” by Eric Ramos and Sunny Sun, explores a long-standing problem in graph theory using advanced artificial intelligence. The paper details how a machine learning architecture called PatternBoost was successfully employed to discover tens of thousands of new counter-examples to a key mathematical conjecture, significantly expanding our understanding of tree structures.
Understanding the Core Problem
At the heart of this research is the concept of an ‘independence sequence’ for a graph. Imagine a graph, which is a collection of points (vertices) connected by lines (edges). An independent set is a group of vertices where no two vertices are connected. The independence sequence, denoted as a1, a2, …, an, simply counts how many independent sets of each possible size ‘i’ exist in the graph.
In the late 1980s, mathematicians Alavi, Erdös, Malde, and Schwenk observed that this sequence doesn’t always follow a simple ‘unimodal’ pattern (where numbers rise to a peak and then fall) for general graphs. However, they conjectured that it always would for a specific type of graph: a tree (a graph with no cycles). This became known as the Tree Unimodality Conjecture.
A stronger condition, called ‘log-concavity,’ was later considered. A sequence is log-concave if the square of any term is greater than or equal to the product of its neighboring terms (a_i^2 ≥ a_i-1 * a_i+1). While log-concavity implies unimodality, it’s a stricter condition and often more amenable to mathematical analysis. For many years, it was believed that tree independence sequences were log-concave, and this was confirmed for trees with up to 25 vertices.
However, in 2023, Kadrawi, Levit, Yosef, and Mizrachi made a breakthrough, proving that there were exactly two trees on 26 vertices whose independence sequences were not log-concave. This finding challenged the long-held belief and opened new avenues for research.
The AI-Enhanced Approach: PatternBoost
Motivated by the success of machine learning in mathematical discovery, Ramos and Sun turned to PatternBoost, an AI architecture developed by Charton, Ellenberg, Wagner, and Williamson. PatternBoost is designed to find mathematical constructions by iteratively refining a database of examples through local search and global learning phases.
The researchers trained PatternBoost to identify trees whose independence sequences failed the log-concavity condition. They represented trees using ‘Prüfer codes,’ a unique string of numbers for each labeled tree, which allowed the AI to process them efficiently. A ‘scoring function’ was defined to measure the extent to which log-concavity was broken at a specific index in the sequence (a_i-1 * a_i+1 – a_i^2). A positive score indicated a counter-example.
The ‘local search’ algorithm involved making small modifications to trees, specifically ‘edge swaps,’ to improve their scores. The AI’s ‘global phase’ then trained a transformer model on the best-scoring trees to generate new, similar constructions, which were then fed back into the local search.
Tens of Thousands of New Discoveries
The AI-enhanced approach proved remarkably successful. Ramos and Sun’s methods uncovered tens of thousands of new counter-examples to the log-concavity conjecture, with trees ranging in size from 27 to 101 vertices. This significantly expanded the known set of such trees beyond the initial two on 26 vertices.
One crucial finding was the sheer diversity of these new counter-examples. Previously, known counter-examples shared a similar structural ‘flavor.’ However, the AI-generated trees, especially as their vertex count grew, appeared more generic, often characterized by an abundance of vertices with degree 2 (vertices connected to only two other vertices).
Also Read:
- Generative AI Tackles Classic Graph Optimization Problems
- OptiTree: Structuring Knowledge for Advanced Optimization with Language Models
Fascinating Failures and Future Directions
The research also highlighted interesting behaviors and limitations of the AI. For instance, the machine often converged on producing ‘path graphs’ (simple linear chains of vertices) if it struggled to find counter-examples. To overcome this, the researchers implemented a ‘path punishing’ mechanism in the local search, which proved crucial for finding counter-examples where log-concavity broke at indices other than N/2 (half the number of vertices).
The AI also showed a strong tendency to find trees with unusually small ‘independence numbers’ (the size of the largest independent set). This was an unexpected behavior, as the independence number is not directly encoded in the Prüfer code, yet the machine became proficient at manipulating it.
Despite its successes, the AI primarily found counter-examples where log-concavity broke within three indices of the top of the independence sequence, mostly at N/2 or N/2-1. Finding examples with breakage at other indices, or where log-concavity breaks multiple times, remains an open challenge. The paper suggests that modifying the AI’s reward function to focus on the ‘global shape’ of the independence sequence, rather than just local breakage, might be a fruitful direction for future study.
This work underscores the growing power of AI in mathematical discovery, not just for solving problems but for generating new insights and counter-examples that can guide human intuition. The code accompanying this paper is publicly available at https://github.com/ericgramos/TreeUnimodalityPatternBoost.
