論文の概要: 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割り当て、分散暗号におけるシークレット共有プロトコルが含まれる。
関連論文リスト
- Stationarity and Spectral Characterization of Random Signals on Simplicial Complexes [45.01439616647312]
単体錯体上で定義されたランダム信号に対する確率的フレームワークを提案する。
具体的には、定常性の古典的な概念を一般化する。
複数の合成および実世界のシミュレーションを通して、これらの利点の実用性を実証的に実証する。
論文 参考訳（メタデータ） (2026-02-03T03:31:10Z) - Classical and Quantum Algorithms for Topological Invariants of Torus Bundles [0.42970700836450476]
我々は非可換トーラス構造を利用して閉トーラスのスキイン代数をその対称部分代数にユニタリの根に埋め込む。
個々の展開係数の抽出は#P完全であることが証明されているが、これらの係数を非無視的な構成の分数に対して効率的に近似できる量子アルゴリズムが存在する。
論文 参考訳（メタデータ） (2025-12-22T04:58:14Z) - 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) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
本稿では,高次元分布をモデル化し,グラフスケルトンと整合した複雑な関係特徴構造を持つデータの新しい例を生成することの問題点を考察する。
提案するモデルは,タスクを2つのフェーズに分割することで,各データポイントのグラフ構造に制約されたデータ特徴を生成する問題に対処する。
第一に、与えられたグラフのノードに関連する機能の分布をモデル化し、第二に、ノードのフィーチャに条件付きでエッジ機能を補完する。
論文 参考訳（メタデータ） (2022-12-01T11:49:07Z) - 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) - Factorizable Graph Convolutional Networks [90.59836684458905]
本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。
FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。
提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
論文 参考訳（メタデータ） (2020-10-12T03:01:40Z) - Can Graph Neural Networks Count Substructures? [53.256112515435355]
グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。
我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
論文 参考訳（メタデータ） (2020-02-10T18:53:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。