論文の概要: The inertia bound is far from tight

• arxiv url: http://arxiv.org/abs/2312.04925v2
• Date: Mon, 18 Dec 2023 14:02:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-20 21:48:01.391180
• Title: The inertia bound is far from tight
• Title（参考訳）: 慣性境界はきつくない
• Authors: Matthew Kwan and Yuval Wigderson
• Abstract要約: 我々は、慣性境界が極端に厳密でないことを示し、実際は比縛を著しく過小評価できることを示した。 これらの結果はルーニー、シンコビッチ、ワクジャン=エルフィック=アビアドの疑問に対処する。
• 参考スコア（独自算出の注目度）: 1.8130068086063336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The inertia bound and ratio bound (also known as the Cvetkovi\'c bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number $\alpha(G)$ of a graph $G$ in terms of spectral information about a weighted adjacency matrix of $G$. For both inequalities, given a graph $G$, one needs to make a judicious choice of weighted adjacency matrix to obtain as strong a bound as possible. While there is a well-established theory surrounding the ratio bound, the inertia bound is much more mysterious, and its limits are rather unclear. In fact, only recently did Sinkovic find the first example of a graph for which the inertia bound is not tight (for any weighted adjacency matrix), answering a longstanding question of Godsil. We show that the inertia bound can be extremely far from tight, and in fact can significantly underperform the ratio bound: for example, one of our results is that for infinitely many $n$, there is an $n$-vertex graph for which even the unweighted ratio bound can prove $\alpha(G)\leq 4n^{3/4}$, but the inertia bound is always at least $n/4$. In particular, these results address questions of Rooney, Sinkovic, and Wocjan--Elphick--Abiad.
• Abstract（参考訳）: inertia bound と ratio bound(cvetkovi\'c bound および hoffman bound とも呼ばれる)は、スペクトルグラフ理論における2つの基本的な不等式であり、重み付き隣接行列に関するスペクトル情報に関して、グラフの独立数 $\alpha(g)$ の上限を与える。 2つの不等式に対して、グラフ $g$ が与えられると、できるだけ強い束縛を得るためには重み付き隣接行列を公平に選択する必要がある。 比境界を取り巻くよく確立された理論があるが、慣性境界はずっと神秘的であり、その限界はかなり不明瞭である。 実際、最近になってシュノビッチは、慣性束縛が(任意の重み付き隣接行列に対して)タイトでないグラフの最初の例を見つけ、ゴドシルの長年の疑問に答えた。 例えば、我々の結果の1つは、無限に多くの$n$に対して、非重み付き比縛でさえ$\alpha(G)\leq 4n^{3/4}$を証明できる$n$-vertex graphが存在するが、慣性境界は常に$n/4$である。 特に、これらの結果はrooney、stovic、wocjan--elphick-abiadの疑問に答えている。

関連論文リスト

• Limitations and Separations in the Quantum Sum-of-squares, and the Quantum Knapsack Problem [0.0]
  我々は、SYKモデルの平方和に関する2つの質問に答える。 次数-$4$マヨラナ作用素の可換関係を考えるが、それらに他の関係を課さない二乗和の断片は、基底状態エネルギーに縛られる正しい等級を与えないことを示す。
  論文  参考訳（メタデータ） (2024-02-22T18:12:03Z)
• Quantum walks on blow-up graphs [0.0]
  グラフ$G$の$n$コピーは、グラフ$oversetnuplusG$である。 ブローアップグラフ $oversetnuplusG$ 上の量子状態移動の存在について検討する。
  論文  参考訳（メタデータ） (2023-08-26T14:07:25Z)
• Rigorous derivation of the Efimov effect in a simple model [68.8204255655161]
  我々は、2体ゼロレンジ相互作用と、与えられた半径$a>0$の3体ハードコア反発を持つ$mathbbR3$の3つの同一ボソンの系を考える。
  論文  参考訳（メタデータ） (2023-06-21T10:11:28Z)
• Tip of the Quantum Entropy Cone [1.1606619391009658]
  N$-partite量子系の異なる部分のフォン・ノイマンエントロピー間の関係は、様々な状況の理解に直接的な影響を与える。 任意の整数倍数へのエントロピーベクトルのアップスケールは常に可能であるが、任意のサイズのエントロピーベクトルをダウンスケールすることは必ずしも不可能である。
  論文  参考訳（メタデータ） (2023-05-31T21:37:24Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
  有向フィードバックグラフが帯域幅を持つ拡張について検討する。 グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。 我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2022-10-09T11:21:08Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Understanding Bandits with Graph Feedback [0.0]
  一般的な後悔すべき上界$Oleft(left(delta*log |V|right)frac13Tfrac23right)$と下界$Omegaleft(left(delta*/alpharight)frac13Tfrac23right)$を証明します。 いくつかのグラフの特別な族に対して、$left(log |V|right)frac13$ factorを排除できることを示す。
  論文  参考訳（メタデータ） (2021-05-29T09:35:28Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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