論文の概要: Quantum isomorphism of graphs from association schemes

• arxiv url: http://arxiv.org/abs/2209.04581v2
• Date: Wed, 26 Oct 2022 16:30:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-27 02:53:55.109453
• Title: Quantum isomorphism of graphs from association schemes
• Title（参考訳）: 結合スキームからのグラフの量子同型
• Authors: Ada Chan and William J. Martin
• Abstract要約: 同じ数の頂点上の任意の2つのアダマールグラフが量子同型であることを示す。 これは、ある関連スキームから生じるグラフの量子同型を示すより一般的なレシピから従う。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that any two Hadamard graphs on the same number of vertices are quantum isomorphic. This follows from a more general recipe for showing quantum isomorphism of graphs arising from certain association schemes. The main result is built from three tools. A remarkable recent result of Man\v{c}inska and Roberson shows that graphs $G$ and $H$ are quantum isomorphic if and only if, for any planar graph $F$, the number of graph homomorphisms from $F$ to $G$ is equal to the number of graph homomorphisms from $F$ to $H$. A generalization of partition functions called "scaffolds" affords some basic reduction rules such as series-parallel reduction and can be applied to counting homomorphisms. The final tool is the classical theorem of Epifanov showing that any plane graph can be reduced to a single vertex and no edges by extended series-parallel reductions and Delta-Wye transformations. This last sort of transformation is available to us in the case of exactly triply regular association schemes. The paper includes open problems and directions for future research.
• Abstract（参考訳）: 同じ数の頂点上の任意の2つのアダマールグラフが量子同型であることを示す。 これは、ある関係スキームから生じるグラフの量子同型を示すより一般的なレシピから従う。 主な成果は3つのツールから成り立っている。 Man\v{c}inska と Roberson の最近の顕著な結果は、グラフ $G$ と $H$ が量子同型であることと、任意の平面グラフ $F$ に対して、$F$ から $G$ までのグラフ準同型数は、$F$ から $H$ までのグラフ準同型の数に等しいことを証明している。 スカフォールド」と呼ばれる分割関数の一般化は、級数-パラレル還元のような基本的な還元規則を与え、数え上げ準同型に応用できる。 最後の道具はエピファノフの古典的な定理であり、任意の平面グラフは1つの頂点に縮められ、拡張直列並列還元とデルタ・ワイ変換によって辺を持たないことを示すものである。 この最後の変換は、正確に3つの規則的なアソシエーションスキームの場合に利用できます。 論文には、今後の研究のためのオープンな問題と方向性が含まれている。

関連論文リスト

• Detecting Homeomorphic 3-manifolds via Graph Neural Networks [0.0]
  グラフニューラルネットワークを用いたグラフ多様体のクラスに対する同相性問題について検討する。 2つの畳み込みレイヤの異なる組み合わせをテストすることで、教師付き学習環境でさまざまなネットワークアーキテクチャをトレーニングし、ベンチマークします。
  論文  参考訳（メタデータ） (2024-09-01T12:58:09Z)
• NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability [0.18749305679160366]
  グラフの量子同型に対するSDP緩和のNPA階層の各々のレベルは、平面グラフの適切なクラスに対する準同型独立性と同値であることを示す。 この準同型不連続性の特徴付けはまた、量子同型に対するSDP緩和のNPA階層の固定レベル毎の正確な実現性を決定するランダム化時間アルゴリズムを与えることもできる。
  論文  参考訳（メタデータ） (2024-07-15T11:48:09Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。 具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。 我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  ホモフィリーなエッジを持つグラフは、同じクラスでノードを接続する傾向がある。 ヘテロフィ的傾向のあるエッジは、異なるクラスを持つノード間の関係を構築する傾向がある。 既存のGNNはトレーニング中にオリジナルのグラフのみを取る。
  論文  参考訳（メタデータ） (2023-06-13T08:06:10Z)
• Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint [0.0]
  グラフ準同型(Graph homomorphism)は、$mathcalF$ と $mathcalF'$ のそれぞれが 1 つの対称な 0-1 値のバイナリ制約関数を含む特別な場合である。 任意のペアの集合 $mathcalF$ と $mathcalF'$ は、任意の平面#CSPインスタンスに同じ値を与える実数値で任意のアリティ制約関数を示す。
  論文  参考訳（メタデータ） (2022-12-06T21:38:40Z)
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
  グラフは、単純な埋め込みとサンプリングを用いて、十分な次元でセットされた点として表すことができる。 それらの同型は、グラフの点集合形式の間の完全登録の存在に対応する。 等値類に関する関連する考えは、グラフの正準化がグラフ同型問題に取り組む上で重要なツールであることを示している。
  論文  参考訳（メタデータ） (2021-11-15T12:16:21Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。 FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。 提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
  論文  参考訳（メタデータ） (2020-10-12T03:01:40Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)
• Graph Homomorphism Convolution [19.94778871237204]
  グラフ準同型数は、グラフ分類に使用できる自然な不変量(同型不変量および$mathcalF$-不変量)を提供することを示す。 木幅が有界な元を持つ$mathcalF$を選択することで、同型法は他の方法と比較して効率的であることを示す。
  論文  参考訳（メタデータ） (2020-05-03T23:56:20Z)

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

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