論文の概要: Doubly Saturated Ramsey Graphs: A Case Study in Computer-Assisted Mathematical Discovery
- arxiv url: http://arxiv.org/abs/2604.21187v1
- Date: Thu, 23 Apr 2026 01:05:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-24 14:40:06.225225
- Title: Doubly Saturated Ramsey Graphs: A Case Study in Computer-Assisted Mathematical Discovery
- Title（参考訳）: 二重飽和ラムゼイグラフ:コンピュータによる数学的発見のケーススタディ
- Authors: Benjamin Przybocki, John Mackey, Marijn J. H. Heule, Bernardo Subercaseaux,
- Abstract要約: 二重飽和ラムゼーグラフについて検討し、任意のエッジの追加や削除が必ずしも$s$-clique あるいは $t$-independent な集合を生成する。
本稿では,SAT の解法と LLM 生成符号を併用して,そのようなグラフの無限族を探索する手法を提案する。
- 参考スコア（独自算出の注目度）: 4.001518483170137
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Ramsey-good graphs are graphs that contain neither a clique of size $s$ nor an independent set of size $t$. We study doubly saturated Ramsey-good graphs, defined as Ramsey-good graphs in which the addition or removal of any edge necessarily creates an $s$-clique or a $t$-independent set. We present a method combining SAT solving with bespoke LLM-generated code to discover infinite families of such graphs, answering a question of Grinstead and Roberts from 1982. In addition, we use LLMs to generate and formalize correctness proofs in Lean. This case study highlights the potential of integrating automated reasoning, large language models, and formal verification to accelerate mathematical discovery. We argue that such tool-driven workflows will play an increasingly central role in experimental mathematics.
- Abstract（参考訳）: ラムゼー・グッドグラフ(Ramsey-good graph)は、大きさが$s$のクリッドも、大きさが$t$の独立した集合も含まないグラフである。
二重飽和ラムゼイグラフはラムゼイグラフとして定義され、任意のエッジの追加や削除が必ずしも$s$-cliqueあるいは$t$-independentな集合を生成する。
1982年のGrinstead と Roberts の質問に答えて,SAT の解法と LLM 生成符号を組み合わせて,そのようなグラフの無限族を探索する手法を提案する。
加えて、リーンで正当性証明を生成し、形式化するのにLLMを使用します。
このケーススタディでは、自動推論、大規模言語モデル、数学的発見を加速するための形式的検証の統合の可能性を強調した。
このようなツール駆動のワークフローは、実験数学においてますます中心的な役割を果たすようになると我々は主張する。
関連論文リスト
- DRESS: A Continuous Framework for Structural Graph Refinement [0.0]
本稿では,グラフ内のエッジの構造的類似性を洗練し,標準指紋を生成するフレームワークDRESSを紹介する。
フィンガープリントは構成上は同型不変であり、数値的には安定である(すべての値は$[0,2]$)。
$-DRESSは、包括的なStrongly Regular Graphベンチマークで7,983グラフを実証的に分離し、反復削除(k$-DRESS)が階段を登り、各深さk$で$(k+2)$-WLを達成する。
論文 参考訳（メタデータ） (2026-02-24T12:18:42Z) - What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
大規模言語モデル(LLM)は、期待される推論能力と推論能力のために、AIコミュニティで再編成されている。
我々は、グラフのこのようなパラメトリック表現、グラフ法則は、LLMがグラフデータを入力として理解させるソリューションであると信じている。
論文 参考訳（メタデータ） (2024-10-16T00:01:31Z) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
大規模言語モデル(LLM)は、特に知識集約的なタスクにおいて幻覚に悩まされる。
既存の研究は、外部知識コーパスから取得した個々のテキスト単位でLLMを拡張することを提案する。
本稿では,グラフを反復的に推論することで,LLMをグラフで拡張するためのGraph Chain-of-thinkt (Graph-CoT) というフレームワークを提案する。
論文 参考訳（メタデータ） (2024-04-10T15:41:53Z) - RamseyRL: A Framework for Intelligent Ramsey Number Counterexample
Searching [0.0]
ラムゼー数はノードの最小数、$n = R(s, t)$ であり、位数 $n$ のすべての無向単純グラフは位数 $s$ あるいは位数 $t$ の独立集合を含む。
本稿では,Ramsey数値に対する反例を見つけるために,最良1次探索アルゴリズムと強化学習(RL)手法の適用について検討する。
論文 参考訳（メタデータ） (2023-08-23T06:32:14Z) - Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
大型言語モデル (LLM) は暗黙的なグラフィカル構造を持つ様々なタスクに採用されている。
自然言語をシミュレーションするグラフベース問題解決のベンチマークであるNLGraphを提案する。
論文 参考訳（メタデータ） (2023-05-17T08:29:21Z) - Multi-armed Bandit Learning on a Graph [0.0]
そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。
我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。
提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
論文 参考訳（メタデータ） (2022-09-20T02:31:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。