強化学習的LLM進化探索によるザランキエヴィチ数の新しい境界

要旨: ザランキエヴィチ数 extbf{Z}(m, n, s, t) は、完全な K_{s, t} の二部部分グラフを含まない二部グラフ G_{m, n} における辺の最大数である。本研究では、3つのザランキエヴィチ数について初めてその正確な値を決定する： extbf{Z}(11, 21, 3, 3)=116、 extbf{Z}(11, 22, 3, 3)=121、および extbf{Z}(12, 22, 3, 3)=132。さらに、41個の追加のザランキエヴィチ数について下界を確立し、これには最良として知られている上界から1本の辺以内にあるものがいくつか含まれる。また、4つのさらなる閉じた場合（クローズドケース）で、確立された値と一致させる。これらの結果は、大規模言語モデル（LLMs）に基づくオープンソースの進化計算アルゴリズムであるOpenEvolveを用いて得られた。OpenEvolveは、特定のこの問題に合わせて調整した報酬信号を最適化することで、数学的構成を生成するアルゴリズムを反復的に改善する。これらの知見は、新たな極値グラフの構成を提供するとともに、LLMに導かれた進化探索が数学研究に寄与しうる可能性を示している。得られた構成を提示するだけでなく、生成アルゴリズムも報告し、関連する実装の詳細を述べ、計算コストを提示する。コストは非常に低く、ザランキエヴィチ数の各パラメータ組合せあたり30ドル未満である。これは、LLMに導かれた進化探索が、新しい組合せ構成を発見するための、安価で、再現可能で、利用しやすい手段になり得ることを示している。