Adam Zsolt Wagner
About me
I am an assistant professor of mathematics at Worcester Polytechnic Institute, and a mathematical consultant for
Google DeepMind.
My research interests are machine learning, combinatorics, graph theory.
Most of my past work has been in combinatorics and graph theory, focusing on central questions in these areas and their connections to other fields such as theoretical computer science and number theory.
In recent years the focus of my work has heavily shifted towards finding new and fun ways to use computers in mathematics research. This includes using reinforcement learning methods so programs can learn disprove open conjectures by themselves, exploring how generative ML methods can be used to attack open problems, and other ways machine learning can be used to guide our intuition.
My full CV.
Publications
| Proceedings of the AMS 2024+ |
The extremal number of Venn diagrams [arXiv] |
| JCTB 2024 |
Intersecting families of sets are typically trivial [arXiv] |
| Electronic Journal of Combinatorics 2023 |
Balanced edge-colorings avoiding rainbow cliques of size four [arXiv] |
| NeurIPS Math-AI 2023 |
Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search [arXiv] |
| JCTA 2022 |
Infinite Sperner's theorem [arXiv] |
| Random Structures & Algorithms 2022 |
Uniform chain decompositions and applications [arXiv] |
| arXiv 2021 |
Constructions in combinatorics via neural networks [arXiv] Quanta article |
| Electronic Journal of Combinatorics 2020 |
Bounded Degree Spanners of the Hypercube [arXiv] |
| Israel Journal of Mathematics 2020 |
Nearly-linear monotone paths in edge-ordered graphs [arXiv] |
| JCTA 2020 |
Refuting conjectures in extremal combinatorics via linear programming [arXiv] |
| JCTB 2020 |
Completion and deficiency problems [arXiv] |
| Electronic Journal of Combinatorics 2020 |
The Ramsey Number of Fano Plane Versus Tight Path [arXiv] |
| Journal of Graph Theory 2020 |
Families in posets minimizing the number of comparable pairs [arXiv] |
| arXiv 2019 |
The performance guarantee of randomized perfect voting trees [arXiv] |
| European Journal of Combinatorics 2019 |
The largest projective cube-free subsets of Z_{2^n} [arXiv] |
| JCTA 2019 |
Partition problems in high dimensional boxes [arXiv] |
| Discrete Mathematics 2019 |
Turan numbers for Berge-hypergraphs and related extremal problems [arXiv] |
| arXiv 2019 |
A note on some conjectures about combinatorial models for RNA secondary structures [arXiv] |
| Electronic Journal of Combinatorics 2019 |
Monochromatic Hilbert cubes and arithmetic progressions [arXiv] |
| Combinatorics, Probability and Computing 2018 |
Tilings in randomly perturbed dense graphs [arXiv] |
| Advances in Mathematics 2018 |
Kleitman's conjecture about families of given size minimizing the number of k-chains [arXiv] |
| Discrete Applied Mathematics 2018 |
Two results about the hypercube [arXiv] |
| Bul. of the London Math. Soc. 2017 |
An improved lower bound for Folkman's Theorem [arXiv] |
| Journal of Graph Theory 2017 |
Large subgraphs in rainbow-triangle free colorings [arXiv] |
| Israel Journal of Mathematics 2017 |
On the number of union-free families [arXiv] |
| Random Structures & Algorithms 2016 |
Applications of Graph Containers in the Boolean Lattice [arXiv] |
| Recent Trends in Combinatorics 2016 |
Further applications of the Container Method [arXiv] |
| Discrete Mathematics 2015 |
Cops and Robbers on diameter two graphs [arXiv] |
| - |
Pursuit on Graphs (Master's thesis) [pdf] |
Selected talks with videos
Finding counterexamples to conjectures via reinforcement learning
We use a simple reinforcement learning setup to find explicit constructions and counterexamples to several open conjectures in extremal combinatorics and graph theory. Amongst the conjectures we refute are a question of Brualdi and Cao about maximizing permanents of pattern avoiding matrices, and several problems related to the adjacency and distance eigenvalues of graphs. You do not need to know much about machine learning or maths to be able to follow this talk, I explain everything from the basics!
Watch Talk
Finding counterexamples to conjectures via reinforcement learning
This is a short, 20 minute version of the talk above. If you don't have much time, this is the talk for you! I don't go into much detail of the setup at all, and you can enjoy some insights from Yann LeCun into automated reasoning right after the talk.
Watch Talk (Day 1, at 1:51:30)
The largest projective cube-free subsets of $Z_{2^n}$
What is the largest subset of $Z_{2^n}$ that doesn’t contain a projective $d$-cube? In the Boolean lattice, Sperner’s, Erdos’s, Kleitman’s and Samotij’s theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $Z_{2^n}$ we work in $Z_{2^n}$, analogous statements hold if one replaces the word $k$-chain by projective cube of dimension $2^{k-1}$. The largest $d$-cube-free subset of $Z_{2^n}$, if $d$ is not a power of two, exhibits a much more interesting behaviour.
Watch TalkTutorials with code
I have made several tutorials on using machine learning methods in mathematical research. Let me know if you have any suggested improvements, or if there are any related topics that I should do a tutorial on!
Getting started with saliency analysis
Saliency analysis is a powerful tool to finding connections between parameters of some objects. Imagine you want to write a code that counts the number of 4-cycles in a graph. There is a simple $O(n^4)$ time algorithm by checking every possibility, but you have an inkling that this could be done better! Can we use the power of supervised learning to find a faster algorithm for computing the number of 4-cycles, and speed up our code significantly?
View Tutorial
The basics of reinforcement learning
We work through a simple reinforcement learning setup, and use it to on the following toy problem: at most how many edges can a triangle-free graph have? Once we have settled this question, we have a brief look at how RL can be useful in real maths research: we generalize our previous theorem in a very natural way, that is "clearly" correct -- but before spending a few weeks rigorously proving it, we do a quick sanity check with RL. Luckily it finds a counterexample and we have saved ourselves quite a bit of time.
View Tutorial
Using transformers to spot patterns
Coming soon!