기초과학연구원 이산수학그룹
On June 2, 2021, Adam Zsolt Wagner from the Tel Aviv University gave an online talk at the Virtual Discrete Math Colloquium on disproving graph theory conjectures by using reinforcement learning. The title of the talk was “Constructions in combinatorics via neural networks“.
Recently, significant progress has been made in the area of machine learning algorithms, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular, recent advances in the field of reinforcement learning have led computers to reach superhuman level play in Atari games and Go, purely through self-play. In this talk, I will give a very basic introduction to neural networks and reinforcement learning algorithms. I will also indicate how these methods can be adapted to the “game” of trying to find a counterexample to a mathematical conjecture, and show some examples where this approach was successful.
On January 20, 2020, Adam Zsolt Wagner from ETH Zurich gave a talk on the largest subset of $\mathbb Z_{2^n}$ having no projective $d$-cube. The title of his talk was “The largest projective cube-free subsets of $Z_{2^n}$“. He has been visiting IBS discrete mathematics group for a week and will leave on this Wednesday.
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.
This is joint work with Jason Long.