This work studies a central extremal graph theory problem inspired by a 1975
conjecture of Erd\H{o}s, which aims to find graphs with a given size (number of
nodes) that maximize the number of edges without having 3- or 4-cycles. We
formulate this problem as a sequential decision-making problem and compare
AlphaZero, a neural network-guided tree search, with tabu search, a heuristic
local search method. Using either method, by introducing a curriculum --
jump-starting the search for larger graphs using good graphs found at smaller
sizes -- we improve the state-of-the-art lower bounds for several sizes. We
also propose a flexible graph-generation environment and a
permutation-invariant network architecture for learning to search in the space
of graphs.

通过对给定规模下最大化边数且无 3 或 4 - 循环的图形的研究，将问题建模为一个顺序决策问题，并比较了 AlphaZero 和 tabu 搜索两种方法的效果，通过引入课程，即使用在较小规模下找到的良好图形来启动搜索更大图形的过程，我们改进了对于多个规模的现有下界。同时，我们还提出了一个灵活的图形生成环境和一个对于在图形空间中进行搜索的排列不变的网络架构。