論文の概要: 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（参考訳）: 二重飽和ラムゼイグラフ:コンピュータによる数学的発見のケーススタディ
- 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を使用します。
このケーススタディでは、自動推論、大規模言語モデル、数学的発見を加速するための形式的検証の統合の可能性を強調した。
このようなツール駆動のワークフローは、実験数学においてますます中心的な役割を果たすようになると我々は主張する。
関連論文リスト
- RamseyGadgets: A Graph Construction Dataset for LLMs [1.4782129768183936]
textbfRamseyGadgetsは70の未探索グラフ構築問題のデータセットである。
これらの問題は、特別な性質を持つラムゼー良いグラフを見つける必要がある。
我々のデータセットは簡単に拡張可能であり、避けられている単色部分グラフを変更すれば、新しい問題の集合を得ることができる。
論文 参考訳（メタデータ） (2026-08-15T03:15:07Z) - Neurosymbolic Discovery of Algebraic Graph Constructions [22.962110170304594]
この生データのみを提供する場合、短い代数的記述を自動的に発見できるかどうかを問う。
本研究では,汎用的な大規模言語モデル上で,微調整や目標ごとの訓練を行わないエージェントを提案する。
提案手法は高対称性グラフ100のベンチマークで検証する。
論文 参考訳（メタデータ） (2026-08-08T13:07:51Z) - 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) - Improved Generalization Bound and Learning of Sparsity Patterns for
Data-Driven Low-Rank Approximation [15.191184049312467]
より優れた$tildemathrmO(nsk)$ bound for rank-k$ approximationを示す。
また、非ゼロの学習位置が脂肪破砕次元を$mathrmO(nslog n)$でのみ増加させることも証明した。
論文 参考訳（メタデータ） (2022-09-17T08:26:27Z) - Learning Graphons via Structured Gromov-Wasserstein Barycenters [143.42601038462965]
本稿では,graphonと呼ばれる非パラメトリックグラフモデルを学ぶための新しい原理的手法を提案する。
提案手法は, 従来の最先端手法の欠点を克服し, 合成データと実データの両方でそれを上回る。
論文 参考訳（メタデータ） (2020-12-10T13:04:29Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。