概要 - どのグラフモチーフのパラメータが重要ですか？
タイトル
どのグラフモチーフのパラメータが重要ですか？
時間
2025-07-16 13:55:16
著者
{"Markus Bläser","Radu Curticapean","Julian Dörfler","Christian Ikenmeyer"}
カテゴリ
{cs.CC,math.CO,"68Q25, 68R99","G.2.1; F.1.3"}
リンク
http://arxiv.org/abs/2507.12244v1
PDF リンク
http://arxiv.org/pdf/2507.12244v1
概要
マルクス・ブラーザー、ラドゥ・クルティカパーン、ジュリアン・ドーフラー、そしてクリスチャン・イケンミューラーによる論文「Which graph motif parameters count?」は、グラフモチーフパラメータの組み合わせ論的解釈を調査しています。グラフモチーフパラメータは、与えられたグラフGにおいて固定されたグラフHの誘導部分図を数える関数の線形結合です。この論文は、どのグラフモチーフパラメータが組み合わせ論的解釈を持つか、つまり何か意味のあることを数えるかを特定することに焦点を当てています。 この論文の主な結果は、孤立点を持たないグラフに関する誘導部分図を数える関数の線形結合の中で、正の整数係数を持つものが組み合わせ論的解釈を保つことを述べています。これは、負の係数を持つグラフモチーフパラメータは意味のあることを数えるとして解釈できないことを意味します。 この論文は、計算复杂性理論の技術、特に#P複雑性クラスを使用して結果を証明しています。論文は、オラクル変種の#Pにおいて、暗黙のグラフにオラクルクエリを通じてアクセスするのが不可能であることを示しています。証明は、ヘルトランプ、ヴォルルメール、ワーガーの#Pの相対化閉包性質の分類と、イケンミューラーとパクが開発した枠組みに従っています。 この論文は、グラフから関係構造までの技術を拡張し、着色グラフを含みます。カテゴリーにおけるモチーフパラメータを導入し、カテゴリー内の部分オブジェクトの発生を数えるものを紹介します。そして、そのようなパラメータが組み合わせ論的解釈を持つかを特徴付ける一般二分法定理を証明します。カテゴリーのラムズイ理论の既知の結果を使用して、有限ベクトル空間のモチーフパラメータやパラメータセットに対する二分法を得ます。 この論文は、組み合わせ論と複雑性理論における計算問題の複雑さの理解に寄与しており、組み合わせ論的解釈を持つグラフモチーフパラメータを特徴付ける枠組みを提供し、計算复杂性理論の技術が計算問題の分析における力を示しています。
推奨論文
証明書敏感な部分和問題：実例複雑度の達成
MCM：MRI中の連続画像を使用したマンゴーに基づく心臓動態追跡
ドブズ対ジャクソン事件後のGoogle検索広告
3DGauCIM：デジタルCIMを通じて、高フレームレートリアルタイムエッジレンダリングのための静的/動的3Dガウススプラッティングを加速します
細胞無しのマスive MIMOシステムにおけるハイブリッド量子卷積神経網補助のパイロットアサインメント
無条件の擬似乱数に対する浅い量子回路に対する無条件の擬似乱数
セキュリティテンソルとしてのクロスモーダルブリッジ：LVLMにおけるテキストアライドセキュリティを視覚に拡張
SVAgent：ハードウェアセキュリティ検証の断言のためのAIアージェント
CCL25-Evalタスク10用システムレポート：微細な中国語のヘイトスピーチ認識のためのSRAG-MAV
デジタルツインと生成型AIを通じてサイバーセキュリティ教育を可能にする