論文の概要: New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search

• arxiv url: http://arxiv.org/abs/2605.01120v2
• Date: Thu, 07 May 2026 02:22:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-08 17:36:05.950604
• Title: New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search
• Title（参考訳）: 強化LLM進化探索によるZarankiewicz数の新しい境界
• Authors: Jay Bhan, Nicole Nobili, Patrick Langer,
• Abstract要約: Zarankiewicz number $textbfZ(m, n, s, t)$ は二部グラフ $G_m, n$ の辺の最大数である。 Zarankiewiczの3つの数値の正確な値が初めて決定される: $textbfZ(11, 21, 3, 3)=116$, $textbfZ(11, 22, 3, 3)=121$, $textbfZ()
• 参考スコア（独自算出の注目度）: 1.9007546108571114
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Zarankiewicz number $\textbf{Z}(m, n, s, t)$ is the maximum number of edges in a bipartite graph $G_{m, n}$ such that there is no complete $K_{s, t}$ bipartite subgraph. We determine for the first time the exact values of three Zarankiewicz numbers: $\textbf{Z}(11, 21, 3, 3)=116$, $\textbf{Z}(11, 22, 3, 3)=121$, and $\textbf{Z}(12, 22, 3, 3)=132$. We further establish lower bounds for 41 more Zarankiewicz numbers, including several that are within one edge of the best known upper bound, and we match the established value in four more closed cases. Our results are obtained using OpenEvolve, an open-source evolutionary algorithm based on Large Language Models (LLMs) that iteratively improves algorithms for generating mathematical constructions by optimizing a reward signal which we tailored for this specific problem. These findings provide new extremal graph constructions and demonstrate the potential of LLM-guided evolutionary search to contribute to mathematical research. In addition to presenting the resulting constructions, we report the generation algorithms produced, describe the relevant implementation details, and provide our computational costs. Our costs are remarkably low, at less than \$30 for each Zarankiewicz parameter combination, showing that LLM-guided evolutionary search can be an inexpensive, reproducible, and accessible tool for discovering new combinatorial constructions.
• Abstract（参考訳）: Zarankiewicz number $\textbf{Z}(m, n, s, t)$ は二部グラフ $G_{m, n}$ の辺の最大数であり、完全な $K_{s, t}$二部グラフは存在しない。 3つのザランキーウィッチ数の正確な値を初めて決定する: $\textbf{Z} 11, 21, 3, 3)=116$, $\textbf{Z} 11, 22, 3, 3)=121$, $\textbf{Z}(12, 22, 3, 3)=132$。 さらに41以上のザランキーヴィチ数に対して下界を定め、その中には最もよく知られた上界の1辺以内にいくつかのものが含まれ、さらに4つの閉ケースで確立された値と一致する。 本研究は,Large Language Models (LLMs) に基づくオープンソースの進化的アルゴリズムであるOpenEvolveを用いて,この問題に適応した報酬信号の最適化により,数学的構成を生成するアルゴリズムを反復的に改良した。 これらの知見は、新しい極端グラフ構造を提供し、数学的研究に寄与するLLM誘導進化探索の可能性を示している。 得られた構成の提示に加えて、生成アルゴリズムを報告し、関連する実装の詳細を説明し、計算コストを提供する。 我々のコストは著しく低く、Zarankiewiczパラメータの組み合わせごとに30ドル以下であり、LLM誘導進化探索は安価で再現可能で、新しい組合せ構造を発見するためのアクセス可能なツールであることを示している。

関連論文リスト

• Reinforced Generation of Combinatorial Structures: Ramsey Numbers [3.359365297148466]
  5つの古典ラムゼー数に対する下界の改善を示す。 AlphaEvolveは1つのメタアルゴリズムで、検索結果の検索アルゴリズムを出力します。
  論文  参考訳（メタデータ） (2026-03-10T04:20:40Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Cut query algorithms with star contraction [4.570617424761779]
  カットクエリを用いた単純なグラフのエッジ接続を決定する複雑さについて検討する。 エッジ接続を$O(n)$ cutクエリで計算する有界誤りランダム化アルゴリズムが存在することを示す。 また、$O(sqrtn)$ cutクエリでエッジ接続を計算する有界エラー量子アルゴリズムがあることも示している。
  論文  参考訳（メタデータ） (2022-01-14T21:13:49Z)
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness [26.71898403195793]
  非常に滑らかな凸関数を最適化する複雑性について検討する。 正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。 我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
  論文  参考訳（メタデータ） (2021-12-02T10:51:43Z)
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction [18.65143269806133]
  我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。 古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
  論文  参考訳（メタデータ） (2021-03-15T11:20:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。