論文の概要: Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications

• arxiv url: http://arxiv.org/abs/2512.07120v1
• Date: Mon, 08 Dec 2025 03:01:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-09 22:03:54.688884
• Title: Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications
• Title（参考訳）: 2-Treesのクロマティックな特徴ベクトル:ネットワークアプリケーションによる分割列挙のための厳密な公式
• Authors: J. Allagan, G. Morgan, S. Langley, R. Lopez-Bonilla, V. Deriglazov,
• Abstract要約: 二色三角形制約の下で2-木の特徴ベクトルの閉形式列挙式を確立する。 これらの効率的な計算可能な構造的特徴は、各三角形が正確に2つの色を使用するような制約付きグラフ彩色から導かれる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish closed-form enumeration formulas for chromatic feature vectors of 2-trees under the bichromatic triangle constraint. These efficiently computable structural features derive from constrained graph colorings where each triangle uses exactly two colors, forbidding monochromatic and rainbow triangles, a constraint arising in distributed systems where components avoid complete concentration or isolation. For theta graphs Theta_n, we prove r_k(Theta_n) = S(n-2, k-1) for k >= 3 (Stirling numbers of the second kind) and r_2(Theta_n) = 2^(n-2) + 1, computable in O(n) time. For fan graphs Phi_n, we establish r_2(Phi_n) = F_{n+1} (Fibonacci numbers) and derive explicit formulas r_k(Phi_n) = sum_{t=k-1}^{n-1} a_{n-1,t} * S(t, k-1) with efficiently computable binomial coefficients, achieving O(n^2) computation per component. Unlike classical chromatic polynomials, which assign identical features to all n-vertex 2-trees, bichromatic constraints provide informative structural features. While not complete graph invariants, these features capture meaningful structural properties through connections to Fibonacci polynomials, Bell numbers, and independent set enumeration. Applications include Byzantine fault tolerance in hierarchical networks, VM allocation in cloud computing, and secret-sharing protocols in distributed cryptography.
• Abstract（参考訳）: 二色三角形制約の下で2-木の彩色特徴ベクトルの閉形式列挙式を構築した。 これらの効率的な計算可能な構造的特徴は、各三角形が正確に2つの色を使用するような制約付きグラフ色付け(英語版)から派生し、一色の三角形と虹色の三角形は禁じられている。 テータグラフ Theta_n に対して、k >= 3 の r_k(Theta_n) = S(n-2, k-1) と r_2(Theta_n) = 2^(n-2) + 1 が O(n) 時間で計算可能であることを証明する。 ファングラフ Phi_n に対し、r_2(Phi_n) = F_{n+1} (フィボナッチ数) を確立し、効率よく計算可能な二項係数を持つ明示公式 r_k(Phi_n) = sum_{t=k-1}^{n-1} a_{n-1,t} * S(t, k-1) を導出し、成分当たりのO(n^2) 計算を達成する。 すべての n-頂点 2-木に同じ特徴を割り当てる古典的な色多項式とは異なり、双色制約は情報的構造的特徴を提供する。 完全なグラフ不変量ではないが、これらの特徴はフィボナッチ多項式、ベル数、独立集合列挙といった接続を通して有意義な構造的性質を捉えている。 アプリケーションには、階層型ネットワークにおけるビザンチンフォールトトレランス、クラウドコンピューティングにおけるVM割り当て、分散暗号におけるシークレット共有プロトコルが含まれる。

関連論文リスト

• Algebraic Obstructions and the Collapse of Elementary Structure in the Kronecker Problem [0.0]
  マーナハンの基礎研究から87年間、真に3列のケースに対して明確な閉形式の公式は得られていない。 階段-フック係数の明示的な公式を5つ導き、サクセル予想を132個の三列分割で検証する。 連続閉塞と離散積分性の間の張力を利用した証明手法である整数強制法を開発した。
  論文  参考訳（メタデータ） (2025-11-28T03:21:01Z)
• PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms [14.601622103700516]
  グラフのクラスタリングノードは、グラフ解析の土台である。 いくつかの一般的な方法は、非常に大きなグラフには適さない。 この研究は、クラスタリングアルゴリズムを高速化するオーバーレイであるPASCOを導入している。
  論文  参考訳（メタデータ） (2024-12-18T08:15:55Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGGSDを提案する。 合成グラフと実世界のグラフの両方に関する広範な実験は、最先端の代替品に対する我々のモデルの強みを実証している。
  論文  参考訳（メタデータ） (2024-02-29T09:26:46Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Pseudo-Euclidean Attract-Repel Embeddings for Undirected Graphs [73.0261182389643]
  ドット積埋め込みはグラフをとり、2つのベクトル間のドット積がエッジの強さを与えるようなノードのベクトルを構成する。 ノードを擬ユークリッド空間に埋め込むことにより、推移性仮定を除去する。 Pseudo-Euclidean 埋め込みはネットワークを効率よく圧縮でき、近接する隣人の複数の概念をそれぞれ独自の解釈で解釈でき、既存のモデルに'スロットできる。
  論文  参考訳（メタデータ） (2021-06-17T17:23:56Z)
• Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
  グラフニューラルネットワーク(MPNN)は、スパースグラフに適用する場合のノード数に関して線形複雑である。 本稿では, 固有値の非線形なカスタム関数により, グラフ畳み込みサポートがスペクトル領域で設計されている場合, MPNNは1-WLテストよりも理論的に強力であることを示す。
  論文  参考訳（メタデータ） (2021-06-08T13:26:56Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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