Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications

• URL: http://arxiv.org/abs/2512.07120v1
• Date: Mon, 08 Dec 2025 03:01:50 GMT
• Title: Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications
• Abstract summary: We establish closed-form enumeration formulas for feature vectors of 2-trees under the bichromatic triangle constraint.<n>These efficiently computable structural features derive from constrained graph colorings where each triangle uses exactly two colors.
• Score: 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.

Related papers

• Holographic functions and neural networks [0.0]
  A fuzzy Boolean function is a map $f:cubento [0,1]$, where $ninmathbb N$.<n>We introduce and compare three ways of saying that such a function has bounded.<n>The implication from holography to structure uses a variant of a weak version of hypergraph regularity.
  arXiv  Detail & Related papers  (2026-05-21T16:08:52Z)
• Graph Structure of Chebyshev Permutation Polynomials over Binary and Ternary Adic Rings [6.769253525763681]
  We investigate the graph structure of Chebyshev permutations over the ring $bbZ_2k13k$.<n>We show that, despite the complexities introduced by the binary and ternary components, the graph exhibits strong regularities.<n>Our results extend previous studies over prime-power rings, offering insights into the emergence of complexity in digital nonlinear maps.
  arXiv  Detail & Related papers  (2026-05-20T23:39:55Z)
• A Partition-Based Generating Function for Row-Convex Polyominoes [0.0]
  An alternative generating function is proposed to enumerate polyominoes without internal holes on a grid.<n>Potential applications include shape priors in discrete image analysis, grid-based modeling, and generation of convex structures.
  arXiv  Detail & Related papers  (2026-05-04T22:46:19Z)
• Layer-wise Lipschitz-Product Control for Deep Kolmogorov--Arnold Network Representations of Compositionally Structured Functions [51.56484100374058]
  Lipschitz product satisfies the primary domain-sensitive bound independent of the input dimension n.<n>Experiments confirm P(KAN)=1.0 for several compositionally structured functions.
  arXiv  Detail & Related papers  (2026-04-29T08:55:49Z)
• Spectral Kernel Dynamics via Maximum Caliber: Fixed Points, Geodesics, and Phase Transitions [0.0]
  We derive a closed-form geometric functional for kernel dynamics on finite graphs by applying the Maximum Caliber (MaxCal) variational principle.<n>The framework is grounded in a structural analogy with Einstein's field equations, used as a guiding template rather than an established equivalence.
  arXiv  Detail & Related papers  (2026-04-10T06:22:17Z)
• Stationarity and Spectral Characterization of Random Signals on Simplicial Complexes [45.01439616647312]
  We propose a probabilistic framework for random signals defined on simplicial complexes.<n>Specifically, we generalize the classical notion of stationarity.<n>We empirically demonstrate the practicality of these benefits through multiple synthetic and real-world simulations.
  arXiv  Detail & Related papers  (2026-02-03T03:31:10Z)
• Classical and Quantum Algorithms for Topological Invariants of Torus Bundles [0.42970700836450476]
  We exploit the non-commutative torus structure to embed the skein algebra of the closed torus into its symmetric subalgebra at roots of unity.<n>We prove that extracting individual expansion coefficients is #P-complete, yet there is a quantum algorithm that can efficiently approximate these coefficients for a non-negligible fraction of configurations.
  arXiv  Detail & Related papers  (2025-12-22T04:58:14Z)
• Algebraic Obstructions and the Collapse of Elementary Structure in the Kronecker Problem [0.0]
  No explicit closed-form formulas have been obtained for genuinely three-row cases in the 87 years since Murnaghan's foundational work.<n>We derive five explicit formulas for staircase-hook coefficients, and verify Saxl's conjecture for 132 three-row partitions.<n>We develop integer forcing, a proof technique exploiting the tension between continuous obstructions and discrete integrality.
  arXiv  Detail & Related papers  (2025-11-28T03:21:01Z)
• PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms [14.601622103700516]
  Clustering nodes of a graph is a cornerstone of graph analysis.<n>Some popular methods are not suitable for very large graphs.<n>This work introduces PASCO, an overlay that accelerates clustering algorithms.
  arXiv  Detail & Related papers  (2024-12-18T08:15:55Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  We present GGSD, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.<n>An extensive set of experiments on both synthetic and real-world graphs demonstrates the strengths of our model against state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Pseudo-Euclidean Attract-Repel Embeddings for Undirected Graphs [73.0261182389643]
  Dot product embeddings take a graph and construct vectors for nodes such that dot products between two vectors give the strength of the edge. We remove the transitivity assumption by embedding nodes into a pseudo-Euclidean space. Pseudo-Euclidean embeddings can compress networks efficiently, allow for multiple notions of nearest neighbors each with their own interpretation, and can be slotted' into existing models.
  arXiv  Detail & Related papers  (2021-06-17T17:23:56Z)
• Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
  Graph Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs. In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues, the MPNN is theoretically more powerful than the 1-WL test.
  arXiv  Detail & Related papers  (2021-06-08T13:26:56Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  We introduce a novel graph convolutional network (GCN) that explicitly disentangles intertwined relations encoded in a graph. FactorGCN takes a simple graph as input, and disentangles it into several factorized graphs. We evaluate the proposed FactorGCN both qualitatively and quantitatively on the synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-10-12T03:01:40Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.