論文の概要: Enumeration of Laplacian integral and {-1,0,1}-diagonalizable graphs

• arxiv url: http://arxiv.org/abs/2607.06336v1
• Date: Tue, 07 Jul 2026 14:31:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-08 21:24:51.553672
• Title: Enumeration of Laplacian integral and {-1,0,1}-diagonalizable graphs
• Title（参考訳）: ラプラス積分と {-1,0,1}-対角化可能なグラフの列挙
• Abstract要約: ラプラス行列 $L$ のグラフがラプラス積分 (Laplacian integral) と呼ばれるのは、$L$ の固有値がすべて整数であるときである。 我々は、ラプラシア積分グラフと$-1,0,1$-対角化可能な素数グラフの両方に対する構造定理を開発する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A graph with Laplacian matrix $L$ is called Laplacian integral if the eigenvalues of $L$ are all integers, and it is called $\{-1,0,1\}$-diagonalizable if $L$ has a full set of eigenvectors with entries from $\{-1,0,1\}$. We herein develop a structure theorem for both Laplacian integral graphs and $\{-1,0,1\}$-diagonalizable graphs of prime order, and combine it with some novel computational techniques to characterize all such graphs for orders larger than was previously possible. For example, we enumerate all Laplacian integral and $\{-1,0,1\}$-diagonalizable graphs of order $13$ or less, all $\{-1,0,1\}$-diagonalizable graphs of prime order $23$ or less, all regular integral graphs of order $15$ or less, and all regular $\{-1,0,1\}$-diagonalizable graphs of prime order $53$ or less. As an immediate byproduct of our work, we show that the $S_{n,n}$ conjecture for Laplacian integral graphs is true when $n = 12$, thus making $n = 16$ the smallest open case; additionally, we disprove two related conjectures regarding Laplacian spectra. We also establish an exponential lower bound on the number of connected $\{-1,0,1\}$-diagonalizable graphs of order $n$, thus beating the previously best-known (subexponential) lower bound. Finally, we show that every bipartite $\{-1,0,1\}$-diagonalizable graph is regular (a fact that fails to generalize to Laplacian integral graphs).
• Abstract（参考訳）: ラプラス行列 $L$ のグラフは、$L$ の固有値がすべて整数であればラプラス積分と呼ばれ、$\{-1,0,1\}$-対角化可能ならば、$L$ は $\{-1,0,1\}$ のエントリを持つ固有ベクトルの完全な集合を持つ。 ここでは、ラプラシア積分グラフと${-1,0,1\}$-対角化可能な素数グラフの両方の構造定理を開発し、それをいくつかの新しい計算手法と組み合わせて、これらのグラフを以前可能であったよりも大きい順序で特徴づける。 例えば、すべてのラプラシア積分と$\{-1,0,1\}$-diagonalizable graphs of order 13$ or less, all $\{-1,0,1\}$-diagonalizable graphs of prime order $23$ or less, all regular $-1,0,1\}$-diagonalizable graphs of prime order 5,3$ or less, all regular $-1,0,1\}$-diagonalizable graphs of prime order 5,3$。 我々の研究の即時副産物として、ラプラシアン積分グラフに対する$S_{n,n}$予想が、$n = 12$ であるときに真であることを示し、したがって$n = 16$ を最小開ケースとし、さらにラプラシアンスペクトルに関する2つの関連する予想を否定する。 また、接続された$\{-1,0,1\}$-対角化可能な次数$n$のグラフの個数に対する指数的下界を確立し、従って、以前に最もよく知られた(部分指数的な)下界を破る。 最後に、すべての二部グラフ $\{-1,0,1\}$-対角化可能グラフが正則であることを示す(これはラプラシア積分グラフへの一般化に失敗する)。

関連論文リスト

• Exponential random graph models with soft clique constraints [0.0]
  指数的ランダムグラフモデルを考えると、$G$が$H$よりも$r$cliquesが小さい場合、mathbfG_n$よりも$H$の方が高い確率を与える。 r$-傾きの少ないグラフがより高い確率で与えられる度合いは、正の重み$w$によって決定される。
  論文  参考訳（メタデータ） (2026-08-31T14:31:57Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers [9.297355862757838]
  本稿では,エッジレベルの差分プライバシーの下で,入力グラフのすべてのカットサイズを近似した合成グラフを公開する問題について検討する。 有界時間 $(varepsilon,)$-differentially private algorithm を与え、これはすべての$n$-vertex 未重み付きグラフ $G$ に対して非負重み付き合成グラフを出力する。
  論文  参考訳（メタデータ） (2026-07-21T08:35:05Z)
• The Quad-$C_5$ Graph: Maximum Contextuality Gap on Eight Vertices [0.0]
  Quad-$C_5$ は$_3=1+sqrt5$ (=$x2-2x-4$) を持つ最小の文脈性証人であるが、ワグナーグラフは4次元のヒルベルト空間を必要とする。 このグラフは4つの重なり合う5つのサイクルを含み、その隣接スペクトルは黄金比固有値によって支配される。
  論文  参考訳（メタデータ） (2026-05-12T23:50:25Z)
• Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts [3.652509571098291]
  微分プライベート (DP) 合成グラフ $G'$ を、任意のグラフ $G'$ のすべてのカットの三角形-モチーフサイズをよく近似する問題について検討する。 このようなグラフの非公開バージョンは、グラフクラスタリング、グラフスペーシフィケーション、ソーシャルネットワーク分析といった様々な分野に応用されている。
  論文  参考訳（メタデータ） (2025-07-20T06:20:53Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Equiangular lines via matrix projection [0.0]
  1973年、Lemmens と Seidel は、角 $arccos(alpha)$ の等角線の最大数を $mathbbRr$ で決定する問題を提起した。 最近のブレークスルーはこの問題のほぼ完全な解決に繋がった。 本稿では,従来のアプローチを統一し,改善する上界を求める新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-10-29T15:06:15Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。 これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
  論文  参考訳（メタデータ） (2021-10-11T05:07:50Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
  グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。 これは高速多重極法について証明された最初の公式な制限である。
  論文  参考訳（メタデータ） (2020-11-04T18:35:02Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。 最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。 本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-25T18:12:50Z)

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

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