論文の概要: An AI enhanced approach to the tree unimodality conjecture

• arxiv url: http://arxiv.org/abs/2510.18826v2
• Date: Wed, 22 Oct 2025 21:17:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 15:28:14.489753
• Title: An AI enhanced approach to the tree unimodality conjecture
• Title（参考訳）: 木の一様性予想に対するAI強化アプローチ
• Authors: Eric Ramos, Sunny Sun,
• Abstract要約: 私たちはAIアーキテクチャのPatternBoostを使って、マシンをトレーニングし、ログ凹凸予想に対する反例を見つけます。 このアプローチの成功について論じる - 27から101までのセットサイズで、ログの凹凸に対する数千の新しい反例を見つける。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a graph $G$, its independence sequence is the integral sequence $a_1,a_2,...,a_n$, where $a_i$ is the number of independent sets of vertices of size i. In the late 80's Alavi, Erdos, Malde, Schwenk showed that this sequence need not be unimodal for general graphs, but conjectured that it is always unimodal whenever $G$ is a tree. This conjecture was then naturally generalized to claim that the independence sequence of trees should be log concave, in the sense that $a_i^2$ is always above $a_{i-1}a_{i+1}$. This conjecture stood for many years, until in 2023, Kadrawi, Levit, Yosef, and Mizrachi proved that there were exactly two trees on 26 vertices whose independence sequence was not log concave. In this paper, we use the AI architecture PatternBoost, developed by Charton, Ellenberg, Wagner, and Williamson to train a machine to find counter-examples to the log-concavity conjecture. We will discuss the successes of this approach - finding tens of thousands of new counter-examples to log-concavity with vertex set sizes varying from 27 to 101 - and some of its fascinating failures.
• Abstract（参考訳）: グラフ $G$ が与えられたとき、その独立列は積分列 $a_1,a_2,...,a_n$ となる。 80年代後半のalavi, Erdos, Malde, Schwenk は、この列は一般グラフに対して一様ではないことを示したが、$G$ が木であるときは常に一様でないと推測した。 この予想は自然に一般化され、$a_i^2$が常に$a_{i-1}a_{i+1}$を超えるという意味で、木の独立列は対数凹であるべきだと主張した。 この予想は長年続いたが、2023年にカドラウィ、レヴィト、ヨセフ、ミズラチは、独立の順序が丸太の凹地ではない26の頂点にちょうど2本の木があることを証明した。 本稿では,Charton,Ellenberg,Wagner,Williamson両氏が開発したAIアーキテクチャであるPatternBoostを用いて,ログ凹凸予想に対する反例を見つける機械のトレーニングを行う。 このアプローチの成功 — 頂点セットのサイズが27から101に変化する数万の新しい反例を見つける — と、その興味深い失敗のいくつかについて論じる。

関連論文リスト

• Low-degree Security of the Planted Random Subgraph Problem [12.329446579556606]
  植付されたランダムな部分グラフを最大$kleq n1 - Omega(1)$まで検出する際の低次硬さを証明した。 我々は,(1) ランダム関数のための通信最適化多元的PSMプロトコル,(2) 共有サイズが$(1 + epsilon)log n$ for any $epsilon > 0$ に対して,最大$r$の任意の最小限の連立関係を再構築し,最大$ell = o(epsilon log n)1/(r-1)$までの未定部分集合に対して秘密保持する,という予想を適用した。
  論文  参考訳（メタデータ） (2024-09-24T16:42:00Z)
• On the Quantum Chromatic Numbers of Small Graphs [0.0]
  パラメータ $chi(1)_q$ と $chi(2)_q$ の分離の最小の例を示す。 さらに$G_21$は、パラメータ $chi(1)_q$ と $chi(2)_q$ の最初の証明可能な分離を提供する。
  論文  参考訳（メタデータ） (2023-11-14T14:27:03Z)
• Higher rank antipodality [2.7309692684728617]
  一般確率論に動機づけられて、集合 $S$ in $mathbbRd$ はランク $k$ のエンファンティポッドであると言う。 この問題は, コンピュータ科学において, 完全ハッシュの発見に関する古典的な問題と結びつくことができることを示す。
  論文  参考訳（メタデータ） (2023-07-31T17:15:46Z)
• Rigorous derivation of the Efimov effect in a simple model [68.8204255655161]
  我々は、2体ゼロレンジ相互作用と、与えられた半径$a>0$の3体ハードコア反発を持つ$mathbbR3$の3つの同一ボソンの系を考える。
  論文  参考訳（メタデータ） (2023-06-21T10:11:28Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  このことは対数的因子の中でのciteSaundersonCPW12 の予想をほぼ成立させる。 後者の予想は、機械学習とある種の統計上の問題に対する2乗下界との結びつきから、過去10年間で大きな注目を集めている。
  論文  参考訳（メタデータ） (2022-12-21T17:48:01Z)
• Repeated Averages on Graphs [2.363388546004777]
  我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。 また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
  論文  参考訳（メタデータ） (2022-05-09T20:18:31Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。 統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
  論文  参考訳（メタデータ） (2021-01-22T01:57:35Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。 低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
  論文  参考訳（メタデータ） (2020-10-13T17:26:09Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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