ACC Seminar: An AI Enhanced Approach to a Conjecture of Erdos

ABSTRACT

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 90’s Erdos and coauthors 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 stronger version of the conjecture was shown to hold for all trees of at most 25 vertices. In 2023, however, using improved computational power and a considerably more efficient algorithm, Kadrawi, Levit, Yosef, and Mizrachi proved that there were exactly two trees on 26 vertices whose independence sequence was not log concave. They also showed how these two examples could be generalized to create two families of trees whose members are all not log concave. Finally, in early 2025, Galvin provided a family of trees with the property that for any chosen positive integer k, there is a member T of the family where log concavity breaks at index alpha(T) – k, where alph(T) is the independence number of T. Outside of these three families, not much else was known about what causes log concavity to break.

In this presentation, I will discuss joint work of myself and Shiqi Sun, where we used the PatternBoost architecture to train a machine to produce counter-examples to the log concavity conjecture. We will discuss the successes of this approach – finding tens of thousands of new counter-examples with vertex set sizes varying from 27 to 101 – and some of its fascinating failures.

BIOGRAPHY

Professor Ramos is an educator in the mathematical sciences with over a decade experience teaching students at the undergraduate and graduate level. He has mentored dozens of students in mathematical research, leading to a number of published works. As a researcher, Professor Ramos has authored over 30 papers spanning a number of mathematical disciplines including algebra, combinatorics, probability, and computation. He has disseminated this work as an invited speaker at almost 100 conferences and seminars. He is currently supported by an individual research grant from the National Science Foundation, DMS-2452031.

Attendance: This is a technical talk open to all.
A campus map is available at https://tour.stevens.edu.
Additional information is available at https://web.stevens.edu/algebraic/.