In 2021, Adam Zsolt Wagner proposed an approach to disprove conjectures in
graph theory using Reinforcement Learning (RL). Wagner's idea can be framed as
follows: consider a conjecture, such as a certain quantity f(G) < 0 for every
graph G; one can then play a single-player graph-building game, where at each
turn the player decides whether to add an edge or not. The game ends when all
edges have been considered, resulting in a certain graph G_T, and f(G_T) is the
final score of the game; RL is then used to maximize this score. This brilliant
idea is as simple as innovative, and it lends itself to systematic
generalization. Several different single-player graph-building games can be
employed, along with various RL algorithms. Moreover, RL maximizes the
cumulative reward, allowing for step-by-step rewards instead of a single final
score, provided the final cumulative reward represents the quantity of interest
f(G_T). In this paper, we discuss these and various other choices that can be
significant in Wagner's framework. As a contribution to this systematization,
we present four distinct single-player graph-building games. Each game employs
both a step-by-step reward system and a single final score. We also propose a
principled approach to select the most suitable neural network architecture for
any given conjecture, and introduce a new dataset of graphs labeled with their
Laplacian spectra. Furthermore, we provide a counterexample for a conjecture
regarding the sum of the matching number and the spectral radius, which is
simpler than the example provided in Wagner's original paper.
The games have been implemented as environments in the Gymnasium framework,
and along with the dataset, are available as open-source supplementary
materials.

提出了一种使用强化学习来反驳图论猜想的方法，通过单人图构建游戏来最大化游戏得分，并通过选择适当的神经网络结构和引入新的带有拉普拉斯光谱标签的图数据集，系统化地探讨了这种方法并提出了四种不同的单人图构建游戏。